Efficient Handling of N-gram Language Models for Statistical Machine Translation

Proceedings of the Second Workshop on Statistical Machine Translation, pages 88–95, Prague, June 2007. c⃝2007 Association for Computational Linguistics Efficient Handling of N-gram Language Models for Statistical Machine Translation Marcello Federico Fondazione Bruno Kessler - IRST I-38050 Trento, Italy federico@itc.it Mauro Cettolo Fondazione Bruno Kessler - IRST I-38050 Trento, Italy cettolo@itc.it Abstract Statistical machine translation, as well as other areas of human language processing, have recently pushed toward the use of large scale n-gram language models. This paper presents efficient algorithmic and architec- tural solutions which have been tested within the Moses decoder, an open source toolkit for statistical machine translation. Exper- iments are reported with a high perform- ing baseline, trained on the Chinese-English NIST 2006 Evaluation task and running on a standard Linux 64-bit PC architecture. Comparative tests show that our representa- tion halves the memory required by SRI LM Toolkit, at the cost of 44% slower translation speed. However, as it can take advantage of memory mapping on disk, the proposed implementation seems to scale-up much bet- ter to very large language models: decoding with a 289-million 5-gram language model runs in 2.1Gb of RAM. 1 Introduction In recent years, we have seen an increasing interest toward the application of n-gram Language Mod- els (LMs) in several areas of computational lin- guistics (Lapata and Keller, 2006), such as ma- chine translation, word sense disambiguation, text tagging, named entity recognition, etc. The origi- nal framework of n-gram LMs was principally au- tomatic speech recognition, under which most of the standard LM estimation techniques (Chen and Goodman, 1999) were developed. Nowadays, the availability of larger and larger text corpora is stress- ing the need for efficient data structures and algo- rithms to estimate, store and access LMs. Unfortu- nately, the rate of progress in computer technology seems for the moment below the space requirements of such huge LMs, at least by considering standard lab equipment. Statistical machine translation (SMT) is today one of the research areas that, together with speech recognition, is pushing mostly toward the use of huge n-gram LMs. In the 2006 NIST Machine Translation Workshop (NIST, 2006), best perform- ing systems employed 5-grams LMs estimated on at least 1.3 billion-word texts. In particular, Google Inc. presented SMT results with LMs trained on 8 trillion-word texts, and announced the availabil- ity of n-gram statistics extracted from one trillion of words. The n-gram Google collection is now publicly available through LDC, but their effective use requires either to significantly expand computer memory, in order to use existing tools (Stolcke, 2002), or to develop new ones. This work presents novel algorithms and data structures suitable to estimate, store, and access very large LMs. The software has been integrated into a popular open source SMT decoder called Moses.1 Experimental results are reported on the Chinese-English NIST task, starting from a quite well-performing baseline, that exploits a large 5- gram LM. This paper is organized as follows. Section 2 presents techniques for the estimation and represen- 1http://www.statmt.org/moses/ 88 tation in memory …

Content truncated to 500 words