Introduction
When word2vec was released by Tomas Mikolov and his team at Google, it revolutionized Natural Language Processing (NLP) by demonstrating that high-quality word embeddings—vector representations of words—could be produced with unprecedented efficiency. Despite its widespread adoption, the underlying mathematical justification for its most effective training method, "Negative Sampling," remained somewhat cryptic in the original research papers.
In their explanatory note, Yoav Goldberg and Omer Levy bridge the gap between the software's implementation and its theoretical foundations. They reveal that Negative Sampling (NEG) is not merely a faster approximation of the traditional Softmax function, but a distinct binary classification task that fundamentally changes how the model learns semantic relationships.
The Computational Bottleneck: Skip-gram and Softmax
The standard Skip-gram model architecture aims to maximize the probability of observing a context word $c$ given a target word $w$. In a traditional probabilistic framework, this is achieved using the Softmax function:
$$P(c|w; \theta) = \frac{\exp(v_c \cdot v_w)}{\sum_{c' \in V} \exp(v_{c'} \cdot v_w)}$$
While mathematically sound, this approach presents a devastating computational hurdle: the denominator requires a summation over the entire vocabulary $V$. In modern NLP tasks, where vocabularies often exceed hundreds of thousands of words, calculating this sum for every training step is prohibitively expensive. Researchers initially looked for ways to approximate this sum, but Negative Sampling provides a more elegant, if theoretically different, alternative.
Reframing the Problem: Negative Sampling as Binary Classification
Goldberg and Levy clarify that Negative Sampling reframes the objective. Instead of asking "Which specific word out of 100,000 choices appears in this context?", the model is tasked with a simpler binary question: "Is this specific $(word, context)$ pair real or fake?"
To implement this, the training process utilizes two types of data:
- Positive Samples ($D$): Pairs $(w, c)$ that actually appear in the text corpus.
- Negative Samples ($D'$): Pairs $(w, c')$ generated by pairing a target word with a random word from the dictionary that likely does not belong in that context.
The goal is to optimize the model parameters $\theta$ such that the probability of "real" pairs is maximized and the probability of "fake" pairs is minimized. This leads to the following objective function:
$$\arg \max_{\theta} \sum_{(w,c) \in D} \log \sigma(v_c \cdot v_w) + \sum_{(w,c) \in D'} \log \sigma(-v_c \cdot v_w)$$
Here, $\sigma(x)$ is the sigmoid function, which maps the dot product of the word vectors to a probability between 0 and 1. This formula ensures that the model pushes the vectors of related words closer together while pulling unrelated words apart.
Key Implementation Nuances
The power of word2vec lies not just in the objective function, but in several specific implementation choices highlighted by the authors:
- The Role of Negative Samples: Without negative samples, the model could reach a "trivial solution." It could simply assign the same vector to every word, making every dot product large and every probability 1. Negative samples act as the necessary "anchor" that prevents the vector space from collapsing.
- The 3/4 Power Rule: When drawing negative samples, word2vec does not use raw word frequencies. Instead, it draws from a distribution where frequencies are raised to the $3/4$ power. This mathematical quirk gives a slight boost to rare words, ensuring they are sampled as negative examples more frequently than they would be otherwise, which improves the quality of the resulting embeddings.
- Dynamic Windows: The authors note that word2vec does not use a fixed context window. Instead, it samples a window size between 1 and a maximum $k$ for each word. This effectively weights nearby words more heavily than distant ones, as closer words are included in the context window more consistently.
Conclusion
Goldberg and Levy’s derivation clarifies that Negative Sampling is not a direct mathematical equivalent to the Skip-gram’s conditional probability; it is a different objective entirely that happens to produce similar, high-quality results. While the "how" of the math is now well-mapped, the authors admit that the "why" remains a subject for further study. The distributional hypothesis—that words in similar contexts have similar meanings—provides the intuition, but the formal geometric reasons why this specific binary optimization leads to such robust semantic representations continue to be a fertile ground for research.
Summary updated