N-gram Language Models › Summary

N-gram language models assign probabilities to word sequences by decomposing joint probabilities into conditional probabilities using the chain rule. The Markov assumption limits the conditioning context to the previous $n-1$ words, making estimation tractable from finite data.

Key takeaways:

• Chain rule decomposition breaks sequence probability into a product of conditional probabilities: $P(w_1, \ldots, w_n) = \prod_{i=1}^{n} P(w_i|w_1, \ldots, w_{i-1})$.
• Markov assumption limits history to $n-1$ words, trading long-range accuracy for tractability.
• Maximum likelihood estimation computes probabilities as normalized n-gram counts: the count of the full n-gram divided by the count of its $(n-1)$-gram prefix.
• Start and end tokens model sentence boundaries explicitly, with $n-1$ start tokens for an order-$n$ model.
• Log probabilities prevent numerical underflow when multiplying many small values.
• Zero probability problem occurs when test data contains unseen n-grams, motivating smoothing.
• Perplexity measures model quality as the inverse per-word probability: lower perplexity means the model assigns higher probability to test text. Perplexity equals $2^{H}$ where $H$ is per-word entropy in bits.
• Text generation samples words from conditional distributions, with temperature controlling the sharpness of the distribution.
• Higher-order n-grams capture more context but suffer exponentially increasing sparsity, with $V^n$ possible n-grams for vocabulary size $V$.
• Sparse storage using dictionaries or tries makes large models practical.
• Smoothing (Laplace and more sophisticated methods) addresses zero probabilities by redistributing probability mass from seen to unseen n-grams.

N-gram models reveal the fundamental tension in language modeling: longer context improves predictions but requires exponentially more data. The next chapter on Smoothing Techniques addresses the zero probability problem directly, showing how to assign non-zero probabilities to unseen n-grams while still respecting patterns learned from training data. Understanding these classical solutions provides essential background for appreciating why neural language models, despite their greater complexity, represent such a decisive advance.