N-gram language models

The bag-of-words classifier answers “which topic”, not “what comes next”. To generate text, autocomplete a query, or score whether a sentence is plausible, we need a model of the sequence: a probability $P(w_1, \dots, w_T)$ for any token sequence. This note builds the simplest such model from counts, introduces the metric used for every language model in the course, and runs into the problem that a count-based model cannot generalize.

Notation. A sequence of $T$ tokens is $w_1, \dots, w_T$, written $w_{1:T}$. $w_{<i}$ means $w_1, \dots, w_{i-1}$. $c(\cdot)$ counts occurrences of a token sequence in the training corpus. $V$ is the vocabulary.

From a joint probability to a product of conditionals#

Every joint distribution over a sequence factorizes by the chain rule of probability, with no assumption:

$$P(w_1, \dots, w_T) = P(w_1)\,P(w_2 \mid w_1)\,P(w_3 \mid w_1, w_2)\cdots = \prod_{i=1}^T P(w_i \mid w_{<i}).$$

Each factor is the probability of the next token given everything before it. This is the form that every language model in the course takes, from this note to the GPT note: a language model is a next-token predictor, and predicting the next token is a classification problem with $|V|$ classes.

The factors cannot be estimated directly. $P(w_i \mid w_{<i})$ conditions on a prefix that, for $i$ beyond a few tokens, has never occurred before in any corpus. The Markov assumption cuts the prefix to the last $n - 1$ tokens:

$$P(w_i \mid w_{<i}) \approx P(w_i \mid w_{i-n+1}, \dots, w_{i-1}).$$

The resulting model is an n-gram language model. For $n = 2$ (bigram) each token depends on one predecessor; for $n = 3$ (trigram) on two. The assumption is wrong (a pronoun can refer back fifty tokens) and useful (two tokens of context already fix most of the local grammar).

Baseline: estimate the conditionals by counting#

With a finite context, each conditional is a categorical distribution over $V$ given a specific prefix, and its maximum-likelihood estimate is a ratio of counts:

$$P(w \mid \text{prefix}) = \frac{c(\text{prefix},\, w)}{\sum_{w' \in V} c(\text{prefix},\, w')}.$$

Two special tokens make the sequence boundaries explicit. The first tokens of a line have no full prefix, so the line is padded on the left with $n - 1$ copies of a start symbol; an end symbol [EOS] is appended so that the model can learn to stop.

Worked example#

A toy corpus of three lines and a bigram model ($n = 2$):

the cat sat
the cat ran
the dog sat

Pad each line with one start symbol [S] and end with [EOS]. Bigram counts:

prefix	next	count	$P(\text{next} \mid \text{prefix})$
[S]	the	3	1
the	cat	2	2/3
the	dog	1	1/3
cat	sat	1	1/2
cat	ran	1	1/2
dog	sat	1	1
sat	[EOS]	2	1
ran	[EOS]	1	1

The probability of the new line the dog ran is

$$P = P(\text{the} \mid \text{[S]})\,P(\text{dog} \mid \text{the})\,P(\text{ran} \mid \text{dog})\,P(\text{[EOS]} \mid \text{ran}) = 1 \cdot \tfrac13 \cdot 0 \cdot 1 = 0.$$

dog ran never occurred, so the whole line gets probability zero. Hold on to this: it is the failure that the rest of the note is about.

The table is easier to read as a graph, which is also how the model generates:

Figure

A bigram model is a graph of transitions

Generation#

Because the model factorizes left to right, it generates the same way. Start from the padding, sample $w_1 \sim P(\cdot \mid \text{[S]})$, append it, sample $w_2 \sim P(\cdot \mid w_1)$, and stop at [EOS]. The output at each step is fed back as input to the next: generation is autoregressive, and this loop is the same in every generative language model in the course. The alternative to sampling, taking the most probable token at each step, is one of the decoding strategies compared in the GPT note.

A trigram model trained on a corpus of short Russian jokes, with BPE tokens, produces lines that are locally grammatical and globally meaningless, such as

мужчина должен постро ##ить дом и вот я однажды мгнове ##нно удалил это сообщение , …

Every run of three consecutive tokens occurred somewhere in the corpus; the sentence as a whole did not and does not cohere. Two tokens of memory are enough for agreement between neighbours and for nothing else.

Perplexity: from probability to a number#

To compare two language models we need a score on held-out text. The sequence probability itself is unusable: it shrinks with length, so a long test set always has a tiny probability whatever the model. Take the logarithm, which turns the product into a sum, and divide by length, which gives a per-token average:

$$H = -\frac{1}{T}\sum_{i=1}^T \log P(w_i \mid w_{<i}).$$

This is the cross-entropy of the test text under the model, in nats per token (bits if the logarithm is base 2). It is the same quantity as the classifier loss of the previous note, seen four ways:

