Noise-Contrastive Estimation

A neural language model over a 10,000-word vocabulary spends almost all of its training time on one line: the softmax denominator, a sum over every word for every prediction. In 2012 that cost made a small log-bilinear model on Penn Treebank take 21 hours to reach a test perplexity of 163.5. Replacing maximum likelihood with noise-contrastive estimation brought the same model to 163.1 in 1.5 hours (Mnih and Teh, 2012, A Fast and Simple Algorithm for Training Neural Probabilistic Language Models, arXiv:1206.6426). Nothing about the model changed. The estimator stopped asking for the partition function.

The partition function problem itself is covered in Energy-Based Models and the Partition Function, and Contrastive Divergence and the Negative Phase attacks it with short MCMC chains. NCE removes the sampler entirely and replaces it with a noise distribution you already know how to sample and evaluate.

Density estimation as logistic regression

Let data \(x\) come from \(p_d\) and draw \(k\) noise samples per data point from a fixed \(p_n\). Model the data with an unnormalised log-density plus a free scalar, \(\ln p_m(u;\theta) = -E_\alpha(u) + c\), where \(\theta = (\alpha, c)\) and \(c\) stands in for \(-\ln Z\). Define

which is the posterior probability that \(u\) came from the data given a data-to-noise ratio of \(1:k\). NCE maximises the logistic log-likelihood of labelling data as data and noise as noise:

Gutmann and Hyvärinen, using equal numbers of data and noise samples, proved that the nonparametric optimum is \(\ln p_m = \ln p_d\) whenever \(p_n\) is non-zero wherever \(p_d\) is, and that the parametric estimator is consistent, with \(c\) converging to the true log-normaliser (Gutmann and Hyvärinen, 2010, Noise-contrastive estimation: A new estimation principle for unnormalized statistical models, AISTATS). No constraint forces the density to integrate to one; the classification objective makes it do so at the optimum. In their experiments NCE reached a given precision at least three times faster than contrastive divergence.

The cost of a 25-sample softmax

Mnih and Teh give the per-update speedup as \((n_c d + V)/(n_c d + k)\) for context size \(n_c\), feature dimension \(d\) and vocabulary \(V\). With \(n_c = 2\), \(d = 100\), \(V = 10{,}000\) and \(k = 25\), that is \(10{,}200 / 225 \approx 45\times\). The measured wall-clock gain was 14 times, since other parts of the update do not shrink.

Their second finding was more surprising. Learning a separate \(c\) for every context worked but did not scale, so they fixed every normaliser at \(Z = 1\) and let the model absorb it. Perplexity did not suffer. Their explanation was that a model with that many free parameters easily satisfies the approximate normalisation the objective encourages.

Noise choice is the whole method

The noise distribution sets the difficulty of the classification. Gutmann and Hyvärinen show that if the noise equals the data distribution, the estimator's asymptotic covariance is twice the Cramér-Rao bound, so noise close to the data gives near-optimal efficiency. Noise far from the data gives a trivially separable problem that teaches little. On Penn Treebank with 25 samples, unigram noise reached perplexity 163.1 and uniform noise 195.1.

Negative sampling and InfoNCE

Word2vec's negative sampling maximises \(\ln\sigma(s(w,c)) + \sum_{j=1}^{k}\ln\sigma(-s(w_j,c))\) with noise words drawn from the unigram distribution raised to the \(3/4\) power (Mikolov et al., 2013, Distributed Representations of Words and Phrases and their Compositionality, arXiv:1310.4546). Compare with NCE's logit \(s - \ln(k\,p_n(w))\): negative sampling drops the correction term, which equals NCE only if \(k\,p_n(w) = 1\) for every word. Dyer's note makes the consequence explicit: NCE is an asymptotically unbiased estimator of the language model, while negative sampling is a binary classifier that yields good embeddings but not calibrated probabilities (Dyer, 2014, Notes on Noise Contrastive Estimation and Negative Sampling, arXiv:1410.8251).

InfoNCE keeps the contrast but changes the question from "is this sample data or noise?" to "which of these \(N\) candidates is the real one?", a softmax over one positive and \(N-1\) negatives whose optimal score is proportional to the density ratio \(p(x \mid c)/p(x)\). That ranking form is what contrastive representation learning inherited. For conditional models, Ma and Collins showed the ranking variant gives consistent estimates under weaker assumptions than the binary classification variant (Ma and Collins, 2018, Noise Contrastive Estimation and Negative Sampling for Conditional Models: Consistency and Statistical Efficiency, arXiv:1809.01812).

When it breaks

Distant noise stops giving signal long before it looks wrong. Density-ratio estimation by classification fails when the two distributions differ sharply; Rhodes, Xu and Gutmann report failures once the KL divergence exceeds tens of nats (2020, Telescoping Density-Ratio Estimation, arXiv:2006.12204). Their remedy bridges the gap with a chain of intermediate distributions, which adds ratios to estimate.

Self-normalisation is a hope, not a guarantee. Fixing \(Z = 1\) worked on a heavily parameterised language model. A smaller model, or one queried on inputs unlike training, can drift away from normalisation, and anything consuming its scores as probabilities, perplexity included, is then wrong.

Negative sampling is not NCE with a shortcut. Using its scores as probabilities, or its trained model as a language model, reintroduces the bias the dropped \(\ln(k\,p_n)\) term was removing.

More noise samples help, at a price. Perplexity improved from 192.5 at \(k = 1\) to 159.1 at \(k = 100\) in Mnih and Teh's runs. Each extra sample costs a forward evaluation, and the asymptotic guarantee says nothing about the \(k\) you can afford.