1. count
training corpus
"the cat sat"
"the cat ran"
"the dog sat"
trigram counts:
(the, cat, sat): 1
(the, cat, ran): 1
(the, dog, sat): 1
(the, cat, *): 2
2. smooth
raw count gives zero
to unseen n-grams.
Kneser-Ney redistributes:
discount seen counts
use continuation prob
for unseen words
P(w | prev) = max(c-D, 0)/N
+ λ · P_cont(w)
3. generate
sample from
P(w | prev):
"the" (start)
-> "cat" (p=0.6)
-> "sat" (p=0.4)
-> "on"
-> "the"
locally plausible,
globally incoherent.
4. evaluate
perplexity
= exp(- (1/N) Σ
log P(w_i | ctx))
lower = better
Brown corpus:
KN 4-gram ~140
transformer ~20
Kneser-Ney stayed the best n-gram smoother for 20 years.
Transformers closed the perplexity gap by ~10x, not by inventing a better smoother.