1. As a sum over classes. At position $i$ the “true distribution” is one-hot on the observed token $w_i$: $q_i(w) = \mathbb 1[w = w_i]$. The cross-entropy between $q_i$ and the model $P(\cdot \mid w_{<i})$ is $-\sum_{w \in V} q_i(w)\log P(w \mid w_{<i}) = -\log P(w_i \mid w_{<i})$. Every term but one vanishes.
2. As an expectation. Averaging over positions is a Monte Carlo estimate of $\mathbb E_{w \sim \text{data}}[-\log P(w \mid \text{context})]$, the expected surprise of the model on text drawn from the true distribution.
3. As negative log-likelihood. $T \cdot H = -\log P(w_{1:T})$ by the chain rule, so minimizing $H$ is maximum-likelihood estimation of the sequence.
4. As entropy plus a divergence. If the true next-token distribution is $p$, then $H(p, P) = H(p) + D_{\mathrm{KL}}(p \,\|\, P)$. The entropy of language is fixed; the model can only reduce the KL term. The decomposition is derived in the Generative Models course.

Perplexity is the exponential of the cross-entropy:

$$\mathrm{PPL} = e^{H} = \exp\!\Big(-\frac1T\sum_{i=1}^T \log P(w_i \mid w_{<i})\Big) = P(w_{1:T})^{-1/T}.$$

The last form is the geometric mean of the inverse per-token probabilities, which is why perplexity reads as an effective branching factor: a model with perplexity 50 is, on average, as uncertain as if it chose uniformly among 50 tokens at every step. Two checks fix the scale. A model that assigns probability 1 to every token has $H = 0$ and $\mathrm{PPL} = 1$. A uniform model over $|V|$ tokens has $H = \log|V|$ and $\mathrm{PPL} = |V|$. Lower is better, and the base of the logarithm cancels as long as the same base is used for $\log$ and $\exp$.

On the toy corpus the line the dog ran has probability 0, so $H = \infty$ and the perplexity is infinite. On training data the opposite happens: on five lines used both to fit and to score, a unigram model has perplexity 81.7, a trigram model 1.14 and a 10-gram model 1.10. The long-context models have memorized the lines, and the number says nothing about new text.

Every perplexity measured on the joke corpus in this note is a mean over lines: the perplexity of each line is computed separately, and the values are averaged. That weights every line equally, where the formula above weights every token equally, so the values are not the corpus perplexity. A toy example shows the difference: a line of 2 tokens with per-token NLL 1 has perplexity $e \approx 2.72$, a line of 8 tokens with NLL 3 has $e^3 \approx 20.1$. Their mean is 11.4, while the corpus perplexity, the exponential of the summed NLL over the summed token count, is $\exp((2 \cdot 1 + 8 \cdot 3)/10) = e^{2.6} \approx 13.5$. The corpus perplexity is the standard recipe and the one to use for new measurements; the means over lines are kept here because they are the measured results this note reports, comparable only within one table, where every model is scored the same way.

Unseen n-grams make perplexity explode#

Split the joke corpus 75/25, fit on the training part and score the held-out part with word tokens. The perplexities are on the order of $10^{46}$ for the unigram model and $10^{48}$ for the trigram model. The cause is the zero from the worked example: any test n-gram that never occurred in training has $P = 0$, and $\log 0 = -\infty$. Probabilities below $10^{-50}$ are clipped to $10^{-50}$ so that the sum stays finite, and the clipped terms dominate everything else. The more context the model uses, the more test n-grams are unseen, so trigrams score worse than unigrams. On this measurement the model with the most memory is the worst, and the measurement is the problem: it reports how many test n-grams were unseen, not how well the model predicts.

Smoothing#

Additive (Laplace) smoothing adds a pseudo-count $\delta$ to every token in every context:

$$P(w \mid \text{prefix}) = \frac{c(\text{prefix},\, w) + \delta}{\sum_{w' \in V}\big(c(\text{prefix},\, w') + \delta\big)} = \frac{c(\text{prefix},\, w) + \delta}{c(\text{prefix}) + \delta\,|V|}.$$

The denominator grows by $\delta|V|$, so the mass given to unseen tokens in a context is $\delta(|V| - \text{seen})/(c(\text{prefix}) + \delta|V|)$, shared equally among them. With $\delta = 1$ and a vocabulary the size of this corpus’s BPE vocabulary, 37,580 tokens, a context seen 10 times keeps only $10/(10 + 37{,}580) \approx 0.03\,\%$ of its mass for the tokens actually observed. That is far too much smoothing, which is why add-one is the illustrative method rather than the practical one, but it removes the zeros:

Tokens	$n = 1$	$n = 2$	$n = 3$
Words, $\delta = 1$	39,956	30,058	70,786
BPE, $\delta = 1$	2,696	3,860	15,598

Read the table within a row; the two rows are not comparable. A BPE text has more tokens than the same text in words, each easier to predict, so a lower per-token perplexity does not mean a better model, and per word the ranking can reverse (the tokenization note does the conversion). Within a row two things are visible. The perplexities are finite and in a range where differences mean something. And the trigram model is worse than the bigram model: with more context, each prefix is seen fewer times, the counts $c(\text{prefix})$ are small, and add-one smoothing flattens the distribution towards uniform. The best $n$ is a trade-off between context and data sparsity, and under a crude smoother it is small.

