Negative Sampling for Efficient Word2Vec Training

The full-softmax Skip-Gram model learns useful word embeddings, but its output calculation is expensive. For every center–target pair, it computes scores for every word in the vocabulary.

Negative sampling replaces this large multiclass prediction problem with a small collection of binary classification problems. For each observed word pair, the model learns to distinguish that positive pair from a handful of randomly constructed negative pairs.

The Problem with Full Softmax

In the full-softmax Skip-Gram model, the probability of a nearby target word \(t\) given a center word \(c\) is\[ P(t\mid c) = \frac{ \exp(u_t^\top v_c) }{ \sum_{j=1}^{|\mathcal{V}|} \exp(u_j^\top v_c) }, \]

where:

\(v_c\) is the input embedding of center word \(c\)
\(u_t\) is the output embedding of target word \(t\)
\(|\mathcal{V}|\) is the vocabulary size

The denominator requires a score for every vocabulary entry.

If\[ |\mathcal{V}|=1{,}000{,}000, \]

then each training pair can require approximately one million dot products. This is prohibitively expensive when the corpus produces billions of center–target pairs.

Reformulating the Learning Problem

Negative sampling asks a different question.

Given a pair \((c,t)\), predict whether it came from:

A genuine nearby occurrence in the corpus
A random pairing produced by a noise distribution

Define the binary label\[ y = \begin{cases} 1, & (c,t)\text{ is an observed nearby pair},\\ 0, & (c,t)\text{ is a sampled noise pair}. \end{cases} \]

For example:

Center word	Candidate target	Label
orange	juice	1
orange	king	0
orange	book	0
orange	the	0
orange	of	0

The first row comes from the corpus. The remaining rows are constructed by sampling candidate target words.

Generating a Positive Pair

A positive example is formed by:

Selecting a center word from the corpus
Defining a window around it
Selecting a nearby word as the target
Assigning label 1

Suppose the corpus contains:

“a glass of orange juice”

With “orange” as the center, a positive pair may be\[ (\text{orange},\text{juice},1). \]

Other positive pairs could be formed with “glass” or “of,” depending on the window and sampling procedure.

Generating Negative Pairs

After selecting the positive pair \((c,t)\), draw \(K\) words independently from a noise distribution \(P_n(w)\):\[ n_1,n_2,\ldots,n_K \sim P_n. \]

Then construct\[ (c,n_1,0), (c,n_2,0), \ldots, (c,n_K,0). \]

If \(K=4\), one positive pair produces five binary examples:

One positive
Four negative

The model therefore performs only \(K+1\) comparisons rather than scoring the complete vocabulary.

False Negatives

A sampled negative word can occasionally be a genuine neighbor of the center word elsewhere in the corpus—or even within the current window.

For example, “of” may be sampled as a negative for “orange” even though the phrase contains “of orange.”

This is a false negative.

The standard method often tolerates such collisions because:

The vocabulary is large.
Any particular collision is usually infrequent.
Genuine pairs recur as positive examples across the corpus.
The objective is statistical rather than a literal statement that two words can never co-occur.

Some implementations reject the known positive target when drawing negatives, but they generally cannot remove every semantically plausible or corpus-valid negative.

The Binary Classifier

For a center word \(c\) and candidate target \(t\), define the score\[ s(c,t)=u_t^\top v_c. \]

The model predicts\[ P(y=1\mid c,t) = \sigma(u_t^\top v_c), \]

where\[ \sigma(z) = \frac{1}{1+\exp(-z)}. \]

Interpretation:

A large positive dot product produces a probability near 1.
A large negative dot product produces a probability near 0.
A dot product near zero produces a probability near \(0.5\).

A bias term can be added, but the classic formulation is often presented without one.

Binary Cross-Entropy Loss

For one labeled pair \((c,t,y)\), the loss is\[ \ell(c,t,y) = -y\log\sigma(u_t^\top v_c) – (1-y)\log \left( 1-\sigma(u_t^\top v_c) \right). \]

For a positive pair,\[ \ell_{\text{positive}} = -\log\sigma(u_t^\top v_c). \]

For a negative pair \((c,n)\),\[ \ell_{\text{negative}} = -\log\sigma(-u_n^\top v_c). \]

The negative form follows from\[ 1-\sigma(z)=\sigma(-z). \]

The Complete Negative-Sampling Loss

For one positive target \(t\) and \(K\) negative samples \(n_1,\ldots,n_K\), the loss is\[ \mathcal{L}_{\text{NS}} = -\log\sigma(u_t^\top v_c) – \sum_{k=1}^{K} \log\sigma(-u_{n_k}^\top v_c). \]

Minimizing this loss encourages\[ u_t^\top v_c \]

to increase for the positive pair and\[ u_{n_k}^\top v_c \]

to decrease for each negative pair.

The equivalent maximization objective is\[ \log\sigma(u_t^\top v_c) + \sum_{k=1}^{K} \log\sigma(-u_{n_k}^\top v_c). \]

The two forms differ only by a negative sign.

Why Training Is Faster

A full softmax touches all output vectors:\[ u_1,u_2,\ldots,u_{|\mathcal{V}|}. \]

