BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies Shihao Ji

Swaminathan Vishwanathan, Nadathur Satish, Michael Anderson, Pradeep DubeyICLR 2016 · arXiv · OpenReview

Training state-of-the-art language models used to be a luxury reserved for those with massive GPU clusters or sprawling CPU farms. The primary bottleneck? The "softmax layer." When your vocabulary hits a million words, calculating the probability of the next word at every single step becomes a computational nightmare.

In their ICLR 2016 paper, researchers from Intel and UC Santa Cruz introduced BlackOut, an approximation algorithm that shatters this bottleneck. By rethinking how we sample and train the output layer, they managed to train massive Recurrent Neural Network Language Models (RNNLMs) on a single CPU machine in just a few days, all while achieving record-breaking accuracy.

TL;DR

BlackOut is a sampling-based approximation algorithm that enables efficient training of RNNs with million-word vocabularies. By using a discriminative loss and a clever weighted sampling strategy, it achieves state-of-the-art perplexity on massive datasets using only a single multi-core CPU machine, outperforming more resource-intensive methods.

What Problem Does This Paper Address?

Unrolled Recurrent Neural Network Language Model architecture.

The core challenge in modern language modeling is the Large Vocabulary Softmax. In a standard RNNLM, the output layer must produce a probability distribution over the entire vocabulary ($V$). If $V$ is 1 million, the computation complexity is $O(Vh)$, where $h$ is the hidden layer size.

Existing solutions like Importance Sampling (IS) or Noise Contrastive Estimation (NCE) try to approximate this by only looking at a small subset of words. However, these often suffer from instability, high variance, or require complex hyperparameter tuning (like the "partition function" in NCE). The authors sought a method that was computationally cheap, numerically stable, and acted as a regularizer to prevent overfitting.

Methods

The authors propose BlackOut, which can be thought of as "DropOut for the output layer."

  1. Discriminative Loss: Instead of trying to calculate the full probability distribution (Maximum Likelihood), BlackOut treats training as a classification task: "Is this the correct word, or one of these $K$ 'noise' words?"
  2. Weighted Sampling: For every training step, they sample a small set of $K$ negative words (non-target words). Crucially, they use a power-raised unigram distribution ($Q(w) \propto p_{uni}^\alpha(w)$) for sampling. Setting $\alpha \approx 0.4$ provides a "sweet spot" between sampling popular words and sampling all words equally.
  3. Weighted Softmax: They introduce a weighting term ($q_j$) into the softmax calculation based on the sampling proposal. This balances the contributions of the target word and the noisy samples, leading to much better stability than standard NCE.
  4. Approximated RMSProp: To further speed up training, they developed a sparse version of the RMSProp optimizer. Since only a tiny fraction of the weights (the target word and $K$ samples) are updated in each batch, this "subnet update" strategy drastically reduces memory access and computation.

Datasets

The authors evaluated BlackOut on two main fronts:

  • Small Dataset (RNNLM Toolkit): Used for baseline comparisons against exact softmax and NCE. It contains ~71k words and a 3,720-word vocabulary.
  • One Billion Word Benchmark: A massive, standard dataset for large-scale language modeling. The authors tested configurations with a 64K vocabulary and a massive 1M word vocabulary.

Key Insights and Ideas

Test perplexity vs. number of noise samples (K).
  • The Regularization Effect: Surprisingly, BlackOut often achieves lower perplexity (better accuracy) than the "exact" softmax. Because it only sees a subset of the output layer at each step, it prevents the model from over-relying on specific output weights, acting much like DropOut.
  • Stability is King: Unlike NCE, which can be numerically unstable and sensitive to the "partition function" constant $Z$, BlackOut’s weighted softmax allows for the use of the "log-sum-exp trick," making it much more robust during training.
  • CPU Optimization: The paper proves that with the right algorithmic shortcuts (like sparse updates and optimized BLAS libraries), high-end CPUs can be competitive with GPUs for training massive, memory-heavy models.

Key Results

  • New State-of-the-Art: On the One Billion Word Benchmark (64K vocab), BlackOut achieved a perplexity of 42.0, outperforming previous published results.
  • Efficiency: They trained a model with 2.2 billion parameters on a single 28-core Intel Xeon machine.
  • Speedup: BlackOut provides a speedup of roughly $V/K$ at the output layer. In practice, they used $K \approx V/200$, meaning they only needed to compute 0.5% of the output layer during training.
  • Scalability: While other methods required clusters of 32 CPU machines or high-end GPUs to handle million-word vocabularies, BlackOut handled a 1M vocabulary on a single box in about 7 days.

Limitations and Future Work

  • Evaluation Bottleneck: While BlackOut makes training fast, evaluation (calculating the final perplexity) still requires a full softmax pass over the entire vocabulary, which remains slow.
  • RNN Focus: The paper focuses on RNNLMs. While the authors note BlackOut can be used for any large softmax layer (like in CNNs or Transformers), those specific architectures weren't tested here.
  • Future Directions: The authors suggest exploring different proposal distributions ($Q(w)$) and implementing a multi-machine distributed version to scale even further.

Summary updated

BibTeX
@inproceedings{vishwanathan2016blackout,
  author = {Swaminathan Vishwanathan and Nadathur Satish and Michael Anderson and Pradeep Dubey},
  title = {{BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies Shihao Ji}},
  booktitle = {International Conference on Learning Representations},
  year = {2016},
  url = {http://arxiv.org/abs/1511.06909},
}
Figure