anthology-of-the-sota

LIT-603: Distributed Representations of Words and Phrases and their Compositionality

4 min read

Properties9
StatusActive
Version3
Tagsrepresentation-and-encoding, training-optimization, signal-structure, concept-geometry
ExtendsLIT-604 — Efficient Estimation of Word Representations in Vector Space
Compared againstLIT-602 — GloVe: Global Vectors for Word Representation, LIT-607 — Improving Distributional Similarity with Lessons Learned from Word Embeddings, LIT-612 — Neural Word Embedding as Implicit Matrix Factorization, LIT-613 — A Latent Variable Model Approach to PMI-based Word Embeddings
SupersedesLIT-609 — Distributed Representations of Words and Phrases and their Compositionality
Cited as “introduced by” bySOTA-374 — When learning embeddings from co-occurrence, subsample very frequent tokens, discarding each occurrence with probability 1 − √(t/f) with t around 10⁻⁵, SOTA-375 — When training with sampled negatives, draw them from the unigram distribution raised to the 3/4 power, not from the unigram or uniform distribution, SOTA-381 — Sample a handful of negatives instead of normalizing over the vocabulary, and let the count fall as the data grows, SOTA-382 — Subsample frequent tokens: it is faster and it improves the rare ones
Cited as “paper” byNOTE-326 — word2vec (negative sampling, subsampling, phrases)
Cited as “source” bySOTA-374 — When learning embeddings from co-occurrence, subsample very frequent tokens, discarding each occurrence with probability 1 − √(t/f) with t around 10⁻⁵, SOTA-375 — When training with sampled negatives, draw them from the unigram distribution raised to the 3/4 power, not from the unigram or uniform distribution, SOTA-381 — Sample a handful of negatives instead of normalizing over the vocabulary, and let the count fall as the data grows, SOTA-382 — Subsample frequent tokens: it is faster and it improves the rare ones, THEORY-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

Graph View

Mikolov, Sutskever, Chen, Corrado and Dean, Google (NIPS 2013) — ARXIV-1310.4546

Key takeaways

  • Negative sampling (§2.2): for each observed pair, distinguish the true context word from k samples drawn from a noise distribution, using logistic regression. k = 5–20 for small data and 2–5 for large. Unlike NCE it needs only samples, not their probabilities
  • Negative sampling is defined as a deliberate degradation, and the paper says so. NEG descends from Noise-Contrastive Estimation (Gutmann & Hyvärinen), which “can be shown to approximately maximize the log probability of the softmax”. This paper then drops that on purpose: “we are only concerned with learning high-quality vector representations, so we are free to simplify NCE as long as the vector representations retain their quality.” NEG is not an estimator of anything — it is a task chosen because it produces good vectors. Almost every contrastive objective in the record inherits the posture; hardly any inherits the sentence.
  • The noise distribution: U(w)^{3/4}/Z “outperformed significantly the unigram and the uniform distributions … on every task we tried”. No numbers are given
  • Subsampling frequent words (§2.3, Table 1): discard each occurrence with probability 1 − √(t/f(w)), t ≈ 10⁻⁵. The rationale is that “the” is near every word and teaches little. Word analogies, 300d skip-gram:
    • NEG-5: 38 → 14 minutes, 59 → 60%
    • NEG-15: 97 → 36 minutes, 61 → 61%
    • HS-Huffman: 41 → 21 minutes, 47 → 55%
  • Phrases (§4, Table 3): bigrams scored by (count(ab) − δ) / (count(a)·count(b)) above a threshold become single tokens, in 2–4 passes. On a new phrase-analogy set, subsampling helps a lot: NEG-15 goes 27 → 42% and HS goes 19 → 47%. The best model reaches 72% with 33B words
  • Additive compositionality (§5, Table 5): the nearest tokens to vec(Russian) + vec(river) include Volga River. The authors’ explanation is that vectors are log-linear in context probabilities, so a sum behaves like a product of context distributions, an AND

Standing in the anthology

Filed on request with its predecessor (LIT-604) and with GloVe (LIT-602), which uses this paper’s skip-gram and CBOW with negative sampling as its baseline. It sources SOTA-374 (subsampling) and SOTA-375 (the 3/4-power noise distribution), and is a source for THEORY-089.

signal-structure, because two of its methods rest on what text is like. Subsampling rests on the heavy head of the word-frequency distribution. Phrase detection treats non-compositional multi-word units, such as “Air Canada”, as words. That is the property LIT-410 and LIT-409 are about.

The 3/4 exponent carries no evidence in the paper. It is asserted to be significantly better, with no table. It became a fixture of embedding and retrieval code anyway. The first measurement in the record is LIT-607, which tests it against no smoothing: a consistent but small gain for SGNS, and a large one for PPMI.

Two later papers compare this one with count-based and generative alternatives. Levy and Goldberg (LIT-612) show that SGNS’s objective is optimised at w·c = PMI(w, c) − log k. They then compare SGNS on 1.5B tokens at d = 1000 with shifted PPMI and with SVD over it. Those match or edge SGNS on word similarity (WS353 0.691 against 0.666), while SGNS keeps a clear lead on syntactic analogies, 0.627 against 0.466 for the best alternative. Arora et al. (LIT-613) set skip-gram and CBOW against their own SN objective on the Google analogies: skip-gram 0.70, CBOW 0.74, SN 0.71 (their Table 1). They also derive CBOW’s averaging of context vectors as the maximum a posteriori estimate of their discourse vector.

k falls as the data grows, and that is a fourth argument in a line this paper predates. The record holds three findings that the number of negatives is not a quality dial — THEORY-085’s log N ceiling on what the InfoNCE bound can certify, LIT-591’s batch-size gaps closing with longer training, and SOTA-377’s measured saturation at 32k. This is the fourth, from a different literature and ten years earlier, and it points further: not that more negatives stop helping, but that fewer are needed as the dataset grows.

Whether it is the same phenomenon is open and should stay open — skip-gram’s k counts negatives per positive against a noise distribution, where the vision line’s batch counts negatives drawn from the data, and nobody has connected them. What it does settle is that “the field believed more negatives were better” is not true of the whole field. Half of it said otherwise, plainly, in 2013.

Read — NOTE-326.

Backlinks