The skip-gram model of word2vec learns vectors by predicting each word's neighbors. With a softmax, every step requires one term per word in the vocabulary, which may have 10⁵ to 10⁷ entries (Mikolov, Sutskever, et al., 2013, sec. 2). Negative sampling changes the question: no longer "which of all words comes next to it?" but "is this pair real or noise?" For each observed pair, k words are drawn at random and a logistic classifier learns to accept the first and reject the others:
log σ(c · w) + Σᵢ log σ(−nᵢ · w)
where w is the word's vector, c that of its real context, and nᵢ those of the sampled words.
(dog, barks) → 1 · (dog, mortgage) → 0
The authors recommended k between 5 and 20 for small corpora and between 2 and 5 for large ones, and sampling by frequency raised to the 3/4 power, which slightly favors rare words (Mikolov, Sutskever, et al., 2013, sec. 2.2). It simplifies noise-contrastive estimation (Gutmann & Hyvärinen, 2010). Without negatives, the model could cheat by always answering "neighbors" (Alammar & Grootendorst, 2024, pp. 64–65).
What is learned? Levy & Goldberg (2014) showed that, given enough dimensions, the optimum satisfies w · c = PMI(w, c) − log k: the pointwise mutual information (how much more often than chance word and context occur together), shifted by a constant (2014, sec. 3.1). It is the distributional hypothesis, computed without counting.
The idea lives on in contrastive learning, where the choice of negatives matters: for "How many people live in Amsterdam?", an easy negative is any unrelated text; a hard one, "More than a million people live in Utrecht" (Alammar & Grootendorst, 2024, pp. 307–308).
A caveat for linguists: these negatives are not corrections. Nobody certifies that dog and mortgage cannot go together, and sometimes the draw brings in a true neighbor. They are closer to what acquisition research calls indirect negative evidence: what one expected to see and did not. Does that change the terms of the poverty-of-the-stimulus argument?