Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 uc⊤vw=PMI⁡(w,c)−log⁡k\mathbf u_c^\top\mathbf v_w=\operatorname{PMI}(w,c)-\log k, 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 ∣V∣×∣V∣|V|\times|V| 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 log⁡0=−∞\log0=-\infty, 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.

Predict before you look

A corpus has ∣D∣=106|D|=10^6 pairs. The word ww occurs in 1,0001{,}000 of them, the context cc in 2,0002{,}000, and they co-occur 2020 times. What is PMI⁡(w,c)\operatorname{PMI}(w,c), in nats?

Show the answer

2.3

PMI⁡=ln⁡20×1061000×2000=ln⁡10≈2.30\operatorname{PMI}=\ln\frac{20\times10^6}{1000\times2000}=\ln10\approx2.30: they co-occur ten times as often as chance predicts. With k=5k=5 negatives, the shifted value that SGNS targets is 2.30−ln⁡5≈0.692.30-\ln5\approx0.69.

Skip-gram is implicit matrix factorization

DerivationProof
  1. ℓ=∑w,c[#(w,c)⏟A log⁡σ(xwc)+k #(w) #(c)∣D∣⏟B log⁡σ(−xwc)]\ell=\sum_{w,c}\Big[\underbrace{\#(w,c)}_{A}\,\log\sigma(x_{wc})+\underbrace{\tfrac{k\,\#(w)\,\#(c)}{|D|}}_{B}\,\log\sigma(-x_{wc})\Big]

    Expand the expectation, Ec′∼Pnf(c′)=∑c#(c)∣D∣f(c)\E_{c'\sim P_n}f(c')=\sum_c\frac{\#(c)}{|D|}f(c), and collect the terms that involve one pair (w,c)(w,c):

  2. ddx[Alog⁡σ(x)+Blog⁡σ(−x)]=A σ(−x)−B σ(x)=0\frac{d}{dx}\Big[A\log\sigma(x)+B\log\sigma(-x)\Big]=A\,\sigma(-x)-B\,\sigma(x)=0

    With free scores, ℓ\ell splits into independent one-dimensional problems. Each is strictly concave, because its second derivative is −(A+B) σ(x)σ(−x)<0-(A+B)\,\sigma(x)\sigma(-x)<0, so a stationary point is the unique maximum:

  3. ex=AB=#(w,c) ∣D∣k #(w) #(c)⟹xwc⋆=PMI⁡(w,c)−log⁡ke^{x}=\frac AB=\frac{\#(w,c)\,|D|}{k\,\#(w)\,\#(c)}\quad\Longrightarrow\quad x^\star_{wc}=\operatorname{PMI}(w,c)-\log k

    Since σ(x)/σ(−x)=ex\sigma(x)/\sigma(-x)=e^x:

  4. σ(xwc⋆)=#(w,c)#(w,c)+k #(w) #(c)/∣D∣\sigma(x^\star_{wc})=\frac{\#(w,c)}{\#(w,c)+k\,\#(w)\,\#(c)/|D|}

    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 A=0A=0, and the optimum runs off to −∞-\infty, matching PMI⁡=−∞\operatorname{PMI}=-\infty.

In practice dd is a few hundred while ∣V∣|V| is 10510^5–10610^6, so the scores cannot be set freely: SGNS computes a weighted low-rank approximation of M=PMI⁡−log⁡kM=\operatorname{PMI}-\log k under a logistic loss whose weights favor frequent pairs. Three consequences follow.

  • The 3/43/4-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 SPPMI⁡k\operatorname{SPPMI}_k 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 O((k+1)d)\order{(k+1)d} per pair and never forms MM; SVD needs the sparse matrix in memory.
Check your understanding

A pair co-occurs exactly as often as independence predicts, so PMI⁡(w,c)=0\operatorname{PMI}(w,c)=0. With k=5k=5 negatives and enough dimensions, what score uc⊤vw\mathbf u_c^\top\mathbf v_w does SGNS converge to?

  1. 00
  2. ln⁡5≈1.61\ln5\approx1.61
  3. 1/61/6
  4. −ln⁡5≈−1.61-\ln5\approx-1.61
Show the answer

D. −ln⁡5≈−1.61-\ln5\approx-1.61

x⋆=PMI⁡−ln⁡k=−ln⁡5x^\star=\operatorname{PMI}-\ln k=-\ln5. Then σ(x⋆)=1/(1+5)=1/6\sigma(x^\star)=1/(1+5)=1/6: 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, p(solid∣ice)/p(solid∣steam)p(\text{solid}\mid\text{ice})/p(\text{solid}\mid\text{steam}) 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, (wi−wj)⊤w~k=log⁡(Pik/Pjk)(\mathbf w_i-\mathbf w_j)^\top\tilde{\mathbf w}_k=\log(P_{ik}/P_{jk}), leads to wi⊤w~k=log⁡Xik−log⁡Xi\mathbf w_i^\top\tilde{\mathbf w}_k=\log X_{ik}-\log X_i; absorbing log⁡Xi\log X_i into a bias and adding a context bias for symmetry gives GloVe, a weighted least-squares fit to log counts:

J=∑i,kf(Xik)(wi⊤w~k+bi+b~k−log⁡Xik)2,f(x)=min⁡(1,(x/xmax⁡)3/4), xmax⁡=100J=\sum_{i,k}f(X_{ik})\big(\mathbf w_i^\top\tilde{\mathbf w}_k+b_i+\tilde b_k-\log X_{ik}\big)^2,\qquad f(x)=\min\big(1,(x/x_{\max})^{3/4}\big),\ x_{\max}=100
f(0)=0f(0)=0 skips the zero cells, so training costs scale with the number of nonzero co-occurrences rather than ∣V∣2|V|^2, and the cap keeps very frequent pairs from dominating. The final vectors are w+w~\mathbf w+\tilde{\mathbf w}.
DerivationFrom co-occurrence ratios to parallelograms
  1. uc⊤(va−vb)=log⁡p(c∣a)p(c∣b)for every context c\mathbf u_c^\top(\mathbf v_a-\mathbf v_b)=\log\frac{p(c\mid a)}{p(c\mid b)}\qquad\text{for every context }c

    Suppose the factorization is exact, uc⊤vw=PMI⁡(w,c)−log⁡k\mathbf u_c^\top\mathbf v_w=\operatorname{PMI}(w,c)-\log k for all w,cw,c. Subtracting two words cancels log⁡k\log k and log⁡p(c)\log p(c):

  2. uc⊤[(vking−vqueen)−(vman−vwoman)]=0∀c\mathbf u_c^\top\big[(\mathbf v_{\text{king}}-\mathbf v_{\text{queen}})-(\mathbf v_{\text{man}}-\mathbf v_{\text{woman}})\big]=0\qquad\forall c

    Now suppose the two pairs have the same ratio profile, p(c∣king)p(c∣queen)=p(c∣man)p(c∣woman)\frac{p(c\mid\text{king})}{p(c\mid\text{queen})}=\frac{p(c\mid\text{man})}{p(c\mid\text{woman})} for every cc. Then the offset difference is orthogonal to every context vector:

  3. vking−vman+vwoman=vqueen\mathbf v_{\text{king}}-\mathbf v_{\text{man}}+\mathbf v_{\text{woman}}=\mathbf v_{\text{queen}}

    If the context vectors span Rd\R^d, 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 r^ui=μ+bu+bi+pu⊤qi\hat r_{ui}=\mu+b_u+b_i+\mathbf p_u^\top\mathbf q_i and fits user vectors pu\mathbf p_u and item vectors qi\mathbf q_i by regularized least squares on the observed entries only, the same logic as GloVe's f(0)=0f(0)=0. 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 uc⊤vw=PMI⁡(w,c)−log⁡k\mathbf u_c^\top\mathbf v_w=\operatorname{PMI}(w,c)-\log k; 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.

Question 1

For a pair with PMI⁡(w,c)=2\operatorname{PMI}(w,c)=2 nats, SGNS is trained with k=5k=5 negatives and many dimensions. What is the optimal score uc⊤vw\mathbf u_c^\top\mathbf v_w?

  1. 22
  2. 2−ln⁡5≈0.392-\ln5\approx0.39
  3. 2+ln⁡5≈3.612+\ln5\approx3.61
  4. 2/5=0.42/5=0.4
Show the answer

B. 2−ln⁡5≈0.392-\ln5\approx0.39

x⋆=PMI⁡−ln⁡k=2−1.61=0.39x^\star=\operatorname{PMI}-\ln k=2-1.61=0.39. Every score is shifted down by the same ln⁡k\ln k, so similarities between words change only slightly; the shift mostly affects how negative unseen or weakly associated pairs become.

Question 2

Why does GloVe's weighting function satisfy f(0)=0f(0)=0 and f(x)=1f(x)=1 for x≥xmax⁡x\ge x_{\max}?

  1. To make the objective convex in the word vectors
  2. To normalize the co-occurrence matrix into probabilities
  3. 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
  4. 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

log⁡0\log0 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.

Question 3

Under an exact factorization uc⊤vw=PMI⁡(w,c)−log⁡k\mathbf u_c^\top\mathbf v_w=\operatorname{PMI}(w,c)-\log k, which condition makes vb−va+vc=vd\mathbf v_b-\mathbf v_a+\mathbf v_c=\mathbf v_d hold exactly?

  1. cos⁡(va,vb)=cos⁡(vc,vd)\cos(\mathbf v_a,\mathbf v_b)=\cos(\mathbf v_c,\mathbf v_d)
  2. p(x∣b)/p(x∣a)=p(x∣d)/p(x∣c)p(x\mid b)/p(x\mid a)=p(x\mid d)/p(x\mid c) for every context xx, with context vectors spanning the space
  3. The four words have the same frequency
  4. aa and cc are nearest neighbors
Show the answer

B. p(x∣b)/p(x∣a)=p(x∣d)/p(x∣c)p(x\mid b)/p(x\mid a)=p(x\mid d)/p(x\mid c) for every context xx, with context vectors spanning the space

Then ux⊤[(vb−va)−(vd−vc)]=0\mathbf u_x^\top\big[(\mathbf v_b-\mathbf v_a)-(\mathbf v_d-\mathbf v_c)\big]=0 for every context xx, and spanning contexts force the bracket to vanish.

Question 4

An analogy benchmark is scored twice with the same vectors: once excluding aa, bb and cc from the candidates, once allowing them. Accuracy collapses in the second run. What does this reveal?

  1. The vectors are untrained
  2. Cosine similarity is the wrong metric for analogies
  3. The benchmark contains errors
  4. vb−va+vc\mathbf v_b-\mathbf v_a+\mathbf v_c usually stays closest to bb or cc, so part of the apparent success comes from the evaluation rule
Show the answer

D. vb−va+vc\mathbf v_b-\mathbf v_a+\mathbf v_c usually stays closest to bb or cc, so part of the apparent success comes from the evaluation rule

The offset vb−va\mathbf v_b-\mathbf v_a is often small relative to vc\mathbf v_c, so the target remains nearest to cc (or bb). 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".