Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-gram Language Models › Computing Sequence Probabilities

Michael BrenndoerferMarch 23, 20256 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 8N-gram Language Models › Computing Sequence Probabilities

Reading section 6 of 15 · Computing Sequence Probabilities · 6 minSection 6 of 15 · 6 min

Section 6 of 15 · 6 min read

N-gram Language Models › Computing Sequence ProbabilitiesOne section · Sections in this chapter6 / 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 n-gram probabilities estimated, we can compute the probability of any sequence. We combine the chain rule decomposition with the Markov approximation to get:

P(w_1, \ldots, w_m) \approx \prod_{i=1}^{m} P(w_i|w_{i-n+1}, \ldots, w_{i-1})

where:

$m$ : the total number of words in the sequence
$n$ : the n-gram order (2 for bigrams, 3 for trigrams)
$w_i$ : the $i$ -th word in the sequence
$w_{i-n+1}, \ldots, w_{i-1}$ : the context of $n-1$ words immediately preceding $w_i$
$\prod_{i=1}^{m}$ : multiply all $m$ conditional probabilities together

For a bigram model ( $n = 2$ ), this simplifies to:

P(w_1, \ldots, w_m) \approx P(w_1|\text{<s>}) \times P(w_2|w_1) \times P(w_3|w_2) \times \cdots \times P(w_m|w_{m-1})

where:

$P(w_1|\text{<s>})$ : the probability of the first word given the start-of-sentence marker
$P(w_i|w_{i-1})$ : the probability of each subsequent word given only the single preceding word

Log Probabilities and Numerical StabilityLink Copied

Multiplying many small probabilities leads to numerical underflow: numbers become too small to represent in floating-point arithmetic. A sentence of 300 words, each with probability 0.1, gives $0.1^{300} = 10^{-300}$ , close to the minimum representable double-precision float near $5 \times 10^{-324}$ . Longer sentences or lower-probability words make this worse. Taking logarithms converts products to sums, keeping values in a manageable range.

Instead of computing a product of probabilities:

P(w_1, \ldots, w_m) = \prod_{i=1}^{m} P(w_i|w_{i-1})

we compute a sum of log probabilities:

\log P(w_1, \ldots, w_m) = \sum_{i=1}^{m} \log P(w_i|w_{i-1})

where:

$\log$ : the natural logarithm function (base $e \approx 2.718$ )
$\sum_{i=1}^{m}$ : sum over all $m$ words in the sequence
$\log P(w_i|w_{i-1})$ : the log probability of each bigram conditional, always a negative number since $0 < P < 1$

This transformation works because of the logarithm's fundamental property: $\log(a \times b) = \log(a) + \log(b)$ . While individual probabilities might be 0.01 or smaller, their log values are manageable negative numbers (for example, $\log(0.01) \approx -4.6$ ). To recover the original probability if needed, compute $P = \exp(\log P)$ .

In[14]:

Code

import math


def sequence_probability(sentence, bigram_counts, unigram_counts, log=True):
    """Calculate the probability of a sentence using bigram model."""
    toks = ["<s>"] + sentence.lower().split() + ["</s>"]

    if log:
        log_prob = 0.0
        for i in range(1, len(toks)):
            w1, w2 = toks[i - 1], toks[i]
            prob = bigram_probability(w1, w2, bigram_counts, unigram_counts)
            if prob == 0:
                return float("-inf")
            log_prob += math.log(prob)
        return log_prob
    else:
        prob = 1.0
        for i in range(1, len(toks)):
            w1, w2 = toks[i - 1], toks[i]
            prob *= bigram_probability(w1, w2, bigram_counts, unigram_counts)
        return prob


# Test sentences
test_sentences = [
    "the cat sat on the mat",
    "the dog sat on the mat",
    "the cat chased the dog",
    "the fish ate the cat",
]

results = [
    (
        s,
        sequence_probability(
            s, bigram_counts_marked, unigram_counts_marked, log=True
        ),
    )
    for s in test_sentences
]

Out[15]:

Console

Sentence Log-Probabilities (bigram model):
------------------------------------------------------------
  log P =   -3.47  "the dog sat on the mat"
  log P =   -3.47  "the cat sat on the mat"
  log P =    -inf  "the cat chased the dog"
  log P =    -inf  "the fish ate the cat"

Out[16]:

Visualization

Log-scale line chart showing raw probabilities collapsing toward the floating-point underflow threshold as sentence length grows from 1 to 350 words. — Raw probabilities shrink exponentially as sentence length grows. With an average per-word probability of 0.1, a 300-word sentence reaches values near floating-point underflow limits, making arithmetic unreliable.

Linear line chart showing log probabilities decreasing steadily as sentence length increases from 1 to 350 words. — Log probabilities decrease linearly with sentence length. The same per-word probability of 0.1 yields log probability decreasing by roughly 2.3 per word, remaining computationally tractable for sequences of any length.

The visualization confirms why log probabilities are essential. With an average per-word probability of 0.1, raw probabilities approach the limits of floating-point representation at around 300 words. Log probabilities decrease linearly and remain tractable for sequences of any length.

The Zero Probability ProblemLink Copied

What happens when we encounter an n-gram that never appeared in training?

In[17]:

Code

# Test with a sentence containing unseen bigrams
unseen_sentence = "the bird flew over the house"
unseen_tokens = ["<s>"] + unseen_sentence.lower().split() + ["</s>"]

# Check each bigram
bigram_analysis = []
for i in range(1, len(unseen_tokens)):
    w1, w2 = unseen_tokens[i - 1], unseen_tokens[i]
    bigram = (w1, w2)
    count = bigram_counts_marked.get(bigram, 0)
    prob = bigram_probability(
        w1, w2, bigram_counts_marked, unigram_counts_marked
    )
    bigram_analysis.append((w1, w2, count, prob))

Out[18]:

Console

Analyzing: "the bird flew over the house"
-------------------------------------------------------
  (<s>, the): count=4, P=1.000  [OK]
  (the, bird): count=0, P=0.000  [UNSEEN]
  (bird, flew): count=0, P=0.000  [UNSEEN]
  (flew, over): count=0, P=0.000  [UNSEEN]
  (over, the): count=0, P=0.000  [UNSEEN]
  (the, house): count=0, P=0.000  [UNSEEN]
  (house, </s>): count=0, P=0.000  [UNSEEN]

Total probability: 0.0

A single unseen bigram makes the entire sequence probability zero. This is the zero probability problem: perfectly valid sentences receive zero probability just because our training data did not contain every possible word combination. The sentence "the bird flew over the house" is entirely plausible English, but our tiny corpus knows nothing about birds or flying. The MLE estimate assigns probability zero to any n-gram not seen in training, and since sequence probability is a product of these terms, any zero drives the whole product to zero.

The deeper issue is that zero probability is semantically wrong, in addition to being numerically inconvenient. A language model that assigns zero probability to valid English sentences fundamentally misrepresents the distribution of language. A well-calibrated language model should assign some small but non-zero probability to any grammatical sequence. This brittleness motivates smoothing techniques, covered in the next chapter. Raw MLE estimates are too brittle for real applications since any test sentence containing an unseen n-gram collapses to zero probability regardless of its plausibility.