Elamur Research⌕
☰
home / papers / 2016 / Efficient softmax approximation for GPUs

Efficient softmax approximation for GPUs

Paper · 2016 · Edouard Grave, Armand Joulin, Moustapha Cisse et al.

Summary

Neural language models with huge vocabularies spend most of their compute on the output softmax, because its cost grows with the number of words. Grave et al. (Facebook AI Research) propose adaptive softmax, an approximate hierarchical model designed for GPUs. It uses the skewed word frequency distribution to group words into clusters, and the clustering is chosen to minimize expected computation time. The cost model is based on measured GPU timings of matrix-matrix products, which do not scale linearly with matrix dimensions, rather than on a naive linear cost. Frequent words live directly in the top level of the hierarchy. Rarer clusters get cheaper, lower-capacity projections.

The authors test single-layer LSTMs on Text8, Europarl (many languages) and One Billion Word. They compare against the full softmax, importance sampling, hierarchical softmax (frequency and Brown-cluster binning) and D-softmax. Adaptive softmax gives roughly 2× to 10× speed-ups and stays close to full-softmax perplexity. On the largest corpus it loses essentially nothing for the same amount of training data. This makes large-vocabulary language modeling feasible on modest hardware. The code is public.

Key points

  • Reported speed-ups over the standard softmax range from 2× to 10×. The code is released at github.com/facebookresearch/adaptive-softmax.
  • On One Billion Word (about 0.8B tokens, a vocabulary close to 800k), test perplexity after 5 epochs is 43.9 for LSTM-2048 and 39.8 for a 2-layer LSTM-2048. The Jozefowicz et al. LSTM-2048-512 reached 43.7.
  • Europarl results after 5 epochs:
    • German (k=143k): perplexity 40 in 110 minutes, versus 42 in 802 minutes for the full softmax.
    • Danish (k=128k): 35 in 105 minutes, versus 37 in 713 minutes.
  • On Text8 (44k vocabulary), adaptive softmax is the fastest method and trails the full softmax by about 3 perplexity points. The improved D-softmax [*] matches its accuracy but runs about 1.8× slower.
  • Training setup:
    • one-layer LSTM, with d=512 on Text8/Europarl and d=2048 on One Billion Word;
    • 256-dimensional input embeddings;
    • Adagrad with step size 0.1, gradient norm clipping at 1;
    • 20-step BPTT unrolling, batch size 128;
    • a single Maxwell GPU.

Interesting ideas

  • I1. Optimize for measured hardware cost. The clusters are built to minimize expected compute time under a cost model fitted from real GPU benchmarks, not to minimize FLOPs or tree depth. Any efficiency-driven design, such as bucketing or sharding, can benefit from profiling the target hardware first.
  • I2. Keep frequent words in the root. Placing the most common words directly in the top level, instead of pushing every word down to a leaf, avoids most of the accuracy loss seen in earlier complexity-driven hierarchies. This could help any classifier over a long-tailed label set, such as product categories, place names or rare morphological forms.
  • I3. Scale capacity with frequency. Rare-word clusters see the full hidden state through smaller projection matrices, so they get less capacity and cost less. This is a cheap way to save compute and memory on rarely used outputs.
  • I4. Report quality against wall-clock time. Perplexity is shown as a function of both training time and epochs, which separates "faster per step" from "better per unit of data." This gives a fairer way to compare approximation methods.
  • I5. Test across many languages. Europarl provides languages with vocabularies from roughly 44k to 250k, which shows how a method behaves as vocabulary size grows. This setup would suit morphologically rich languages like Ukrainian.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksHardware and Architecture · 38 works

🧭 Topics 1Research subjects and languages the work is about.GPU & parallel computing · 7 works

Cite

Cite as Edouard Grave, Armand Joulin, Moustapha Cisse, David Grangier and Herve Jegou. 2016. Efficient softmax approximation for GPUs. arXiv:1609.04309.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1609.04309 · arXiv 1609.04309

@misc{grave2016efficient,
  title = {{Efficient softmax approximation for GPUs}},
  author = {Edouard Grave, Armand Joulin, Moustapha Cisse, David Grangier and Herve Jegou},
  year = {2016},
  doi = {10.48550/arxiv.1609.04309},
  eprint = {1609.04309},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1609.04309}
}

