Smoothing for Language Models

An n-gram model estimates the probability of a word given its preceding context using relative frequencies from a training corpus: ``` P_MLE(wᵢ | wᵢ₋ₙ₊₁ … wᵢ₋₁) = count(wᵢ₋ₙ₊₁ … wᵢ) / count(wᵢ₋ₙ₊₁ … wᵢ₋₁) ``` This is the maximum-likelihood estimate: it is the probability assignment that makes the training corpus itself as likely as possible. The problem is sparsity. For a vocabulary of size V, the number of possible n-grams is Vⁿ, which explodes far faster than any corpus can be collected. Most grammatical, semantically sensible n-grams simply never occur in training, giving `count = 0` and therefore `P_MLE = 0`.

Smoothing (also called discounting) is any technique that reassigns probability mass away from observed n-grams toward unobserved ones, so that the resulting distribution never assigns zero probability to a valid sequence. Formally, a smoothing method replaces the raw counts `count(w)` with adjusted counts `count(w) ≤ count(w)` for observed events, and uses the recovered mass `Σ (count(w) − count(w))` to fund a positive probability for unobserved events. The two dominant strategies for where to send that recovered mass are:

• Backoff: if the highest-order n-gram (e.g., trigram) has a nonzero count, use it (discounted); otherwise recursively fall back to the (n−1)-gram, and so on down to unigrams. Only one order's estimate is used for any given prediction, chosen by availability.
• Interpolation: always combine estimates from all orders simultaneously, as a weighted sum, so a low-order estimate always contributes a small stabilizing influence even when the high-order count is nonzero.

Both families require a discount — a rule for how much to shave off the seen counts — since simply adding new nonzero probabilities without removing mass elsewhere would break normalization (probabilities must sum to one). The simplest discount is a flat additive constant (add-k); the most refined is a data-driven absolute discount combined with a clever reweighting of context probabilities (Kneser-Ney).

Add-k (Laplace) smoothing

