Negative Sampling: Efficient Word2Vec Training

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.

The full Skip-gram model answers: "What is the probability of each vocabulary word being a context word?" This requires computing a probability distribution over 100,000+ words. Negative sampling asks a simpler question: "Is this specific word pair a real context pair or a fake one?" This is binary classification, requiring only a single probability per pair.

Consider the sentence "The quick brown fox jumps." When "fox" is the center word, "brown" is a observed context word. But "elephant" or "democracy" don't appear near "fox" in this context. They're negatives, and we can use them to train the model.

The model learns by maximizing the probability for the positive pair while minimizing it for the negative pairs. Through millions of such updates, the embedding space organizes so that words appearing in similar contexts end up nearby.

The mathematical reformulation is straightforward. Instead of softmax, we use the sigmoid function $\sigma(x) = 1 / (1 + e^{-x})$ to output a probability for each pair independently.

For a positive (center, context) pair, we want the model to output a high probability that this pair comes from the corpus. The sigmoid function maps the dot product of the embeddings to a probability:

where:

• $P(D = 1 | w_c, w_t)$: probability that the word pair $(w_c, w_t)$ is a observed context pair from the data
• $D$: binary indicator variable (1 = observed pair from data, 0 = fake pair)
• $\sigma(x)$: sigmoid function, mapping any real number to the range $(0, 1)$
• $\mathbf{w}'_c$: context embedding vector for word $w_c$
• $\mathbf{w}_t$: center embedding vector for word $w_t$
• $\mathbf{w}'_c \cdot \mathbf{w}_t$: dot product between the context and center embeddings, measuring their similarity

When the embeddings are similar (large positive dot product), the sigmoid output approaches 1, indicating high confidence that the pair comes from the corpus.

For negative pairs, we want $P(D = 1) \approx 0$, or equivalently $P(D = 0) \approx 1$. Using the property that $1 - \sigma(x) = \sigma(-x)$, we write:

where:

• $w_n$: a negative (randomly sampled) word that did not appear in the context
• $\mathbf{w}'_n$: context embedding vector for the negative word $w_n$