References

48 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Andreas, Jacob and Klein, Dan. When and why are log-linear models self-normalizing. In ACL, 2014. find
  2. Bahl, Lalit R, Jelinek, Frederick, and Mercer, Robert L. A maximum likelihood approach to continuous speech recognition. PAMI, 1983. find
  3. Bengio, Yoshua and Senécal, Jean-Sébastien. Adaptive importance sampling to accelerate training of a neural probabilistic language model. Neural Networks, 2008. find
  4. Bengio, Yoshua, Ducharme, Réjean, Vincent, Pascal, and Jauvin, Christian. A neural probabilistic language model. JMLR, 2003a.
  5. Bengio, Yoshua, Senécal, Jean-Sébastien, et al. Quick training of probabilistic neural nets by importance sampling. In AISTATS, 2003b. find
  6. Brown, Peter F, Desouza, Peter V, Mercer, Robert L, Pietra, Vincent J Della, and Lai, Jenifer C. Class-based n-gram models of natural language. Computational linguistics, 1992. find
  7. Chelba, Ciprian, Mikolov, Tomas, Schuster, Mike, Ge, Qi, Brants, Thorsten, Koehn, Phillipp, and Robinson, Tony. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv:1312.3005, 2013.
  8. Chen, Welin, Grangier, David, and Auli, Michael. Strategies for training large vocabulary neural language models. arXiv preprint arXiv:1512.04906, 2015. find
  9. Chung, Junyoung, Gulcehre, Caglar, Cho, KyungHyun, and Bengio, Yoshua. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014. find
  10. Devlin, Jacob, Zbib, Rabih, Huang, Zhongqiang, Lamar, Thomas, Schwartz, Richard M, and Makhoul, John. Fast and robust neural network joint models for statistical machine translation. In ACL, 2014.
  11. Duchi, John, Hazan, Elad, and Singer, Yoram. Adaptive subgradient methods for online learning and stochastic optimization. JMLR, 2011. find
  12. Elman, Jeffrey L. Finding structure in time. Cognitive science, 1990. find
  13. Goodman, Joshua. Classes for fast maximum entropy training. In ICASSP, 2001a. find
  14. Goodman, Joshua T. A bit of progress in language modeling. Computer Speech & Language, 2001b. find
  15. Graves, Alan, Mohamed, Abdel-rahman, and Hinton, Geoffrey. Speech recognition with deep recurrent neural networks. In ICASSP, 2013. find
  16. Gutmann, Michael and Hyvärinen, Aapo. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In International Conference on Artificial Intelligence and Statistics, 2010. find
  17. Hinton, Geoffrey, Deng, Li, Yu, Dong, Dahl, George E, Mohamed, Abdel-rahman, Jaitly, Navdeep, Senior, Andrew, Vanhoucke, Vincent, Nguyen, Patrick, Sainath, Tara N, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. Signal Processing Mag… find
  18. Hochreiter, Sepp and Schmidhuber, Jürgen. Long short-term memory. Neural computation, 1997. find
  19. Jean, Sebastien, Cho, Kyunghyun, Memisevic, Roland, and Bengio, Yoshua. On using very large target vocabulary for neural machine translation. 2015.
  20. Ji, Shihao, Vishwanathan, SVN, Satish, Nadathur, Anderson, Michael J, and Dubey, Pradeep. Blackout: Speeding up recurrent neural network language models with very large vocabularies. arXiv preprint arXiv:1511.06909, 2015. find
  21. Joulin, Armand, van der Maaten, Laurens, Jabri, Allan, and Vasilache, Nicolas. Learning visual features from large weakly supervised data. arXiv preprint arXiv:1511.02251, 2015. — [arXiv:1511.02251](https://arxiv.org/abs/1511.02251) find
  22. Jozefowicz, Rafal, Vinyals, Oriol, Schuster, Mike, Shazeer, Noam, and Wu, Yonghui. Exploring the limits of language modeling. arXiv preprint arXiv:1602.02410, 2016. find
  23. Katz, Slava M. Estimation of probabilities from sparse data for the language model component of a speech recognizer. ICASSP, 1987. find
  24. Kneser, Reinhard and Ney, Hermann. Improved backing-off for m-gram language modeling. In ICASSP, 1995. find
  25. Koehn, Philipp. Europarl: A parallel corpus for statistical machine translation. In MT summit, 2005. find
  26. Kuhn, Roland and De Mori, Renato. A cache-based natural language model for speech recognition. PAMI, 1990. find
  27. Le, Hai-Son, Oparin, Ilya, Allauzen, Alexandre, Gauvain, Jean-Luc, and Yvon, François. Structured output layer neural network language model. In ICASSP, 2011. find
  28. Le, Quoc V, Jaitly, Navdeep, and Hinton, Geoffrey E. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv:1504.00941, 2015. — [arXiv:1504.00941](https://arxiv.org/abs/1504.00941) find
  29. Mikolov, Tomas and Zweig, Geoffrey. Context dependent recurrent neural network language model. In SLT, 2012. find
  30. Mikolov, Tomas, Karafiát, Martin, Burget, Lukas, Cernockỳ, Jan, and Khudanpur, Sanjeev. Recurrent neural network based language model. In INTERSPEECH, 2010. find
  31. Mikolov, Tomas, Deoras, Anoop, Kombrink, Stefan, Burget, Lukas, and Cernockỳ, Jan. Empirical evaluation and combination of advanced language modeling techniques. In INTER-SPEECH, 2011a. find
  32. Mikolov, Tomáš, Deoras, Anoop, Povey, Daniel, Burget, Lukáš, and Černockỳ, Jan. Strategies for training large scale neural network language models. In ASRU, 2011b. find
  33. Mikolov, Tomáš, Kombrink, Stefan, Burget, Lukáš, Černockỳ, Jan Honza, and Khudanpur, Sanjeev. Extensions of recurrent neural network language model. In ICASSP, 2011c. find
  34. Mikolov, Tomas, Chen, Kai, Corrado, Greg, and Dean, Jeffrey. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781, 2013.
  35. Mikolov, Tomas, Joulin, Armand, Chopra, Sumit, Mathieu, Michael, and Ranzato, Marc’Aurelio. Learning longer memory in recurrent neural networks. arXiv preprint arXiv:1412.7753, 2014. — [arXiv:1412.7753](https://arxiv.org/abs/1412.7753) find
  36. Mnih, Andriy and Hinton, Geoffrey E. A scalable hierarchical distributed language model. In NIPS, 2009. find
  37. Mnih, Andriy and Teh, Yee Whye. A fast and simple algorithm for training neural probabilistic language models. arXiv preprint arXiv:1206.6426, 2012. find
  38. Morin, Frederic and Bengio, Yoshua. Hierarchical probabilistic neural network language model. In Aistats, 2005. find
  39. Schwenk, Holger. Continuous space language models. Computer Speech & Language, pp. 492–518, 2007. find
  40. Schwenk, Holger, Rousseau, Anthony, and Attik, Mohammed. Large, pruned or continuous space language models on a gpu for statistical machine translation. In NAACL-HLT Workshop, 2012. find
  41. Shazeer, Noam, Pelemans, Joris, and Chelba, Ciprian. Sparse non-negative matrix language modeling for skip-grams. In Proceedings of Interspeech, pp. 1428–1432, 2015. find
  42. Sutskever, Ilya, Vinyals, Oriol, and Le, Quoc V. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, 2014. find
  43. Vaswani, Ashish, Zhao, Yinggong, Fossum, Victoria, and Chiang, David. Decoding with large-scale neural language models improves translation. In EMNLP, 2013.
  44. Vincent, Pascal, de Brébisson, Alexandre, and Bouthillier, Xavier. Efficient exact gradient update for training deep networks with very large sparse targets. In NIPS, 2015. find
  45. Werbos, Paul J. Backpropagation through time: what it does and how to do it. 1990. find
  46. Williams, Ronald J and Peng, Jing. An efficient gradient-based algorithm for on-line training of recurrent network trajectories. Neural computation, 1990. find
  47. Zipf, George Kingsley. Human behavior and the principle of least effort. 1949. find
  48. Zweig, Geoffrey and Makarychev, Konstantin. Speed regularization and optimality in word classing. In ICASSP, 2013. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/grave-2016-efficient-softmax-approximation-gpus/