N-grams › N-gram Language Models

One of the most powerful applications of n-gram statistics is building language models, models that assign a probability to any sequence of words. A language model answers the question: how likely is this sentence? This capability underlies autocomplete, speech recognition, machine translation, and text generation.

The probability of a sequence of words $w_1, w_2, \ldots, w_T$ can be written using the chain rule of probability:

$$P(w_1, w_2, \ldots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_1, w_2, \ldots, w_{t-1})$$

where $P(w_t \mid w_1, \ldots, w_{t-1})$ is the conditional probability of word $w_t$ given all preceding words. The problem with this exact formulation is that the history $w_1, \ldots, w_{t-1}$ grows without bound as $t$ increases, making it impossible to estimate reliably from finite data.

The n-gram approximation solves this by applying the Markov assumption: the probability of the next word depends only on the last $n-1$ words, not the full history. For a bigram model ($n = 2$), the assumption is:

$$P(w_t \mid w_1, w_2, \ldots, w_{t-1}) \approx P(w_t \mid w_{t-1})$$

For a trigram model ($n = 3$):

$$P(w_t \mid w_1, w_2, \ldots, w_{t-1}) \approx P(w_t \mid w_{t-2}, w_{t-1})$$

In general, an n-gram model conditions on the preceding $n - 1$ words:

$$P(w_t \mid w_1, \ldots, w_{t-1}) \approx P(w_t \mid w_{t-n+1}, \ldots, w_{t-1})$$

The intuition is that most of the predictive signal about the next word comes from the immediately preceding few words. Knowing that the last two words were "machine learning" tells you a lot about what comes next. Knowing that the word 20 positions back was "the" tells you very little.

The parameters of an n-gram language model are the conditional probabilities $P(w_t \mid w_{t-n+1}, \ldots, w_{t-1})$. The simplest way to estimate these from training data is maximum likelihood estimation (MLE):

$$P_{\text{MLE}}(w_t \mid w_{t-n+1}, \ldots, w_{t-1}) = \frac{C(w_{t-n+1}, \ldots, w_{t-1}, w_t)}{C(w_{t-n+1}, \ldots, w_{t-1})}$$

where:

• $C(w_{t-n+1}, \ldots, w_{t-1}, w_t)$: the count of the full n-gram (the $n-1$ context words followed by $w_t$) in training data
• $C(w_{t-n+1}, \ldots, w_{t-1})$: the count of the context (the $n-1$ preceding words) alone

In plain language: the probability of word $w_t$ following a given context is the fraction of times that context in training data was followed by $w_t$. If the bigram "machine learning" appears 100 times and the word "machine" appears 200 times total, then $P_{\text{MLE}}(\text{learning} \mid \text{machine}) = 100 / 200 = 0.5$.

This estimate is intuitive and easy to compute. However, it assigns zero probability to any n-gram that did not appear in training data. Since any held-out text will contain many unseen n-grams, a pure MLE n-gram model assigns zero probability to real sentences, which makes it unusable for tasks like perplexity evaluation or speech recognition scoring.

Smoothing is the family of techniques used to assign non-zero probabilities to unseen n-grams by redistributing probability mass from seen n-grams to unseen ones. Every practical n-gram language model uses some form of smoothing.

Laplace (Add-one) Smoothing is the simplest approach. We add 1 to every n-gram count, including unseen ones:

$$P_{\text{Laplace}}(w_t \mid w_{t-1}) = \frac{C(w_{t-1}, w_t) + 1}{C(w_{t-1}) + V}$$

where:

• $C(w_{t-1}, w_t)$: the observed bigram count
• $C(w_{t-1})$: the observed unigram count for the context word
• $V$: the vocabulary size (the number of word types)

The denominator increases by $V$ rather than by $1$ because we are adding 1 to the count of every possible next word, and there are $V$ of them. Think of it as: every word in the vocabulary is given one free observation following every context. This ensures no zero-probability outcomes.

The key insight is that adding $V$ to the denominator normalizes the distribution so that probabilities still sum to 1 over all possible next words. Without this correction, the probabilities would be inflated.

In practice, Laplace smoothing assigns far too much probability mass to unseen n-grams, which dilutes the probability of observed ones. More sophisticated methods like Kneser-Ney smoothing achieve much better results in practice by using a more careful accounting of how probability mass should be redistributed based on the diversity of contexts each word appears in. But Laplace smoothing is useful to understand because it captures the essential idea: every technique in the smoothing family is ultimately trying to solve the same problem of zero counts.