Negative sampling touches only:

The center vector \(v_c\)
The positive output vector \(u_t\)
The \(K\) negative output vectors

The approximate cost changes from\[ O(|\mathcal{V}|d) \]

to\[ O((K+1)d). \]

When\[ K\ll|\mathcal{V}|, \]

the reduction is enormous.

For example, with a vocabulary of one million words and \(K=10\), each pair updates roughly 11 target-side vectors instead of one million.

Viewing the Model as Many Binary Classifiers

Conceptually, imagine one binary classifier for every vocabulary word.

Given center word \(c\), the classifier associated with target \(t\) estimates\[ P(y=1\mid c,t). \]

A full update across all classifiers would still be expensive. Negative sampling updates only:

The classifier for the observed target
The classifiers for \(K\) sampled noise words

This interpretation explains both the efficiency and the name of the method.

Gradient of the Pair Score

Let\[ s=u^\top v. \]

For a labeled pair with binary cross-entropy loss, the derivative with respect to the score is\[ \frac{\partial\ell}{\partial s} = \sigma(s)-y. \]

Therefore,\[ \frac{\partial\ell}{\partial v} = (\sigma(s)-y)u, \]

and\[ \frac{\partial\ell}{\partial u} = (\sigma(s)-y)v. \]

For a positive pair, \(y=1\), so gradient descent tends to increase the dot product.

For a negative pair, \(y=0\), so gradient descent tends to decrease it.

Input and Output Embeddings

Negative sampling learns two vectors for each vocabulary word.

Input embedding

\[ v_w \]

is used when \(w\) acts as the center word.

Output embedding

\[ u_w \]

is used when \(w\) acts as the candidate nearby word.

These vectors are not constrained to be equal.

After training, downstream systems may use:\[ e_w=v_w, \]\[ e_w=u_w, \]

or a combination such as\[ e_w=v_w+u_w. \]

The input vectors are a common default, but the most useful choice depends on the evaluation task.

Choosing the Number of Negative Samples

The hyperparameter \(K\) controls the number of negative words per positive pair.

A larger \(K\):

Provides a stronger contrastive signal
Increases computation
May improve representations on smaller corpora
Produces more negative updates per positive pair

A smaller \(K\):

Trains faster
May be sufficient for very large corpora
Reduces the variety of negatives seen per update

Historically, values around 5–20 have often been used, but there is no universal optimum. Appropriate values depend on:

Corpus size
Vocabulary size
Embedding dimension
Batch size
Noise distribution
Available computation
Downstream evaluation

Choosing the Noise Distribution

Negative words must be drawn from a probability distribution \(P_n(w)\).

Two simple choices create problems.

Empirical unigram distribution

Sampling according to raw frequency gives\[ P_n(w) = \frac{f(w)} {\sum_j f(w_j)}. \]

This produces too many extremely common words such as “the,” “of,” and “and.”

Uniform distribution

Uniform sampling gives\[ P_n(w) = \frac{1}{|\mathcal{V}|}. \]

This overrepresents rare vocabulary items relative to their actual occurrence and may produce too many uninformative negatives.

The Three-Quarter-Power Distribution

A widely used compromise is\[ P_n(w) = \frac{ f(w)^{3/4} }{ \sum_j f(w_j)^{3/4} }. \]

Because the exponent is less than 1, it flattens the empirical distribution.

For two words with frequencies \(f_1>f_2\),\[ \frac{f_1^{3/4}}{f_2^{3/4}} < \frac{f_1}{f_2}. \]

Thus:

Frequent words remain more likely than rare words.
Their dominance is reduced.
Rare words receive more exposure than under raw-frequency sampling.

The exponent \(3/4\) is an empirical heuristic rather than a universal theoretical constant, but it has worked well in many settings.

Negative Sampling Is Not Full Softmax

Negative sampling changes the objective. It does not approximate the full-softmax denominator exactly in the ordinary implementation.

The learned sigmoid score\[ \sigma(u_t^\top v_c) \]

estimates whether a pair resembles observed data rather than directly producing\[ P(t\mid c) \]

as a normalized vocabulary distribution.

Therefore:

The scores do not sum to 1 across vocabulary words.
They are not automatically calibrated next-word probabilities.
The method is excellent for learning embeddings.
It is not a drop-in probability model when exact normalized likelihood is required.

Negative sampling is designed primarily for efficient representation learning, not for producing a complete probabilistic language model.

Relationship to Noise-Contrastive Learning

Negative sampling belongs to a broader family of contrastive methods. The model learns by distinguishing observed data from artificially generated noise.

The core pattern is:

Identify an observed positive relationship.
Generate alternative negative relationships.
Increase the positive score.
Decrease the negative scores.

This basic principle appears in many modern representation-learning methods, even when the precise objectives and sampling procedures differ.

Negative sampling should nevertheless not be treated as identical to every noise-contrastive objective. Some related methods include explicit corrections for the noise distribution or aim to recover normalized model probabilities, while the standard Word2Vec objective does not.

Efficient Batched Computation

Suppose:

