A Generalized Language Model as the Combination of Skipped n-grams and Modified Kneser Ney Smoothing

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1145–1154, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Generalized Language Model as the Combination of Skipped n-grams and Modified Kneser-Ney Smoothing Rene Pickhardt, Thomas Gottron, Martin K¨orner, Steffen Staab Institute for Web Science and Technologies, University of Koblenz-Landau, Germany {rpickhardt,gottron,mkoerner,staab}@uni-koblenz.de Paul Georg Wagner and Till Speicher Typology GbR mail@typology.de Abstract We introduce a novel approach for build- ing language models based on a system- atic, recursive exploration of skip n-gram models which are interpolated using modi- fied Kneser-Ney smoothing. Our approach generalizes language models as it contains the classical interpolation with lower or- der models as a special case. In this pa- per we motivate, formalize and present our approach. In an extensive empirical experiment over English text corpora we demonstrate that our generalized language models lead to a substantial reduction of perplexity between 3.1% and 12.7% in comparison to traditional language mod- els using modified Kneser-Ney smoothing. Furthermore, we investigate the behaviour over three other languages and a domain specific corpus where we observed consis- tent improvements. Finally, we also show that the strength of our approach lies in its ability to cope in particular with sparse training data. Using a very small train- ing data set of only 736 KB text we yield improvements of even 25.7% reduction of perplexity. 1 Introduction motivation Language Models are a probabilistic approach for predicting the occurrence of a sequence of words. They are used in many applications, e.g. word prediction (Bickel et al., 2005), speech recogni- tion (Rabiner and Juang, 1993), machine trans- lation (Brown et al., 1990), or spelling correc- tion (Mays et al., 1991). The task language models attempt to solve is the estimation of a probability of a given sequence of words wl 1 = w1, . . . , wl. The probability P(wl 1) of this sequence can be broken down into a product of conditional prob- abilities: P(wl 1) =P(w1) · P(w2|w1) · . . . · P(wl|w1 · · · wl−1) = l� i=1 P(wi|w1 · · · wi−1) (1) Because of combinatorial explosion and data sparsity, it is very difficult to reliably estimate the probabilities that are conditioned on a longer sub- sequence. Therefore, by making a Markov as- sumption the true probability of a word sequence is only approximated by restricting conditional probabilities to depend only on a local context wi−1 i−n+1 of n − 1 preceding words rather than the full sequence wi−1 1 . The challenge in the construc- tion of language models is to provide reliable esti- mators for the conditional probabilities. While the estimators can be learnt—using, e.g., a maximum likelihood estimator over n-grams obtained from training data—the obtained values are not very re- liable for events which may have been observed only a few times or not at all in the training data. Smoothing is a standard technique to over- come this data sparsity problem. Various smooth- ing approaches have …

Content truncated to 500 words