N-gram language models

A language model assigns a probability to every sequence of tokens. That probability is the central object of NLP: generate text by sampling from it, score a candidate translation by evaluating it, measure how surprised a model is by a new document with it. Before neural networks, the canonical parameterization was the n-gram model[1, 2]: simple, interpretable, and fast to build, but with fundamental structural limits that motivate every architecture that follows.

The autoregressive factorization

The chain rule of probability factors any joint distribution over a sequence $x_1, \dots, x_T$ into a product of conditionals:

This factorization is exact, no approximation so far. The challenge is representing $p(x_t \mid x_{<t})$, which in principle conditions on the entire prefix $x_1, \dots, x_{t-1}$.

The Markov approximation

An n-gram model truncates the conditioning context to the last $n-1$ tokens:

This is the $(n-1)$th-order Markov assumption. The special cases:

• $n=1$ (unigram): $p(x_t)$, no context, just a bag-of-words distribution.
• $n=2$ (bigram): $p(x_t \mid x_{t-1})$, conditions on one previous token.
• $n=3$ (trigram): $p(x_t \mid x_{t-2}, x_{t-1})$, two-token context.

Maximum-likelihood estimation

Given a corpus $\mathcal{C}$, let $c(w_1, \dots, w_k)$ count how often the sequence $(w_1, \dots, w_k)$ appears. The MLE bigram probability is:

Training is just counting. There are no parameters to learn by gradient descent.

To handle sentence boundaries, prepend $\langle\text{bos}\rangle$ and append $\langle\text{eos}\rangle$ to each sentence. This lets the model assign probability to "the sentence ends here" and ensures the joint distribution over sequences of any length normalizes to 1.

A worked bigram

Toy corpus (three sentences):

Selected bigram counts:

Bigram MLE table (partial):

Probability of "Sam I am":

The three structural limits

1. Sparsity. Most n-grams never appear, even in billion-token corpora. The MLE assigns them probability zero, so any test sentence containing an unseen bigram gets probability zero and infinite cross-entropy loss.

2. Parameter explosion. For vocabulary size $V$ and order $n$, the table has $V^n$ entries. At $V = 50{,}000$ and $n = 3$: $1.25 \times 10^{14}$ entries, impossible to store or estimate.

3. Fixed range. The Markov assumption guarantees that any dependency spanning more than $n-1$ tokens is invisible. The model can never resolve long-distance coreference or syntactic agreement.

These limits are the structural motivation for neural language models.

Perplexity

Perplexity is the standard metric for comparing language models on held-out text:

It equals the exponentiated average per-token cross-entropy loss. Lower is better: a perfect model (assigns probability 1 to every correct next token) has $\text{PPL} = 1$. Smoothed trigrams on news text achieve $\text{PPL} \approx 200$; modern LLMs achieve $\sim 10$.

import numpy as np
from collections import Counter, defaultdict

corpus = [
    ["<bos>", "I", "am", "Sam", "<eos>"],
    ["<bos>", "Sam", "I", "am", "<eos>"],
    ["<bos>", "I", "do", "not", "like", "green", "eggs", "<eos>"],
]

# Count unigrams and bigrams
unigrams = Counter()
bigrams = Counter()
for sent in corpus:
    for w in sent:
        unigrams[w] += 1
    for a, b in zip(sent, sent[1:]):
        bigrams[(a, b)] += 1

def bigram_prob(a, b):
    return bigrams[(a, b)] / unigrams[a] if unigrams[a] > 0 else 0.0

# Score a test sentence
test = ["<bos>", "Sam", "I", "am", "<eos>"]
log_prob = sum(
    np.log(bigram_prob(a, b) + 1e-30)
    for a, b in zip(test, test[1:])
)
n_tokens = len(test) - 1  # predict all but <bos>
ppl = np.exp(-log_prob / n_tokens)
print(f"log p = {log_prob:.3f}, perplexity = {ppl:.2f}")

The zero-probability problem is immediate: any unseen bigram sends log probability to $-\infty$.

Exercises

Exercise 1. Using the toy corpus $\mathcal{C} = \{\text{I am Sam},\ \text{Sam I am},\ \text{I do not like green eggs}\}$ with $\langle\text{bos}\rangle$ and $\langle\text{eos}\rangle$ markers, compute the bigram MLE probability of the sentence "I am Sam" by hand.

Exercise 2. A bigram model with vocabulary size $V$ has at most $V^2$ free parameters. Show that the bigram rows are not all independent: how many genuinely free numbers does the model carry, given that each row $\hat{p}(\cdot \mid a)$ must sum to 1?

Exercise 3 (code). Build a bigram model from the toy corpus and verify that every context row sums to 1 (a valid conditional distribution), and that $\hat{p}(\text{am} \mid \text{I}) = 2/3$.

import numpy as np
from collections import Counter, defaultdict

corpus = [
    ["<bos>", "I", "am", "Sam", "<eos>"],
    ["<bos>", "Sam", "I", "am", "<eos>"],
    ["<bos>", "I", "do", "not", "like", "green", "eggs", "<eos>"],
]

unigrams = Counter(w for sent in corpus for w in sent)
bigrams = Counter((a, b) for sent in corpus for a, b in zip(sent, sent[1:]))

# Group next-token probabilities by context
rows = defaultdict(dict)
for (a, b), c in bigrams.items():
    rows[a][b] = c / unigrams[a]

# Every context that starts a bigram must define a proper distribution.
# <eos> never starts a bigram, so it has no row.
for a, dist in rows.items():
    total = sum(dist.values())
    assert np.isclose(total, 1.0), (a, total)

assert np.isclose(rows["I"]["am"], 2 / 3)
print("rows valid; p(am | I) =", round(rows["I"]["am"], 4))

The next lesson introduces smoothing to fix the zero-probability problem.