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

Duplicate, retired. This paper was already filed as LIT-603, and the record requires one entry per arXiv identifier. This entry’s body is kept as written; LIT-603 is the one to cite.

Mikolov et al. (2013) — ARXIV-1310.4546

Key takeaways

• Negative sampling is defined here, and it is defined as a deliberate degradation. It descends from Noise-Contrastive Estimation (Gutmann & Hyvärinen), which “can be shown to approximately maximize the log probability of the softmax”. The paper then says the quiet part: “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 that produces good vectors. The record’s contrastive documents inherit that posture without usually inheriting the sentence.
• The number of negatives falls as the dataset grows. k in the range 5–20 is useful for small datasets; for large ones “k can be as small as 2–5”. Stated plainly, unremarkably, in 2013.
• The noise distribution is tuned and the tuning is reported. The unigram raised to the 3/4 power beat both the plain unigram and the uniform distribution “on every task we tried” — an exponent with no derivation behind it, carried forward by everyone since.
• Subsampling frequent words does two things at once. It gives “significant speedup” and improves “accuracy of the representations of less frequent words”. A throughput change that improves quality is rare enough to be worth its own document — SOTA-382.
• Phrases as units. Idiomatic phrases are not compositions of their words, so the paper finds phrases in text and learns vectors for them directly, “millions of phrases”. The what counts as a unit question, asked and answered empirically.

Standing in the anthology

Unit G of #304. It sources SOTA-381 (sample negatives; let the count fall with data) and SOTA-382 (subsample frequent tokens).

Its predecessor is LIT-610, and the abstract opens on it: the continuous Skip-gram model is taken as given, and this paper presents “several extensions that improve both the quality of the vectors and the training speed”. The extensions are the ones above: negative sampling as “a simple alternative to the hierarchical softmax” that LIT-610 used, subsampling of frequent words, and phrase tokens. Without subsampling, NEG-15 reaches 61% on word analogies against 47% for hierarchical softmax (per LIT-603’s reading).

The k finding is the reason this unit was worth doing at all. The record now holds three arguments that the negative count is not a quality dial — THEORY-085’s log N ceiling on the InfoNCE certificate, LIT-591’s finding that batch-size gaps close with longer training, and SOTA-377’s measured saturation at 32k. This is a fourth, from a different literature, ten years earlier, and pointing further: not merely that more negatives stop helping, but that fewer are needed as data grows.

Four arguments, four literatures, none downstream of the others. Whether the word-embedding case is really the same phenomenon is not settled here — the objectives differ and nobody has connected them — but the record should at least stop treating “more negatives is better” as something the field believed uniformly. It did not; the text side said otherwise, first.