Neural Word Embedding as Implicit Matrix Factorization

Omer Levy, Yoav Goldberg

This seminal paper by Omer Levy and Yoav Goldberg provides a theoretical bridge between the "neural" word embeddings that took the natural language processing (NLP) world by storm in the early 2010s and traditional "count-based" distributional semantics.

TL;DR

The authors prove that word2vec’s Skip-Gram with Negative Sampling (SGNS) is not a "black box" neural method, but is actually implicitly factorizing a word-context matrix shifted by a constant. Specifically, it optimizes for the Pointwise Mutual Information (PMI) between words and contexts, providing a solid mathematical foundation for why these embeddings work so well.

What Problem Does This Paper Address?

When Mikolov et al. released word2vec in 2013, it achieved state-of-the-art results on linguistic tasks with surprising efficiency. However, the underlying reason why it worked was poorly understood. It was framed as a neural network objective, but it lacked a clear connection to the decades of research on distributional semantics—the idea that words with similar contexts have similar meanings.

Levy and Goldberg set out to demystify SGNS by asking two fundamental questions: "What is the mathematical quantity being optimized here?" and "How does this relate to traditional matrix-based methods like Singular Value Decomposition (SVD)?"

Methods

The paper employs a rigorous mathematical derivation to characterize the "implicit matrix" that SGNS explores.

  1. Objective Analysis: They analyze the SGNS objective function and show that for a sufficiently large dimensionality, the optimal solution for the dot product of a word vector ($w$) and a context vector ($c$) is: $$w \cdot c = \text{PMI}(w, c) - \log k$$ where $k$ is the number of negative samples.

  2. Shifted PPMI (SPPMI): Based on this finding, they propose a new, non-neural representation: a sparse matrix where each cell is the Positive PMI (PPMI) shifted by $\log k$.

  3. Symmetric SVD: They suggest a variation of SVD that distributes the singular values equally between the word and context matrices ($W = U_d \sqrt{\Sigma_d}$), arguing that this "symmetry" better reflects the nature of the SGNS training process.

Datasets

The models were trained on a 2013 dump of English Wikipedia, comprising approximately 1.5 billion tokens.

For evaluation, they used four standard benchmarks:

  • Word Similarity: WordSim353 and MEN (measuring how well vector cosine similarity correlates with human judgments).
  • Word Analogies: The Google "Mixed" analogy dataset and a "Syntactic" analogy dataset (e.g., "king is to queen as man is to woman").

Key Insights and Ideas

  • The "Aha" Moment: SGNS is essentially a weighted matrix factorization algorithm. It doesn't treat every word-context pair equally; it gives more weight to frequent pairs, which helps it ignore the "noise" of rare word combinations.
  • The Role of $k$: The number of negative samples ($k$) isn't just a performance hyperparameter. Mathematically, it acts as a "prior" that shifts the PMI. A higher $k$ requires a stronger association between a word and context for their vectors to be close.
  • Neural vs. Count-based: The paper shows that "neural" isn't necessarily better. A simple, sparse SPPMI matrix or a well-tuned SVD can actually outperform SGNS on word similarity tasks.
  • Why SGNS Wins at Analogies: SGNS remains superior on analogy tasks. The authors conjecture this is because SGNS performs weighted factorization, whereas standard SVD treats all cells (even those representing rare, noisy pairs) with equal importance.

Key Results

The evaluation reveals nuanced tradeoffs between neural and count-based methods across different tasks.

Performance of different representations across similarity and analogy tasks
  • Similarity: On the MEN dataset, SVD ($k=1$) achieved a correlation of 0.735, slightly outperforming the best SGNS configuration (0.716).
  • Analogies: SGNS dominated the syntactic analogy task with 62.7% accuracy, while SVD lagged significantly behind at 44.8%.
  • Optimization: The authors demonstrated that their proposed SPPMI matrix is a near-perfect approximation of the objective SGNS is trying to reach. As shown in their sparsity analysis, SPPMI often comes within 0.0001% of the optimal value (e.g., 0.00009% for $k=1$).
Percentage of unobserved word-context pairs with non-zero values

Limitations and Future Work

  • SVD and Noise: The main limitation of SVD identified is its sensitivity to unobserved or rare pairs. Because SVD's objective is unweighted, it struggles to generalize as well as SGNS on complex relational tasks like analogies.
  • Future Directions: The authors suggest that the "middle ground" lies in Stochastic Matrix Factorization (SMF). SMF could combine the explicit objective of matrix factorization with the importance-weighting and scalability of stochastic gradient descent used in neural models.
  • Hyperparameter Sensitivity: The paper highlights that many "neural" gains might actually come from clever hyperparameter tuning (like the shift $k$) rather than the neural architecture itself.

Summary updated

Abstract

We analyze skip-gram with negative-sampling (SGNS), a word embedding method introduced by Mikolov et al., and show that it is implicitly factorizing a word-context matrix, whose cells are the pointwise mutual information (PMI) of the respective word and context pairs, shifted by a global constant. We find that another embedding method, NCE, is implicitly factorizing a similar matrix, where each cell is the (shifted) log conditional probability of a word given its context. We show that using a sparse Shifted Positive PMI word-context matrix to represent words improves results on two word similarity tasks and one of two analogy tasks. When dense low-dimensional vectors are preferred, exact factorization with SVD can achieve solutions that are at least as good as SGNS's solutions for word similarity tasks. On analogy questions SGNS remains superior to SVD. We conjecture that this stems from the weighted nature of SGNS's factorization.
BibTeX
@inproceedings{levy2014neural,
  author = {Omer Levy and Yoav Goldberg},
  title = {{Neural Word Embedding as Implicit Matrix Factorization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure