Estimating n-gram probabilities with maximum likelihood

Suppose the word "Chinese" occurs 400 times in a corpus of one million words. What probability should a unigram model give it? The obvious answer is 400 / 1,000,000 = 0.0004, and that obvious answer has a name: it is the maximum likelihood estimate. Among every possible value you could pick, 0.0004 is the one that makes the observed data, 400 occurrences in a million draws, most probable. SLP3 is careful about what this does and does not mean: it is not a claim that the "true" probability of Chinese in all English is 0.0004. It is the best fit to this one training set.

Stated generally, maximum likelihood chooses the parameters of a model M that maximize P(T | M), the probability of the training set T. For a language model made of n-gram probabilities, the maximizing parameters turn out to be relative frequencies: count how often something happened and normalize, meaning divide by a total so the results lie between 0 and 1 and sum to 1.

From counts to a conditional probability

A Bigram model needs P(w_n | w_(n-1)): given the previous word, how likely is each next word? The relative frequency is the count of the pair divided by the total count of all pairs that start with the same previous word. That is SLP3 equation 3.10:

The denominator looks awkward, but it collapses. Walk through the corpus and look at every occurrence of the word w_(n-1). Each occurrence is immediately followed by exactly one word, so it starts exactly one bigram. Summing the bigram counts over all possible followers therefore just counts the occurrences of w_(n-1) itself. The only occurrence that could break this is a word at the very end of a sentence, which has no follower, and closing every sentence with </s> fixes this too: the last real word is followed by the end token, so it too starts a bigram. The result is equation 3.11:

It helps to see what the wrong denominator would give. If you divided C(w_(n-1) w_n) by the total number of bigrams N in the corpus, you would get the joint probability P(w_(n-1), w_n): how often this particular pair occurs among all pairs. That is a perfectly good number, but it answers a different question. All the joint values together sum to 1, while what theChain rule of probability needs is a distribution over next words for a fixed history.

The best way to make equation 3.11 automatic is to run it once by hand on a corpus small enough to hold in your head. SLP3 uses three sentences from Dr. Seuss, each wrapped in sentence boundary tokens:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

Now try it on your own data. The builder below pads every line, fills the count matrix and the MLE matrix, and scores any sentence as a product and as a sum of natural logs. Load the I am Sam preset and check the numbers above, then type a sentence containing a Bigram the corpus never saw and watch the product collapse to zero.

From bigrams to any N

Nothing in the recipe depends on the history being one word. For an n-gram model, the Markov assumption keeps the last N - 1 words as the history, and the estimate is the count of the full n-gram divided by the count of its prefix (equation 3.12):

For a Trigram, P(Sam | I am) is C(I am Sam) / C(I am). In the toy corpus that is 1/2: "I am" occurs twice, followed once by Sam and once by </s>. The price of the longer history is Sparsity. With a vocabulary of V words there are V^(N-1) possible histories, and each needs enough occurrences for its row of fractions to mean anything. The rows get thinner fast.

In the Berkeley Restaurant Project corpus, the word i occurs 2533 times and the pair "i want" occurs 827 times. So the maximum likelihood estimate is P(want | i) = 827 / 2533 = 0.33: a third of the time a user of this system says i, the next word is want. That single division is all there is to reading a real Bigram table.

BeRP was a spoken question-answering system from the 1990s that answered questions about a database of restaurants in Berkeley, California. Its transcripts are exactly the sort of text an assistant hears: can you tell me about any good cantonese restaurants close by, i'm looking for a good place to eat breakfast. SLP3 uses 9332 sentences with a vocabulary of V = 1446 and shows an 8 by 8 slice of the bigram table for eight hand-picked words.

Read the table as row then column: the row is the history and the column is the next word. The 827 in row i, column want means want followed i 827 times. To turn counts into probabilities, divide every cell in a row by that row word's unigram count. Row i is divided by 2533, row want by 927, row to by 2417, and so on:

