Kneser-Ney smoothing
At ICASSP-95 in Detroit (9-12 May 1995) Reinhard Kneser of Philips' research laboratories in Aachen and Hermann Ney of Aachen proposed backing-off distributions for n-gram language models optimised for exactly the cases where the longer sequence had not been seen. Perplexity fell by about 10%, and the word error rate in speech recognition by 5%.
Why it matters
N-gram language models for speech recognition and translation gained a way of estimating the unseen that later proved the best of those compared. In Chen and Goodman's explanation of 1998, a word's probability at the lower level should depend not on how often the word occurs but on how many different words it follows.
Backing-off means falling back to a shorter history when the longer n-gram is absent from the training data. Kneser and Ney derived distributions for this step in two ways. In the first, the lower-level probability of a word is the number of different histories it has been seen after, divided by that number summed over all words: in the paper's words, only the information that a word has been observed in some context is taken into account, and the frequency is ignored. The paper's own example is dollars, very frequent in the Wall Street Journal corpus but found almost exclusively after numbers and some country names. Chen and Goodman's later example is Francisco, which occurs only after San. The measurements, read in the full text (pp. 183-184). Two corpora: German Verbmobil dialogues, about 30,000 words with a closed 2,000-word vocabulary, and the Wall Street Journal, about 40 million words with an open 45,000-word vocabulary covering 99.7%, tested on the official 1992 and 1993 evaluation material; all models are trigrams. On the Wall Street Journal perplexity fell from 161.0 to 145.7 and 144.3 for the two new distributions, and the word error rate from 11.9% to 11.2% and 11.1%; on Verbmobil perplexity fell from 105.4 to 97.9 and 96.2, and recognition was not tested. Against the official ARPA trigram model of 1993, on a 20,000-word vocabulary, perplexity was 134.0 against 147.0. The abstract's about 10% and 5% summarise these figures; the body of the paper says up to 10%. What the record does not claim: that the method was already the best of its kind in 1995, which is Chen and Goodman's later finding.