Negative Sampling › Negative Sampling

The Skip-gram model learns powerful word representations, but it has a computational bottleneck: the softmax denominator. Every training step requires computing a sum over the entire vocabulary. Given a center word $w_t$, the probability of a context word $w_c$ is:

where:

• $P(w_c | w_t)$: probability of context word $w_c$ given center word $w_t$
• $\mathbf{w}'_c$: context embedding vector for word $w_c$
• $\mathbf{w}_t$: center embedding vector for word $w_t$
• $V$: vocabulary size

For a vocabulary of 100,000 words, this means 100,000 dot products and exponentials per training step. With billions of training examples, full softmax becomes impractical. Training would take months instead of days.

Negative sampling solves this problem by reformulating the task as binary classification. Instead of predicting the exact probability of a context word, we ask: is this word pair a observed co-occurrence from the corpus, or a fake pair we constructed? This transformation reduces the computational cost from $O(V)$ to $O(k)$, where $k$ is a small constant (typically 5 to 20), making large-scale training feasible.

This chapter develops negative sampling from first principles. We'll derive the objective function, understand why the sampling distribution matters, implement efficient training, and see how this approximation achieves nearly the same quality as full softmax at a fraction of the cost.