When the embeddings are dissimilar (negative dot product), $\sigma(-\mathbf{w}'_n \cdot \mathbf{w}_t)$ approaches 1, correctly indicating that the pair is likely fake.

Having established that we can use sigmoid to score individual word pairs, we now face a key question: what exactly should the model optimize? The answer lies in constructing a clever objective function that captures our core intuition: observed context pairs should score high, while fake pairs should score low.

For each positive pair $(w_t, w_c)$ from the corpus, we sample $k$ negative words $\{w_{n_1}, w_{n_2}, \ldots, w_{n_k}\}$ from a noise distribution $P_n(w)$. The objective for this training example combines both goals into a single expression:

where:

• $\mathcal{L}$: objective function to maximize (higher is better)
• $\mathbf{w}_t$: center word embedding vector for word $w_t$
• $\mathbf{w}'_c$: context embedding vector for the positive context word $w_c$
• $\mathbf{w}'_{n_i}$: context embedding vector for the $i$-th negative sample word
• $k$: number of negative samples per positive pair
• $\sigma(\cdot)$: sigmoid function
• $\log \sigma(\mathbf{w}'_c \cdot \mathbf{w}_t)$: positive term, maximized when the positive pair has high similarity
• $\log \sigma(-\mathbf{w}'_{n_i} \cdot \mathbf{w}_t)$: negative term, maximized when the negative pair has low similarity (negative dot product)

The positive term $\log \sigma(\mathbf{w}'_c \cdot \mathbf{w}_t)$ rewards the model for assigning high probability to observed pairs. When the dot product is large and positive, the sigmoid approaches 1, and $\log(1) = 0$. When the dot product is small or negative, the sigmoid drops toward 0, and $\log(\text{small number})$ is a large negative penalty.

The negative terms $\sum_{i=1}^{k} \log \sigma(-\mathbf{w}'_{n_i} \cdot \mathbf{w}_t)$ reward the model for correctly identifying fake pairs. Notice the negative sign inside the sigmoid. For a negative pair to score well, we need $\sigma(-\text{dot product}) \approx 1$, which happens when the dot product itself is negative (dissimilar embeddings). If the model mistakenly places a negative word close to the center word, the dot product becomes positive, the sigmoid drops, and the log becomes a large penalty.

Together, these terms create opposing forces: the first pulls observed context words toward the center word, while the second pushes random words away. Through millions of such updates, the embedding space self-organizes so that semantically related words cluster together.

The loss landscape reveals the asymmetric pressure applied by each term. For positive pairs (left), the loss drops sharply as the dot product increases, strongly encouraging the model to push observed context words closer. For negative pairs (right), the loss drops as the dot product becomes negative. The steepest gradients occur near zero, where the model is most uncertain.

The objective function creates a tug-of-war in embedding space. Each training step applies forces that reshape the geometry of word representations. Understanding these gradients reveals how semantic structure emerges from local updates.

During backpropagation, two types of forces act on each embedding. An attractive force from positive pairs pulls the center word embedding toward its true context word. A repulsive force from negative pairs pushes the center word away from each sampled negative. The magnitude of each force depends on the current prediction confidence. If the model already correctly predicts a positive pair, the gradient is small. If it is uncertain or wrong, the gradient is large, focusing learning where it matters most.

Starting from the objective function $\mathcal{L} = \log \sigma(\mathbf{w}'_c \cdot \mathbf{w}_t) + \sum_{i=1}^{k} \log \sigma(-\mathbf{w}'_{n_i} \cdot \mathbf{w}_t)$, we compute gradients using the chain rule and the sigmoid derivative $\frac{d\sigma(x)}{dx} = \sigma(x)(1 - \sigma(x))$.

Gradient for the center word embedding $\mathbf{w}_t$:

where:

• $(\sigma(\mathbf{w}'_c \cdot \mathbf{w}_t) - 1)$: always negative since $\sigma(\cdot) \in (0, 1)$, so this term pulls the center embedding toward the positive context
• $\sigma(\mathbf{w}'_{n_i} \cdot \mathbf{w}_t)$: the model's (mistaken) confidence that the $i$-th negative pair comes from the corpus; during gradient ascent, this pushes the center embedding away from each negative

Gradient for the positive context word embedding $\mathbf{w}'_c$:

Since the coefficient $(\sigma - 1)$ is negative, this gradient points toward the center word during gradient ascent, pulling the context embedding closer.

Gradient for each negative word embedding $\mathbf{w}'_{n_i}$:

The positive coefficient $\sigma(\cdot)$ means we subtract this during gradient ascent, pushing each negative embedding away from the center word. The key observation is that this gradient is proportional to how much the model currently confuses the negative for a real pair: if the model already assigns low probability to this negative pair, the gradient is small and the update is minor.

The gradient curves cross at zero, where the model is maximally uncertain. For positive pairs, the model learns strongly when embeddings are dissimilar but relaxes when they are already similar. For negative pairs, the opposite holds. This elegant self-regulation emerges naturally from the sigmoid function.

The choice of how to sample negative words turns out to be surprisingly consequential. A naive approach might sample words uniformly at random. But consider what happens: "the" appears in nearly every sentence, yet with uniform sampling it would be drawn as a negative in only $1/V$ of cases. Meanwhile, "aardvark" appears rarely in real text but would be sampled just as often as "the."

This mismatch creates problems. Common function words occur near almost every word in the corpus, so sampling them as negatives is confusing because they are often legitimate context words too. Rare words sampled too often as negatives cause the model to push everything away from them, hurting their embedding quality.

The Word2Vec authors discovered that a modified unigram distribution works best:

where:

• $P_n(w)$: probability of sampling word $w$ as a negative sample
• $f(w)$: frequency (count) of word $w$ in the corpus
• $f(w)^{0.75}$: the frequency raised to the power 0.75, which compresses the range
• $\sum_{w'} f(w')^{0.75}$: normalizing constant summing over all vocabulary words $w'$
• $0.75$: smoothing exponent determined empirically by the Word2Vec authors

The key insight is that raising to a power less than 1 compresses the range of values. If word A appears 10,000 times and word B appears 10 times, their raw frequency ratio is 1000:1. After applying the 0.75 exponent, $10000^{0.75} / 10^{0.75} \approx 178$. The ratio shrinks from 1000:1 to about 178:1, boosting the representation of rare words without ignoring frequency entirely.

The exponent 0.75 was found empirically by the Word2Vec authors. Consider the intuition by looking at the extremes. An exponent of 1.0 (raw frequency) means frequent words dominate: "the" might account for 7% of samples, wasting computation on a word the model has already learned to handle. An exponent of 0.0 (uniform) treats rare words as often as frequent ones, but rare words share contexts with fewer other words, making them less informative negatives. The value 0.75 strikes a balance: common words still appear often enough to learn good embeddings, while rare words get meaningful representation in the negative samples.

The number of negative samples $k$ is a central hyperparameter that controls the trade-off between training signal quality and computational cost. More negatives provide stronger gradient information per positive pair but increase the work per training step linearly.

The intuition behind these recommendations is straightforward. With a large corpus, each positive word pair appears many times throughout training. This provides ample signal to position that pair correctly. A modest number of negatives is sufficient to push away distractors. With a smaller corpus, each positive pair appears less frequently, so more negatives per step compensate by providing stronger repulsive signal that helps separate unrelated words even with limited data.

The trade-off between the number of negative samples and computational cost is linear: doubling $k$ doubles the work per training step. But the relationship between $k$ and embedding quality is sublinear, with diminishing returns as $k$ increases. The sweet spot at $k = 5$ to $15$ captures most of the quality gains while keeping training times manageable.

Negative sampling didn't emerge from thin air. It is a practical simplification of a more principled technique called Noise Contrastive Estimation (NCE), developed by Gutmann and Hyvärinen (2010). Understanding NCE illuminates why negative sampling works and what theoretical guarantees we sacrifice for efficiency.

The core insight of NCE is elegant: if you can perfectly distinguish real data from noise, you must have learned what makes the data real. The procedure draws positive samples from the true data distribution $P_d(w | c)$ (context words given center) and negative samples from a known noise distribution $P_n(w)$, then trains a classifier to distinguish them.

Since we draw 1 data sample and $k$ noise samples, the prior odds are $1 : k$. The Bayes-optimal decision rule becomes:

where:

• $P(D = 1 | w, c)$: posterior probability that sample $w$ came from the data distribution given context $c$
• $P_d(w | c)$: true data distribution (probability of observing word $w$ in the context of word $c$)
• $P_n(w)$: noise distribution probability for word $w$ (assumed independent of context)
• $k$: number of noise samples drawn per data sample
• $k \cdot P_n(w)$: accounts for the $k$-fold higher chance of seeing noise samples

NCE models this probability using a learnable score function:

where:

• $s(w, c)$: the model's unnormalized log-probability score for word pair $(w, c)$, typically the dot product $\mathbf{w}' \cdot \mathbf{c}$
• $\exp(s(w, c))$: the model's estimate of the unnormalized data probability

When training converges and the classifier achieves optimal performance, comparing the two formulas reveals that the model must have learned $\exp(s(w, c)) \propto P_d(w | c)$. The model recovers the true data distribution up to a normalizing constant.

Negative sampling departs from NCE in two important ways, each trading theoretical rigor for practical efficiency.

First simplification: ignoring the partition function. NCE explicitly models the normalization constant (the sum over all vocabulary words that makes probabilities sum to 1). This constant is precisely what makes softmax expensive. Negative sampling simply ignores it, treating $\exp(s(w, c))$ as an unnormalized score. We lose the ability to compute true probabilities, but for learning embeddings, relative scores suffice.

Second simplification: using sigmoid directly. NCE's probability formula accounts for the ratio of data to noise samples and the noise distribution. Negative sampling replaces this with the simpler sigmoid $\sigma(s(w, c))$. This makes implementation straightforward and gradients clean, at the cost of some theoretical precision.

What do we lose? Negative sampling no longer guarantees convergence to the true data distribution. The embeddings might not represent exact co-occurrence probabilities. But for downstream tasks like analogy completion, similarity search, and transfer learning, this rarely matters. The embeddings capture semantic relationships just as well, at a fraction of the computational cost.

A practical implementation needs to sample from the noise distribution efficiently. Computing probabilities for 100,000 words on every sample would be slow. Instead, we precompute a sampling structure. The key approach uses a cumulative probability array and binary search, giving $O(\log V)$ per sample after $O(V)$ preprocessing.

Now let's put everything together into a complete, trainable Skip-gram model with negative sampling. The model maintains two embedding matrices (center word embeddings $W$ and context embeddings $W'$), performs forward and backward passes, and updates weights via stochastic gradient ascent on the negative sampling objective.

Let's train the model on a corpus with clear semantic structure to observe whether the embeddings capture meaningful relationships:

With the model trained, we can examine whether it has captured meaningful semantic relationships:

A natural question is how the quality of embeddings from negative sampling compares to those from full softmax. Let's train both models on the same corpus:

The comparison reveals a key insight: negative sampling produces embeddings of similar quality to full softmax, despite using a fundamentally different and much cheaper objective. This explains why negative sampling became the default training method for Word2Vec and similar models.

Very frequent words like "the" and "a" provide limited information because they appear in nearly every context. They don't help distinguish different semantic meanings. Word2Vec subsamples frequent words by randomly discarding some occurrences during training based on their frequency:

where:

• $P(\text{keep } w)$: probability of keeping an occurrence of word $w$ during training
• $f(w)$: relative frequency of word $w$ in the corpus, computed as count$(w)$ / total word count
• $t$: subsampling threshold, typically $10^{-5}$
• $\sqrt{t/f(w)}$: dominant term for very frequent words, which provides aggressive subsampling
• $t/f(w)$: additive term that prevents the probability from dropping too sharply

The formula has an intuitive interpretation: when $f(w) \gg t$ (very frequent words), $P(\text{keep } w) \approx \sqrt{t/f(w)}$, which is much less than 1. If "the" has relative frequency $f = 0.05$ and $t = 10^{-5}$, then $P(\text{keep}) \approx \sqrt{10^{-5}/0.05} \approx 0.014$, meaning only about 1.4% of "the" occurrences are kept. When $f(w) \leq t$ (rare words), the formula yields values above 1, which are clamped to 1. This ensures rare words always contribute.

The most frequent words like "the" and "a" have very low keep probabilities, meaning they are discarded during most training iterations. Rarer words like "aardvark" and "quixotic" have keep probability 1.0. This ensures every occurrence contributes to their embeddings.

The key parameters for negative sampling training are:

• num_negatives (k): Number of negative samples per positive pair. Typical range is 5 to 10 for large datasets and 15 to 25 for smaller ones. More negatives improve quality with diminishing returns and increase training time linearly.
• alpha: Smoothing exponent for the noise distribution. The recommended value is 0.75. Values closer to 1.0 give more weight to frequent words; values closer to 0 approach uniform sampling.
• learning_rate: Initial learning rate. The Word2Vec implementation uses 0.025 by default with linear decay to 0.0001 over training.
• window_size: Context window size. Larger windows capture broader topical similarity; smaller windows capture tighter syntactic relationships.

Negative sampling made Word2Vec practical, but it comes with limitations worth understanding.

The most fundamental limitation is that negative sampling does not optimize the true softmax objective. It optimizes a surrogate that happens to produce good embeddings for most downstream tasks, but tasks requiring precise probability estimates or calibrated outputs may be better served by exact methods. The theoretical connection to NCE provides some justification for why the surrogate works, but the guarantees are weaker.

The hyperparameters $k$ and $\alpha$ require tuning. The defaults from the original paper (k=5 to 10, $\alpha$=0.75) work well across many settings, but they are not universally optimal. Low-resource languages, specialized technical vocabularies, or domains with very skewed frequency distributions may benefit from different choices.

Negative sampling also inherits the fundamental limitation of all Word2Vec models: it produces static embeddings. Each word receives a single fixed vector regardless of context. "Bank" in a financial document and "bank" near a river share the same embedding, even though they mean different things. This limitation motivated the development of contextual embedding models like ELMo, BERT, and GPT, which represent the next generation of word representations. We will explore these models in later parts of the book.

Despite these limitations, negative sampling's impact on NLP research was enormous. It made embedding training practical at billion-word scale, enabling the empirical discoveries about embedding geometry (analogies, semantic arithmetic) that captured the community's imagination. It influenced the design of subsequent models, and the core idea of binary discrimination objectives reappears in modern contrastive learning methods that train vision models, cross-modal systems, and sentence encoders. The same principle that makes negative sampling work for word embeddings powers frameworks like SimCLR, CLIP, and many others: rather than computing expensive normalizations over large output spaces, learn by distinguishing real examples from carefully sampled negatives.

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.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about negative sampling.