Perplexity › Implementing Perplexity for N-gram Models
Language AI HandbookAll chapters Perplexity › Implementing Perplexity for N-gram ModelsOne section · Sections in this chapter8 / 17 ↓
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 build a complete perplexity evaluation system for n-gram language models. This implementation will demonstrate how the theory we've developed connects to practical evaluation code.
import math
from collections import Counter
class NgramModel:
"""N-gram language model with add-k smoothing."""
def __init__(self, n=2, k=0.01):
self.n = n
self.k = k
self.ngram_counts = Counter()
self.context_counts = Counter()
self.vocab = set()
def train(self, sentences):
"""Train on a list of tokenized sentences."""
for tokens in sentences:
# Add start and end markers
padded = ["<s>"] * (self.n - 1) + tokens + ["</s>"]
self.vocab.update(padded)
# Count n-grams and contexts
for i in range(len(padded) - self.n + 1):
ngram = tuple(padded[i : i + self.n])
context = tuple(padded[i : i + self.n - 1])
self.ngram_counts[ngram] += 1
self.context_counts[context] += 1
def log_prob(self, word, context):
"""Return log2 P(word | context) with add-k smoothing."""
if isinstance(context, list):
context = tuple(context)
ngram = context + (word,)
ngram_count = self.ngram_counts.get(ngram, 0)
context_count = self.context_counts.get(context, 0)
V = len(self.vocab)
# Add-k smoothing
prob = (ngram_count + self.k) / (context_count + self.k * V)
return math.log2(prob)
def sentence_log_prob(self, tokens):
"""Return total log probability of a sentence."""
padded = ["<s>"] * (self.n - 1) + tokens + ["</s>"]
total_log_prob = 0.0
for i in range(self.n - 1, len(padded)):
context = tuple(padded[i - self.n + 1 : i])
word = padded[i]
total_log_prob += self.log_prob(word, context)
return total_log_prob
def perplexity(self, test_sentences):
"""Calculate perplexity on test sentences."""
total_log_prob = 0.0
total_words = 0
for tokens in test_sentences:
padded = ["<s>"] * (self.n - 1) + tokens + ["</s>"]
for i in range(self.n - 1, len(padded)):
context = tuple(padded[i - self.n + 1 : i])
word = padded[i]
total_log_prob += self.log_prob(word, context)
total_words += 1
avg_log_prob = total_log_prob / total_words
return 2 ** (-avg_log_prob)
# Prepare training data
train_text = """
the cat sat on the mat
the dog sat on the rug
the cat chased the dog
the dog chased the cat
the bird flew over the tree
the cat watched the bird
the dog watched the cat
a cat sat on a mat
a dog sat on a rug
"""
train_sentences = [
line.lower().split()
for line in train_text.strip().split("\n")
if line.strip()
]
# Train models of different orders
models = {}
for n in [1, 2, 3]:
model = NgramModel(n=n, k=0.01)
model.train(train_sentences)
models[n] = modelTraining corpus: 9 sentences Vocabulary size: 16 tokens 1-gram model: Unique 1-grams: 15 Unique contexts: 1 2-gram model: Unique 2-grams: 32 Unique contexts: 15 3-gram model: Unique 3-grams: 43 Unique contexts: 27
With 9 training sentences, we have a small but workable corpus. The vocabulary of about 20 tokens is typical for toy examples. Notice how higher-order models have more unique n-grams: the trigram model distinguishes more context patterns than the bigram model, but it also has sparser coverage because there are fewer examples of each 3-word sequence.
Now let's evaluate these models on held-out test data.
# Test sentences (some seen, some novel)
test_sentences = [
"the cat sat on the mat".split(), # Seen in training
"the dog chased the bird".split(), # Partially novel
"a bird flew over the mat".split(), # More novel combinations
"the cat and the dog played".split(), # Novel structure
]
# Calculate perplexity for each model
results = []
for n, model in models.items():
pp = model.perplexity(test_sentences)
results.append((n, pp))Perplexity on Test Set:
----------------------------------------
Model Perplexity Bits/Word
----------------------------------------
1-gram 17.72 4.15
2-gram 5.09 2.35
3-gram 6.34 2.66The results reveal a common pattern: higher-order models can achieve lower perplexity when they have sufficient training data. The bigram model outperforms the unigram model because it captures local word dependencies, like "the cat" being more likely than "the xylophone." The trigram model may or may not improve further depending on corpus size. With limited data, trigrams suffer from the data sparsity problem: most 3-word sequences in the test data have never been seen in training, so the model is essentially guessing using smoothed estimates. This tradeoff between capturing longer context and having sparse coverage is one of the central challenges n-gram models face.