Smoothing Techniques for N-gram Models

As shown in the previous lesson, raw Maximum Likelihood Estimation (MLE) assigns zero probability to any n-gram unseen during training — which then zeroes out the probability of the entire sentence. Smoothing techniques reserve some probability mass for unseen events.

1. Laplace (Add-One) Smoothing

The simplest fix: pretend every possible n-gram was seen one extra time.

P_Laplace(w_i | w_{i-1}) = (Count(w_{i-1}, w_i) + 1) / (Count(w_{i-1}) + V)

where V is the size of the vocabulary (so probabilities still sum to 1).

from collections import Counter
from nltk import word_tokenize, bigrams

corpus = "the cat sat on the mat the cat ate the fish"
tokens = word_tokenize(corpus)
vocab = set(tokens)
V = len(vocab)

unigram_counts = Counter(tokens)
bigram_counts = Counter(bigrams(tokens))

def laplace_bigram_prob(w1, w2):
    return (bigram_counts[(w1, w2)] + 1) / (unigram_counts[w1] + V)

print(laplace_bigram_prob("the", "cat"))    # (2+1)/(4+7) = 0.27  (was 0.5 before)
print(laplace_bigram_prob("fish", "sat"))   # (0+1)/(1+7) = 0.125 (was 0.0 before!)

• Pros: extremely simple, guarantees no zero probabilities.
• Cons: takes too much probability mass away from seen events when the vocabulary is large — tends to over-smooth.

2. Add-k Smoothing (Generalized Laplace)

Instead of adding exactly 1, add a smaller fractional constant k (0 < k < 1) to reduce over-smoothing.

def add_k_bigram_prob(w1, w2, k=0.1):
    return (bigram_counts[(w1, w2)] + k) / (unigram_counts[w1] + k * V)

print(add_k_bigram_prob("the", "cat", k=0.1))

3. Good-Turing Smoothing

Re-estimates the probability of unseen events using the count of events that occurred exactly once ("singletons"). The core idea: the total probability mass reserved for unseen n-grams is estimated from how many n-grams were seen only once — if many bigrams appeared exactly once, it suggests many more unseen bigrams are still "out there" waiting to occur.

P_GT(unseen) ≈ N1 / N        where N1 = number of n-grams seen exactly once,
                                    N  = total n-gram count

4. Backoff and Interpolation

Instead of purely guessing for unseen n-grams, back off to a lower-order model when the higher-order n-gram is unseen.

Katz Backoff:
  If trigram count > 0: use the trigram probability
  Else if bigram count > 0: back off to the bigram probability (discounted)
  Else: back off further to the unigram probability

Interpolation goes further and always blends all orders together using learned weights:

P_interp(w_i | w_{i-2}, w_{i-1}) =
      λ1 · P(w_i)                          -- unigram
    + λ2 · P(w_i | w_{i-1})                -- bigram
    + λ3 · P(w_i | w_{i-2}, w_{i-1})       -- trigram
    where λ1 + λ2 + λ3 = 1

# Simple linear interpolation example
def interpolated_prob(w1, w2, l1=0.2, l2=0.8):
    unigram_p = unigram_counts[w2] / sum(unigram_counts.values())
    bigram_p = bigram_counts[(w1, w2)] / unigram_counts[w1] if unigram_counts[w1] else 0
    return l1 * unigram_p + l2 * bigram_p

print(interpolated_prob("the", "fish"))

5. Kneser-Ney Smoothing (Industry Standard for N-grams)

The most sophisticated classical smoothing method, and the standard baseline before neural LMs. It improves on simple backoff by considering not just how often a word occurs, but how many distinct contexts it appears in (its "versatility") — e.g. "Francisco" is common but almost always follows "San", so it should get a low backed-off unigram probability despite decent raw frequency.

Summary — Choosing a Smoothing Method

Smoothing was the dominant technique for handling data sparsity before neural language models. Modern approaches (Word2Vec embeddings, Transformers, LLMs — Unit 4) sidestep this problem almost entirely by representing words as dense vectors that generalize naturally to unseen combinations.