Explain Negative Sampling for a 2M-Item item2vec Model
A shopping app wants "similar items" for a catalogue of 2,000,000 products. An engineer treats each of 50M browsing sessions as a sentence of item ids and trains skip-gram with a full softmax over all items, embedding size 128. One epoch is projected to take weeks. A colleague says "just use negative sampling with k = 10 negatives" but cannot explain what it optimizes, and another asks why the noise words are drawn from "frequency to the power 0.75" instead of uniformly or by raw frequency.
- Compare the output-layer cost per (centre, context) pair of the full softmax and of negative sampling with k = 10.
- Write the negative-sampling loss for one pair and compute it for an observed pair with score 2.0 and two sampled negatives with scores 0.5 and -1.0. Which term dominates and why?
- Explain the unigram^0.75 noise distribution with a three-item example whose frequencies are 0.9, 0.09 and 0.01.
- State what negative sampling implicitly optimizes at its optimum and what changing k does to it.
- Name three practical adjustments for session data (not for text) and the cold-start limitation that remains.
1. Cost. The full softmax scores every one of the V = 2{,}000{,}000 output vectors: about 2dV = 2 \cdot 128 \cdot 2{,}000{,}000 = 512{,}000{,}000 FLOPs per pair, and the backward pass updates all V output vectors. Negative sampling scores the one positive and k = 10 negatives: 2 \cdot 128 \cdot 11 = 2{,}816 FLOPs, and only 11 output vectors are updated. That is a factor of about 181,800 (verified arithmetic). It turns a V-way multiclass problem into k + 1 binary classifications.
2. The loss. For an observed pair (w, c) and noise words n_1,\dots,n_k sampled from P_n:
With scores 2.0, 0.5, -1.0: the positive term is -\log \sigma(2.0) = 0.127, the first negative is -\log \sigma(-0.5) = 0.974 and the second is -\log \sigma(1.0) = 0.313, total 1.414 (verified). The first negative dominates: the model currently scores that noise word as plausible (positive score), so it carries the largest loss and gradient. The second negative has a score of -1.0, already on the correct side, so it is cheap but not free. The observed pair is almost satisfied. Training moves the centre vector away from the noise vectors it is wrongly close to.
3. Why frequency^0.75. Sampling uniformly over items would mostly draw the millions of rare items, so the model would rarely see the popular items as negatives, which are the ones most likely to be wrongly retrieved. Sampling by raw frequency would draw the same few blockbusters nearly every time and waste most negatives. Raising frequency to the power 3/4 and renormalizing flattens the distribution between those extremes: frequencies (0.9, 0.09, 0.01) become (0.825, 0.147, 0.028) (verified). The head item is still the most likely negative, but the rare items are drawn 2.8 times more often than their raw share (0.028 versus 0.01). The exponent 0.75 was found empirically by Mikolov et al. (2013), not derived.
4. What it optimizes. Levy and Goldberg (2014) showed that, for vectors with enough capacity, the optimum satisfies u_w \cdot v_c = \operatorname{PMI}(w, c) - \log k: SGNS implicitly factorizes the pointwise-mutual-information matrix shifted by \log k (with the noise distribution playing the role of P(c)). Verified on a 5-item toy co-occurrence table with k = 5: the trained scores match PMI - \log 5 with a maximum error of 0.014 on observed pairs, and never-observed pairs are pushed to very negative values. Increasing k lowers every optimal score by \log k and makes the model more conservative about calling a pair similar. In practice k = 5 to 20 for small data and 2 to 5 for large data.
5. Session-specific adjustments.
- Subsample popular items (discard probability 1 - \sqrt{t/f}; with t = 10^{-5} an item with frequency 10^{-3} is dropped 90 percent of the time) so a handful of bestsellers do not dominate every context.
- Define sessions carefully: split on long gaps and bot-like behaviour, limit the window to items that plausibly relate, and consider using the purchased item as a global context for the whole session (Airbnb) and drawing negatives from the same category or market so the model learns within-category distinctions rather than "different department".
- Evaluate on a held-out next-item task (recall@k) rather than eyeballing neighbours.
Limitation. Pure co-occurrence embeddings are cold-start blind: an item with no sessions has no vector. You need content features (text, image, category) in a model that can embed unseen items (a two-tower item tower) or a fallback that averages the vectors of content-similar items.
Share this question