N-Gram Language Models

Some word sequences are more probable than others. Its water is so transparent that the is ordinary English; its water is so transparent that which is not. A model that could put a number on that difference — that could say the is a likely next word here and which is not — would be useful almost everywhere in language technology: it picks the fluent transcription in speech recognition, the natural phrasing in translation, the plausible completion in text prediction.

A language model does precisely that job: it assigns a probability to a sequence of words, and equivalently predicts the next word given the words so far.¹ The two views are equivalent: a model that scores whole sequences can rank candidate next words, and a model that predicts each next word can multiply those predictions into a sequence probability. The n-gram is the simplest such model, and though neural language models have replaced it in practice, every concept here — the prediction task, maximum likelihood from counts, perplexity, the zero-probability problem — carries forward unchanged.

The prediction task

Start with the conditional form. Let $h$ be a history, the words seen so far, and $w$ a candidate next word. We want

One estimate comes straight from counts: take a very large corpus, count how often the history $h$ appears, count how often it is followed by $w$, and divide.²

This estimate fails in practice. Language is creative — new sentences are coined constantly — so even a corpus the size of the web will not contain most histories even once, and the ratio is $0/0$. The same problem affects the sequence view: to get $P(w_1,\dots ,w_n)$ directly we would count how often that exact sequence occurs among all sequences of the same length, and long sequences essentially never repeat. We need a way to estimate these probabilities without having seen the exact string.

Notation

Write a sequence of $N$ words as $w_1\dots w_N$, and abbreviate the span $w_i,w_{i+1},\dots ,w_j$ as $w_{i:j}$. So $w_{1:i-1}$ is the entire history before position $i$. Counts are written $C(\cdot )$: $C(w_{i-1}{w}_i)$ is the number of times the bigram $w_{i-1}{w}_i$ appears in the corpus. The vocabulary is $V$, and $|V|$ is its size.

The chain rule and the Markov approximation

Counting a whole sequence directly is infeasible. Two steps make the problem tractable: rewrite the sequence probability exactly as a product of next-word predictions, then approximate each prediction by conditioning on only the most recent words.

The joint probability of a sequence factors exactly, with no approximation, by the chain rule of probability: each word is conditioned on everything before it.

This is exact but does not yet help: the last factor $P(w_n\mid w_{1:n-1})$ conditions on the full history, the very quantity we cannot estimate. The chain rule has only converted one uncountable quantity (a whole sequence) into a product of uncountable quantities (each word on its entire past).

The n-gram idea is to approximate each factor by conditioning on only the last few words rather than the full history. The bigram model keeps just the single preceding word:

The assumption that the next word depends only on a bounded window of recent words is the Markov assumption.³ Generalizing from one word of context to $n-1$ gives the general n-gram approximation:

Substituting the approximation back into the chain rule gives the model's estimate of a whole sequence — for the bigram case,

The figure below shows the two views side by side: the same product of factors, read left-to-right as next-word prediction or collected as a sequence score.

Estimating the probabilities: maximum likelihood

An n-gram probability is estimated by maximum likelihood estimation (MLE): take counts from a corpus and normalize them to lie between $0$ and $1$.⁴ For a bigram, count the two-word sequence $C(w_{i-1}{w}_i)$ and divide by the count of all bigrams that share the same first word — which is just the unigram count of that word:

The general n-gram case divides the count of the full n-gram by the count of its $(n-1)$-word prefix:

This ratio, an observed frequency over the frequency of a prefix, is a relative frequency, and using relative frequencies as probability estimates is what makes this MLE: the resulting parameters maximize the probability the model assigns to the training corpus.

A worked bigram example

Take a three-sentence corpus. Each sentence is padded with a start token <s> and an end token </s> — the start token supplies a left context for the first real word, and the end token lets the model assign probability to where a sentence stops, so that sequence probabilities of different lengths remain comparable.

<s> I am Sam </s><s> Sam I am </s><s> I do not like green eggs and ham </s>

Reading counts off the corpus, some of the bigram MLE probabilities are

I is followed by am twice and by do once out of its three occurrences, so the three bigrams starting with I split as $\frac{2}{3},\frac{1}{3}$.

