An Empirical Study of Smoothing Techniques for Language Modeling

An Empirical Study of Smoothing Techniques for Language Modeling Stanley F. Chen Harvard University Aiken Computation Laboratory 33 Oxford St. Cambridge, MA 02138 sfc©eecs, harvard, edu Joshua Goodman Harvard University Aiken Computation Laboratory 33 Oxford St. Cambridge, MA 02138 goodma.n~eecs, harvard, edu Abstract We present an extensive empirical com- parison of several smoothing techniques in the domain of language modeling, includ- ing those described by Jelinek and Mer- cer (1980), Katz (1987), and Church and Gale (1991). We investigate for the first time how factors such as training data size, corpus (e.g., Brown versus Wall Street Journal), and n-gram order (bigram versus trigram) affect the relative performance of these methods, which we measure through the cross-entropy of test data. In addition, we introduce two novel smoothing tech- niques, one a variation of Jelinek-Mercer smoothing and one a very simple linear in- terpolation technique, both of which out- perform existing methods. 1 Introduction Smoothing is a technique essential in the construc- tion of n-gram language models, a staple in speech recognition (Bahl, Jelinek, and Mercer, 1983) as well as many other domains (Church, 1988; Brown et al., 1990; Kernighan, Church, and Gale, 1990). A lan- guage model is a probability distribution over strings P(s) that attempts to reflect the frequency with which each string s occurs as a sentence in natu- ral text. Language models are used in speech recog- nition to resolve acoustically ambiguous utterances. For example, if we have that P(it takes two) >> P(it takes too), then we know ceteris paribus to pre- fer the former transcription over the latter. While smoothing is a central issue in language modeling, the literature lacks a definitive compar- ison between the many existing techniques. Previ- ous studies (Nadas, 1984; Katz, 1987; Church and Gale, 1991; MacKay and Peto, 1995) only compare a small number of methods (typically two) on a sin- gle corpus and using a single training data size. As a result, it is currently difficult for a researcher to intelligently choose between smoothing schemes. In this work, we carry out an extensive empirical comparison of the most widely used smoothing techniques, including those described by 3elinek and Mercer (1980), Katz (1987), and Church and Gale (1991). We carry out experiments over many training data sizes on varied corpora us- ing both bigram and trigram models. We demon- strate that the relative performance of techniques depends greatly on training data size and n-gram order. For example, for bigram models produced from large training sets Church-Gale smoothing has superior performance, while Katz smoothing per- forms best on bigram models produced from smaller data. For the methods with parameters that can be tuned to improve performance, we perform an automated search for optimal values and show that sub-optimal parameter selection can significantly de- crease performance. To our knowledge, this is the first smoothing work that systematically investigates any of these issues. In addition, we introduce two novel smooth- ing techniques: the first belonging to the class of smoothing models described by 3elinek …

Content truncated to 500 words