A fast and simple algorithm for training neural probabilistic language models

Andriy Mnih, Yee Whye Teh

Introduction

Training neural language models historically took weeks due to the "softmax bottleneck"—the computational burden of calculating a sum over the entire vocabulary for every single word prediction. This paper introduces Noise-Contrastive Estimation (NCE) to the field, a method that swaps expensive probability calculations for a simple binary classification task. By distinguishing real data from noise, NCE speeds up training by over 10x without sacrificing accuracy.

The Softmax Bottleneck

In 2012, Neural Probabilistic Language Models (NPLMs) were already known to outperform traditional $n$-gram models, but they suffered from a massive practical flaw: agonizingly slow training times.

The culprit is the normalization constant (the denominator in the softmax function). To calculate the probability of a single target word, the model must compute scores for every word in its vocabulary (often 50,000+ words) just to ensure the total probability distribution sums to one. Consequently, training time scales linearly with vocabulary size. While techniques like importance sampling existed to approximate this, they were notoriously unstable and difficult to tune.

Noise-Contrastive Estimation (NCE)

To bypass the softmax bottleneck, the authors propose using Noise-Contrastive Estimation. Instead of directly modeling the probability distribution of the next word, NCE re-frames the problem as binary classification:

  • The Goal: Train a classifier to distinguish between "real" words (drawn from the actual training data) and "noise" words (randomly sampled from a known distribution, such as a unigram model).
  • The Math: By learning to differentiate between data and noise, the model implicitly learns the underlying structure of the language.
  • The Shortcut: Crucially, NCE allows the model to treat the normalization constant as a learnable parameter. The authors discovered they could simply fix the normalization constant to 1, drastically simplifying gradient calculations.

The researchers evaluated this using a Log-Bilinear (LBL) model, a straightforward but effective neural architecture that predicts a word's vector representation based on a linear combination of the preceding words' vectors.

Key Insights

  • Stability over Importance Sampling: Unlike importance sampling, where weights can become arbitrarily large and cause the model to diverge, NCE weights are naturally bounded between 0 and 1. This makes NCE significantly more robust.
  • The $Z=1$ Trick: Surprisingly, the model doesn't actually need to learn a normalization constant ($Z$) for each context. Setting $Z=1$ (or the log-constant $c=0$) worked perfectly. The high dimensionality of neural models allows them to naturally find "self-normalizing" solutions.
  • Noise Quality Matters: Using a unigram distribution (sampling noise based on corpus frequency) performed significantly better than a uniform distribution (sampling all words equally).
  • Bidirectional Context: For sentence completion tasks, looking at words both before and after the blank (bidirectional context) significantly improved performance over looking only at preceding words.

Experimental Results

The paper evaluates the algorithm on two main benchmarks: the Penn Treebank (PTB) and the Microsoft Research (MSR) Sentence Completion Challenge.

Speed and Efficiency on Penn Treebank

On the PTB corpus (approx. 1M words, 10K vocabulary), NCE was compared directly against exact Maximum Likelihood (ML) training.

Comparison of training time and perplexity between Maximum Likelihood (ML) and NCE.

As shown above, NCE was 14 times faster than exact ML training (1.5 hours vs. 21 hours). Furthermore, using just 25 noise samples per real word was sufficient to match the perplexity of the computationally expensive exact training.

State-of-the-Art on MSR Sentence Completion

The MSR challenge is a much larger task involving 522 works from Project Gutenberg (approx. 47M words) and an 80K-word vocabulary. It requires the model to choose the correct word to fill a blank, testing its contextual understanding.

Performance of various models on the MSR Sentence Completion Challenge.

On this benchmark, the LBL model trained with NCE achieved 54.7% accuracy, setting a new state-of-the-art record at the time. It significantly outperformed both traditional $n$-gram models and complex Latent Semantic Analysis (LSA) approaches.

Limitations and Future Work

  • Noise Distribution: While unigram noise proved effective, the authors suggest that context-dependent noise distributions might lead to even faster training, as the "fake" samples would be harder to distinguish from real data.
  • Optimization: The authors noted their NCE implementation was less optimized than standard BLAS-based matrix routines used for ML, implying even greater speedups are possible with better engineering.
  • Generalization: While focused on the LBL model, the authors position NCE as a prime candidate for any probabilistic classifier with a massive number of classes.

Summary updated

Abstract

In spite of their superior performance, neural probabilistic language models (NPLMs) remain far less widely used than n-gram models due to their notoriously long training times, which are measured in weeks even for moderately-sized datasets. Training NPLMs is computationally expensive because they are explicitly normalized, which leads to having to consider all words in the vocabulary when computing the log-likelihood gradients. We propose a fast and simple algorithm for training NPLMs based on noise-contrastive estimation, a newly introduced procedure for estimating unnormalized continuous distributions. We investigate the behaviour of the algorithm on the Penn Treebank corpus and show that it reduces the training times by more than an order of magnitude without affecting the quality of the resulting models. The algorithm is also more efficient and much more stable than importance sampling because it requires far fewer noise samples to perform well. We demonstrate the scalability of the proposed approach by training several neural language models on a 47M-word corpus with a 80K-word vocabulary, obtaining state-of-the-art results on the Microsoft Research Sentence Completion Challenge dataset.
BibTeX
@inproceedings{mnih2012fast,
  author = {Andriy Mnih and Yee Whye Teh},
  title = {{A fast and simple algorithm for training neural probabilistic language models}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  url = {https://openreview.net/forum?id=B1-amsWubr},
}
Figure