Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Negative Sampling › Noise Contrastive Estimation: The Theoretical Foundation

Michael BrenndoerferApril 4, 20255 min read

Language AI HandbookAll chapters

Part 4 of 67Word Embeddings

Chapter 21Negative Sampling › Noise Contrastive Estimation: The Theoretical Foundation

Reading section 7 of 15 · Noise Contrastive Estimation: The Theoretical Foundation · 5 minSection 7 of 15 · 5 min

Section 7 of 15 · 5 min read

Negative Sampling › Noise Contrastive Estimation: The Theoretical FoundationOne section · Sections in this chapter7 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

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.

Noise Contrastive Estimation (NCE)

NCE converts the problem of estimating a probability distribution into a binary classification problem: distinguish data samples from noise samples. Under certain conditions, the good classifier recovers the true data distribution up to a normalizing constant.

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:

P(D = 1 | w, c) = \frac{P_d(w | c)}{P_d(w | c) + k \cdot P_n(w)}

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:

P(D = 1 | w, c) = \frac{\exp(s(w, c))}{\exp(s(w, c)) + k \cdot P_n(w)}

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.

From NCE to Negative SamplingLink Copied

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.

In[20]:

Code

def nce_probability(score, noise_prob, k):
    """
    Compute NCE probability that a sample is from data (not noise).

    Args:
        score: Model's score s(w, c) for word pair
        noise_prob: P_n(w) for the sampled word
        k: Number of noise samples per data sample
    """
    exp_score = np.exp(score)
    return exp_score / (exp_score + k * noise_prob)


def neg_sampling_probability(score):
    """Compute negative sampling probability using sigmoid."""
    return sigmoid(score)


# Compare the two for various scores
scores = np.linspace(-4, 4, 100)
noise_prob = 0.1  # Chosen so k*noise_prob ~ 1 at s=0, making curves comparable
k_nce = 10

nce_probs = [nce_probability(s, noise_prob, k_nce) for s in scores]
ns_probs = [neg_sampling_probability(s) for s in scores]

Out[21]:

Visualization