What probability does a computer give a 150-word sentence?

Part 1 ended on one word: the model read the cat sat on the and said mat, 70%. A model never stops at one word, though. It writes whole paragraphs, and training scores whole documents, so sooner or later it has to say how likely an entire sentence is.

That takes two rules, and MML says they are the only two there are: the sum rule and the product rule. This part builds both from one table of twenty phrases, then multiplies its way through a sentence until it hits a wall.

The puzzle A model gives every word of a 150-word sentence probability 0.5, which is generous. What probability does float32 give the whole sentence?
The 30-second version Exactly 0. A sentence's probability is the product of its words' probabilities, each given the words before it, so this one is 0.5¹⁵⁰ ≈ 7 × 10⁻⁴⁶. Float32 cannot hold anything below 2⁻¹⁴⁹ ≈ 1.4 × 10⁻⁴⁵, so the product rounds to zero and stays there. A real 1,000-token document has probability around e⁻²⁰⁰⁰, too small even for float64. So every language model works with log probabilities: the log turns the product into a sum, and the training loss into a sum of per-word losses.

What is a joint distribution?

Here is the corpus: twenty two-word phrases, the cat, a dog, my dog and so on. Count them in a table, first word down the side and second word across the top, the way MML’s Example 6.2 does.

Pick one of the twenty at random. The chance it is the cat is its count over the total (MML eq. 6.9):

\[p(\textit{the}, \textit{cat}) = \frac{n_{\textit{the},\,\textit{cat}}}{N} = \frac{5}{20} = 0.25\]

That is a joint probability: both words at once. The nine cells are one distribution with nine outcomes, and together they add up to 1.

One cell is empty. Nobody in the corpus ever wrote my mat. Remember that zero.

How do you forget one of the words?

Add it away. To get the chance that the second word is cat, whatever came first, add down the cat column. That is MML’s sum rule (eq. 6.20), also called marginalisation:

\[p(y) = \sum_x p(x, y)\]

Before you watch the columns add up, guess which second word is more common overall.

Cat and dog tie at 8 each. The prefers cat, but a and my prefer dog, and the sum weighs each row by how often it occurs. The margins are distributions too: $p(\textit{cat}) = 0.4$, and the first words split 0.5, 0.3, 0.2.

Here the sum is three additions. MML warns that this is where the cost of probability hides. Ask a real model how likely it is that the 500th word of a document is mat, whatever the first 499 were, and the sum runs over 128,256⁴⁹⁹ possible beginnings.

What does reading the first word change?

Everything after it. Once you have read the, only its 10 phrases are still possible. Take that row on its own and divide by its total. That is conditioning (MML eq. 6.13): same counts, a new denominator.

\[p(\textit{cat} \mid \textit{the}) = \frac{5}{10} = 0.5\]

Reading the moved cat from 0.4 to 0.5. Reading my would drop it to 0.25. This is all a language model’s prediction is: the distribution of the next word, given what it has read.

Multiply the denominator back in and the joint returns. That is the product rule (eq. 6.22), and it works in either order:

\[p(\textit{the}, \textit{cat}) = p(\textit{cat} \mid \textit{the})\,p(\textit{the}) = 0.5 \times 0.5 = p(\textit{the} \mid \textit{cat})\,p(\textit{cat}) = 0.625 \times 0.4\]

Two ways to build the same 0.25. Part 3 is nothing more than that equality, solved for one of its pieces.

When does the first word tell you nothing?

When every row splits the same way as the whole corpus. Then reading the first word changes nothing, and every joint is just the product of two margins. That is MML’s independence (Definition 6.10):

\[p(x, y) = p(x)\,p(y)\]

So test the table. If the words were independent, how many of the twenty phrases would be the cat?

Four: $20 \times 0.5 \times 0.4$. The corpus has five, so these words are not independent. In the independent version every row splits 0.4 : 0.4 : 0.2 and the boundaries line up.

Language is about as far from independent as data gets, which is the whole reason a model reads the context. A bag-of-words model that treats words as independent throws away exactly what this table shows.