Batch size is \(B\)
Embedding dimension is \(d\)
Number of negatives is \(K\)

Then the tensors may have shapes:\[ V_c\in\mathbb{R}^{B\times d}, \]\[ U_t\in\mathbb{R}^{B\times d}, \]\[ U_n\in\mathbb{R}^{B\times K\times d}. \]

Positive scores are\[ s^+ = \sum_{j=1}^{d} V_{c,j}U_{t,j}. \]

Negative scores can be computed with batched matrix multiplication.

import torch
import torch.nn.functional as F

def negative_sampling_loss(
    center_vectors,
    positive_vectors,
    negative_vectors
):
    positive_scores = torch.sum(
        center_vectors * positive_vectors,
        dim=1
    )

    negative_scores = torch.bmm(
        negative_vectors,
        center_vectors.unsqueeze(2)
    ).squeeze(2)

    positive_term = F.logsigmoid(
        positive_scores
    )

    negative_term = F.logsigmoid(
        -negative_scores
    ).sum(dim=1)

    return -(positive_term + negative_term).mean()

import torch
import torch.nn.functional as F

def negative_sampling_loss(
    center_vectors,
    positive_vectors,
    negative_vectors
):
    positive_scores = torch.sum(
        center_vectors * positive_vectors,
        dim=1
    )

    negative_scores = torch.bmm(
        negative_vectors,
        center_vectors.unsqueeze(2)
    ).squeeze(2)

    positive_term = F.logsigmoid(
        positive_scores
    )

    negative_term = F.logsigmoid(
        -negative_scores
    ).sum(dim=1)

    return -(positive_term + negative_term).mean()

This implementation avoids constructing a vocabulary-sized output tensor.

Numerical Stability

Directly calculating\[ \log\sigma(s) \]

or\[ \log(1-\sigma(s)) \]

can be numerically unstable for large positive or negative scores.

Stable implementations use functions equivalent to:\[ \log\sigma(s) = -\operatorname{softplus}(-s), \]

and\[ \log\sigma(-s) = -\operatorname{softplus}(s). \]

Library functions such as logsigmoid should be preferred over manually applying a sigmoid followed by a logarithm.

Duplicate Negative Samples

Sampling with replacement can produce the same negative word more than once.

This is not necessarily incorrect. Repeated negatives simply give that word greater weight in the current update.

However, implementations should be aware of duplicates when:

Aggregating sparse gradients
Comparing results across different samplers
Attempting to enforce unique negative samples
Measuring the effective number of negatives

Sampling without replacement is possible but can be more expensive and is not required by the standard formulation.

Interaction with Frequent-Word Subsampling

Negative sampling controls how noise words are selected. A separate preprocessing technique controls how frequently observed corpus tokens become positive examples.

Frequent-word subsampling may discard some occurrences of high-frequency words before positive pairs are generated.

These two mechanisms should not be confused:

Mechanism	Affects	Purpose
Frequent-word subsampling	Observed corpus tokens	Prevent common words from dominating positive pairs
Negative-sample distribution	Artificial noise words	Choose informative and efficient negative comparisons

Both can be used simultaneously.

Pretrained Embeddings

Training high-quality embeddings may require:

A large corpus
Careful tokenization
Frequency filtering
Efficient sampling
Substantial computation
Evaluation for domain fit and bias

Pretrained embeddings can provide a useful starting point when their:

Vocabulary covers the application
Source domain is reasonably compatible
License permits the intended use
Preprocessing conventions are understood
Bias and quality characteristics have been evaluated

They can be frozen or fine-tuned within a downstream model.

Common Mistakes

Treating every random pair as semantically impossible

A negative sample means the pair was generated from noise for that update. It does not prove the words can never occur together.

Using the positive target as a negative without awareness

Some samplers permit collisions; others explicitly reject the current positive target. The implementation choice should be understood.

Sampling uniformly without evaluating the effect

Uniform negatives may overemphasize rare words and produce less useful training signals.

Calling sigmoid scores normalized word probabilities

The independent binary scores do not form a distribution over the vocabulary.

Using only one embedding table accidentally

Center and target roles normally have separate vectors.

Computing sigmoid and logarithm separately

This can cause numerical underflow. Stable combined functions are safer.

Assuming more negatives are always better

Increasing \(K\) raises computational cost and may provide diminishing returns.

Key Takeaway

Negative sampling makes Skip-Gram training efficient by replacing a vocabulary-wide softmax with \(K+1\) binary comparisons:\[ \mathcal{L}_{\text{NS}} = -\log\sigma(u_t^\top v_c) – \sum_{k=1}^{K} \log\sigma(-u_{n_k}^\top v_c). \]

The observed center–target pair is treated as positive, while randomly sampled words create negative pairs. The model raises the dot product of genuine nearby words and lowers the dot products of sampled noise pairs.

This reduces the per-example cost from dependence on the full vocabulary to dependence on a small number of samples. A frequency distribution raised to the \(3/4\) power is commonly used to balance frequent and rare negative words. The resulting model learns useful embeddings efficiently, although its sigmoid scores are not normalized next-word probabilities.