Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-gram Language Models › Maximum Likelihood Estimation

Michael BrenndoerferMarch 23, 20257 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 8N-gram Language Models › Maximum Likelihood Estimation

Reading section 4 of 15 · Maximum Likelihood Estimation · 7 minSection 4 of 15 · 7 min

Section 4 of 15 · 7 min read

N-gram Language Models › Maximum Likelihood EstimationOne section · Sections in this chapter4 / 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

With the Markov assumption in hand, we have reduced our problem to estimating conditional probabilities like $P(\text{mat}|\text{on the})$ . But how do we compute these from data?

The most straightforward approach is maximum likelihood estimation (MLE): count how often each n-gram appears in our training corpus, then normalize. For a given context, the MLE probability of the next word is simply the fraction of times that word followed that context in training.

Deriving the MLE FormulaLink Copied

The MLE formula follows directly from the definition of conditional probability. Recall that conditional probability is defined as the joint probability of both events divided by the marginal probability of the conditioning event:

P(B|A) = \frac{P(A, B)}{P(A)}

To estimate $P(w_i|w_{i-1})$ from training data, we approximate each probability with its empirical relative frequency. The joint probability $P(w_{i-1}, w_i)$ is approximated by how often the pair $(w_{i-1}, w_i)$ occurs, divided by the total number of bigrams. The marginal probability $P(w_{i-1})$ is approximated by how often $w_{i-1}$ occurs, divided by the total number of words.

When we compute the ratio, the denominators cancel, and we are left with:

P(w_i|w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}

where:

$C(w_{i-1}, w_i)$ : the count of times the bigram $(w_{i-1}, w_i)$ appears consecutively in the training corpus
$C(w_{i-1})$ : the count of times the context word $w_{i-1}$ appears anywhere in the corpus
The ratio gives the proportion of $w_{i-1}$ occurrences that are followed by $w_i$

Worked example: If "the" appears 100 times in our corpus and "the cat" appears 8 times, then:

P(\text{cat}|\text{the}) = \frac{C(\text{the, cat})}{C(\text{the})} = \frac{8}{100} = 0.08

This means 8% of the time "the" is followed by "cat."

For trigrams, we extend the same logic to two-word contexts:

P(w_i|w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i)}{C(w_{i-2}, w_{i-1})}

where:

$C(w_{i-2}, w_{i-1}, w_i)$ : the count of the trigram (three consecutive words)
$C(w_{i-2}, w_{i-1})$ : the count of the two-word context alone (the bigram prefix)

The general MLE formula for any n-gram order is:

P(w_i|w_{i-n+1}, \ldots, w_{i-1}) = \frac{C(w_{i-n+1}, \ldots, w_{i-1}, w_i)}{C(w_{i-n+1}, \ldots, w_{i-1})}

where:

$w_i$ : the word whose probability we want to estimate
$w_{i-n+1}, \ldots, w_{i-1}$ : the context of $n-1$ words immediately preceding $w_i$
$C(w_{i-n+1}, \ldots, w_{i-1}, w_i)$ : the count of the complete n-gram in the training corpus
$C(w_{i-n+1}, \ldots, w_{i-1})$ : the count of the $(n-1)$ -gram context alone

The formula always divides the count of the full n-gram by the count of its $(n-1)$ -gram prefix. This relative frequency estimate is the maximum likelihood solution because it maximizes the probability of observing the training data under the model. No other choice of conditional probability parameters would assign a higher likelihood to the observed training corpus. If you were to increase any single $P(w|context)$ above the relative frequency estimate, you would have to decrease the probability of other words following that context, and the net effect would be a decrease in training data likelihood.

Implementing MLE EstimationLink Copied

Let us implement this and see it work on a small corpus:

In[7]:

Code

from collections import Counter


def count_ngrams(tokens, n):
    """Count n-grams in a token sequence."""
    ngram_counts = Counter()
    for i in range(len(tokens) - n + 1):
        ngram = tuple(tokens[i : i + n])
        ngram_counts[ngram] += 1
    return ngram_counts


