N-gram Language Models: Probability-Based Text Generation & Prediction

What makes some word sequences sound natural while others feel wrong? "The cat sat on the mat" flows effortlessly, but "mat the on sat cat the" is gibberish. Native speakers intuitively know which sequences are likely, even for sentences they've never encountered. N-gram language models capture this intuition mathematically, assigning probabilities to sequences of words based on patterns learned from text.

Language models are foundational to NLP. They power spell checkers that suggest "their" over "thier," autocomplete systems that predict your next word, and speech recognizers that disambiguate "recognize speech" from "wreck a nice beach." Before neural networks dominated the field, n-gram models were the workhorses of language modeling, and understanding them provides essential intuition for modern approaches.

This chapter builds n-gram language models from first principles. You'll learn the probability theory that makes them work, implement them from scratch, and discover both their power and fundamental limitations.

A language model assigns probabilities to sequences of words. Given a sequence of $n$ words, denoted $w_1, w_2, \ldots, w_n$, the model estimates $P(w_1, w_2, \ldots, w_n)$, the probability of that exact sequence occurring in natural language. Here $w_i$ represents the $i$-th word in the sequence (e.g., $w_1$ might be "the" and $w_2$ might be "cat").

Why is this useful? Consider a speech recognition system that hears an ambiguous audio signal. It might produce two candidate transcriptions: "I saw a van" and "eyes awe of an." A language model knows the first is far more probable and helps the system choose correctly.

Language models also enable text generation. If we can compute $P(w_1, \ldots, w_n)$ for any sequence, we can generate new text by sampling words according to their probabilities given the preceding context.

Computing the probability of a full sequence seems daunting at first. How could we possibly estimate $P(\text{"the cat sat on the mat"})$ directly? We'd need to count how often this exact six-word sequence appears in our training data, then divide by the total number of six-word sequences. But most sentences are unique. Even in a corpus of billions of words, we're unlikely to see any specific sentence more than a handful of times.

The chain rule of probability offers an escape from this dilemma. Instead of estimating the joint probability directly, we decompose it into a product of conditional probabilities. Each conditional asks a simpler question: given everything that came before, how likely is the next word?

The chain rule derives from the definition of conditional probability. Recall that conditional probability is defined as:

where:

• $P(A|B)$: the probability of event $A$ occurring given that event $B$ has already occurred
• $P(A, B)$: the joint probability of both $A$ and $B$ occurring together
• $P(B)$: the probability of event $B$ occurring (the denominator normalizes by the probability of the condition)

Rearranging, we get the multiplication rule: $P(A, B) = P(B) \times P(A|B)$. This says the probability of both events equals the probability of the first event times the probability of the second event given the first. For a sequence of words, we apply this rule repeatedly to break down the joint probability into simpler conditional probabilities:

Step 1: Start with the joint probability of all words. This is what we ultimately want to compute:

Step 2: Apply the multiplication rule to separate the last word. We treat "all words up to $w_{n-1}$" as event $B$ and "$w_n$ appears next" as event $A$:

Step 3: Repeat for the remaining words, working backwards. Each application peels off one more word from the joint probability until we reach the first word:

We can write this more compactly using product notation:

where:

• $w_i$: the $i$-th word in the sequence (e.g., $w_1 = \text{"the"}$, $w_2 = \text{"cat"}$)
• $P(w_i|w_1, \ldots, w_{i-1})$: the conditional probability of word $w_i$ given all preceding words (the "history")
• $\prod_{i=1}^{n}$: the product operator, which multiplies all $n$ terms together

The intuition is straightforward: the probability of a sequence equals the probability of the first word, times the probability of the second word given the first, times the probability of the third word given the first two, and so on. Each step conditions on all previously observed words.

This decomposition is exact, not an approximation. The probability of any sequence equals the product of each word's probability given its entire preceding context.

Let's see this decomposition in action with a concrete example:

Each term in this product answers a progressively more specific question. The first asks: how likely is "the" to start a sentence? The second asks: given we started with "the," how likely is "cat" to follow? By the time we reach the final word, we're asking: given the entire context "the cat sat on the," how likely is "mat"?

