Integrating history-length interpolation and classes in language modeling

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1516–1525, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Integrating history-length interpolation and classes in language modeling Hinrich Sch¨utze Institute for NLP University of Stuttgart Germany Abstract Building on earlier work that integrates dif- ferent factors in language modeling, we view (i) backing off to a shorter history and (ii) class-based generalization as two complemen- tary mechanisms of using a larger equivalence class for prediction when the default equiv- alence class is too small for reliable estima- tion. This view entails that the classes in a language model should be learned from rare events only and should be preferably applied to rare events. We construct such a model and show that both training on rare events and preferable application to rare events improve perplexity when compared to a simple direct interpolation of class-based with standard lan- guage models. 1 Introduction Language models, probability distributions over strings of words, are fundamental to many ap- plications in natural language processing. The main challenge in language modeling is to estimate string probabilities accurately given that even very large training corpora cannot overcome the inherent sparseness of word sequence data. One way to im- prove the accuracy of estimation is class-based gen- eralization. The idea is that even though a particular word sequence s may not have occurred in the train- ing set (or too infrequently for accurate estimation), the occurrence of sequences similar to s can help us better estimate p(s). Plausible though this line of reasoning is, the lan- guage models most commonly used today do not incorporate class-based generalization. This is par- tially due to the additional cost of creating classes and using classes as part of the model. But an equally important reason is that most models that integrate class-based information do so by way of a simple interpolation and achieve only a modest im- provement in performance. In this paper, we propose a new type of class- based language model. The key novelty is that we recognize that certain probability estimates are hard to improve based on classes. In particular, the best probability estimate for frequent events is often the maximum likelihood estimator and this estimator is hard to improve by using other information sources like classes or word similarity. We therefore design a model that attempts to focus the effect of class-based generalization on rare events. Specifically, we propose to employ the same strategy for this that history-length interpo- lated (HI) models use. We define HI models as models that interpolate the predictions of different-length histories, e.g., p(w3|w1w2) λ1(w1w2)p′(w3|w1w2) + λ2(w1w2)p′(w3|w2) += (1 − λ1(w1w2) − λ2(w1w2))p′(w3) where p′ is a simple estimate; in this section, we use p′ = pML, the maximum likelihood estimate, as an example. Jelinek-Mercer (Jelinek and Mercer, 1980) and modified Kneser-Ney (Kneser and Ney, 1995) models are examples of HI models. HI models address the challenge that frequent events are best estimated by a method close to max- …

Content truncated to 500 words