Source-linked AI summary
A Fast and Simple Algorithm for Training Neural Probabilistic Language Models
Andriy Mnih, Yee Whye Teh
TL;DR
Neural probabilistic language models are powerful but slow to train because normalized likelihood gradients consider the full vocabulary. The paper applies noise-contrastive estimation to train them efficiently, achieving comparable model quality in less than one-tenth the time and state-of-the-art sentence-completion performance. The approach is also more stable than importance sampling, while context-dependent noise distributions remain an open direction.
Problem
Neural probabilistic language models are slow to train because computing normalized likelihood gradients requires considering the entire vocabulary.
Method
The paper trains neural language models with noise-contrastive estimation, an efficient alternative applicable to neural probabilistic and maximum-entropy language models.
Results
Less than one-tenth the training time produced models performing as well as maximum-likelihood models, while large-scale experiments achieved state-of-the-art performance on the Microsoft Research Sentence Completion Challenge dataset.
Takeaways & Limitations
Noise-contrastive estimation provides a stable, scalable training method for neural language models without dynamically adapting the number of samples or proposal distribution.
Takeaways & Limitations
The experiments used a unigram noise distribution; context-dependent noise distributions remain worth investigating for potentially faster training.
Abstract
from arXiv · showhide
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.
1. Introduction
Neural probabilistic language models outperform n-grams but are slow because normalized training considers the whole vocabulary. The paper proposes noise-contrastive estimation as a faster, more stable alternative to importance sampling.
- Motivation: Neural language models routinely outperform n-grams by learning smooth representations of context and target words.Words used similarly receive similar representations and probability values.
- Problem: Training is slow because computing a word probability or gradient requires considering the entire vocabulary.The computation scales with vocabulary size and word-feature dimensionality.
- Existing approaches: Reducing the neural vocabulary and backing off to n-grams accelerates computation but limits the neural model to frequent words.The remaining words are handled by an n-gram model.
- Existing approaches: Tree-structured vocabularies provide exponentially faster probability and gradient computation, but performance depends heavily on finding a good tree.Finding an effective tree is difficult.
- Proposed approach: Importance sampling preserves the model but can make learning unstable because its estimates have high variance.The paper proposes noise-contrastive estimation as a more stable training alternative.
- Proposed approach: Noise-contrastive estimation achieves performance comparable to maximum likelihood without dynamically adapting the sample count or proposal distribution.It uses sampling to approximate the gradients needed for learning.
2. Neural probabilistic language models
Neural probabilistic language models represent words and contexts with learned vectors and score their compatibility, but maximum-likelihood gradients require expensive vocabulary-wide computation. Importance sampling reduces this cost but can become unstable because its proposal distribution diverges from the model.
- Model representation: A neural language model represents each vocabulary word with a real-valued feature vector and learns features jointly with its other parameters.The scoring function uses feature vectors for context words and the next word.
- Log-bilinear model: The LBL model performs linear prediction in semantic word-feature space and is used as the paper’s simple experimental neural model.The proposed training method also applies to neural probabilistic and maximum-entropy language models.
- Log-bilinear model: LBL computes a predicted target representation by linearly combining context-word vectors with position-dependent weight matrices.Separate feature tables represent context and target words.
- Log-bilinear model: The model scores a candidate target by taking the dot product between its representation and the predicted context representation.A base-rate parameter models the target word’s popularity before the score is converted into a probability.
- Maximum likelihood learning: Maximum-likelihood gradient computation is expensive because it requires evaluating scores for every word in the vocabulary.This makes training slow for vocabularies containing tens of thousands of words.
- Importance sampling: Importance sampling approximates the model expectation using samples drawn from an easy-to-sample proposal distribution, often an n-gram model.Importance weights are computed from the unnormalized model distribution and require normalization by the vocabulary constant.
- Importance sampling: Importance sampling can become unstable because variance grows as the model distribution moves away from the proposal distribution.Variance control may require increasing the sample count or adapting the proposal during training.
3. Noise-contrastive estimation
Noise-contrastive estimation trains neural language models by replacing explicit normalization with binary discrimination between data and noise samples. The resulting updates can approach maximum-likelihood gradients while requiring substantially less computation than maximum-likelihood training.
- Noise-contrastive estimation: NCE reduces density estimation to binary classification between data samples and samples from a known noise distribution.The language-model formulation uses a context-dependent data distribution and, for simplicity, a context-independent unigram noise distribution.
- Noise-contrastive estimation: NCE avoids explicit normalization by treating the normalizing constant as a learned parameter of an unnormalized model.The parameters comprise the unnormalized distribution parameters θ0 and a context-specific parameter ch for the logarithm of the normalizing constant.
- Noise-contrastive estimation: As the ratio of noise samples to observations increases, the NCE gradient approaches the maximum-likelihood gradient.This establishes the connection between the sampled training objective and maximum-likelihood learning.
- Potential speedup: For a 2-word context, 100D feature vectors, and a 10K-word vocabulary, 25 noise samples yield an estimated 45-times speedup over an ML update.The comparison follows from evaluating k sampled words for NCE instead of all V vocabulary words for maximum likelihood.
- Potential speedup: Using diagonal context matrices reduces predicted-representation computation and raises the estimated speedup to a factor of 370 for the same model.The diagonal structure reduces the representation cost from quadratic to linear in the feature dimensionality.
4. Penn Treebank results
On Penn Treebank, noise-contrastive estimation matched maximum-likelihood model quality with substantially shorter training, while importance sampling was unstable.
- Training efficiency: 14 times faster: NCE matched the ML-trained model with 25 noise samples.NCE required about twice as many epochs to converge, and its implementation was less optimized than ML.
- Training efficiency: 25 noise samples were sufficient for NCE to match the maximum-likelihood model’s test perplexity.Increasing the number of noise samples improved model performance.
- Noise distribution: Unigram noise produced much better test perplexity than uniform noise at every tested sample count.The gap narrowed from almost 100 with one sample to under 15 with 100 samples.
- Noise distribution: Uniform noise remained stable even with a single noise sample despite its poorer test-set performance.This separates learning stability from the quality of the resulting model.
- Comparison with importance sampling: Importance sampling diverged in virtually all experiments, including runs with adaptive sample sizes and target effective sample sizes in the hundreds.The failures were attributed to extremely large importance weights when the model diverged from the unigram proposal.
5. Sentence Completion Challenge
The authors applied bidirectional and unidirectional LBL models to sentence completion, where larger contexts and feature vectors improved accuracy, culminating in a 54.7% record.
- Task and data: The challenge required selecting the correct missing word from five candidates across 1,040 sentences.The benchmark was designed for semantic models.
- Task and data: The models used a vocabulary of just under 80,000 words after lowercasing and replacing words occurring fewer than five times.Training data came from 522 Project Gutenberg works.
- Results: 54.7% accuracy: a 10-word-context LBL with 300D features set a new record on the MSR challenge.It outperformed the LSA model by a large margin.
- Results: LBL models performed considerably better than n-gram models on sentence completion despite having higher test perplexity.Even the LBL model with a two-word context outperformed every n-gram model.
- Results: More word features and larger contexts improved LBL performance in both accuracy and perplexity.The five-word-context LBL matched the best published result before the 10-word model surpassed it.
- Method: Bidirectional context conditioned on words following the target, making it suitable for filling a missing middle word.The scoring procedure also incorporates following words because their probabilities depend on the candidate word.
- Results: Bidirectional LBL models achieved lower test perplexity but were less effective for sentence completion than their unidirectional counterparts.The unidirectional models appeared to make better use of the available information under the scoring procedures.
6. Discussion
The paper concludes that NCE provides stable, efficient neural language-model training and scales to state-of-the-art sentence-completion performance, while identifying extensions for future study.
- Conclusion: Less than one-tenth the time: NCE produced models performing as well as maximum-likelihood-trained models.The authors characterize the learning algorithm as simple, efficient, and very stable.
- Conclusion: Large-scale training on Project Gutenberg texts achieved state-of-the-art performance on the Microsoft Research Sentence Completion Challenge.The result demonstrates scalability of the approach.
- Future directions: Context-dependent noise distributions may enable faster training by reducing the number of noise samples needed.The paper shows that a unigram noise distribution is already sufficient for efficient training.
- Future directions: Other estimators in the family containing NCE and importance sampling may also be relevant, although preliminary results did not outperform NCE.This comparison is explicitly preliminary.
- Future directions: NCE may apply beyond neural and maximum-entropy language models, particularly to probabilistic classifiers with many classes.The paper presents this as a candidate application rather than an established result.