Move with the arrow keys, a presentation clicker, or the buttons at the bottom left; the gear at the bottom right opens the slide settings.
The cat sat on the ____ .
You just ranked candidate words by how well they fit. A ranking of this kind can be written as a set of probabilities.
Every system in this lesson plays the same game: given the text so far, assign a probability to every possible continuation.
Part 2 continues with RNNs and transformers.
A computer stores numbers. Before a model can read text, the text is cut into small pieces called tokens; each token is mapped to a whole number, called its token ID.
A helpful analogy: tokens behave like syllables. They are larger than single letters; they are smaller than many words; together they can spell out any text.
A tokenizer carries a fixed list of tokens, called the vocabulary. The list is built from data: character sequences that appear often in real text earn their own token.
Frequent words hold a single token; rare words are spelled from several tokens. One widely used tokenizer, released with a 2019 language model, holds exactly 50,257 tokens.
The splits above are illustrative; each tokenizer learns its own cuts from its own training text.
Given the tokens so far, the player outputs a probability for every token in the vocabulary. A high probability means the token fits the context well; a low probability means it fits poorly.
Probability theory began with independent events. In 1713, Jacob Bernoulli's law of large numbers explained why averages settle down, provided that every trial, like every flip of a coin, ignores the ones before it.
For the following two centuries, mathematicians kept the assumption: averages settle when the trials stay independent.
In 1874, Francis Galton and Henry Watson asked why some family names die out, and they modeled the question as a chain: the sons of one generation carry the name into the next, so each generation depends on the one before it.
Their chain answered a practical question: if each man has some random number of sons, how likely is the name to survive forever? Dependence between the steps sat at the center of the mathematics, four decades before the poem experiment.
Around 1902, Pavel Nekrasov claimed that the law of large numbers requires independence, and he read support for free will into the claim: social statistics settle down, so the individual acts behind them, he argued, must be independent, hence freely chosen.
Markov set out to break the claim with a counterexample: a dependent sequence that still obeys the law of large numbers. He chose text as his material, because each letter of a text depends on the letters around it so plainly that no one could deny the dependence.
A mathematical quarrel produced the Markov chain; the applications arrived later.
Andrey Markov took 20,000 letters of Pushkin's poem Eugene Onegin and marked each letter as a vowel or a consonant.
He then counted transitions. In his tally: about 43 of every 100 letters were vowels; after a vowel, a vowel followed about 13 times in 100; after a consonant, a vowel followed about 66 times in 100.
Although the next letter clearly depends on the current letter, the counted sequence still obeyed the law of large numbers, so the counterexample worked. Models of this kind now carry his name.
In 1948, while founding information theory, Claude Shannon played the same game with whole words. Because no computer held English statistics yet, he sampled from books by hand: after writing a word, he opened a book at a random page, read until that word appeared again, and wrote down the word printed right after it.
Every neighboring pair above fits together, because each pair came from real text; the sentence as a whole wanders, because nothing beyond the current word steers it.
A Markov chain is a set of states joined by arrows, where each arrow carries the probability of moving to the next state. Its defining rule, called the Markov property, says the following: the probability of the next state depends only on the current state. Below, in a chain counted from a corpus of three sentences, the states are tokens.
They are counted. Take a pile of training text, called the corpus, and tally every neighboring pair of tokens:
The counting carries a guarantee: these values make the corpus itself as probable as it can be. Statisticians call it maximum likelihood estimation; it is the optimization step of the Markov chain.
Pairs never seen in the corpus get probability zero; practical systems soften the zeros with smoothing.
Counting the pairs that start with the (5 in total):
| pair | count | probability |
|---|---|---|
| the cat | 2 | 2 / 5 = 0.4 |
| the dog | 1 | 1 / 5 = 0.2 |
| the mat | 1 | 1 / 5 = 0.2 |
| the rug | 1 | 1 / 5 = 0.2 |
| total | 5 | 1.0 |
To generate, the chain repeats a single step again and again: from the current token, choose the next at random, so that each arrow wins in proportion to its probability. Random choice in proportion to probability is called sampling. Starting from the, our counted arrows cut the interval from 0 to 1 like this:
| position | what happens | move |
|---|---|---|
| the | roll 1 gives 0.57, which lands in the dog segment (0.40 to 0.60) | dog |
| dog, sat, on | no roll is needed, because each has a single arrow with probability 1.0 | sat, on, the |
| the | roll 2 gives 0.71, which lands in the mat segment (0.60 to 0.80) | mat |
| mat | a single arrow leads to the period, which ends the walk | . |
The walk spells the dog sat on the mat . Although this exact sentence appears nowhere in the corpus, every step is backed by a counted pair.
Our chain reads one token of context. To read two, the state becomes a pair of tokens, and the count table needs a row for every possible pair. With a vocabulary of 50,000 tokens:
| context the chain reads | rows the count table needs |
|---|---|
| 1 token | 50,000 |
| 2 tokens | 2,500,000,000 (2.5 billion) |
| 3 tokens | 125,000,000,000,000 (125 trillion) |
"Keep counting with longer and longer contexts." Because each added token multiplies the table by 50,000, while real text supplies examples for almost none of the longer contexts, the table grows even as the counts inside it stay at zero.
Start from a correct sentence, exactly as a book would print it:
A model that reads only nearby tokens follows cats to were; because the subject girl sits seven tokens back, the correct choice, was, depends on information far outside a short window.
Part 2: a network that reads token by token while carrying a learned memory; then the transformer, which reads the whole window at once.
Slides: Mehmet Kerem Turkcan, Center for Smart Streetscapes, Columbia University; keremturkcan.com; mkt2126@columbia.edu