Ch 1. Predicting by counting

Once everything is counted, each word’s counts turn into chances: after little, the three followers each get one in three. Pick a word in the widget to see its chances as bars. To make up text, start with a word, pick the next one using those chances, and repeat.

Once everything is counted, each row turns into probabilities: divide each count by the row’s total. That’s all the model knows. Pick a word in the widget to see its row as bars.

To generate text, start with a word, spin for the next one using those probabilities, then repeat with the new word. Claude Shannon generated English this way in 1948, choosing each word based only on the one before it.^[2][2]

The counting rule

As a formula, the bigram model’s chance for the next word is

where $w_{i-1}$ is the word just read, $w_i$ is a candidate next word, $C(w_{i-1}{w}_i)$ is how many times that pair appears in the training text, and $C(w_{i-1})$ is how many times $w_{i-1}$ appears with any word after it. For little, $C(\text{little lamb})=1$ and $C(\text{little})=3$, so $P(\text{lamb}|\text{little})=1/3$. These are the chances that make the training text as likely as possible.^[1]

Real n-gram models look further back (a trigram uses the last two words) and deal with pairs they never saw. Here, any unseen pair gets a chance of 0, and since a sentence’s chance is its words’ chances multiplied, one new pair makes the whole sentence impossible. Smoothing moves a little probability onto unseen pairs. The simplest version adds one to every count:

where $V$ is the number of different words.^[1]

Counting also stops scaling. With GPT-2’s 50,257 tokens, a table of every pair would have about 2.5 billion cells, and a table of every triple about 127 trillion. Bengio and colleagues called this the curse of dimensionality, and proposed learning to compute a prediction instead of looking one up.^[3]