N-gram Language Models, Smoothing and Perplexity

A language model (LM) assigns a probability to any sequence of words. That simple capability powers spelling correction, speech recognition, machine translation, autocomplete — and, scaled up enormously, today's large language models. Before neural networks, the dominant language models were n-gram models. They introduce every core concept we need: the chain rule, the Markov assumption, sparsity, smoothing and perplexity.

The chain rule#

The probability of a sentence $w_1, \dots, w_n$ decomposes exactly:

P(w_1, \dots, w_n) = \prod_{i=1}^{n}P(w_i \mid w_1, \dots, w_{i-1})

Every language model — from bigrams to GPT — estimates these conditional next-word probabilities.

The Markov assumption#

Full histories are too varied to estimate from data. An n-gram model assumes each word depends only on the previous $n - 1$ words:

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

Bigram ($n = 2$): $P(w_i \mid w_{i-1})$. Trigram: $P(w_i \mid w_{i-2}, w_{i-1})$.

Maximum likelihood estimation#

Estimate probabilities from counts in a corpus:

P_{\text{MLE}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}

Special tokens <s> and </s> mark sentence boundaries so we can model how sentences begin and end.

The sparsity problem#

Language is productive: most plausible n-grams never appear in any finite corpus. If the test sentence contains a bigram with zero count, MLE assigns the whole sentence probability zero. The larger $n$, the worse the sparsity — a trigram model on a vocabulary of 50,000 words has $1.25 \times 10^{14}$ possible trigrams.

Smoothing#

Add-one (Laplace) smoothing pretends every n-gram occurred once more:

P_{\text{Laplace}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) + 1}{C(w_{i-1}) + |V|}

Simple, but it moves far too much probability mass to unseen events for large vocabularies. Add-k uses $k < 1$.

Backoff and interpolation combine models of different orders:

P_{\text{interp}}(w_i \mid w_{i-2}, w_{i-1}) = \lambda_3 P(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P(w_i \mid w_{i-1}) + \lambda_1 P(w_i)

with $\sum\lambda = 1$, tuned on held-out data.

Kneser–Ney smoothing, the best classical method, subtracts a fixed discount from observed counts and redistributes it using a clever continuation probability: how many different contexts a word appears in. "Francisco" is frequent but almost always follows "San", so it should get little probability after an unfamiliar context; "glasses" follows many different words.

A bigram model from scratch#

python

import math, random
from collections import Counter, defaultdict

corpus = """the model learns from data . the model predicts the next word .
students learn from teachers . teachers learn from students .
the data helps the model learn .""".split(" . ")
sents = [["<s>"] + s.replace(".", "").split() + ["</s>"] for s in corpus]

unigrams, bigrams = Counter(), Counter()
for s in sents:
    unigrams.update(s[:-1])
    bigrams.update(zip(s[:-1], s[1:]))
V = len(set(w for s in sents for w in s))

def p(w, prev, k=0.1):                       # add-k smoothing
    return (bigrams[(prev, w)] + k) / (unigrams[prev] + k * V)

def perplexity(sentence):
    toks = ["<s>"] + sentence.split() + ["</s>"]
    logp = sum(math.log(p(w, prev)) for prev, w in zip(toks[:-1], toks[1:]))
    return math.exp(-logp / (len(toks) - 1))

print(perplexity("the model learns from students"))
print(perplexity("students predicts data the"))      # less fluent -> higher perplexity

def generate(max_len=12):
    w, out = "<s>", []
    nxt = defaultdict(list)
    for (a, b), c in bigrams.items():
        nxt[a] += [b] * c
    for _ in range(max_len):
        w = random.choice(nxt[w])
        if w == "</s>":
            break
        out.append(w)
    return " ".join(out)
print(generate())

Evaluating language models: perplexity#

Perplexity is the exponentiated average negative log-likelihood per word on held-out text:

\text{PPL}(W) = P(w_1, \dots, w_N)^{-1/N} = \exp\left(-\frac{1}{N}\sum_{i=1}^{N}\log P(w_i \mid w_{<i})\right)

Lower is better. Intuitively, perplexity is the effective branching factor: a perplexity of 100 means the model is as uncertain as choosing uniformly among 100 words at each step. On the Wall Street Journal, classic results showed perplexity falling from roughly 960 (unigram) to 170 (bigram) to 110 (trigram). Perplexities are only comparable across models with the same vocabulary and tokenisation.

Limitations of n-grams#

No generalisation across similar words: seeing "the cat sat" says nothing about "the dog sat".
Short context: dependencies beyond $n - 1$ words are invisible ("The students who attended the lecture on Tuesday were tired").
Storage: large n-gram tables require gigabytes.

Neural language models (Bengio et al., 2003) addressed the first problem with word embeddings; RNNs and then transformers addressed the second. But n-gram models remain useful: in speech recognition decoders, for fast spelling correction, for data deduplication and for detecting benchmark contamination.

#language models#n-grams#smoothing#perplexity#markov assumption

Written by

Janin A Apurba

B.Sc. in CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. Teaching AI, ML and Deep Learning to the next generation of engineers and researchers.