Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-gram Language Models › A Worked Example: From Corpus to Probability

Michael BrenndoerferMarch 23, 20253 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 8N-gram Language Models › A Worked Example: From Corpus to Probability

Reading section 11 of 15 · A Worked Example: From Corpus to Probability · 3 minSection 11 of 15 · 3 min

Section 11 of 15 · 3 min read

N-gram Language Models › A Worked Example: From Corpus to ProbabilityOne section · Sections in this chapter11 / 15 ↓

Sections in this chapter15

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 us walk through the complete process step by step with a concrete example, starting from a raw sentence and ending with a sequence probability. This ties together everything from this chapter.

Setup. Suppose we train a bigram model on the sentence "the cat sat on the mat" (treated as both training and test for illustration). We want to compute the probability of the new sentence "the cat sat on the mat" under the learned model.

Step 1: Tokenize and add markers.

The sentence becomes: <s> the cat sat on the mat </s>

Step 2: Count unigrams.

From "the cat sat on the mat":

the: 2
cat: 1
sat: 1
on: 1
mat: 1

Step 3: Count bigrams (with markers).

<s> the: 1
the cat: 1
cat sat: 1
sat on: 1
on the: 1
the mat: 1
mat </s>: 1

Step 4: Apply MLE formula.

P(\text{the}|\text{<s>}) = \frac{C(\text{<s>, the})}{C(\text{<s>})} = \frac{1}{1} = 1.0

P(\text{cat}|\text{the}) = \frac{C(\text{the, cat})}{C(\text{the})} = \frac{1}{2} = 0.5

P(\text{sat}|\text{cat}) = \frac{C(\text{cat, sat})}{C(\text{cat})} = \frac{1}{1} = 1.0

P(\text{on}|\text{sat}) = \frac{C(\text{sat, on})}{C(\text{sat})} = \frac{1}{1} = 1.0

P(\text{the}|\text{on}) = \frac{C(\text{on, the})}{C(\text{on})} = \frac{1}{1} = 1.0

P(\text{mat}|\text{the}) = \frac{C(\text{the, mat})}{C(\text{the})} = \frac{1}{2} = 0.5

P(\text{</s>}|\text{mat}) = \frac{C(\text{mat, </s>})}{C(\text{mat})} = \frac{1}{1} = 1.0

Step 5: Multiply the conditional probabilities.

\begin{aligned} P(\text{the cat sat on the mat}) &= P(\text{the}|\text{<s>}) \times P(\text{cat}|\text{the}) \\ &\quad \times P(\text{sat}|\text{cat}) \times P(\text{on}|\text{sat}) \\ &\quad \times P(\text{the}|\text{on}) \times P(\text{mat}|\text{the}) \\ &\quad \times P(\text{</s>}|\text{mat}) \\ &= 1.0 \times 0.5 \times 1.0 \times 1.0 \times 1.0 \times 0.5 \times 1.0 \\ &= 0.25 \end{aligned}

Step 6: Compute log probability.

\log P = \log(1.0) + \log(0.5) + \log(1.0) + \log(1.0) + \log(1.0) + \log(0.5) + \log(1.0)

= 0 + (-0.693) + 0 + 0 + 0 + (-0.693) + 0 = -1.386

Step 7: Compute perplexity.

The sequence has 6 content words plus the end token, so $N = 7$ :

\text{PP} = \exp\!\left(-\frac{-1.386}{7}\right) = \exp(0.198) \approx 1.219

This is remarkably low perplexity, essentially because the model was evaluated on its own training sentence. In real evaluation, we always separate training and test data.

Let us verify this programmatically:

In[37]:

Code

# Verify the worked example
example_corpus = "the cat sat on the mat"
example_model = NgramLanguageModel(n=2)
example_model.train(example_corpus)

# Walk through each bigram probability
example_toks = ["<s>"] + example_corpus.split() + ["</s>"]
print_probs = []
for i in range(1, len(example_toks)):
    w1, w2 = example_toks[i - 1], example_toks[i]
    context = (w1,)
    ngram = (w1, w2)
    ngram_c = example_model.ngram_counts.get(ngram, 0)
    context_c = example_model.context_counts.get(context, 0)
    prob = example_model.probability(w2, context)
    print_probs.append((w1, w2, ngram_c, context_c, prob))

Out[38]:

Console

Step-by-step bigram probability computation:
-----------------------------------------------------------------
Context    Word        C(bigram)   C(context)        P
-----------------------------------------------------------------
<s>        the                 1            1   1.0000
the        cat                 1            2   0.5000
cat        sat                 1            1   1.0000
sat        on                  1            1   1.0000
on         the                 1            1   1.0000
the        mat                 1            2   0.5000
mat        </s>                1            1   1.0000

Product (P(sentence)) = 0.2500
Log P = -1.3863
Perplexity (N=7) = 1.2190

The computed values match our manual calculation exactly. Notice that "the" has context count 2 because it appears twice in the training sentence, which creates the non-trivial probability of 0.5 for $P(\text{cat}|\text{the})$ and $P(\text{mat}|\text{the})$ .