N-gram models on a toy corpus with add-k, Good-Turing, Kneser-Ney and perplexity
|
Next Words - Lesson 3 - N-gram Models, Smoothing (pdf)
|
345.28 K |
A 5-gram model with modified Kneser-Ney smoothing has a perplexity of about 141 on a standard 10,000-word vocabulary. On a toy corpus of four sentences with 16 distinct bigrams, the probability of cat after the is 3/8 = 0.375, and a sentence with one unseen bigram has probability zero. Over 99 percent of a bigram table is unobserved. The repairs are add-k, Good-Turing, Kneser-Ney and interpolation, and under add-one smoothing the probability of a bigram seen 10 times falls from 0.10 to 0.00022. The gain from a higher order is smaller at each step, 6.3 percent from trigram to 4-gram on 14 million words, and a subject fourteen words back lies outside a 5-gram window. In the notebooks, students build the bigram table, generate text from it, and score the rug sat on the cat under maximum likelihood, add-one and Kneser-Ney.