The chain rule is mathematically exact, but it creates a severe practical problem. To compute $P(w_n|w_1, \ldots, w_{n-1})$, we need the probability of word $w_n$ given the entire preceding context. For long sentences, this context can be arbitrarily long. A 20-word sentence requires us to estimate the probability of the 20th word given all 19 preceding words. We'll never have enough data to estimate these long-context probabilities reliably, since most 19-word contexts appear only once, if ever.

This is where the Markov assumption comes to the rescue.

The chain rule gives us an exact decomposition, but it demands something impossible: reliable estimates of probabilities conditioned on arbitrarily long histories. The key insight of n-gram models is to make a simplifying assumption that trades some accuracy for tractability.

The assumption is named after the Russian mathematician Andrey Markov, who studied stochastic processes with this "memoryless" property. In the context of language, it means we pretend the future depends only on the recent past, not the distant past.

For a bigram model ($n=2$), each word depends only on the single word immediately before it:

where:

• $P(w_i|w_1, \ldots, w_{i-1})$: the true conditional probability given the full history (left side)
• $P(w_i|w_{i-1})$: the bigram approximation using only the immediately preceding word (right side)
• $\approx$: indicates this is an approximation, not an equality

For a trigram model ($n=3$), the memory extends to two previous words:

where:

• $w_{i-2}$: the word two positions before the current word
• $w_{i-1}$: the word immediately before the current word
• The context $(w_{i-2}, w_{i-1})$ forms a two-word history

In general, for an n-gram model, we approximate:

where the context window spans exactly $n-1$ preceding words. The approximation symbol $\approx$ reminds us this is a simplification: we're discarding information from the distant past to make estimation tractable.

Why does this help? Consider the difference in what we need to estimate:

• Full history: We need $P(\text{mat}|\text{the cat sat on the})$, requiring counts of the specific five-word context "the cat sat on the"
• Trigram: We need $P(\text{mat}|\text{on the})$, requiring only counts of the two-word context "on the"
• Bigram: We need $P(\text{mat}|\text{the})$, requiring only counts of the single word "the"

Shorter contexts appear far more frequently in training data, giving us more reliable probability estimates.

Is the Markov assumption reasonable? Strictly speaking, no. The probability of "mat" after "the cat sat on the" depends on "cat" and "sat," which establish that we're talking about an animal sitting somewhere. A bigram model, seeing only "the," has no idea whether we're discussing cats on mats, birds in trees, or books on shelves.

Yet this approximation works well in practice, especially for larger values of $n$. Language has enough local structure that nearby words carry most of the predictive information. The word "on" strongly predicts a location or surface will follow. The phrase "sat on" even more strongly suggests something like "mat," "chair," or "floor." We lose some information, but we gain the ability to estimate probabilities reliably.

With the Markov assumption in hand, we've reduced our problem to estimating conditional probabilities like $P(\text{mat}|\text{on the})$. But how do we actually 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. The intuition comes from the definition of conditional probability:

where:

• $P(A|B)$: the probability of $A$ given $B$
• $P(A \text{ and } B)$: the joint probability of both events occurring
• $P(B)$: the probability of the conditioning event

For language, this translates to: the probability of word $w$ following context $c$ equals the fraction of times we observed $c$ followed by $w$, out of all the times we observed $c$.

For bigrams, the MLE estimate is:

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 (in any context)
• The ratio gives the proportion of $w_{i-1}$ occurrences that are followed by $w_i$

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

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

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

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 bigram context (the first two words of the trigram)

The general pattern for any n-gram order is:

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 (context plus target word) in the training corpus
• $C(w_{i-n+1}, \ldots, w_{i-1})$: the count of the context alone (how often this $(n-1)$-gram appears)

The formula always divides the count of the full n-gram by the count of its $(n-1)$-gram prefix (the context). This relative frequency estimate is the maximum likelihood solution because it maximizes the probability of observing the training data under the model.

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

Our small corpus contains 24 tokens but only 9 unique words. The most frequent bigrams are ("the", "cat") and ("the", "dog"), each appearing twice. Notice how "the" dominates as the first element of many bigrams, reflecting its role as the most common English word.

