Smoothed Bloom Filter Language Models: Tera-Scale LMs on the Cheap

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 468–476, Prague, June 2007. c⃝2007 Association for Computational Linguistics Smoothed Bloom filter language models: Tera-Scale LMs on the Cheap 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 fall significantly below lossless information-theoretic lower bounds but it produces false positives with some quantifiable probability. Here we present a general framework for deriving smoothed language model probabilities from BFs. We investigate how a BF containing n-gram statistics can be used as a direct replacement for a conventional n-gram model. Recent work has demonstrated that corpus statistics can be stored efficiently within a BF, here we consider how smoothed language model probabilities can be derived efficiently from this randomised representation. Our pro- posal takes advantage of the one-sided error guarantees of the BF and simple inequali- ties that hold between related n-gram statis- tics in order to further reduce the BF stor- age requirements and the error rate of the derived probabilities. We use these models as replacements for a conventional language model in machine translation experiments. 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 (Chiang, 2005). Al- though it is well-known that higher-order language models and models trained on additional monolin- gual corpora can significantly improve translation performance, deploying such language models is not trivial. Increasing the order of an n-gram model can result in an exponential increase in the number of parameters; for the English Gigaword corpus, for instance, there are 300 million distinct trigrams and over 1.2 billion distinct five-grams. Since a language model is potentially queried millions of times per sentence, it should ideally reside locally in memory to avoid time-consuming remote 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 from our corpus, we create an implicit randomised represen- tation of these statistics. This allows us to drastically reduce the space requirements of our models. In this paper, we build on recent work (Talbot and Os- borne, 2007) that demonstrated how the Bloom filter (Bloom (1970); BF), a space-efficient randomised data structure for representing sets, could be used to store corpus statistics efficiently. Here, we propose a framework for deriving smoothed n-gram models from such structures and show via machine trans- lation experiments that these smoothed Bloom filter language models may be used as direct replacements for standard n-gram models in SMT. The space requirements of a Bloom filter are quite spectacular, falling significantly below information- theoretic error-free lower bounds. This efficiency, however, comes at the price of false positives: the fil- ter may erroneously report that an item not …

Content truncated to 500 words