N-gram Language Models

Historical notes

1. Who first proposed the mathematics of n-grams, and for what?
   Andrey Markov (1913), who used Markov chains to predict whether the next letter in Pushkin’s Eugene Onegin would be a vowel or a consonant.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, Historical notes, pp. 88–89
2. What was Chomsky’s argument against n-gram models, and what was its effect?
   That finite-state Markov processes, whatever their engineering use, cannot be a complete cognitive model of grammatical knowledge. It led many linguists to ignore statistical modeling for decades.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, Historical notes, p. 89
3. Where did the resurgence of n-gram LMs come from, and who coined “language model” and “perplexity”?
   From speech recognition at IBM (Fred Jelinek and colleagues) and at CMU (James Baker, building on declassified work by Leonard Baum). The IBM group coined both terms.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, Historical notes, p. 89
4. Which smoothing method became the standard n-gram baseline around 2000?
   Modified Interpolated Kneser-Ney, following Chen & Goodman’s careful comparisons.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, Historical notes, p. 89
5. Which two major problems of n-grams do neural language models solve?
   (1) Parameters grow exponentially with n-gram order; (2) n-grams can’t generalize between training and test examples unless the words are identical. Neural LMs map words into a continuous space where words in similar contexts get similar representations.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3, Historical notes, p. 89