Elamur Research
☰
home / papers / 2013 / Scalable Modified Kneser-Ney Language Model Estimation

Scalable Modified Kneser-Ney Language Model Estimation

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P13-2121.pdf

Summary

Modified Kneser-Ney smoothing yields low-perplexity n-gram language models, but standard toolkits either need very large amounts of memory (SRILM, IRSTLM) or large clusters (Google's MapReduce approach). The authors propose an estimation algorithm that runs on a single machine with a user-set RAM budget and uses disk for the rest. It is organized as streaming passes: counting, adjusting counts, normalization (with paired sum and divide threads per order), and interpolation merged with backoff joining. The passes are linked by three disk-based merge sorts that use pipelining and optimal arity. Exact integer arithmetic also avoids the numerical-precision problems seen in SRILM. On ClueWeb09, cleaned down to 126 billion English tokens, they trained an unpruned 5-gram model in under three days on one server. Adding it to strong WMT 2013 systems consistently raised BLEU. On small data the method is also much cheaper than SRILM and IRSTLM. The work shows that full Kneser-Ney smoothing can scale without simplifications such as Stupid Backoff. The code is released in KenLM.

Key points

  • Scaling to 126 billion tokens: The ClueWeb09 model (about 59.8 billion unique 5-grams) used 123 GB of RAM on a 140 GB machine. It took 2.8 days of wall time and 5.4 CPU days.
  • Translation gains: After 10-bit quantization and compression, the model occupied 643 GB. Used as an extra feature in Edinburgh's Moses systems, it gave +0.8 BLEU over the constrained baseline (7 billion tokens) for Czech-, French-, and Spanish-English at WMT 2013.
  • Speed and memory on small data: On 302 million tokens, it used 7.7% of SRILM's RAM, 14.0% of its wall time, and 25.4% of its CPU time. Against IRSTLM, it used 16.6% of the RAM, 9.0% of the wall time, and 16.4% of the CPU time.
  • Standard output: Unlike MSRLM, it performs full normalization and interpolation at estimation time, so it produces standard ARPA output.
  • Availability: The code is open source (LGPL) as part of KenLM.

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

Fields: Natural language processing

Cited by

278 papers of our library cite it (of the 140673 whose bibliographies we read); 18 of them have a page here, 260 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{heafield2013scalable,
  title = {{Scalable Modified Kneser-Ney Language Model Estimation}},
  author = {Heafield, Kenneth and Pouzyrevsky, Ivan and Clark, Jonathan H. and Koehn, Philipp},
  booktitle = {Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2013},
  url = {https://aclanthology.org/P13-2121/}
}

References

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

  1. James M. Abello and Jeffrey Scott Vitter, editors. 1999. External memory algorithms. American Mathematical Society, Boston, MA, USA. find
  2. Raja Appuswamy, Christos Gkantsidis, Dushyanth Narayanan, Orion Hodson, and Antony Rowstron. 2013. Nobody ever got fired for buying a cluster. Technical Report MSR-TR-2013-2, Microsoft Research. find
  3. Dina Bitton and David J DeWitt. 1983. Duplicate record elimination in large data files. ACM Transactions on database systems (TODS), 8(2):255–265. find
  4. Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, and Jeffrey Dean. 2007. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Language Learning, pages 858–867, June. find our card
  5. Chris Callison-Burch, Philipp Koehn, Christof Monz, Matt Post, Radu Soricut, and Lucia Specia. 2012. Findings of the 2012 workshop on statistical machine translation. In Proceedings of the Seventh Workshop on Statistical Machine Translation, pages 10–51, Montréal, Canada, June. Association for Comp… find our card
  6. Ciprian Chelba and Johan Schalkwyk, 2013. Empirical Exploration of Language Modeling for the google.com Query Stream as Applied to Mobile Voice Search, pages 197–229. Springer, New York. find
  7. Stanley Chen and Joshua Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University, August. find
  8. Colin Cherry and George Foster. 2012. Batch tuning strategies for statistical machine translation. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 427–436. Association for Computational Linguisti… find
  9. Gordon V Cormack, Mark D Smucker, and Charles LA Clarke. 2011. Efficient and effective spam filtering and re-ranking for large web datasets. Information retrieval, 14(5):441–465. find
  10. Jeffrey Dean and Sanjay Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In OSDI’04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, USA, 12. find
  11. Roman Dementiev, Lutz Kettner, and Peter Sanders. 2008. STXXL: standard template library for XXL data sets. Software: Practice and Experience, 38(6):589–637. find
  12. Nadir Durrani, Barry Haddow, Kenneth Heafield, and Philipp Koehn. 2013. Edinburgh’s machine translation systems for European language pairs. In Proceedings of the ACL 2013 Eighth Workshop on Statistical Machine Translation, Sofia, Bulgaria, August. find
  13. Marcello Federico, Nicola Bertoldi, and Mauro Cettolo. 2008. IRSTLM: an open source toolkit for handling large scale language models. In Proceedings of Interspeech, Brisbane, Australia. find
  14. David Guthrie and Mark Hepple. 2010. Storing the web in memory: Space efficient language models with constant time retrieval. In Proceedings of EMNLP 2010, Los Angeles, CA. find
  15. Kenneth Heafield, Philipp Koehn, and Alon Lavie. 2012. Language model rest costs and space-efficient storage. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, Jeju Island, Korea. find
  16. Kenneth Heafield. 2011. KenLM: Faster and smaller language model queries. In Proceedings of the Sixth Workshop on Statistical Machine Translation, Edinburgh, UK, July. Association for Computational Linguistics. find our card
  17. Mark Hopkins and Jonathan May. 2011. Tuning as ranking. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1352–1362, Edinburgh, Scotland, July. find
  18. Slava Katz. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-35(3):400– 401, March. find
  19. Reinhard Kneser and Hermann Ney. 1995. Improved backing-off for m-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 181–184. find
  20. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Ann… find
  21. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Proceedings of MT Summit. find
  22. Patrick Nguyen, Jianfeng Gao, and Milind Mahajan. 2007. MSRLM: a scalable language modeling toolkit. Technical Report MSR-TR-2007-144, Microsoft Research. find
  23. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: A method for automatic evalution of machine translation. In Proceedings 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, PA, July. find
  24. Andreas Stolcke. 2002. SRILM - an extensible language modeling toolkit. In Proceedings of the Seventh International Conference on Spoken Language Processing, pages 901–904. find
  25. David Talbot and Miles Osborne. 2007. Randomised language modelling for statistical machine translation. In Proceedings of ACL, pages 512–519, Prague, Czech Republic. find
  26. Edward Whittaker and Bhiksha Raj. 2001. Quantization-based language model compression. In Proceedings of Eurospeech, pages 33–36, Aalborg, Denmark, December. find