anthology-of-the-sota

THEORY-093: Skip-gram with negative sampling implicitly factorizes the word-context PMI matrix shifted by log k, weighting frequent pairs more heavily

3 min read

Properties4
StatusActive
Tagsrepresentation-and-encoding, signal-structure
SourceLIT-612 — Neural Word Embedding as Implicit Matrix Factorization
Extended byTHEORY-089 — Word vectors trained on co-occurrence behave linearly because they encode log co-occurrence statistics: differences carry log ratios, which gives analogies, and sums carry products of context distributions, which gives composition, THEORY-092 — Raising context counts to the 3/4 power helps word representations because PMI overweights rare contexts, and smoothing lowers their association scores, THEORY-094 — Word vectors approximate PMI in low dimensions, and relations appear as clean directions despite a noisy fit, because text behaves as if generated by a slowly drifting discourse over isotropic word vectors

Graph View

Source

Levy and Goldberg (2014), LIT-612, read as NOTE-331.

The account

SGNS scores each observed pair (w, c) by log σ(w·c) and each of k sampled negatives by log σ(−w·c). Summed over the corpus, a pair’s contribution is #(w,c)·log σ(w·c) + k·#(w)#(c)/|D|·log σ(−w·c). The first term pulls the dot product up in proportion to how often the pair occurs. The second pushes it down in proportion to how often it would occur by chance. The balance point is

w·c = log( #(w,c)·|D| / (#(w)·#(c)) ) − log k = PMI(w, c) − log k.

So the dot products SGNS learns are trying to equal PMI, shifted down by log k. When the dimension is too small to hit every target, the error on each pair is weighted by its counts, so frequent pairs are fitted better than rare ones. Changing the noise distribution to count^α changes the PMI’s denominator the same way.

The derivation is LIT-612’s (its Eq. 6–7, with Eq. 8 giving the NCE form), and the paper also measures how near real fits come to that optimum: shifted PPMI is within about 0.0001% of SGNS’s optimal objective, while SGNS’s own embeddings land 6–39% from it, closer as d grows (Table 1).

Why Active

It is a derivation, and it holds exactly under its stated assumption: dot products free to take any value. It is the standard account of what word2vec fits, and later work (LIT-607) uses it to transfer SGNS’s settings to count methods, with results that behave as the account predicts.

What it explains

  • Why count and prediction methods converge once tuned alike (LIT-607). They fit the same statistic, and the differences are in weighting and settings.
  • Why the number of negatives acts like a prior. It shifts every target by log k, which is why the same shift can be applied to PPMI.
  • Why SVD degrades as k grows. The shifted positive matrix gets more zeros, and SVD’s unweighted L2 loss cannot tell unobserved cells from observed ones (§5.1, a hypothesis in the source).

Where it is weak

  • The optimum is not what training reaches. At d = 100–1000, SGNS is 6–39% off the optimal objective. The account describes what SGNS aims at. What it actually encodes is a weighted low-rank approximation of that target.
  • word2vec’s default uses a smoothed noise distribution, so the factorized matrix uses count^0.75 in place of P(c). The source sets this aside.
  • Why the weighting helps analogies is conjecture.

Backlinks