Why does skip-gram training use negative sampling instead of a full softmax?
answer
- the denominator sums over every word
- turn ranking into a yes-or-no question
- a handful of fake pairs per real one
- flatten Zipf before drawing noise
- the tree alternative costs log of vocabulary
basics
~20 sA full softmax normalises over the whole vocabulary, so every update touches every output vector. Negative sampling instead scores the real pair up and a few sampled noise pairs down, making cost independent of vocabulary size.
solid answer
~50 sThe exact objective needs a softmax over the entire vocabulary, and its denominator sums a score for every word — so each update costs O(V) and touches every output vector. Negative sampling reframes the step as binary classification: for one observed (centre, context) pair, draw k noise words (5-20 for a small corpus, 2-5 for a large one) and train a logistic classifier to say "real" for the observed pair and "noise" for the sampled ones. The update now touches k+1 output vectors, so cost stops depending on vocabulary size. Noise words are drawn from the unigram distribution raised to the 3/4 power, which flattens it: frequent words are still sampled most, but rare words appear as negatives far more often than raw frequency allows. The alternative, hierarchical softmax, keeps a normalised distribution but replaces the flat output layer with a binary Huffman tree costing about log2(V) sigmoid decisions per word.
code
python · 13 linescounts = {"the": 1_000_000, "bank": 10_000, "otter": 100}
total = sum(counts.values())
z = sum(c ** 0.75 for c in counts.values())
print("word unigram noise lift")
for word, c in counts.items():
unigram = c / total
noise = (c ** 0.75) / z
print(f"{word:8} {unigram:.6f} {noise:.6f} {noise / unigram:.1f}x")
# the 0.990001 0.968408 1.0x
# bank 0.009900 0.030624 3.1x
# otter 0.000099 0.000968 9.8xgo deeper
Know that computing a softmax over a vocabulary of hundreds of thousands of words for every training pair is too expensive, and that negative sampling replaces it with a small number of fake pairs to push down.
Write the loss: one log-sigmoid on the real pair plus k log-sigmoids on sampled noise pairs. Explain that only k+1 output vectors get updated, and state the 3/4-power noise distribution and what it is fixing.
Show you understand the objective actually changed — the model is a real-versus-noise discriminator, not a normalised language model — and be able to reason about how k and the noise exponent interact with corpus size and vector quality on the tail.
Frame it as the general pattern: when a normalising constant over a huge output space blocks training, you either sample it away or restructure the output space into a tree. Be ready to argue which trade the team should take and what evaluation would settle it.
## What the expensive version costs The clean probabilistic form of the skip-gram objective is a softmax over the vocabulary: the probability of context word `c` given centre word `w` is `exp(u_c . v_w)` divided by the sum of `exp(u_j . v_w)` over every word `j` in the vocabulary. The numerator is one dot product. The denominator is a sum over all V words — and V is routinely 100,000 to a few million. The gradient inherits that cost. Differentiating the log-probability produces a term for *every* output vector, weighted by its softmax probability, so a single training pair updates the entire output matrix. Multiply by billions of (centre, context) pairs in a real corpus and the exact objective is simply not trainable at that scale. ## The reframing Negative sampling drops the requirement to produce a normalised distribution at all. Instead of asking "which of V words is the context here?", it asks a much cheaper question: "is this (centre, context) pair one that really occurred, or one I fabricated?" For each observed pair `(w, c)`, draw k noise words `n_1..n_k` from a noise distribution. The per-pair loss is `- log sigmoid(u_c . v_w) - sum_i log sigmoid(-u_ni . v_w)` The first term pushes the real pair's dot product up; each remaining term pushes a sampled pair's dot product down. Only k+1 output vectors and one input vector appear in the gradient, so an update costs O(k) rather than O(V) — independent of vocabulary size. Typical k is 5-20 on a small corpus and 2-5 on a very large one, where there is enough data that fewer negatives per pair suffice. The important consequence: the trained model is **not** a language model. It never produces a normalised probability over the next word, and its scores are not calibrated probabilities. It is a discriminator between real and fabricated co-occurrences, and the vectors are a by-product of that discrimination. If you need `P(context | word)` you cannot get it from this model without re-normalising, and nobody does — the vectors are the deliverable. ## Why the 3/4 power Negatives are drawn not from the raw unigram distribution but from unigram frequency raised to the power 0.75, then re-normalised. The exponent compresses the dynamic range of a Zipfian distribution. Concretely, take a toy vocabulary of three words with counts 1,000,000, 10,000 and 100. Their raw unigram probabilities are about 0.9900, 0.0099 and 0.000099. After raising counts to the 3/4 power and re-normalising they become about 0.9684, 0.0306 and 0.000968. The very frequent word barely moves down, the mid-frequency word roughly triples its share, and the rare word is drawn about ten times more often than its raw frequency would allow. That is the point. If negatives came from the raw distribution, the model would spend nearly all its negative capacity pushing down pairs involving the handful of hyper-frequent function words, and rare words would almost never receive a negative gradient — leaving their vectors under-constrained. If negatives came from a uniform distribution, common words would rarely be sampled and the model would never learn to separate them from genuinely related words. The 3/4 exponent is an empirical compromise between those failure modes, not a derived constant. ## The other escape route: hierarchical softmax Hierarchical softmax attacks the same O(V) denominator while keeping a properly normalised distribution. The flat output layer is replaced by a binary tree whose leaves are the vocabulary words, built as a Huffman tree so that frequent words sit on short paths. Each internal node holds its own vector and makes one logistic decision (go left or go right). The probability of a word is the product of the sigmoid decisions along the root-to-leaf path, which is guaranteed to sum to one over all leaves. Cost per update becomes the path length — roughly log2(V) nodes, and less than that for frequent words thanks to the Huffman coding. Empirically hierarchical softmax tends to do relatively better on infrequent words, and negative sampling relatively better on frequent ones and on lower-dimensional vectors; negative sampling is the more common default because it is simpler and its cost does not depend on where a word sits in a tree. ## What an interviewer is probing Three things. First, that you know *why* the softmax denominator is the bottleneck — that it is a sum over the vocabulary appearing in every gradient, not merely "a big matrix multiply". Second, that negative sampling changes the objective, not just its implementation: you trade a normalised distribution for a binary discrimination task, and accept that the outputs stop being probabilities. Third, that the noise distribution is a designed choice with a purpose, and you can say what breaks at each extreme.
- After training this way, can you read a probability distribution over context words out of the model?Not directly. Negative sampling never normalises over the vocabulary, so the sigmoid scores are un-normalised pair scores, not calibrated probabilities. You would have to compute the full softmax denominator yourself at inference to recover a distribution. In practice nobody does — the point of the run is the vectors, not the predictive head, and the output matrix is usually discarded.
- What goes wrong if you draw negatives uniformly over the vocabulary instead?Frequent words then almost never appear as negatives, so nothing pushes down spurious high scores between a centre word and a common function word, and those neighbours pollute the nearest-neighbour lists. The 3/4 exponent exists precisely to keep frequent words well represented among negatives while still giving the long tail a real share.
- How does hierarchical softmax's cost profile differ across the vocabulary?It is not uniform. Cost is the root-to-leaf path length, and the Huffman construction gives frequent words short paths and rare words long ones — so the average update is cheaper than log2(V) on real Zipfian text. Negative sampling, by contrast, costs exactly k+1 output-vector updates regardless of which word it is.
saying these in an interview costs you the question
- Says negative sampling is just an approximation of the same softmax
- Thinks the trained scores are calibrated probabilities
- Claims negatives are drawn uniformly over the vocabulary
- Confuses hierarchical softmax with sampling negatives
- Believes cost still scales with vocabulary size