Language Model Rest Costs and Space-Efficient Storage

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1169–1178, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Language Model Rest Costs and Space-Efficient Storage Kenneth Heafield∗,† Philipp Koehn† Alon Lavie∗ ∗ Language Technologies Institute Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213, USA {heafield,alavie}@cs.cmu.edu † School of Informatics University of Edinburgh 10 Crichton Street Edinburgh EH8 9AB, UK pkoehn@inf.ed.ac.uk Abstract Approximate search algorithms, such as cube pruning in syntactic machine translation, rely on the language model to estimate probabili- ties of sentence fragments. We contribute two changes that trade between accuracy of these estimates and memory, holding sentence-level scores constant. Common practice uses lower- order entries in an N-gram model to score the first few words of a fragment; this vio- lates assumptions made by common smooth- ing strategies, including Kneser-Ney. Instead, we use a unigram model to score the first word, a bigram for the second, etc. This im- proves search at the expense of memory. Con- versely, we show how to save memory by col- lapsing probability and backoff into a single value without changing sentence-level scores, at the expense of less accurate estimates for sentence fragments. These changes can be stacked, achieving better estimates with un- changed memory usage. In order to interpret changes in search accuracy, we adjust the pop limit so that accuracy is unchanged and re- port the change in CPU time. In a German- English Moses system with target-side syntax, improved estimates yielded a 63% reduction in CPU time; for a Hiero-style version, the reduction is 21%. The compressed language model uses 26% less RAM while equivalent search quality takes 27% more CPU. Source code is released as part of KenLM. 1 Introduction Language model storage is typically evaluated in terms of speed, space, and accuracy. We introduce a fourth dimension, rest cost quality, that captures how well the model scores sentence fragments for purposes of approximate search. Rest cost quality is distinct from accuracy in the sense that the score of a complete sentence is held constant. We first show how to improve rest cost quality over standard prac- tice by using additional space. Then, conversely, we show how to compress the language model by mak- ing a pessimistic rest cost assumption1. Language models are designed to assign probabil- ity to sentences. However, approximate search algo- rithms use estimates for sentence fragments. If the language model has order N (an N-gram model), then the first N − 1 words of the fragment have in- complete context and the last N − 1 words have not been completely used as context. Our baseline is common practice (Koehn et al., 2007; Dyer et al., 2010; Li et al., 2009) that uses lower-order entries from the language model for the first words in the fragment and no rest cost adjustment for the last few words. Formally, the baseline estimate for sentence fragment wk 1 is �N−1 � n=1 pN(wn|wn−1 1 …

Content truncated to 500 words