The frequency distributions reveal a pattern common to all natural language: a few items dominate while most appear rarely. "The" appears 8 times, more than any other word, while most bigrams appear only once. This Zipf-like distribution 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's apply the MLE formula to compute actual probabilities:

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, reflecting the fixed phrase "sat on" that appears in every relevant sentence. After "on," the word "the" follows every time, since our corpus always uses "on the" before the final noun.

These probabilities capture the local structure of our tiny corpus. A model trained on this data would predict that "sat" is always followed by "on," and "on" is always followed by "the." Of course, with only four sentences, these patterns are artifacts of our limited data. A larger corpus would reveal more nuanced distributions.

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

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.

Sentences have beginnings and endings. To model this, we add special tokens: <s> marks the start of a sentence and </s> marks the end. These tokens let us model which words typically start sentences and which words end them.

The start marker <s> lets us compute $P(w_1|\text{<s>})$, the probability of a word starting a sentence. In our corpus, "the" starts every sentence, so $P(\text{the}|\text{<s>}) = 1.0$. The end marker </s> lets us model sentence endings: "mat," "fish," and "cat" all end sentences.

For higher-order n-grams, we add multiple start tokens. A trigram model needs two <s> tokens at the beginning to provide context for the first two words.

With n-gram probabilities estimated, we can compute the probability of any sequence. We combine the chain rule decomposition with our Markov approximation to get:

where:

• $m$: the total number of words in the sequence
• $n$: the n-gram order (e.g., 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 together all $m$ conditional probabilities

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

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 word $i$ given only the single preceding word
• The product includes $m$ terms for a sentence of $m$ words (plus the end token if we include it)

Each term uses only the single preceding word as context. For the first word in the sequence, we use the start token <s> to provide the required context. This ensures every word has a well-defined conditioning context, even at sentence boundaries.

Notice we use log probabilities. Multiplying many small probabilities leads to numerical underflow, where numbers become too small to represent in floating-point arithmetic. Taking logarithms converts products to sums, keeping values in a manageable range.

The mathematical transformation works as follows. Instead of computing a product of probabilities (which can underflow):

we compute a sum of log probabilities (which remains numerically stable):

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 negative since $P < 1$)
• The result is the log of the original sequence probability

This transformation works because of the logarithm's fundamental property: $\log(a \times b) = \log(a) + \log(b)$. The log of a product equals the sum of the logs. While individual probabilities might be 0.01 or smaller, their log values are manageable negative numbers (e.g., $\log(0.01) \approx -4.6$). Summing these values is numerically stable even for very long sequences. To recover the original probability if needed, we compute $P = \exp(\log P)$.

The visualization shows why log probabilities are essential. With an average per-word probability of 0.1, raw probabilities become vanishingly small after about 30 words, approaching the limits of floating-point representation. Log probabilities decrease linearly and remain computationally tractable for sentences of any length.

The rankings reveal what our model learned. Sentences similar to the training data ("the cat sat on the mat") get higher probabilities. Sentences with unseen bigrams ("the fish ate") may get zero probability, resulting in negative infinity log probability.

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

A single unseen bigram makes the entire sequence probability zero. This is a serious problem: perfectly valid sentences get zero probability just because our training data didn't contain every possible word combination.

This is the zero probability problem. It motivates the smoothing techniques covered in the next chapter. Raw MLE estimates are too brittle for real applications.

Let's build a complete, reusable n-gram language model class:

The NgramLanguageModel class encapsulates all the logic we've built: n-gram counting, context tracking, and probability computation. The train() method processes text and builds the count tables. The probability() method returns $P(\text{word}|\text{context})$ using MLE, and sentence_log_probability() computes the log probability of an entire sentence.

Let's train models of different orders and compare them:

The results reveal key differences between model orders. The unigram model assigns similar probabilities to all sentences because it ignores word order entirely, treating each word independently. The bigram model shows more variation, penalizing sentences with rare or unseen word transitions. The trigram model provides the finest discrimination, since it captures two-word context patterns.

Notice that some sentences receive -inf (negative infinity) log probability when they contain unseen n-grams. The sentence "the cat ate the bird" might score well with lower-order models but fail with the trigram if the specific three-word sequence never appeared in training. This illustrates the data sparsity problem: higher-order models are more expressive but require more training data.

N-gram models can generate new text by sampling words according to their conditional probabilities. Starting from the start token, we repeatedly sample the next word given the current context.

