Smoothed marginal distribution constraints for language modeling

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 43–52, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Smoothed marginal distribution constraints for language modeling Brian Roark†◦, Cyril Allauzen◦ and Michael Riley◦ †Oregon Health & Science University, Portland, Oregon ◦Google, Inc., New York roarkbr@gmail.com, {allauzen,riley}@google.com Abstract We present an algorithm for re-estimating parameters of backoff n-gram language models so as to preserve given marginal distributions, along the lines of well- known Kneser-Ney (1995) smoothing. Unlike Kneser-Ney, our approach is de- signed to be applied to any given smoothed backoff model, including models that have already been heavily pruned. As a result, the algorithm avoids issues observed when pruning Kneser-Ney models (Siivola et al., 2007; Chelba et al., 2010), while retain- ing the benefits of such marginal distribu- tion constraints. We present experimen- tal results for heavily pruned backoff n- gram models, and demonstrate perplexity and word error rate reductions when used with various baseline smoothing methods. An open-source version of the algorithm has been released as part of the OpenGrm ngram library.1 1 Introduction Smoothed n-gram language models are the de- facto standard statistical models of language for a wide range of natural language applications, in- cluding speech recognition and machine transla- tion. Such models are trained on large text cor- pora, by counting the frequency of n-gram col- locations, then normalizing and smoothing (reg- ularizing) the resulting multinomial distributions. Standard techniques store the observed n-grams and derive probabilities of unobserved n-grams via their longest observed suffix and “backoff” costs associated with the prefix histories of the unob- served suffixes. Hence the size of the model grows with the number of observed n-grams, which is very large for typical training corpora. 1www.opengrm.org Natural language applications, however, are commonly used in scenarios requiring relatively small footprint models. For example, applica- tions running on mobile devices or in low latency streaming scenarios may be required to limit the complexity of models and algorithms to achieve the desired operating profile. As a result, statisti- cal language models – an important component of many such applications – are often trained on very large corpora, then modified to fit within some pre-specified size bound. One method to achieve significant space reduction is through random- ized data structures, such as Bloom (Talbot and Osborne, 2007) or Bloomier (Talbot and Brants, 2008) filters. These data structures permit effi- cient querying for specific n-grams in a model that has been stored in a fraction of the space required to store the full, exact model, though with some probability of false positives. Another common approach – which we pursue in this pa- per – is model pruning, whereby some number of the n-grams are removed from explicit storage in the model, so that their probability must be as- signed via backoff smoothing. One simple prun- ing method is count thresholding, i.e., discarding n-grams that occur less than k times in the corpus. Beyond count thresholding, the most widely used pruning methods (Seymore and …

Content truncated to 500 words