The oldest and simplest fix is to pretend every possible n-gram was seen k extra times, for some small constant k (k = 1 is "Laplace smoothing," historically motivated by Laplace's rule of succession). For a bigram model with vocabulary size V: ``` P_add-k(wᵢ | wᵢ₋₁) = ( count(wᵢ₋₁, wᵢ) + k ) / ( count(wᵢ₋₁) + k·V ) ``` The `+ k·V` in the denominator is forced by normalization: summing the numerator over all V possible words `wᵢ` must give exactly `count(wᵢ₋₁) + k·V`, so the fractions sum to 1. The trouble is scale. Real vocabularies have V in the tens of thousands to hundreds of thousands. Even for k = 1, the denominator term `k·V` dwarfs typical bigram counts, so every probability — including well-attested bigrams — gets crushed toward `1/V`. Add-k smoothing effectively "steals too much" from the events we're most confident about. This motivates smarter methods that discount conservatively and route the recovered mass more intelligently.

Backoff (Katz backoff)

Katz backoff addresses this by using higher-order n-grams whenever there's reliable evidence, and falling back to lower orders only when necessary — and it uses Good-Turing discounting to decide how much mass to remove from seen counts, rather than a flat constant. The recursive definition for a trigram-to-bigram-to-unigram backoff: ``` P_katz(wᵢ | wᵢ₋₂, wᵢ₋₁) = P(wᵢ | wᵢ₋₂, wᵢ₋₁) if count(wᵢ₋₂, wᵢ₋₁, wᵢ) > 0 α(wᵢ₋₂, wᵢ₋₁) · P_katz(wᵢ | wᵢ₋₁) otherwise ``` where `P` is a discounted probability (strictly less than the MLE estimate, freeing up mass), and `α(wᵢ₋₂, wᵢ₋₁)` is a backoff weight computed so that the whole distribution over `wᵢ` still sums to 1 given the context. The backoff weight redistributes exactly the mass freed by discounting, proportionally to how the lower-order model distributes it among the words that were unseen at the higher order.

Interpolation

Linear interpolation instead always mixes all orders: ``` P_interp(wᵢ | wᵢ₋₂, wᵢ₋₁) = λ₃ · P_MLE(wᵢ | wᵢ₋₂, wᵢ₋₁) + λ₂ · P_MLE(wᵢ | wᵢ₋₁) + λ₁ · P_MLE(wᵢ) ``` with `λ₁ + λ₂ + λ₃ = 1` and each `λ ≥ 0`, guaranteeing the result is a valid probability distribution (a convex combination of distributions is a distribution). The λ weights are typically not fixed by hand; they are tuned on a held-out development set to maximize the likelihood of that data, often via Expectation-Maximization-style iterative reestimation. A natural refinement is to make λ context-dependent: contexts with high counts should trust the higher-order estimate more (larger λ₃), while rare contexts should lean on the lower orders. This is the seed idea behind Kneser-Ney's context-dependent backoff weight.

Kneser-Ney smoothing

Kneser-Ney is the most important classical smoothing method and remains a strong baseline even in the neural era for comparison purposes. It rests on two ideas:

1. Absolute discounting. Instead of Good-Turing's variable discount, subtract a fixed constant D (typically 0 < D < 1, often estimated from corpus statistics) from every nonzero count: ``` count(w) = max(count(w) − D, 0) ``` This is justified empirically: Good-Turing estimated discounts for n-grams occurring r* times are, for most r in real corpora, remarkably close to a single constant, so a flat subtraction loses little accuracy while being far simpler.

2. Continuation probability. Kneser-Ney's key insight concerns the lower-order distribution used in backoff/interpolation. Consider the phrase "San Francisco." The word "Francisco" has high unigram frequency purely because it always follows "San" — but a standard unigram model would predict "Francisco" is a good filler word in any context, which is wrong. Kneser-Ney replaces the raw unigram probability with a continuation probability: how many distinct contexts a word has appeared in, not how often it appears overall. ``` P_continuation(w) = |{ w' : count(w', w) > 0 }| / |{ (w'', w''') : count(w'', w''') > 0 }| ``` The numerator counts how many unique preceding words `w` has followed; the denominator normalizes over all observed bigram types. A word like "Francisco" that follows almost only "San" gets a low continuation probability, correctly reflecting that it's a poor general-purpose backoff choice — even though its raw frequency is high. The full recursive interpolated Kneser-Ney formula: ``` P_KN(wᵢ | wᵢ₋₁) = max(count(wᵢ₋₁, wᵢ) − D, 0) / count(wᵢ₋₁) + λ(wᵢ₋₁) · P_continuation(wᵢ) ``` where `λ(wᵢ₋₁) = D · |{ w : count(wᵢ₋₁, w) > 0 }| / count(wᵢ₋₁)` is exactly the amount of probability mass freed by discounting at this context, ensuring the two terms together sum to 1 over all `wᵢ`. This recursive structure generalizes cleanly to higher orders, with each level's "lower-order" call using continuation counts instead of raw counts.

Pseudocode

```

# Add-k smoothed bigram probability function ADD_K_PROB(w_prev, w, counts, vocab_size, k): numerator = counts.bigram[w_prev, w] + k denominator = counts.unigram[w_prev] + k * vocab_size return numerator / denominator

# Katz backoff (trigram -> bigram -> unigram), simplified function KATZ_TRIGRAM_PROB(w2, w1, w, counts, discount): c3 = counts.trigram[w2, w1, w] if c3 > 0: return discount_trigram(c3, counts) / counts.bigram[w2, w1] else: alpha = backoff_weight_trigram(w2, w1, counts, discount) return alpha KATZ_BIGRAM_PROB(w1, w, counts, discount) function KATZ_BIGRAM_PROB(w1, w, counts, discount): c2 = counts.bigram[w1, w] if c2 > 0: return discount_bigram(c2, counts) / counts.unigram[w1] else: alpha = backoff_weight_bigram(w1, counts, discount) return alpha counts.unigram_prob[w] # base case: unigram MLE

# Interpolated Kneser-Ney bigram probability function KN_BIGRAM_PROB(w_prev, w, counts, D): c_bigram = counts.bigram[w_prev, w] c_context = counts.unigram[w_prev] discounted_term = max(c_bigram - D, 0) / c_context num_types_after_context = count_distinct_words_following(w_prev, counts) lambda_weight = (D num_types_after_context) / c_context p_continuation = continuation_count(w) / total_bigram_types(counts) return discounted_term + lambda_weight p_continuation function continuation_count(w, counts):

# number of DISTINCT word types that precede w anywhere in the corpus return |{ w_prev : counts.bigram[w_prev, w] > 0 }| ``` Every branch terminates: Katz backoff bottoms out at the unigram MLE (which is nonzero for any word in the vocabulary, since vocabulary is defined as the set of words seen at least once), and Kneser-Ney's recursion bottoms out similarly at a uniform or unigram-continuation base case. This guarantees no infinite recursion and no residual zero probabilities, as long as the vocabulary itself covers all words that can appear at test time (handled separately via an out-of-vocabulary/`` token).

Time complexity. Computing a smoothed probability for a single n-gram query is `O(1)` amortized under both schemes, assuming counts are stored in a hash table indexed by n-gram: each requires a constant number of lookups (the n-gram itself, plus its context, plus — for backoff — a constant number of recursive calls bounded by the fixed order `n`, typically n ≤ 5). Precomputing the backoff weights `α` or interpolation weights `λ` for every context requires one pass over all observed n-grams of each order, so training-time complexity is `O(N)`, where N is the total number of n-gram tokens (or n-gram types, if weights are stored per context) in the corpus — the same order as simply counting n-grams, since smoothing adds only a constant-factor overhead per distinct context (computing sums like `Σ count` and `Σ (count − count)`).

Space complexity. Storing counts (and derived quantities like continuation counts or backoff weights) requires space proportional to the number of distinct n-grams observed, `O(|distinct n-grams of order ≤ n|)`, which in the worst case is `O(N)` but in practice is far smaller than `Vⁿ` due to the long-tailed, sparse nature of language — this sparsity is precisely why smoothing is needed in the first place, and precisely why the fix is computationally cheap (we never need to enumerate the full `Vⁿ` space).

Correctness (normalization invariant). The central correctness requirement for any smoothing scheme is: ``` ∀ context c : Σ_{w ∈ vocabulary} P_smoothed(w | c) = 1 ``` Add-k satisfies this by construction: the denominator is defined as exactly the sum of all numerators over the vocabulary (`count(c) + k·V` equals `Σ_w [count(c,w) + k]`), so the fractions telescope to 1 by algebraic necessity — this is a direct proof, not an approximation. Backoff satisfies it by an inductive argument on the recursion. At the base case (unigram MLE over a fixed vocabulary), the invariant holds trivially since it is the MLE distribution. For the inductive step, assume the (n−1)-order model sums to 1. The n-order model splits the vocabulary into "seen" words (using discounted probability `P`, which sums to `1 − mass_freed` by definition of the discount) and "unseen" words (using `α · P_{n−1}`). The backoff weight `α` is defined as `mass_freed / Σ_{unseen w} P_{n−1}(w)`, precisely so that the unseen branch sums to `mass_freed`. Adding the two branches: `(1 − mass_freed) + mass_freed = 1`. This is why `α` is a derived quantity, not a free hyperparameter — it is forced by the normalization requirement. Interpolation* satisfies it even more simply: it is a convex combination (`λᵢ ≥ 0`, `Σλᵢ = 1`) of distributions that each individually sum to 1, and a convex combination of probability distributions is always a probability distribution — this follows directly from linearity of summation: ``` Σ_w P_interp(w|c) = Σ_w Σᵢ λᵢ Pᵢ(w|c) = Σᵢ λᵢ (Σ_w Pᵢ(w|c)) = Σᵢ λᵢ · 1 = 1 ```

Correctness of the estimate (why it generalizes better). The deeper justification isn't just "it sums to 1" — a uniform distribution also sums to 1 but is useless. The real claim is that smoothing reduces held-out cross-entropy compared to raw MLE. This follows from the bias–variance tradeoff: MLE is the unbiased, minimum-variance estimator given the training sample, but it has infinite loss on any held-out event with zero training count. Smoothing introduces a small, controlled bias (probabilities are shifted away from raw frequencies) in exchange for eliminating the infinite-loss failure mode, which — since real held-out data always contains some novel n-grams — strictly dominates MLE in expected held-out log-loss for any nontrivial corpus size. Kneser-Ney's continuation-probability refinement further reduces bias in exactly the cases (like "Francisco") where a word's raw frequency misrepresents its true distributional flexibility as a backoff target.

Tradeoffs. Add-k is cheap and simple but over-smooths at realistic vocabulary sizes — the uniform `k·V` term dominates for any V in the tens of thousands. Katz backoff preserves higher-order specificity well but has a discontinuity: probability estimates can jump abruptly when a count crosses from 0 to 1, and it requires careful Good-Turing count estimation for rare-count buckets. Interpolation is smoother and generally outperforms backoff empirically, but requires tuning λ on held-out data, adding an optimization step (commonly EM or a simplex-constrained search) to training. Kneser-Ney gives the best empirical perplexity among classical methods but is the most complex to implement correctly, especially the recursive continuation-count computation at each order.

Suppose our tiny training corpus (with a vocabulary of just V = 4 words: `the`, `cat`, `sat`, `mat`, plus sentence boundary ``/`` treated separately) yields these bigram counts:

Unigram counts: `count(the) = 4`, `count(cat) = 2`, `count(sat) = 2`, `count(mat) = 1`. Vocabulary size V = 4. We want `P(mat | sat)` — an unseen bigram — under three schemes.

Add-1 (Laplace): ``` P_add1(mat | sat) = (count(sat, mat) + 1) / (count(sat) + V) = (0 + 1) / (2 + 4) = 1/6 ≈ 0.167 ``` That's suspiciously high for something never observed — a symptom of add-1's over-smoothing at small denominators (this gets far worse as V grows into the thousands, where the same math yields near-uniform tiny probabilities for everything, seen or not).

Katz backoff (illustrative, simplified discount d = 0.5 flat for seen bigrams following `sat`): `count(sat, mat) = 0`, so we back off. Seen bigrams from `sat`: only `sat → sat`-type doesn't exist here — assume only `cat → sat` is relevant elsewhere; for context `sat`, suppose no bigrams were observed at all starting with `sat` except implicitly none, forcing full backoff mass α(sat) = 1 (no discounting needed since there's nothing to discount). Then: ``` P_katz(mat | sat) = 1 · P(mat) [unigram MLE] = count(mat) / total_unigrams = 1 / 9 ≈ 0.111 ``` (using total unigram count 4+2+2+1 = 9). This is lower than add-1's estimate and directly reflects `mat`'s low overall corpus frequency, rather than an artifact of vocabulary size.

Interpolated Kneser-Ney (D = 0.5, illustrative): Continuation count of `mat` — how many distinct words precede it — is 1 (only `the` precedes it). Total bigram types in corpus = 3 (`the-cat`, `the-mat`, `cat-sat`). So: ``` P_continuation(mat) = 1 / 3 ≈ 0.333 ``` Number of distinct words following `sat` in training = 0 (no bigrams starting with `sat` observed), so the discounted term is 0 and λ(sat) is computed from the fallback rule (when a context has zero continuations, λ defaults to 1, meaning full mass flows to the continuation distribution): ``` P_KN(mat | sat) = 0 + 1 · P_continuation(mat) = 0.333 ``` Here Kneser-Ney gives the highest estimate of the three, because it recognizes that even though `sat` has no observed continuations at all in training, `mat` is a plausible general English word (it has appeared as a continuation of something, unlike, say, a totally unseen token). This example also exposes the fragility of small-corpus statistics: with more data, `sat` would have observed continuations and the discounted term would dominate, pulling the estimate down. The key behavioral difference — Kneser-Ney weighting words by contextual diversity rather than raw frequency — is best seen at scale, e.g., with "Francisco," which would receive a very low continuation probability despite a high raw unigram count, correctly demoting it as a generic backoff filler.

Smoothed n-gram models were, for decades, the backbone of production speech recognition systems (mapping acoustic hypotheses to fluent word sequences), statistical machine translation (scoring candidate translations for fluency), and spelling/grammar correction (ranking candidate corrections by likelihood). Toolkits like SRILM and KenLM implement modified Kneser-Ney smoothing as their default, and KenLM in particular remains embedded in production MT pipelines and as a fast fluency-scoring component even in hybrid neural systems. Beyond direct use, smoothing's conceptual legacy runs through the entire field. The core problem it solves — assigning nonzero, well-calibrated probability to events unseen in training — reappears in neural language models as label smoothing, temperature scaling, and the softmax's inherent (if implicit) smoothing over an enormous output vocabulary. Understanding why MLE alone fails, and how discounting/backoff/interpolation restore generalization, is essential context for understanding why neural models need their own regularization tricks, and it directly sets up the next natural question: how do we measure whether a smoothing choice actually helped, which is the role of Perplexity as an evaluation metric.

Ask the tutor: How does modified Kneser-Ney smoothing change when moving from bigrams to trigrams — specifically, how are continuation counts defined at each recursive level?