Smoothing Techniques › Code Implementation
Language AI HandbookAll chapters Smoothing Techniques › Code ImplementationOne section · Sections in this chapter9 / 13 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Let's implement each smoothing method step by step, building up to Kneser-Ney. We'll use a simple corpus to make the computations visible and verifiable.
Setup and Corpus
First, let's prepare a small corpus and build the basic counting infrastructure. We'll use a slightly extended corpus so that the frequency-of-frequency statistics have enough variety to be meaningful.
from collections import Counter
# Small illustrative corpus
corpus = (
"the cat sat on the mat the cat sat the dog sat on the mat "
"a cat and a dog sat on a mat the dog and the cat ran away "
"the quick brown fox jumped over the lazy dog the fox ran fast"
)
# Tokenize
tokens = corpus.lower().split()
# Build vocabulary
vocab = sorted(set(tokens))
V = len(vocab)
# Count unigrams, bigrams, trigrams
def build_ngrams(tokens, n):
ngrams = []
for i in range(len(tokens) - n + 1):
ngrams.append(tuple(tokens[i : i + n]))
return ngrams
unigrams = build_ngrams(tokens, 1)
bigrams = build_ngrams(tokens, 2)
trigrams = build_ngrams(tokens, 3)
unigram_counts = Counter(unigrams)
bigram_counts = Counter(bigrams)
trigram_counts = Counter(trigrams)
N = len(tokens) # Total tokensCorpus size: 44 tokens
Vocabulary size: 17 unique words
Unique bigrams: 33
Unique trigrams: 38
Top 5 bigrams: [(('the', 'cat'), 3), (('sat', 'on'), 3), (('cat', 'sat'), 2), (('on', 'the'), 2), (('the', 'mat'), 2)]Laplace Smoothing
Now let's implement Laplace and add-k smoothing functions and compare them to MLE for both seen and unseen bigrams.
def laplace_bigram_prob(w2, w1, bigram_counts, unigram_counts, V):
"""Add-one smoothed bigram probability P(w2 | w1)."""
numerator = bigram_counts.get((w1, w2), 0) + 1
denominator = unigram_counts.get((w1,), 0) + V
return numerator / denominator
def add_k_bigram_prob(w2, w1, bigram_counts, unigram_counts, V, k=0.1):
"""Add-k smoothed bigram probability P(w2 | w1)."""
numerator = bigram_counts.get((w1, w2), 0) + k
denominator = unigram_counts.get((w1,), 0) + k * V
return numerator / denominator
# Compare MLE vs Laplace vs add-k for a seen bigram
w1, w2 = "the", "cat"
mle_count = bigram_counts.get((w1, w2), 0)
ctx_count = unigram_counts.get((w1,), 0)
mle_prob = mle_count / ctx_count if ctx_count > 0 else 0.0
laplace_prob = laplace_bigram_prob(w2, w1, bigram_counts, unigram_counts, V)
addk_prob = add_k_bigram_prob(w2, w1, bigram_counts, unigram_counts, V, k=0.1)
# For an unseen bigram
w1_u, w2_u = "the", "fox"
mle_unseen = bigram_counts.get((w1_u, w2_u), 0) / unigram_counts.get((w1_u,), 1)
laplace_unseen = laplace_bigram_prob(
w2_u, w1_u, bigram_counts, unigram_counts, V
)
addk_unseen = add_k_bigram_prob(
w2_u, w1_u, bigram_counts, unigram_counts, V, k=0.1
)Bigram ('the', 'cat'): count=3, context count=10
MLE: 0.3000
Laplace: 0.1481
Add-k(0.1): 0.2650
Unseen bigram ('the', 'fox'):
MLE: 0.1000 (zero probability!)
Laplace: 0.0741
Add-k(0.1): 0.0940Notice that both Laplace and add-k give the same probability to the unseen bigram "the fox" regardless of the word "fox." This uniform treatment of all unseen words is the fundamental weakness that Kneser-Ney addresses.
Let's also visualize how the discount varies with count for these simple methods. We want to see how much probability mass is being moved relative to the raw count.
The discount ratio shows how much of the original count is preserved. A ratio below 1 means we're reducing the effective probability of this bigram. Laplace with discounts aggressively for low counts, bringing a count-1 bigram down to roughly 10% of its original probability in this example. Add-k with is more conservative, and barely discounts at all. The key insight is that none of these methods differentiate between how much they discount based on the structure of the language, they just use the same mechanical formula for all contexts.
Good-Turing Estimation
Now let's implement Good-Turing and examine the frequency-of-frequency distribution for our corpus.
def compute_frequency_of_frequencies(count_dict):
"""Compute N_c: number of n-grams with count c."""
freq_of_freq = Counter(count_dict.values())
return freq_of_freq
def good_turing_adjusted_count(c, freq_of_freq):
"""
Compute the Good-Turing adjusted count c* for a given raw count c.
Formula: c* = (c+1) * N_{c+1} / N_c
Falls back to raw count c when estimate is unreliable.
"""
N_c = freq_of_freq.get(c, 0)
N_c1 = freq_of_freq.get(c + 1, 0)
if N_c == 0 or N_c1 == 0:
return c # Fall back to MLE for unreliable estimates
return (c + 1) * N_c1 / N_c
# Build frequency of frequencies for bigrams
bigram_fof = compute_frequency_of_frequencies(bigram_counts)
N1 = bigram_fof.get(1, 0)
N2 = bigram_fof.get(2, 0)
p_unseen = N1 / N # Total probability of all unseen n-grams
# GT adjusted counts for common values
gt_adjusted = {
c: good_turing_adjusted_count(c, bigram_fof) for c in range(1, 6)
}Frequency of Frequencies (bigrams): N_1 = 25 (25 distinct bigrams appear 1 time(s)) N_2 = 6 (6 distinct bigrams appear 2 time(s)) N_3 = 2 (2 distinct bigrams appear 3 time(s)) N1 (hapax count) = 25 N2 (twice-seen) = 6 Estimated prob. mass for all unseen bigrams: 0.5682 Good-Turing adjusted counts: c=1 -> c* = 0.480 (discount = 0.520) c=2 -> c* = 1.000 (discount = 1.000) c=3 -> c* = 3.000 (discount = 0.000) c=4 -> c* = 4.000 (discount = 0.000) c=5 -> c* = 5.000 (discount = 0.000)
The shaded region shows the probability mass that Good-Turing redistributes from seen to unseen n-grams. For our small corpus, the adjustments may be large because values fluctuate heavily with so few samples. In a real corpus of millions of sentences, the sequence is much smoother and the Good-Turing estimates are more reliable.
Absolute Discounting
Now let's implement absolute discounting, which approximates Good-Turing with a single constant discount.
def estimate_discount(bigram_fof):
"""
Estimate absolute discount d from frequency-of-frequency counts.
Formula: d = N1 / (N1 + 2*N2)
"""
N1 = bigram_fof.get(1, 0)
N2 = bigram_fof.get(2, 0)
if N1 + 2 * N2 == 0:
return 0.75 # Fallback default
return N1 / (N1 + 2 * N2)
d = estimate_discount(bigram_fof)
def abs_discount_prob(w2, w1, bigram_counts, unigram_counts, unigram_probs, d):
"""Absolute discounting bigram probability P(w2 | w1)."""
c_w1w2 = bigram_counts.get((w1, w2), 0)
c_w1 = unigram_counts.get((w1,), 0)
if c_w1 == 0:
return unigram_probs.get(w2, 1e-10)
# Distinct word types following w1
n_types = sum(1 for (a, _) in bigram_counts if a == w1)
lambda_w1 = (d * n_types) / c_w1
discounted = max(c_w1w2 - d, 0) / c_w1
return discounted + lambda_w1 * unigram_probs.get(w2, 1e-10)
# Compute unigram probabilities (MLE)
total_tokens = sum(unigram_counts.values())
unigram_probs = {w[0]: c / total_tokens for w, c in unigram_counts.items()}
# Test
prob_seen = abs_discount_prob(
"cat", "the", bigram_counts, unigram_counts, unigram_probs, d
)
prob_unseen = abs_discount_prob(
"fox", "the", bigram_counts, unigram_counts, unigram_probs, d
)Estimated discount d = 0.6757
Absolute discounting P('cat' | 'the') = 0.2693
Absolute discounting P('fox' | 'the') = 0.0509Kneser-Ney Smoothing
Now let's implement Kneser-Ney. The key addition is computing continuation counts for each word.
from collections import defaultdict
def build_kneser_ney_counts(bigram_counts):
"""
Build continuation counts for Kneser-Ney.
For each word w, count the number of distinct words that precede it.
This gives the continuation count |{v : C(v, w) > 0}|.
"""
predecessors = defaultdict(set)
for u, w in bigram_counts:
predecessors[w].add(u)
continuation_count = {w: len(preds) for w, preds in predecessors.items()}
total_distinct_bigrams = len(bigram_counts)
return continuation_count, total_distinct_bigrams
continuation_count, total_distinct_bigrams = build_kneser_ney_counts(
bigram_counts
)
def kneser_ney_unigram(w, continuation_count, total_distinct_bigrams):
"""KN continuation probability for word w (lower-order unigram)."""
return continuation_count.get(w, 0) / total_distinct_bigrams
def kneser_ney_bigram(
w2,
w1,
bigram_counts,
unigram_counts,
continuation_count,
total_distinct_bigrams,
d,
):
"""Kneser-Ney smoothed bigram probability P(w2 | w1)."""
c_w1w2 = bigram_counts.get((w1, w2), 0)
c_w1 = unigram_counts.get((w1,), 0)
if c_w1 == 0:
return kneser_ney_unigram(
w2, continuation_count, total_distinct_bigrams
)
n_types = sum(1 for (a, _) in bigram_counts if a == w1)
lambda_w1 = (d * n_types) / c_w1
discounted = max(c_w1w2 - d, 0) / c_w1
lower = kneser_ney_unigram(w2, continuation_count, total_distinct_bigrams)
return discounted + lambda_w1 * lower
# Test for several words
test_words = ["cat", "dog", "mat", "fox", "aardvark"]Continuation counts (number of distinct predecessors):
'cat': continuation_count=2, KN_unigram=0.0606, MLE_unigram=0.0909
'dog': continuation_count=3, KN_unigram=0.0909, MLE_unigram=0.0909
'mat': continuation_count=2, KN_unigram=0.0606, MLE_unigram=0.0682
'fox': continuation_count=2, KN_unigram=0.0606, MLE_unigram=0.0455
'aardvark': continuation_count=0, KN_unigram=0.0000, MLE_unigram=0.0000
Kneser-Ney bigram probabilities P(w | 'the'):
P('cat' | 'the'): KN=0.2570, AbsDiscount=0.2693
P('dog' | 'the'): KN=0.1693, AbsDiscount=0.1693
P('mat' | 'the'): KN=0.1570, AbsDiscount=0.1601
P('fox' | 'the'): KN=0.0570, AbsDiscount=0.0509
P('aardvark' | 'the'): KN=0.0000, AbsDiscount=0.0000Notice how the KN unigram for "fox" differs from its MLE unigram. In the MLE model, "fox" might appear several times in the corpus, but Kneser-Ney asks: how many distinct words precede "fox"? Only "the" does in our corpus, so the continuation count is 1 and the KN unigram is small. This correctly reflects that "fox" is not a versatile continuation word.
The contrast between the two plots reveals the power of the continuation count. In the MLE plot, words rank by their raw frequency in the corpus. In the KN continuation plot, words rank by how many distinct predecessors they have, capturing their contextual versatility. This is exactly the signal that makes Kneser-Ney a superior lower-order distribution.
Comparing Perplexity on a Test Set
Let's now evaluate all four methods on a held-out set of test sentences using perplexity as the evaluation metric.
import math
def sentence_log_prob(sentence, prob_fn):
"""Compute log probability of a sentence using a bigram model."""
words = sentence.lower().split()
log_p = 0.0
for i in range(1, len(words)):
p = prob_fn(words[i], words[i - 1])
if p <= 0:
p = 1e-10 # Clamp to avoid log(0)
log_p += math.log2(p)
return log_p
def perplexity(sentences, prob_fn):
"""Compute perplexity of a list of sentences under a bigram model."""
total_log_p = 0.0
total_words = 0
for sent in sentences:
words = sent.lower().split()
total_log_p += sentence_log_prob(sent, prob_fn)
total_words += len(words) - 1 # Number of prediction steps
avg_log_p = total_log_p / total_words
return 2 ** (-avg_log_p)
# Test sentences (some seen patterns, some new combinations)
test_sentences = [
"the cat ran fast",
"a dog sat on a mat",
"the fox jumped over a mat",
"the brown cat sat on the mat",
"a quick dog ran away",
]
# Build probability functions for each method
laplace_fn = lambda w2, w1: laplace_bigram_prob(
w2, w1, bigram_counts, unigram_counts, V
)
addk_fn = lambda w2, w1: add_k_bigram_prob(
w2, w1, bigram_counts, unigram_counts, V, k=0.1
)
abs_fn = lambda w2, w1: abs_discount_prob(
w2, w1, bigram_counts, unigram_counts, unigram_probs, d
)
kn_fn = lambda w2, w1: kneser_ney_bigram(
w2,
w1,
bigram_counts,
unigram_counts,
continuation_count,
total_distinct_bigrams,
d,
)
pp_laplace = perplexity(test_sentences, laplace_fn)
pp_addk = perplexity(test_sentences, addk_fn)
pp_abs = perplexity(test_sentences, abs_fn)
pp_kn = perplexity(test_sentences, kn_fn)Perplexity comparison on test sentences: Laplace (add-1): 10.62 Add-k (k=0.1): 6.76 Absolute Discounting: 7.72 Kneser-Ney: 7.44 Lower perplexity = better model (less surprised by the test data)
Lower perplexity indicates a better model. Kneser-Ney and absolute discounting typically outperform Laplace and add-k, especially as the test set contains more unseen n-grams. On larger, more realistic corpora, the gap between Kneser-Ney and simpler methods like Laplace is dramatic.
The U-shaped curve in the add-k perplexity chart is informative. Too-small fails because unseen bigrams get near-zero probability and the test sentences contain many novel combinations. Too-large fails because it smooths away the evidence from well-attested bigrams, making the model approximately uniform. The optimal sits in the middle, but even that optimum falls short of Kneser-Ney, which achieves lower perplexity without any tuning of at all.
Key Parameters
The key parameters for smoothing methods are:
- k (add-k smoothing): The additive constant. Tune on a held-out development set. Typical range: 0.001 to 0.5. Smaller values preserve more of the MLE signal; larger values move toward uniform redistribution.
- d (absolute discounting / Kneser-Ney): The discount subtracted from every non-zero count. Estimated automatically as from the training data. Typically around 0.75 for most natural language corpora.
- n (n-gram order): Higher orders capture more context but suffer more from data sparsity. Smoothing is more important for higher-order models. Trigrams with Kneser-Ney often give the best balance of expressiveness and reliability.