Learning word embeddings efficiently with noise-contrastive estimation

Andriy Mnih, Koray KavukcuogluNeurIPS 2013 · OpenReview

Overview

This paper introduces a highly efficient method for training word embeddings by combining simple log-bilinear models with Noise-Contrastive Estimation (NCE). By reframing language modeling as a binary classification task—distinguishing real data from noise—the authors achieve state-of-the-art results on a single CPU core. Previously, these results required massive computing clusters and significantly more training data.

The Softmax Bottleneck

In 2013, the "gold standard" for word representations was shifting from sparse co-occurrence counts to dense, real-valued vectors (embeddings) learned by neural networks. However, these models faced a massive scaling wall known as the Softmax Bottleneck.

To predict the next word in a sentence, a standard neural language model must calculate a probability distribution over the entire vocabulary. If a vocabulary contains 100,000 words, every single training step requires computing an expensive normalization constant (the denominator of the softmax function) across all 100,000 words. Researchers initially tried to solve this using complex tree-structured models like Hierarchical Softmax, but these were difficult to implement and highly sensitive to the specific tree structure used.

The authors sought a method that was simpler to implement, faster to train, and capable of scaling to billion-word datasets without relying on a supercomputer.

Methods: Log-Bilinear Models and NCE

The authors propose using Log-Bilinear (LBL) models trained via Noise-Contrastive Estimation (NCE).

1. Log-Bilinear Models

Unlike traditional neural networks with complex hidden layers, LBL models perform linear prediction directly in the embedding space. The authors focus on two primary variants:

  • vLBL (Vector LBL): Predicts a target word based on the average of its context words (conceptually similar to the Continuous Bag-of-Words or CBOW model).
  • ivLBL (Inverse LBL): Predicts context words given a target word (conceptually similar to the Skip-gram model).

2. Noise-Contrastive Estimation (NCE)

NCE is the core innovation for scaling these models. Instead of calculating the probability of a word out of the entire vocabulary, NCE fundamentally changes the objective. For every real word in the training data, the model is shown $k$ "noise" words sampled from a random distribution.

The model's job is simply to perform binary classification: "Is this a real word from the text, or is it noise?" This approach makes training time independent of the vocabulary size and linear with respect to the embedding dimensionality, unlocking massive speedups.

Key Insights

  • The Power of Binary Classification: NCE proves that computing exact probabilities is not necessary to learn high-quality representations. Discriminating against noise is a sufficient proxy for learning the underlying semantic and syntactic structure of language.
  • Simplicity Wins: The authors found that "flat" models (without hidden layers) often performed as well as, or better than, more complex neural architectures.
  • Position Independence: Surprisingly, ignoring the specific order of context words (using position-independent weights) often led to better semantic representations. This likely forced the model to capture broader topical information rather than just local, rigid syntax.

Key Results

The models were evaluated on Word Analogy Tasks (Google and MSR datasets) and the MSR Sentence Completion Challenge, trained primarily on a 1.5 billion word English Wikipedia dump.

Speed and Accuracy: The NCE-based models were more than an order of magnitude faster than previous state-of-the-art methods. On the Google analogy task, their best models achieved results comparable to the massive models trained by Mikolov et al., despite using 4x less data and a fraction of the compute.

Comparison of model performance and training time.

As shown above, an ivLBL model trained in just over a day outperformed a Skip-gram model that used twice as much data and time. Furthermore, the method is so efficient that a single-core implementation could match the performance of models trained on 125-CPU clusters.

Sentence Completion: On the MSR Sentence Completion Challenge—a task requiring the model to select the most likely word to fill a gap in a sentence—their ivLBL model achieved 55.5% accuracy, surpassing the previous best single-model score of 54.7%.

Results on the MSR Sentence Completion Challenge.

Limitations and Future Work

While highly efficient, the proposed models still rely on a fixed-length context window, which may miss long-range dependencies in text. Additionally, like most models of that era, this approach assigns exactly one vector per word, failing to account for polysemy (words with multiple meanings, like "bank").

For future directions, the authors suggest exploring "mixture modeling" to learn multiple representations per word by clustering contexts before training. They also note that sharing parameters between context and target word embeddings could help improve estimations for rare words.

Summary updated

Abstract

Continuous-valued word embeddings learned by neural language models have recently been shown to capture semantic and syntactic information about words very well, setting performance records on several word similarity tasks. The best results are obtained by learning high-dimensional embeddings from very large quantities of data, which makes scalability of the training method a critical factor. We propose a simple and scalable new approach to learning word embeddings based on training log-bilinear models with noise-contrastive estimation. Our approach is simpler, faster, and produces better results than the current state-of-the art method of Mikolov et al. (2013a). We achieve results comparable to the best ones reported, which were obtained on a cluster, using four times less data and more than an order of magnitude less computing time. We also investigate several model types and find that the embeddings learned by the simpler models perform at least as well as those learned by the more complex ones.
BibTeX
@inproceedings{mnih2013learning,
  author = {Andriy Mnih and Koray Kavukcuoglu},
  title = {{Learning word embeddings efficiently with noise-contrastive estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=SJbYRdbdZS},
}
Figure