Randomized Language Models via Perfect Hash Functions

Proceedings of ACL-08: HLT, pages 505–513, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Randomized Language Models via Perfect Hash Functions David Talbot∗ School of Informatics University of Edinburgh 2 Buccleuch Place, Edinburgh, UK d.r.talbot@sms.ed.ac.uk Thorsten Brants Google Inc. 1600 Amphitheatre Parkway Mountain View, CA 94303, USA brants@google.com Abstract We propose a succinct randomized language model which employs a perfect hash func- tion to encode fingerprints of n-grams and their associated probabilities, backoff weights, or other parameters. The scheme can repre- sent any standard n-gram model and is easily combined with existing model reduction tech- niques such as entropy-pruning. We demon- strate the space-savings of the scheme via ma- chine translation experiments within a dis- tributed language modeling framework. 1 Introduction Language models (LMs) are a core component in statistical machine translation, speech recognition, optical character recognition and many other areas. They distinguish plausible word sequences from a set of candidates. LMs are usually implemented as n-gram models parameterized for each distinct sequence of up to n words observed in the train- ing corpus. Using higher-order models and larger amounts of training data can significantly improve performance in applications, however the size of the resulting LM can become prohibitive. With large monolingual corpora available in ma- jor languages, making use of all the available data is now a fundamental challenge in language mod- eling. Efficiency is paramount in applications such as machine translation which make huge numbers of LM requests per sentence. To scale LMs to larger corpora with higher-order dependencies, researchers ∗Work completed while this author was at Google Inc. have considered alternative parameterizations such as class-based models (Brown et al., 1992), model reduction techniques such as entropy-based pruning (Stolcke, 1998), novel represention schemes such as suffix arrays (Emami et al., 2007), Golomb Coding (Church et al., 2007) and distributed language mod- els that scale more readily (Brants et al., 2007). In this paper we propose a novel randomized lan- guage model. Recent work (Talbot and Osborne, 2007b) has demonstrated that randomized encod- ings can be used to represent n-gram counts for LMs with signficant space-savings, circumventing information-theoretic constraints on lossless data structures by allowing errors with some small prob- ability. In contrast the representation scheme used by our model encodes parameters directly. It can be combined with any n-gram parameter estimation method and existing model reduction techniques such as entropy-based pruning. Parameters that are stored in the model are retrieved without error; how- ever, false positives may occur whereby n-grams not in the model are incorrectly ‘found’ when requested. The false positive rate is determined by the space us- age of the model. Our randomized language model is based on the Bloomier filter (Chazelle et al., 2004). We encode fingerprints (random hashes) of n-grams together with their associated probabilities using a perfect hash function generated at random (Majewski et al., 1996). Lookup is very efficient: the values of 3 cells in a large array are combined with the fingerprint of an n-gram. This paper focuses on …

Content truncated to 500 words