# Sample corpus
corpus = """
the cat sat on the mat
the cat ate the fish
the dog sat on the mat
the dog chased the cat
"""

# Tokenize
tokens = corpus.lower().split()

# Count unigrams and bigrams
unigram_counts = count_ngrams(tokens, 1)
bigram_counts = count_ngrams(tokens, 2)

Out[8]:

Console

Corpus tokens: 22
Unique unigrams: 9
Unique bigrams: 14

Top 10 bigrams:
  ('the', 'cat'): 3
  ('sat', 'on'): 2
  ('on', 'the'): 2
  ('the', 'mat'): 2
  ('mat', 'the'): 2
  ('the', 'dog'): 2
  ('cat', 'sat'): 1
  ('cat', 'ate'): 1
  ('ate', 'the'): 1
  ('the', 'fish'): 1

Our small corpus contains 24 tokens but only 9 unique words. The most frequent bigrams involve "the," reflecting its role as the most common English word. Notice the Zipf-like distribution: a few bigrams appear multiple times while most appear only once. This pattern explains why n-gram models struggle with data sparsity. As we move to higher-order n-grams, the long tail grows longer and most n-grams remain unseen even in large corpora.

Now let us apply the MLE formula to compute actual probabilities:

In[9]:

Code

def bigram_probability(w1, w2, bigram_counts, unigram_counts):
    """Calculate P(w2|w1) using MLE."""
    bigram = (w1, w2)
    unigram = (w1,)

    bigram_count = bigram_counts.get(bigram, 0)
    unigram_count = unigram_counts.get(unigram, 0)

    if unigram_count == 0:
        return 0.0

    return bigram_count / unigram_count


# Calculate example probabilities
examples = [
    ("the", "cat"),
    ("the", "dog"),
    ("the", "mat"),
    ("cat", "sat"),
    ("sat", "on"),
    ("on", "the"),
]

probabilities = [
    (w1, w2, bigram_probability(w1, w2, bigram_counts, unigram_counts))
    for w1, w2 in examples
]

Out[10]:

Console

Bigram Probabilities P(w2|w1):
---------------------------------------------
P(cat|the) = 3/8 = 0.375
P(dog|the) = 2/8 = 0.250
P(mat|the) = 2/8 = 0.250
P(sat|cat) = 1/3 = 0.333
P(on|sat) = 2/2 = 1.000
P(the|on) = 2/2 = 1.000

The probabilities reveal patterns in our corpus. After "the," both "cat" and "dog" appear with equal probability (25% each), while "mat" also appears 25% of the time. After "sat," the word "on" appears with 100% probability. This reflects the fixed phrase "sat on" that appears in every relevant sentence. After "on," the word "the" follows every time.

These probabilities capture the local structure of our tiny corpus. With only four sentences, these patterns are artifacts of limited data. A larger corpus would reveal more detailed distributions, but the estimation procedure is exactly the same.

We can visualize the complete bigram probability matrix as a heatmap, where each cell $(i, j)$ shows $P(w_j|w_i)$ , the probability of word $w_j$ given context word $w_i$ :

Out[11]:

Visualization

Heatmap of bigram transition probabilities with context words on rows and next words on columns. — Bigram transition probability matrix for our sample corpus. Each row represents a context word and each column represents a possible next word. Cells show the transition probability, with white indicating zero probability. The sparse structure reveals that most word pairs never co-occur: ''sat'' always transitions to ''on'' (probability 1.0) and ''on'' always leads to ''the'', while ''the'' distributes probability across several possible continuations.

The heatmap reveals the sparse structure of bigram probabilities. Most cells are empty (zero probability), indicating word pairs that never occurred in our corpus. The non-zero cells cluster around specific patterns: "the" can be followed by several words, but "sat" is always followed by "on." This sparsity becomes even more pronounced with larger vocabularies and higher-order n-grams. With a real vocabulary of 50,000 words, the matrix would be 50,000 by 50,000 with the overwhelming majority of cells set to zero.