---
title: N-Gram Language Models
module: Foundations
moduleNumber: 1
lessonNumber: 4
order: 104
summary: >
  A language model assigns a probability to a sequence of words and, equivalently,
  predicts the next word from its history. The n-gram model makes this tractable by
  truncating the history to the last few words, estimates the resulting conditional
  probabilities by counting, and is scored by perplexity. We build the model from the
  chain rule, work a bigram example on a small corpus, and read perplexity as a
  branching factor. The next lesson covers the zero counts that break this model
  and the smoothing that repairs them.
topics: [Foundations]
sources:
  - book: Jurafsky
    ref: "Ch. 3 — N-gram Language Models; §3.1 N-Grams; §3.2 Evaluating 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.[^jm-intro]
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](/natural-language-processing/semantics/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

$$
P(w \mid h), \qquad \text{e.g.} \quad P(\texttt{the} \mid \textit{its water is so transparent that}).
$$

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.[^jm-relfreq]

$$
P(\texttt{the} \mid \textit{its water is so transparent that}) =
\frac{C(\textit{its water is so transparent that the})}{C(\textit{its water is so transparent that})}.
$$

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, \ldots, 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 \ldots w_N$, and abbreviate the span
$w_i, w_{i+1}, \ldots, 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.

$$
P(w_{1:n}) = P(w_1)\,P(w_2 \mid w_1)\,P(w_3 \mid w_{1:2}) \cdots P(w_n \mid w_{1:n-1})
= \prod_{k=1}^{n} P(w_k \mid w_{1:k-1}).
$$

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:

$$
P(w_i \mid w_{1:i-1}) \approx P(w_i \mid w_{i-1}).
$$

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

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

> **Definition (N-gram model).** A language model that approximates the probability of
> a word given its full history by conditioning only on the previous $n-1$ words,
> $P(w_i \mid w_{1:i-1}) \approx P(w_i \mid w_{i-n+1:i-1})$. A bigram uses $n=2$ (one
> word of context), a trigram $n=3$ (two words), and so on.

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

$$
P(w_{1:n}) \approx \prod_{k=1}^{n} P(w_k \mid w_{k-1}).
$$

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.

$$
% caption: The bigram model as a chain. Each word conditions only on its predecessor,
% so the arrow into $w_k$ carries the factor $P(w_k \mid w_{k-1})$; multiplying the
% factors gives the sequence probability. START and END are the $\texttt{<s>}$ and
% $\texttt{</s>}$ sentence markers.
\begin{tikzpicture}[>=stealth, font=\small,
  wbox/.style={draw, minimum width=15mm, minimum height=8mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[wbox, draw=black, text=black] (s0) at (0,0)   {START};
  \node[wbox] (w1) at (3.2,0)  {I};
  \node[wbox] (w2) at (6.4,0)  {want};
  \node[wbox] (w3) at (9.6,0)  {food};
  \node[wbox, draw=black, text=black] (s1) at (12.8,0) {END};
  \draw[->, acc, thick] (s0) -- (w1);
  \draw[->, acc, thick] (w1) -- (w2);
  \draw[->, acc, thick] (w2) -- (w3);
  \draw[->, acc, thick] (w3) -- (s1);
  \node[font=\scriptsize, text=acc, anchor=south] at (1.6,0.35) {P(I after START)};
  \node[font=\scriptsize, text=acc, anchor=south] at (4.8,0.35) {P(want after I)};
  \node[font=\scriptsize, text=acc, anchor=south] at (8.0,0.35) {P(food after want)};
  \node[font=\scriptsize, text=acc, anchor=south] at (11.2,0.35) {P(END after food)};
\end{tikzpicture}
$$

## 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$.[^jm-mle] 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:

$$
P(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i)}{\sum_{w} C(w_{i-1} w)} = \frac{C(w_{i-1} w_i)}{C(w_{i-1})}.
$$

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

$$
P(w_i \mid w_{i-n+1:i-1}) = \frac{C(w_{i-n+1:i-1}\, w_i)}{C(w_{i-n+1:i-1})}.
$$

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

$$
P(\texttt{I} \mid \texttt{<s>}) = \tfrac{2}{3} = 0.67, \qquad
P(\texttt{Sam} \mid \texttt{<s>}) = \tfrac{1}{3} = 0.33, \qquad
P(\texttt{am} \mid \texttt{I}) = \tfrac{2}{3} = 0.67,
$$

$$
P(\texttt{Sam} \mid \texttt{am}) = \tfrac{1}{2} = 0.5, \qquad
P(\texttt{</s>} \mid \texttt{Sam}) = \tfrac{1}{2} = 0.5, \qquad
P(\texttt{do} \mid \texttt{I}) = \tfrac{1}{3} = 0.33.
$$

`I` is followed by `am` twice and by `do` once out of its three occurrences, so the
three bigrams starting with `I` split as $\tfrac{2}{3}, \tfrac{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.[^jm-berp] First the raw bigram **counts**
$C(w_{i-1} w_i)$ — rows are the first word, columns the second:

| | i | want | to | eat | chinese | food | lunch | spend |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| **i** | 5 | 827 | 0 | 9 | 0 | 0 | 0 | 2 |
| **want** | 2 | 0 | 608 | 1 | 6 | 6 | 5 | 1 |
| **to** | 2 | 0 | 4 | 686 | 2 | 0 | 6 | 211 |
| **eat** | 0 | 0 | 2 | 0 | 16 | 2 | 42 | 0 |
| **chinese** | 1 | 0 | 0 | 0 | 0 | 82 | 1 | 0 |
| **food** | 15 | 0 | 15 | 0 | 1 | 4 | 0 | 0 |
| **lunch** | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| **spend** | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

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})$:

| | i | want | to | eat | chinese | food | lunch | spend |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| **i** | 0.002 | 0.33 | 0 | 0.0036 | 0 | 0 | 0 | 0.00079 |
| **want** | 0.0022 | 0 | 0.66 | 0.0011 | 0.0065 | 0.0065 | 0.0054 | 0.0011 |
| **to** | 0.00083 | 0 | 0.0017 | 0.28 | 0.00083 | 0 | 0.0025 | 0.087 |
| **eat** | 0 | 0 | 0.0027 | 0 | 0.021 | 0.0027 | 0.056 | 0 |
| **chinese** | 0.0063 | 0 | 0 | 0 | 0 | 0.52 | 0.0063 | 0 |
| **food** | 0.014 | 0 | 0.014 | 0 | 0.00092 | 0.0037 | 0 | 0 |
| **lunch** | 0.0059 | 0 | 0 | 0 | 0 | 0.0029 | 0 | 0 |
| **spend** | 0.0036 | 0 | 0.0036 | 0 | 0 | 0 | 0 | 0 |

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

$$
\begin{aligned}
P(\texttt{<s> i want english food </s>})
&= P(\texttt{i} \mid \texttt{<s>})\,P(\texttt{want} \mid \texttt{i})\,P(\texttt{english} \mid \texttt{want}) \\
&\quad \times P(\texttt{food} \mid \texttt{english})\,P(\texttt{</s>} \mid \texttt{food}) \\
&= 0.25 \times 0.33 \times 0.0011 \times 0.5 \times 0.68 \approx 0.000031.
\end{aligned}
$$

Some of these numbers are syntactic (whatever follows `to` tends to be a verb;
$P(\texttt{to} \mid \texttt{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.

> **Note (Log probabilities).** In practice these products are computed in log space.
> Each factor is $\le 1$, so multiplying many of them underflows to zero in floating
> point. Since $\log$ is monotonic and $\log(p_1 p_2 \cdots p_k) = \sum_i \log p_i$,
> the model stores and adds log probabilities, exponentiating only at the end to
> recover a probability.

### 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.

$$
% caption: The next-word distribution given the context `<s>` i want. Probability mass
% concentrates on a few continuations (to, a, some) and is near zero on the rest;
% heights are the conditional probabilities $P(w \mid \textit{want})$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (0,0) -- (9.4,0) node[right, black, font=\scriptsize] {next word};
  \draw[->, black] (0,0) -- (0,3.4) node[above, black, font=\scriptsize] {P(w $\mid$ want)};
  % bars: (x, height, label)
  \foreach \x/\h/\lab in {0.6/2.9/to, 1.9/1.7/a, 3.2/0.9/some, 4.5/0.55/the, 5.8/0.3/thai, 7.1/0.18/food, 8.4/0.08/chinese} {
    \fill[acc!22, draw=acc] (\x-0.28,0) rectangle (\x+0.28,\h);
    \node[anchor=north, black, font=\scriptsize] at (\x,-0.08) {\lab};
  }
\end{tikzpicture}
$$

## 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.[^jm-eval] 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 \ldots w_N$,

$$
\mathrm{PPL}(W) = P(w_1 w_2 \ldots w_N)^{-1/N} = \sqrt[N]{\frac{1}{P(w_1 w_2 \ldots w_N)}}.
$$

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

$$
\mathrm{PPL}(W) = \sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i \mid w_{1:i-1})}}
\;\xrightarrow{\text{bigram}}\;
\sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i \mid w_{i-1})}}.
$$