The bigram model generates sentences that reflect local word patterns from the training data. Each transition depends only on the immediately preceding word, so the model can produce grammatically plausible fragments but may lose coherence over longer spans. Notice how sentences often loop back to common patterns like "the cat" or "the dog."

Now let's generate with the trigram model, which uses two words of context:

The generated text reflects patterns in the training data. Bigram models produce locally coherent text but may wander incoherently over longer spans. Trigram models maintain coherence over slightly longer distances, but neither captures long-range dependencies like subject-verb agreement across clauses.

We can control the randomness of generation with a temperature parameter $T$. Given a probability distribution over next words, temperature scaling adjusts the distribution's "sharpness" before sampling.

The idea is to divide the log probabilities by $T$ before re-normalizing. Since log probabilities are negative (probabilities are less than 1), dividing by a small $T$ amplifies the differences between them. For example, if $\log P(w_1) = -1$ and $\log P(w_2) = -2$, dividing by $T = 0.5$ gives $-2$ and $-4$, doubling the gap. Conversely, dividing by a large $T$ shrinks differences, making the distribution more uniform.

where:

• $P(w_i)$: the original probability of word $w_i$ from the language model
• $T$: the temperature parameter (a positive real number, typically between 0.1 and 2.0)
• $P_T(w_i)$: the temperature-adjusted probability used for sampling
• $\exp$: the exponential function, which converts log probabilities back to probabilities
• $\log P(w_i) / T$: the scaled log probability (dividing by $T$ controls how much we amplify or compress differences)
• $\sum_j \exp(\log P(w_j) / T)$: the normalization constant, ensuring probabilities sum to 1

The temperature controls how "peaked" or "flat" the distribution becomes:

• $T < 1$ (low temperature): Dividing log probabilities by a small number makes differences larger, sharpening the distribution and concentrating probability on the most likely words
• $T = 1$: Uses the original probabilities unchanged
• $T > 1$ (high temperature): Dividing by a large number shrinks differences, flattening the distribution and giving rare words more chance of being selected

Lower temperatures make the model more deterministic, always choosing high-probability words. Higher temperatures increase diversity:

At low temperatures, the model gravitates toward the most common patterns. At high temperatures, it explores less likely paths and sometimes produces more creative but less coherent output.

The visualization shows how temperature reshapes probability distributions. At low temperature (0.5), the highest-probability words become even more dominant, making generation more predictable. At high temperature (1.5), the distribution flattens, giving rare words a fighting chance. This trade-off between coherence and diversity is fundamental to text generation with language models.

N-gram models can grow large. The number of possible n-grams grows exponentially with $n$. Given a vocabulary of $V$ unique words, the total number of possible n-grams is:

where:

• $V$: the vocabulary size (number of unique words)
• $n$: the n-gram order
• $V^n$: $V$ multiplied by itself $n$ times (exponential growth)

This exponential growth creates a storage challenge. For English with $V = 100{,}000$ words and $n = 3$ (trigrams), we have $100{,}000^3 = 10^{15}$ potential trigrams. Even storing just one byte per trigram would require a petabyte of memory. Fortunately, most of these combinations never occur in real text.

Most possible n-grams never occur. We store only observed n-grams using dictionaries or hash tables:

The trigram model stores more n-grams than the bigram model because it tracks longer sequences. Our toy corpus produces tiny models measured in kilobytes, but real-world models trained on billions of words can require gigabytes of storage. This makes efficient data structures essential.

For faster lookups, n-grams can be stored in a trie (prefix tree). Each path from root to node represents an n-gram prefix. Nodes store counts:

The trie efficiently retrieves counts for any prefix. Notice how "the" has a high count because it appears in every sentence, while longer n-grams like "the cat sat" are less frequent. Tries share prefixes between n-grams, reducing memory for models with many overlapping contexts. They also enable efficient prefix queries like "What words can follow 'the cat'?"

How do n-gram probabilities distribute across possible continuations? The following tables show how different contexts constrain the next word:

The distributions reveal how context constrains possibilities. After "the," many words are plausible, but after "sat," almost all probability mass concentrates on "on." Longer contexts generally produce more peaked distributions, reflecting stronger constraints.

NLTK provides built-in n-gram functionality: