Negative Sampling › Summary

Negative sampling transforms the Skip-gram training problem from an expensive multi-class classification (softmax over vocabulary) to efficient binary classification (real vs. fake pairs). This simple change reduces computational complexity from $O(V)$ to $O(k)$ per training step, making large-scale training feasible.

Key takeaways:

• Binary classification reformulation: Instead of predicting which word is the context, predict whether a given pair comes from the corpus or randomly sampled. This eliminates the need to compute probabilities over the entire vocabulary.
• Sigmoid instead of softmax: Each pair is scored independently using the sigmoid function. The positive term pulls context words closer; the negative terms push random words away.
• The sampling distribution matters: Using $P_n(w) \propto f(w)^{0.75}$ balances representation between frequent and rare words better than either uniform or raw frequency sampling.
• Number of negatives ($k$): Typically 5 to 20, with smaller values for larger datasets. More negatives provide stronger training signal with diminishing returns and linear cost increase.
• Theoretical foundation in NCE: Negative sampling is a simplification of Noise Contrastive Estimation, trading theoretical guarantees for practical efficiency. It ignores the partition function and replaces the NCE probability formula with a plain sigmoid.
• Comparable quality to full softmax: Despite the approximation, embeddings from negative sampling rival those from full softmax in downstream tasks, which is why it became the standard training method.

The next chapter explores hierarchical softmax, an alternative approximation that organizes the vocabulary as a binary tree, reducing softmax complexity from $O(V)$ to $O(\log V)$ without the binary classification reformulation.