> **Definition (Perplexity).** The perplexity of a test set $W = w_1 \ldots w_N$ under
> a model is the inverse probability of $W$, normalized by length:
> $\mathrm{PPL}(W) = P(w_1 \ldots w_N)^{-1/N}$. Because of the inverse, a model that
> assigns _higher_ probability to the test set has _lower_ perplexity; minimizing
> perplexity is maximizing test-set probability.

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.[^jm-branch] Consider a toy language of the ten
digits, each equally likely, $P(\text{digit}) = \tfrac{1}{10}$. For any test string of
digits,

$$
\mathrm{PPL}(W) = \parens{\tfrac{1}{10}^{N}}^{-1/N} = \tfrac{1}{10}^{-1} = 10.
$$

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).

$$
% caption: Perplexity as weighted branching factor. A flat distribution (left)
% spreads mass over many words, so many continuations are plausible and perplexity is
% high; a peaked distribution (right) commits to a few, and perplexity is low.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % --- left: flat / high perplexity ---
  \draw[->, black] (0,0) -- (3.6,0);
  \draw[->, black] (0,0) -- (0,2.6);
  \foreach \x in {0.35,0.85,1.35,1.85,2.35,2.85} \fill[acc!22, draw=acc] (\x-0.16,0) rectangle (\x+0.16,1.1);
  \node[anchor=north, font=\scriptsize] at (1.7,-0.1) {f\/lat: high perplexity};
  % --- right: peaked / low perplexity ---
  \begin{scope}[xshift=5.2cm]
    \draw[->, black] (0,0) -- (3.6,0);
    \draw[->, black] (0,0) -- (0,2.6);
    \foreach \x/\h in {0.35/2.3,0.85/0.35,1.35/0.2,1.85/0.15,2.35/0.1,2.85/0.08} \fill[acc!22, draw=acc] (\x-0.16,0) rectangle (\x+0.16,\h);
    \node[anchor=north, font=\scriptsize] at (1.7,-0.1) {peaked: low perplexity};
  \end{scope}
\end{tikzpicture}
$$

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:

| Model | Unigram | Bigram | Trigram |
| --- | --- | --- | --- |
| Perplexity | 962 | 170 | 109 |

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](/natural-language-processing/foundations/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.

[^jm-intro]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 3 — N-gram Language Models: models that assign probabilities to word sequences are language models; the n-gram is the simplest, and a foundational tool for the concepts that carry into neural models.
[^jm-relfreq]: **Jurafsky & Martin**, §3.1 — N-Grams: estimating $P(w \mid h)$ from relative frequency counts, and why even a web-sized corpus is too sparse to count long histories directly.
[^jm-markov]: **Jurafsky & Martin**, §3.1 — the Markov assumption and the n-gram approximation $P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-N+1:n-1})$, generalizing the bigram to arbitrary order.
[^jm-mle]: **Jurafsky & Martin**, §3.1 — maximum likelihood estimation of n-gram parameters as normalized counts, worked on the Sam/ham mini-corpus and the Berkeley Restaurant Project.
[^jm-berp]: **Jurafsky & Martin**, §3.1, Figs. 3.1–3.2 — bigram counts and normalized probabilities for eight words of the Berkeley Restaurant Project corpus ($9332$ sentences, $|V| = 1446$).
[^jm-eval]: **Jurafsky & Martin**, §3.2 — Evaluating Language Models: extrinsic vs. intrinsic evaluation, the train/dev/test split, and why the better model assigns higher probability to a held-out test set.
[^jm-branch]: **Jurafsky & Martin**, §3.2.1 — Perplexity: the inverse test-set probability normalized by length, and its reading as the weighted average branching factor of the language.