Better smoothers fix the uniform-sharing flaw. Interpolation mixes the trigram, bigram and unigram estimates with learned weights, so a rare trigram context falls back on its bigram statistics rather than on uniform. Kneser–Ney smoothing (Kneser and Ney, 1995; Chen and Goodman, 1999) subtracts a fixed discount from every seen count and redistributes it in proportion to how many distinct contexts a token appears in, which is the state of the art for count-based models. A good perplexity for a modern neural model on English web text is in the tens; for the small joke corpus here, anything below a few hundred would be a reasonable target that add-one smoothing does not reach.

What changed#

	Bag-of-words classifier	N-gram language model
Question	Which label?	What comes next?
Statistic	Token counts per document	Counts of $n$-token sequences
Output	One distribution over $K$ labels	One distribution over $V$ per position
Order	Ignored	Last $n - 1$ tokens
Can generate	No	Yes, autoregressively
Metric	Accuracy, $F_1$	Perplexity

Limitations#

• Sparsity grows with $n$. The number of possible n-grams is $|V|^n$. Most are never seen, so the model cannot use more than a few tokens of context however much data it has.
• No generalization across tokens. the cat sat and the dog sat are unrelated events; seeing the first does not raise the probability of the second. Every token is an atom, as in the bag of words. This is the limitation that the next note addresses.
• Storage. The model is a table of counts for every observed prefix. It grows with the corpus and is awkward to compress.
• Perplexity is intrinsic. A lower perplexity does not guarantee better generations or a better downstream system; see the evaluation note. It is also not comparable across different tokenizers, because the per-token average changes when the tokens change.

What you should remember#

• Chain rule: $P(w_{1:T}) = \prod_i P(w_i \mid w_{<i})$. A language model is a next-token classifier over $V$.
• Markov assumption: condition on the last $n-1$ tokens; estimate by count ratios; pad with start and end symbols.
• Cross-entropy $H = -\frac1T\sum_i \log P(w_i \mid w_{<i})$ is the per-token negative log-likelihood; perplexity is $e^{H}$, an effective branching factor; uniform over $V$ gives $|V|$.
• An unseen n-gram gives $P = 0$ and infinite perplexity. Smoothing reserves mass for the unseen; add-$\delta$ is the simplest and over-smooths large vocabularies.
• Generation is autoregressive: sample, append, repeat.

Notebook#

week03_lm.ipynb. Cell numbers count every cell, markdown included, from 1. Quoted numbers come from the run saved with the course; cells changed since then for current library versions have no saved output.

• Cells 4–5 load a corpus of short Russian jokes, one per paragraph; cells 6–17 build the BPE tokenizer described in the tokenization note.
• Cells 18–28 state the chain rule and the Markov assumption, implement count_ngrams (left-padding with $n - 1$ copies of [UNK], which replaces the start symbol and counts as an ordinary token, and appending [EOS]) and the NGramLanguageModel class, which turns counts into conditional probabilities exactly as in the formula above. Cells 22–25 show the trigram counts on five lines.
• Cells 30–33 fit a trigram model with BPE tokens on the whole corpus and sample a joke token by token with np.random.choice; the generated line quoted above is the saved output of cell 33.
• Cells 34–36 implement perplexity with a min_prob clip of $10^{-50}$, as the mean of per-line perplexities, and report 81.663, 1.142 and 1.103 for $n = 1, 3, 10$ on the five training lines.
• Cell 38 splits 75/25 and reports the held-out word-token perplexities of order $10^{46}$ to $10^{48}$ for $n = 1, 2, 3$.
• Cells 39–43 implement LaplaceLanguageModel and report the smoothed held-out perplexities in the table above, first with word tokens, then with BPE tokens. In the first version the class’s get_tokens_and_probs called a method that does not exist in the parent class, so sampling from the smoothed model failed (scoring, which uses get_token_prob, was unaffected); the current notebook calls the parent’s get_tokens_and_probs, and cell 41 checks that the smoothed probabilities over the vocabulary sum to 1 for $n = 1, 2, 3$.
• Cells 44–55 start a recurrent language model on the same tokens; the RNN note picks it up.

Next#

The n-gram model treats every token as an atom with no relation to any other. It cannot transfer what it learned about cat sat to dog sat, and with a vocabulary of tens of thousands of atoms, most short sequences are never seen at all. The next note replaces the atom with a vector, so that similar tokens have similar vectors and whatever the model learns for one of them carries over to its neighbours.

References#

• D. Jurafsky, J. H. Martin. Speech and Language Processing, 3rd ed. draft. Chapter 3 (n-gram language models, perplexity, smoothing).
• R. Kneser, H. Ney. Improved backing-off for M-gram language modeling. ICASSP, 1995.
• S. F. Chen, J. Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 1999. The comparison that established modified Kneser–Ney.
• C. E. Shannon. Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 1951. Entropy per character of English and the n-gram approximations.
• T. M. Cover, J. A. Thomas. Elements of Information Theory, 2nd ed. Wiley, 2006. §2.3 (relative entropy) for the entropy-plus-KL decomposition.