Smoothing Techniques › Interpolation and Backoff: Combining N-gram Orders

Laplace and Good-Turing both focus on a single n-gram order and address the zero-count problem in isolation. A more powerful idea is to combine evidence from different orders: use trigrams when you have enough data, but fall back to bigrams or unigrams when you don't. This captures a natural intuition. If you've seen "San Francisco" 1,000 times and "San Francisco Giants" 200 times, but never "San Francisco aardvark," the best estimate for P("aardvark" | "San Francisco") comes from the general bigram distribution for words following "Francisco," not from the trigram count alone.

There are two main ways to combine n-gram orders: interpolation and backoff. They differ in philosophy but often produce similar results.

Interpolation mixes the probabilities from different n-gram orders using learned weights. The idea is to always use all orders simultaneously, weighted by how reliable each one is. For a trigram model with interpolation, the probability of $w_i$ given its two-word context combines trigram and bigram predictions with the unigram prediction:

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

where:

• $\lambda_1, \lambda_2, \lambda_3$: mixing coefficients satisfying $\lambda_1 + \lambda_2 + \lambda_3 = 1$ and each $\lambda_i \geq 0$
• $P_3(w_i \mid w_{i-2}, w_{i-1})$: the trigram MLE probability
• $P_2(w_i \mid w_{i-1})$: the bigram MLE probability
• $P_1(w_i)$: the unigram MLE probability

The key is that all three probabilities are always present in the mixture. Even when the trigram count is zero, the bigram and unigram terms ensure a positive overall probability. The weighted sum is always positive as long as the unigram probability is positive (which it is for any word that appeared in training).

The $\lambda$ weights are estimated using Expectation-Maximization (EM) on held-out data. This is the method of Jelinek and Mercer (1980), hence the name. The EM procedure alternates between computing the expected contribution of each n-gram order given the current weights, and then updating the weights to maximize the likelihood of the held-out data. This converges to a local maximum fairly quickly.

A more powerful variant makes the weights context-dependent: if the trigram context has been seen many times in training, give more weight to $\lambda_3$; if the context is rare, lean more on $\lambda_2$ and $\lambda_1$. This deleted interpolation method adapts the mixing to how much statistical evidence each order has for the given context. You estimate $\lambda$ values for each distinct context rather than using global values, which captures the fact that a trigram with context count of 1,000 is far more reliable than one with context count of 3.

Interpolation works well but has a conceptual limitation: it mixes probabilities from all orders all the time, even when the higher-order estimate is reliable and specific. The mixing somewhat dilutes the high-quality estimate with lower-quality ones. If the trigram is very well-attested, the bigram information is mostly noise that drags down the probability slightly.

Backoff takes a different philosophy: use the highest-order estimate when the context has been seen enough times, and fall back to a lower-order model only when the count is zero. The most influential backoff scheme is Katz backoff (1987).

The core intuition is: trust the data when you have it, back off when you don't. When the trigram "San Francisco aardvark" has a nonzero count, use the trigram probability. When it's zero, fall back to the bigram P("aardvark" | "Francisco"), scaled by a factor that preserves the probability distribution.

Katz backoff uses Good-Turing-style discounting to set aside probability mass, then distributes it through backoff. The probability is:

$$P_{\text{Katz}}(w_i \mid w_{i-n+1}^{i-1}) = \begin{cases} \dfrac{C^*(w_{i-n+1}^{i-1}, w_i)}{C(w_{i-n+1}^{i-1})} & \text{if } C(w_{i-n+1}^{i-1}, w_i) > 0 \\[6pt] \alpha(w_{i-n+1}^{i-1}) \cdot P_{\text{Katz}}(w_i \mid w_{i-n+2}^{i-1}) & \text{otherwise} \end{cases}$$

where:

• $C^*$: the Good-Turing discounted count (always less than or equal to the raw count $C$)
• $\alpha(w_{i-n+1}^{i-1})$: a backoff weight that ensures the probabilities sum to 1 over all possible next words
• $P_{\text{Katz}}(w_i \mid w_{i-n+2}^{i-1})$: the Katz probability using a shorter context (one word less)

The discounting of seen n-grams is required. Without it, when you back off to a lower-order model for unseen n-grams, the total probability would exceed 1 (because the seen n-grams already use up all the probability mass under the context). By pre-discounting every seen n-gram slightly, Katz creates "leftover" probability mass that can be distributed to unseen n-grams via backoff.

The backoff weight $\alpha$ ensures that the leftover probability mass (after discounting seen n-grams) is allocated proportionally to the lower-order model. It is defined as:

$$\alpha(w_{i-n+1}^{i-1}) = \frac{1 - \displaystyle\sum_{w:\, C > 0} \dfrac{C^*(w_{i-n+1}^{i-1}, w)}{C(w_{i-n+1}^{i-1})}}{1 - \displaystyle\sum_{w:\, C > 0} P_{\text{Katz}}(w \mid w_{i-n+2}^{i-1})}$$

where:

• The numerator is the leftover probability mass after all discounted seen n-grams take their share
• The denominator normalizes so that the backoff distribution sums to 1

Katz backoff is computationally efficient and works well in practice. The main drawback is that it uses Good-Turing-style discounting, which can be unreliable for larger counts. Also, the backoff structure means it never blends in higher-order evidence when backing off, which sometimes leaves useful signal on the table.

Interpolation and backoff represent two fundamentally different approaches to the same problem, and they have different strengths.

Interpolation always uses all orders, which means even when you have zero trigram evidence, you smoothly blend in bigram and unigram evidence. This prevents sharp discontinuities in the probability estimates. The downside is that even well-attested trigrams get diluted by bigram and unigram noise.

Backoff uses the highest-order estimate when available, which preserves the precision of specific n-gram observations. But the transition from using a trigram to backing off to a bigram is a hard step function: if the trigram count is 0, you get bigram, and if it's 1, you get (discounted) trigram. This can produce undesirable behavior near the boundary.

In practice, both methods perform similarly for large corpora. The more important distinction is the choice of discount and the choice of lower-order distribution, which is where Kneser-Ney makes its key innovation.