Word & Item Embeddings
word2vec, GloVe and the geometry of meaning.
Count how often each word appears near each other word, take logarithms, factor the resulting matrix, and you get word vectors competitive with word2vec's. That is no coincidence: in 2014 Levy and Goldberg proved that skip-gram with negative sampling performs exactly this kind of factorization, implicitly. This lesson develops the theory, from PMI and the factorization theorem through GloVe and the geometry of analogies to embeddings of users and items.
What you’ll learn
- Define PMI, PPMI and the shifted PMI matrix, and compute them from co-occurrence counts.
- Prove that skip-gram with negative sampling is optimized by , and read SGNS as weighted low-rank factorization.
- Derive GloVe's weighted least-squares objective, and prove that matching co-occurrence ratios make analogies exact parallelograms.
- Critique analogy benchmarks and debiasing, and carry the same machinery over to recommendation.
Co-occurrence and PMI
Classical distributional semantics builds the matrix of such statistics, reweights it and factors it with a truncated SVD. Latent semantic analysis (Deerwester et al., 1990) did this for word–document counts; for word–context matrices, PPMI with cosine similarity worked best in Bullinaria and Levy's (2007) comparison. PMI has two well-known defects. Unseen pairs get , hence the clipping in PPMI. And pairs of rare words get inflated values: one chance co-occurrence of two rare words looks like a strong association.
A corpus has pairs. The word occurs in of them, the context in , and they co-occur times. What is , in nats?
Show the answer
2.3
: they co-occur ten times as often as chance predicts. With negatives, the shifted value that SGNS targets is .
Skip-gram is implicit matrix factorization
Expand the expectation, , and collect the terms that involve one pair :
With free scores, splits into independent one-dimensional problems. Each is strictly concave, because its second derivative is , so a stationary point is the unique maximum:
Since :
At the optimum, the logistic output is the posterior probability that the pair came from the corpus rather than from the noise, the link to noise-contrastive estimation (Gutmann & Hyvärinen, 2010). For unseen pairs , and the optimum runs off to , matching .
In practice is a few hundred while is –, so the scores cannot be set freely: SGNS computes a weighted low-rank approximation of under a logistic loss whose weights favor frequent pairs. Three consequences follow.
- The -smoothed noise distribution amounts to computing PMI with a smoothed context distribution, which damps PMI's inflation of rare contexts.
- Explicit factorization works too: a truncated SVD of gives competitive vectors, and Levy, Goldberg and Dagan (2015) found that with matched hyperparameters (window, subsampling, context smoothing) count-based and prediction-based methods perform comparably. The hyperparameters mattered more than the algorithm.
- Cost: SGNS streams over the corpus at per pair and never forms ; SVD needs the sparse matrix in memory.
A pair co-occurs exactly as often as independence predicts, so . With negatives and enough dimensions, what score does SGNS converge to?
Show the answer
D.
. Then : when each real pair is matched by five noise pairs and the real pair is no more common than chance, the best guess that a given pair is real is one in six.
GloVe, and why analogies are parallelograms
Pennington, Socher and Manning (2014) started from ratios. In their corpus, is about 9, the same ratio for gas is about 0.09, and for water or fashion it is close to 1: ratios separate relevant contexts from irrelevant ones better than raw probabilities do. Asking that vector differences reproduce log-ratios, , leads to ; absorbing into a bias and adding a context bias for symmetry gives GloVe, a weighted least-squares fit to log counts:
Suppose the factorization is exact, for all . Subtracting two words cancels and :
Now suppose the two pairs have the same ratio profile, for every . Then the offset difference is orthogonal to every context vector:
If the context vectors span , the bracket vanishes and the analogy is an exact parallelogram. Approximately equal ratios give an approximate parallelogram; Allen and Hospedales (2019) and Ethayarajh, Duvenaud and Hirst (2019) turn this into error bounds.
Items, bias and context
Nothing above needs words. In recommendation, matrix factorization (Koren, Bell & Volinsky, 2009) predicts a rating as and fits user vectors and item vectors by regularized least squares on the observed entries only, the same logic as GloVe's . Treat a shopping session as a sentence and SGNS gives item vectors (item2vec, 2016); treat random walks on a graph as sentences and it gives node vectors (DeepWalk, 2014). Relational facts have their own variant in Knowledge Graph Embeddings.
The same statistics carry social associations. Bolukbasi et al. (2016) found occupations ordered along a he–she direction in vectors trained on news text, and Caliskan, Bryson and Narayanan (2017) reproduced classic implicit-association findings with embedding similarities. Projecting out a "gender direction" reduces benchmark measures, yet the bias remains recoverable from neighborhood structure (Gonen & Goldberg, 2019), and some widely shared biased analogies were inflated by the exclusion rule above (Nissim, van Noord & van der Goot, 2020).
A static embedding gives "bank" one vector for rivers and money alike. Contextual models such as ELMo (2018) and BERT (2019) compute a vector per occurrence, and today's language models keep static tables only at their input and output layers, often tied together (Press & Wolf, 2017). Their contextual vectors turned out to be strongly anisotropic, crowded into a narrow cone, rather than spread over the sphere (Ethayarajh, 2019).
Key takeaways
- PMI compares co-occurrence with independence; PPMI clips unseen pairs and rare-word pairs inflate it. Factoring (P)PMI matrices is classical distributional semantics.
- Levy–Goldberg: with free scores, SGNS's optimum is ; at practical dimensions it is a weighted low-rank factorization of that matrix.
- GloVe fits log counts by weighted least squares, skipping zeros and capping frequent pairs. Matching co-occurrence ratios plus spanning contexts make analogies exact parallelograms.
- Analogy benchmarks depend on excluding the input words; embeddings absorb social biases that projection-based debiasing hides more than removes.
- The same factorization logic powers recommenders (user and item vectors) and graph embeddings.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
For a pair with nats, SGNS is trained with negatives and many dimensions. What is the optimal score ?
Show the answer
B.
. Every score is shifted down by the same , so similarities between words change only slightly; the shift mostly affects how negative unseen or weakly associated pairs become.
Why does GloVe's weighting function satisfy and for ?
- To make the objective convex in the word vectors
- To normalize the co-occurrence matrix into probabilities
- Zero counts have no logarithm and are skipped, which also makes the cost scale with the nonzero entries; the cap stops very frequent pairs from dominating
- To implement negative sampling inside a least-squares loss
Show the answer
C. Zero counts have no logarithm and are skipped, which also makes the cost scale with the nonzero entries; the cap stops very frequent pairs from dominating
is undefined, so zero cells must drop out, and skipping them makes training cost proportional to the nonzeros. Raw counts would let pairs like (the, of) swamp the loss, so the weight grows sublinearly and then saturates.
Under an exact factorization , which condition makes hold exactly?
- for every context , with context vectors spanning the space
- The four words have the same frequency
- and are nearest neighbors
Show the answer
B. for every context , with context vectors spanning the space
Then for every context , and spanning contexts force the bracket to vanish.
An analogy benchmark is scored twice with the same vectors: once excluding , and from the candidates, once allowing them. Accuracy collapses in the second run. What does this reveal?
- The vectors are untrained
- Cosine similarity is the wrong metric for analogies
- The benchmark contains errors
- usually stays closest to or , so part of the apparent success comes from the evaluation rule
Show the answer
D. usually stays closest to or , so part of the apparent success comes from the evaluation rule
The offset is often small relative to , so the target remains nearest to (or ). Excluding the inputs hides this, which is Linzen's (2016) point.
Further reading
- O. Levy & Y. Goldberg, "Neural word embedding as implicit matrix factorization," NeurIPS (2014).
- J. Pennington, R. Socher & C. D. Manning, "GloVe: Global vectors for word representation," EMNLP (2014).
- O. Levy, Y. Goldberg & I. Dagan, "Improving distributional similarity with lessons learned from word embeddings," Transactions of the ACL 3, 211–225 (2015).
- S. Arora, Y. Li, Y. Liang, T. Ma & A. Risteski, "A latent variable model approach to PMI-based word embeddings," Transactions of the ACL 4, 385–399 (2016).
- D. Jurafsky & J. H. Martin, Speech and Language Processing (3rd ed. draft), ch. 6 "Vector Semantics and Embeddings".