Counts and probabilities on a larger corpus

The pattern is clearer on real data. The tables below use eight words from the Berkeley Restaurant Project, a spoken-query corpus of $9332$ sentences over a vocabulary of $|V|=1446$ words.⁵ First the raw bigram counts$C(w_{i-1}{w}_i)$ — rows are the first word, columns the second:

Most cells are zero — and this matrix was hand-picked to cohere; a random set of eight words would be sparser still. Dividing each row by that word's unigram count (for these rows: i $2533$, want $927$, to $2417$, eat $746$, chinese $158$, food $1093$, lunch $341$, spend $278$) turns the counts into the bigram probabilities $P(w_i\mid w_{i-1})$:

With a few extra probabilities — $P(\text{i}\mid \text{<s>})=0.25$, $P(\text{food}\mid \text{english})=0.5$, $P(\text{</s>}\mid \text{food})=0.68$ — the model scores a whole sentence by multiplying the appropriate bigrams:

Some of these numbers are syntactic (whatever follows to tends to be a verb; $P(\text{to}\mid \text{want})=0.66$), some reflect the task (people starting sentences with i), and some are cultural (chinese food more probable than english). The bigram model has absorbed all three from counts alone.

The next-word distribution

Fix a context and a bigram model induces a probability distribution over the whole vocabulary for what comes next. Most of the mass concentrates on a handful of words and the long tail is near zero. That distribution is the model's prediction.

Evaluating a language model: perplexity

How good is a model? The gold standard is extrinsic evaluation: embed the model in an application — a speech recognizer, a translator — and measure whether the application improves.⁶ That is the only test that certifies a real gain, but it is slow and expensive. For quick iteration we want an intrinsic metric that scores the model on its own, independent of any application.

The setup is the usual one. Split the data into a training set, a development set for tuning, and a held-out test set the model never sees during training. The better of two models is the one that assigns higher probability to the test set: a model that predicts the test data more tightly fits it better. (Letting test sentences leak into training inflates this number dishonestly — never train on the test set.)

Rather than raw probability, the standard intrinsic metric is perplexity, the inverse probability of the test set normalized by the number of words. For a test set $W=w_1{w}_2\dots w_N$,

Expanding the joint probability by the chain rule, and then applying the bigram approximation, gives the forms actually computed:

The $-1/N$ exponent (the $N$-th root) normalizes for length so that longer test sets do not automatically look worse; $N$ counts every token including the end-of-sentence marker </s> but not the start marker <s>.

Perplexity as a branching factor

There is a second, more intuitive reading: perplexity is the weighted average branching factor of the language — roughly, how many words are plausible continuations under the model at each step.⁷ Consider a toy language of the ten digits, each equally likely, $P(\text{digit})=\frac{1}{10}$. For any test string of digits,

The perplexity is exactly $10$ — the true branching factor, since any of ten digits is equally possible next. Now make the digit 0 far more frequent than the rest. The branching factor is still nominally ten, but a good model that has learned 0 is common will predict it confidently, so the weighted branching factor — the perplexity — drops below ten. Perplexity rewards a model for concentrating its probability on the words that actually occur.

The figure contrasts a flat next-word distribution (high perplexity, many equally likely continuations) with a peaked one (low perplexity, the model commits).

The effect shows up when comparing model orders. Trained on $38$ million words of the Wall Street Journal and tested on $1.5$ million held-out words, higher-order n-grams carry more context and reach lower perplexity:

Two cautions. Perplexity is only comparable across models that share the same vocabulary — shrink the vocabulary and perplexity drops artificially. And an intrinsic gain in perplexity is only a proxy; it usually tracks extrinsic quality but should be confirmed by a real end-to-end evaluation before you trust it.

Where part one leads

The n-gram model so far: factor a sequence by the chain rule, truncate the history with the Markov assumption, estimate each conditional by counting, and score with perplexity. This procedure breaks as soon as the test set contains a word sequence the training corpus never included: the count is zero, the probability is zero, and perplexity is undefined. Smoothing and Backoff repairs those zeros by moving probability mass from seen events to unseen ones, works Kneser-Ney by hand, and ends with the neural models that avoid the zero problem entirely.