How does a model score a whole sentence?

By using the product rule again and again. Split off the last word, $p(\text{all}) = p(\text{last} \mid \text{the rest})\,p(\text{the rest})$, and repeat until one word is left:

\[p(w_1, \dots, w_T) = p(w_1)\,p(w_2 \mid w_1)\,p(w_3 \mid w_1, w_2)\cdots p(w_T \mid w_1, \dots, w_{T-1})\]

This is the chain rule of probability, and it is exactly what a language model computes. Each factor is one next-word prediction, the kind Part 1’s model made. Nothing is assumed independent: every word is conditioned on all the words before it.

The first two factors of the sentence below come straight from the table, $p(\textit{the}) = 10/20$ and $p(\textit{cat} \mid \textit{the}) = 5/10$. The last is Part 1’s 0.7. Guess the total before it multiplies out.

0.0504, from six words that each got at least 0.4. Every factor is at most 1, so every word can only shrink the sentence.

Why does every language model work in logs?

Because the product never stops shrinking. Six words gave 0.05. Here is the puzzle’s sentence, 150 words at 0.5 each, multiplied out the way a GPU stores numbers.

Float32 gives up at word 150, and from then on every later word multiplies a zero. A real document is worse: at a loss of 2 nats per token, float32 hits zero by token 53 and float64 by token 373.

The way out is the log, which turns the product into a sum:

\[\log p(w_1, \dots, w_T) = \sum_{t=1}^{T} \log p(w_t \mid w_1, \dots, w_{t-1})\]

Each term’s negative, $-\log p$, is that word’s surprise. Which word in the toy sentence surprises the model most?

The 150-word sentence that float32 called 0 is a surprise of 104 nats. The 1,000-token document is 2,000 nats. Both are ordinary numbers. Averaged over the words, this sum is the training loss, and Part 6 is about why.

What does the table say about a phrase it never saw?

That it is impossible. My mat never appears, so a model built by counting says $p(\textit{mat} \mid \textit{my}) = 0/4 = 0$.

Every sentence containing my mat then gets probability exactly 0, however likely its other words are, and its log is minus infinity. One unseen pair sinks the whole sentence.

Four phrases starting with my are not much evidence for calling anything impossible. The fix is to hold a belief about $p(\textit{mat} \mid \textit{my})$ before you start counting, and update it as the counts come in. That is Bayes’ rule, and Part 3 turns the question around.

Rapid fire: can you do these from memory?

  1. From the table: what are p(a, dog), p(dog) and p(dog | a)?
  2. Say the sum rule and the product rule in words, without symbols.
  3. p(cat | the) = 0.5 and p(the) = 0.5. What is p(the, cat)? If p(cat) = 0.4, what is p(the | cat)?
  4. How do you tell from a table of counts whether two variables are independent?
  5. Write the probability of a four-word sentence as a product of conditionals. What independence does it assume?
  6. Why does a sentence's probability shrink with every word, even when every word is likely?
  7. Why does a 150-word sentence at 0.5 a word come out as exactly 0 in float32, and what do models store instead?
  8. What goes wrong when a counting model has never seen a pair of words, and why is four observations too few to fix it by counting alone?

Where can you go deeper?

Everything here is from Chapter 6, Probability and Distributions, of Mathematics for Machine Learning by Deisenroth, Faisal and Ong (Cambridge University Press, 2020), free at mml-book.github.io:

  • §6.2.1, discrete probabilities: the joint as a count over a total (eq. 6.9), and Example 6.2 with Figure 6.2’s table, where marginals are row and column sums (6.10, 6.11) and conditionals are a cell over its row or column total (6.13, 6.14). This part’s table is a small copy of it.
  • §6.3, the sum rule (6.20), with the remark on why the sums are the expensive part, and the product rule (6.22). Bayes’ theorem (6.23) is in the same section, and in Part 3.
  • §6.4.5, statistical independence (Definition 6.10, eq. 6.53), and conditional independence (Definition 6.11) for when a third variable is known.