Now look at the zeros. These eight words were chosen because they cohere, they are the words of "i want to eat chinese food" plus two neighbors, and still 32 of the 64 cells are zero. The full table has 1446 x 1446, about 2.09 million, cells, filled from only 9332sentences, so the overwhelming majority of the full table must be zero. That is Sparsity seen directly, and some of those zeros (chinese to and lunch to are both zero, yet "chinese to go" is ordinary English, while a zero for i lunch reflects grammar) are accidents of a small sample rather than facts about English.

With a table in hand, scoring a sentence is mechanical. The Chain rule of probability writes the sentence probability as a product of next-word probabilities, and the Markov assumption cuts each history down to one word. For "i want english food", with the boundary tokens included, that is five factors:

Four of the five factors lie between 0.25 and 0.68. The fifth, 0.0011, is what makes the sentence improbable: the running product falls from 0.0825 to about 0.00009 at that single step. A sentence probability is dominated by its rarest transition.

What the numbers know

The table was built by counting, yet it already encodes several kinds of knowledge. Some is syntactic: after to, the high-probability words are verbs (P(eat | to) = 0.28), and after eat SLP3 notes that what follows is usually a noun or an adjective (lunch, chinese). Some is about the task: sentences tend to start with i, and "i want" is how people talk to an assistant. Some is cultural: the corpus makes Chinese food much more probable than English food, compare P(english | want) = 0.0011 with P(chinese | want) = 0.0065.

Multiply 400 probabilities of 0.1 in Python and the answer is exactly 0.0. The true value, 10^-400, is far below the smallest positive normalized double, 2.2 x 10^-308, and even below the smallest subnormal, about 5 x 10^-324, so the hardware rounds it to zero. Four hundred tokens is a paragraph, not a book. Yet the logarithm of the same product is simply 400 x ln 0.1 = -921.03, an unremarkable number.

This failure is called numerical underflow, and SLP3 gives it as the reason language models always work with log probabilities: probabilities are at most 1, so the more of them you multiply, the smaller the product gets. The identity that saves us is that the log of a product is the sum of the logs (equation 3.13):

import math, sys

print(0.1 ** 400)
print(400 * math.log(0.1))
print(sys.float_info.min, math.ulp(0.0))

factors = [0.25, 0.33, 0.0011, 0.5, 0.68]
log_p = sum(math.log(p) for p in factors)
print(log_p, math.exp(log_p))

The script prints 0.0, then -921.034..., then 2.2250738585072014e-308 and 5e-324, then -10.386 and 3.0855e-05. Note that math.log is the natural log unless you pass a base.

Longer context

With enough data, a bigram history is too short. Production systems use Trigram, 4-gram and 5-gram models, and the recipe is equation 3.12 again. The first words of a sentence need a full-length history, so a model of order N prepends N - 1 start tokens. For a trigram that is two, and the first word is scored as P(I | <s> <s>).

The tradeoff is direct. Each extra word of context makes predictions more specific and the generated text more fluent, but multiplies the number of possible histories by V, so each history is seen less often and the table fills with zeros. On a small corpus a high-order MLE model has almost one continuation per history and simply copies training sentences, the Overfitting that Part 06 shows with Shakespeare samples.

At web scale the balance shifts. Google's Web 1T 5-gram corpus counted n-grams over about one trillion tokens, with 13,588,391 unigram types and 1,176,470,663 distinct five-grams. Brants and colleagues in 2007 trained on two trillion tokens, about 300 billion n-grams, with the stupid backoff scheme you will meet in Part 07. Infini-gram (2024) drops the fixed N entirely: it indexes five trillion tokens with suffix arrays and computes counts for an n-gram of any length at query time. Toolkits like KenLM make large models fit in memory by storing log10 probabilities, quantizing them to 4 to 8 bits, hashing words to 64-bit integers, storing n-grams in reverse tries, and pruning rare n-grams.