Deconstructing word embedding algorithms

Kian Kenyon-Dean, Edward Newell, Jackie Chi Kit Cheung

Introduction

In the mid-2010s, natural language processing was transformed by "uncontextualized" word embeddings—static vectors where a single representation is learned for each word. While algorithms such as Word2vec (SGNS) and GloVe achieved significant success, they appeared to operate on fundamentally different principles: one utilizing neural-style negative sampling and the other relying on global matrix factorization. This paper introduces the low rank embedder framework, a mathematical "Rosetta Stone" that unifies these disparate algorithms. The authors demonstrate that despite their different training objectives, these models all converge on a singular goal: using vector dot products to approximate Pointwise Mutual Information (PMI).

The Low Rank Embedder Framework

The authors propose a unifying framework that decomposes any embedding algorithm into three constituent parts:

  1. $\psi$ (The Kernel): A function of learned parameters, typically the dot product of two vectors $\langle i|j \rangle$.
  2. $\phi$ (The Target): A scalar measure of association derived from the text corpus, usually related to word co-occurrence.
  3. $f_{ij}$ (The Loss Term): A function that penalizes the discrepancy between the model's prediction ($\psi$) and the corpus reality ($\phi$).

By performing "mathematical archaeology" on SVD, SGNS, FastText, GloVe, and LDS, the researchers prove that the "characteristic gradient"—the force moving vectors during training—consistently takes the form: $$\text{(Multiplier)} \times \text{(Difference between Model and PMI target)}$$

Unifying Word Embeddings

The primary theoretical result is that almost every major embedding algorithm is implicitly factorizing a PMI matrix. Whether it is the explicit objective (as in SVD) or an emergent property of negative sampling (as in Word2vec), the dot product of word vectors ends up approximating the PMI between those words.

Table 1: Comparison of characteristic gradients and PMI approximations across major embedding models.

As shown in Table 1, SGNS approximates $\text{PMI}(i, j) - \ln k$, while GloVe approximates $\text{PMI}(i, j)$ once learned biases are accounted for. This unification suggests that the success of these models stems from their shared ability to capture the underlying statistical structure of language.

Empirical Validation

To validate their theoretical findings, the authors utilized a Wikipedia 2018 corpus. This empirical analysis confirmed two critical points: first, that PMI values in real-world text are approximately normally distributed, and second, that the "bias" terms learned by GloVe naturally align with the unigram frequencies required to calculate PMI.

Empirical analysis of PMI distribution (A) and the relationship between GloVe bias terms and word frequency (B).

Figure B specifically demonstrates that GloVe’s learned bias terms ($b_i$) are not merely extra parameters for flexibility; they specifically capture the "unigram" component of the PMI formula, allowing the main vector dot product to focus purely on the relationship between word pairs.

Key Insights

  • Gradient Tempering: The "Multiplier" in the framework is essential. Because word frequencies vary by orders of magnitude, successful algorithms use "tempered" versions of word counts (e.g., square roots) to ensure that rare but meaningful word pairs still influence the model.
  • The Dual Role of Words: Every word plays two roles: a focal word and a context word. Models must learn two separate vectors (vectors and "covectors") to satisfy the mathematical requirements of the framework, even if one set is typically discarded after training.

Limitations and Future Work

While this work provides a rigorous foundation for uncontextualized embeddings, it does not provide a formal proof for deep contextualized models like BERT or GPT. However, the authors conjecture that these insights could inform the design of future models by more intentionally utilizing PMI statistics or the dual nature of word representations.

Summary updated

Abstract

Word embeddings are reliable feature representations of words used to obtain high quality results for various NLP applications. Uncontextualized word embeddings are used in many NLP tasks today, especially in resource-limited settings where high memory capacity and GPUs are not available. Given the historical success of word embeddings in NLP, we propose a retrospective on some of the most well-known word embedding algorithms. In this work, we deconstruct Word2vec, GloVe, and others, into a common form, unveiling some of the common conditions that seem to be required for making performant word embeddings. We believe that the theoretical findings in this paper can provide a basis for more informed development of future models.
BibTeX
@inproceedings{kenyondean2020deconstructing,
  author = {Kian Kenyon-Dean and Edward Newell and Jackie Chi Kit Cheung},
  title = {{Deconstructing word embedding algorithms}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=N9g00iYIzA},
}
Figure