Foundations of Statistical Natural Language Processing Christopher D. Manning and Hinrich Schütze (Stanford University and Xerox Palo Alto Research Center) Cambridge, MA: The MIT Press, 1999, xxxvii + 680 pp; hardbound, ISBN 0-262-13360-1, $60.00

(6.24) Briefly noted Bell et al. (1990) and Witten and Bell (1991) introduce a number of smoothing algorithms for the goal of improving text compression. Their “Method C” is normally referred to as M&ten-Bell smoothing and has been used for smoothing speech language models. The idea is to model the probability of a previously unseen event by estimating the probability of seeing such a new (previously unseen) event at each point as one proceeds through the training corpus. In particular, this probability is worked out relative to a certain history. So to calculate the probability of seeing a new word after, say, sat in one is calculating from the training data how often one saw a new word after sat in, which is just the count of the number of trigram types seen which begin with sat in. It is thus an instance of generalized linear interpolation: + (1 Aw+n+llcld) )PWB(WiIW(i-n+2)(i~l)) where the probability mass given to new n-grams is given by: (I &&n+l)(i&l) ) = , IWi . c(w._’ y. ‘.c;)-;+;;, ‘+ ;’ ;Y!!_ 1 n+ I WI I n+l” ' Wi) However, Chen and Goodman’s (1998) results suggest that this method is not as good a smoothing technique for language models as others that we discuss in this section (performing particularly poorly when used on small training sets). Samuelsson (1996) develops Linear Successive Abstraction, a method of determining the parameters of deleted interpolation style models without the need for their empirical determination on held out data. Samuelsson’s results suggest similar performance within a part-of-speech tagger to that resulting from conventional deleted interpolation; we are unaware of any evaluation of this technique on word n-gram models. Another simple but quite successful smoothing method examined by Chen and Goodman (1996) is the following. MacKay and Peto (1990) argue for a smoothed distribution of the form: P&fP(WjlWi-n+l ’ ’ ’ Wi-1) = C(Wi-n+l ’ ’ ’ Wi) $_ aPMMp(WiIWi-n+Z ’ ’ ’ Wj-1) C(Wi-n+l ’ . ’ Wi-1) + o( where o( represents the number of counts added, in the spirit of Lidstone’s law, but distributed according to the lower order distribution. 6.3 Combining Estimators Model Cross-entropy Perplexity 223 Bigram 7.98 bits 252.3 Trigram 7.90 bits 239.1 Fourgram 7.95 bits 247.0 Table 6.10 Back-off language models with Good-Turing estimation tested on Persuasion. Chen and Goodman (1996) suggest that the number of added counts should be proportional to the number of words seen exactly once, and suggest taking: (6.25) O( = y(Nl(wi-n+l . . . wi-1) + fi) where Nt (w~_~+I . . . Wi-1) = I{Wi : C(Wi-n+l . . . wi) = 111, and then optimizing fi and y on held out data. Kneser and Ney (1995) develop a back-off model based on an extension of absolute discounting which provides a new more accurate way of estimating the distribution to which one backs off. Chen and Goodman (1998) find that both this method and an extension of it that they propose provide excellent smoothing performance. 6.3.5 Language models for Austen With the introduction of interpolation and back-off, we are at last at the point where we can build first-rate language models for our Austen corpus. Using the CMU-Cambridge Statistical Language Modeling Toolkit (see the website) we built back-off language models using Good-Turing estimates, following basically the approach of Katz (1987).14 We then calculated the cross-entropy (and perplexity) of these language models on our test set, Persuasion. The results appear in table 6.10. The estimated probabilities for each following word, and the n-gram size used to estimate it for our sample clause is then shown in table 6.11. Our probability estimates are at last pleasingly higher than the unigram estimate with which we began! While overall the trigram model outperforms the bigram model on the test data, note that on our example clause, the bigram model actually as14. The version of Good-Turing smoothing that the package implements only discounts low frequencies words that occurred fewer than 7 times. 224 6 Statistical Inference: n-gram Models over Sparse Data P(shelh) P(was(h) P(inferior(h) P(tolh) PCbothlh) P(sisterslh) ( P r o d u c t Unigram 0.011 0.015 0.00005 0.032 0.0005 0.0003 1 3.96 x lo-” Bigram 0.00529 0.1219 0.0000159 0.183 0.000449 0.00372 3.14 x 10-15 n used 2 2 1 2 2 2 Trigram 0.00529 0.0741 0.0000162 0.183 0.000384 0.00323 1.44 x 10-1s n used * 2 3 1 2 2 2 Table 6.11 Probability estimates of the test clause according to various language models. The unigram estimate is our previous MLE unigram estimate. The other two estimates are back-off language models. The last column gives the overall probability estimate given to the clause by the model. signs a higher probability. Overall, the fourgram model performs slightly worse than the trigram model. This is expected given the small amount of training data. Back-off models are in general not perfectly successful at simply ignoring inappropriately long contexts, and the models tend to deteriorate if too large n-grams are chosen for model building relative to the amount of data available.