Randomised Language Modelling for Statistical Machine Translation

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 512–519, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Randomised Language Modelling for Statistical Machine Translation David Talbot and Miles Osborne School of Informatics, University of Edinburgh 2 Buccleuch Place, Edinburgh, EH8 9LW, UK d.r.talbot@sms.ed.ac.uk, miles@inf.ed.ac.uk Abstract A Bloom filter (BF) is a randomised data structure for set membership queries. Its space requirements are significantly below lossless information-theoretic lower bounds but it produces false positives with some quantifiable probability. Here we explore the use of BFs for language modelling in statis- tical machine translation. We show how a BF containing n-grams can enable us to use much larger corpora and higher-order models complementing a con- ventional n-gram LM within an SMT sys- tem. We also consider (i) how to include ap- proximate frequency information efficiently within a BF and (ii) how to reduce the er- ror rate of these models by first checking for lower-order sub-sequences in candidate n- grams. Our solutions in both cases retain the one-sided error guarantees of the BF while taking advantage of the Zipf-like distribution of word frequencies to reduce the space re- quirements. 1 Introduction Language modelling (LM) is a crucial component in statistical machine translation (SMT). Standard n- gram language models assign probabilities to trans- lation hypotheses in the target language, typically as smoothed trigram models, e.g. (Chiang, 2005). Al- though it is well-known that higher-order LMs and models trained on additional monolingual corpora can yield better translation performance, the chal- lenges in deploying large LMs are not trivial. In- creasing the order of an n-gram model can result in an exponential increase in the number of parameters; for corpora such as the English Gigaword corpus, for instance, there are 300 million distinct trigrams and over 1.2 billion 5-grams. Since a LM may be queried millions of times per sentence, it should ideally re- side locally in memory to avoid time-consuming re- mote or disk-based look-ups. Against this background, we consider a radically different approach to language modelling: instead of explicitly storing all distinct n-grams, we store a randomised representation. In particular, we show that the Bloom filter (Bloom (1970); BF), a sim- ple space-efficient randomised data structure for rep- resenting sets, may be used to represent statistics from larger corpora and for higher-order n-grams to complement a conventional smoothed trigram model within an SMT decoder. 1 The space requirements of a Bloom filter are quite spectacular, falling significantly below information- theoretic error-free lower bounds while query times are constant. This efficiency, however, comes at the price of false positives: the filter may erroneously report that an item not in the set is a member. False negatives, on the other hand, will never occur: the error is said to be one-sided. In this paper, we show that a Bloom filter can be used effectively for language modelling within an SMT decoder and present the log-frequency Bloom filter, an extension of the standard Boolean BF that 1For extensions of …

Content truncated to 500 words