Counting letters

Let’s start with a question we can answer without a neural network: which letter most often follows “t”? We will count neighbouring pairs in a text and turn their frequencies into probabilities. The result is a small language model: a table that can choose the next letter. Counting is its training procedure. We find the parameters directly from the data, without taking repeated optimisation steps.

Here is the idea. Taking everything that came before into account is hard, so let's cheat and look at just the last letter. Suppose the text so far ends in a "t". What comes next? You already have a hunch: quite often an "h" ("the", "that", "then"), sometimes a space, sometimes an "o". You never learned this rule; you just read a lot. A computer can read a lot too, and it is much better at keeping score.

Letters become numbers

The program needs numbers to perform its calculations. First we choose the units of text our model will use and give each unit an identifier. In this chapter, each unit is a single character. Later we will use tokens that can contain several characters.

For the first few chapters of this course, Sprout's alphabet has 97 symbols: the 95 printable characters of a standard English keyboard (the space, punctuation, digits, upper- and lower-case Latin letters), the newline, and one special mark with the number 0. We will draw it as ◆. It stands between texts, in front of the first letter of every story and after its last one. Thanks to it, the model can learn how stories begin, and it can also say "this is the end".

Type something into the box and watch the text turn into what the model actually receives.

Why letters, and not whole words?

We could give every word a number, making “cat” one unit rather than three. But a new surname or a typo might be missing from the vocabulary. We would need a fallback, such as splitting the word into smaller pieces. For now, we will use a small set of characters. It covers our cleaned English text, but not every possible English text: curly quotation marks and accented letters, for example, are outside it. The advantage is that we can examine the entire table. Chapter 6 introduces a more general tokenizer.

Two things are worth noticing. First, "a" and "A" are different symbols, 67 and 35: to the model they are as different as "a" and "?". Nothing tells it that one is the capital form of the other; if that link matters, it has to discover it from the data. Second, the numbers themselves mean nothing. "a" being 67 does not make it "bigger" than "A". The numbers are just names, like seat numbers in a theatre, and we could have handed them out in any other order.

Who follows whom

Let's start with something tiny: the word banana. Put the ◆ marks around it, ◆banana◆, and write out every pair of neighbours: ◆b, ba, an, na, an, na, a◆. Seven pairs. Now sort them by the first letter:

after…	came…
◆	b once
b	a once
a	n twice, ◆ once
n	a twice

That's it: this table is a complete language model of the word "banana". It knows that a word starts with "b", that "n" is always followed by "a", and that after "a" there is either an "n" or the end.

Now let's do exactly the same on a larger scale. We took 41.3 million letters of the stories and dialogues Sprout learns from, 39,184 texts in all, and counted every pair of neighbours. A table with a row and a column for each of the 97 symbols has 97 × 97 = 9,409 cells. Here it is. Rows are the previous letter, columns the next one, and the brighter the cell, the more likely the pair.

Spend a minute with the map; it is full of little stories about English.

• q is almost always followed by u. Out of 13,061 "q"s, 13,003 were followed by a "u": 99.6%. Row "q" is almost empty: one bright cell and a few pale specks.
• The most frequent pair is "e␣", an "e" at the end of a word: 1,312,444 times, 3.2% of all pairs. Close behind come "he" and "␣t". Think "the".
• Punctuation and capitals have habits. A comma is followed by a space 96.5% of the time. A capital T is followed by "h" in 82.3% of cases: "The", "They", "There".
• A quarter of all stories begin with a capital O. In row ◆, "O" gets 25.4%: "Once upon a time…", "One day…".
• Most cells are empty. 7,051 of the 9,409 pairs never occurred at all, three quarters of the table. Even among lower-case letters and the space, 136 of the 729 pairs are missing: "jj", "qa", "fq"… Nor are there ever two spaces in a row: the corpus was cleaned before training, and double spaces were removed.

Let’s count pairs in a short passage whose results we can check by eye. The dictionary counts stores how many times each pair appears: every new occurrence adds one. Press Run, then replace the passage with your own and compare the results.

text = """once upon a time there was a little cat. the cat liked to sit in the sun. one day the cat saw a bird in the tree.""" counts = {} # (previous, next) -> how many times for a, b in zip(text, text[1:]): # every letter with the one right after it counts[(a, b)] = counts.get((a, b), 0) + 1 print(len(text), 'letters,', len(counts), 'different pairs') for (a, b), n in sorted(counts.items(), key=lambda kv: -kv[1])[:6]: print(repr(a + b), n)

zip(text, text[1:]) is a neat trick: it walks through the text and its copy shifted by one letter at the same time, so each step gives us a letter together with its right-hand neighbour.

From counts to probabilities

The pair “th” occurred 829,367 times. To judge how common that is, we need to know how many opportunities there were for a character to follow “t”: 2,702,151. About 31 out of every hundred “t”s were followed by “h”. That is an observed frequency. Our model uses it to estimate a probability for the next character. A different corpus could give a different estimate.

We want the probability of the next letter $b$ given that the previous one was $a$. It is written $p(b \mid a)$, and in our table it is computed in one line:

$$p(b \mid a) = \frac{\text{count}(a, b)}{\text{count}(a)}$$

On top is how many times the pair $a b$ occurred; underneath, how many times $a$ occurred at all (with anything after it). For our "t": $p(\text{h} \mid \text{t}) = 829\,367 / 2\,702\,151 \approx 0.307$. For banana: $p(\text{n} \mid \text{a}) = 2/3$ and $p(\blacklozenge \mid \text{a}) = 1/3$.

This kind of probability is called conditional. We don't ask how likely "h" is in general, but how likely it is on condition that a "t" has just appeared. That makes a big difference. Among all 41.3 million pairs, "th" makes up only 2.0%. Yet once we know a "t" is there, the chance of an "h" jumps to 30.7%. Knowing what came before is the whole point of a language model.

A bigram is a sequence of two units of text. Here the units are characters, but they could also be words, as in “little cat”. Sequences of three units are trigrams; the general term is n-grams.

There is one catch. A zero in the table means "impossible". Is "jj" really impossible? The word "hajj" exists, just not in children's stories. A model that swears something can never happen will be in trouble the moment it does. So the real table inside Sprout adds one to every cell before dividing:

$$p(b \mid a) = \frac{\text{count}(a, b) + 1}{\text{count}(a) + 97}$$

This is called add-one (Laplace) smoothing. For frequent pairs it changes practically nothing: 829,368 / 2,702,248 is still 30.7%. But no pair is completely forbidden any more. You'll see why that matters so much in the next chapter, where a zero turns into infinity.

After "q", the letter "u" came 13,003 times; "q" appeared 13,061 times; the corpus has 41.3 million letters. What is p(u | q)?

13,003 / 41.3 million: tiny, about 0.03% 13,003 / 13,061: about 99.6% Exactly 1: after "q" there is always a "u"

A conditional probability divides by the number of chances, that is, by how many times "q" occurred, not by the size of the whole corpus. And it is not exactly one: "q" was followed by a colon 25 times, in dialogues with characters called Eriq, Tariq and Tyriq ("Tariq: So…"), and by a handful of other symbols.

A loaded die

The table tells us how likely every next letter is. To make it write, we have to actually choose one. We could always take the most likely letter, but then after "t" we'd always write "h", after "h" always "e", after "e" always a space… and get "the the the the" forever. We want to pick at random, but in proportion: "h" after "t" three times out of ten, a space two and a half times out of ten, and so on.

Think of this choice as rolling a die whose outcomes have different probabilities. In the raw counts, 42 different characters followed “h”, and “e” accounted for more than half of those occurrences. Smoothing gives all 97 characters a small chance. To sample from this distribution, we start with a uniform pseudorandom number $u$ between 0 and 1. Standard programming libraries provide generators for these numbers.

The trick is to lay the probabilities out end to end along a line from 0 to 1. The first letter gets the segment from 0 to $p_1$, the second from $p_1$ to $p_1 + p_2$, and so on: the edges of the segments are the cumulative sums of the probabilities. Now drop the needle $u$ onto the line. The chance that it lands in a segment is exactly that segment's length, which is the letter's probability. The die has been rolled.

Roll a few times by hand, then press “×10,000”. After many independent rolls, the observed frequencies will usually be close to the assigned probabilities, though they will not match exactly. This illustrates the law of large numbers. Text needs more care: neighbouring letters are dependent, and a collection of children’s stories does not represent an entire language. Its frequencies give us a useful model of this corpus, not a universal table of English.

In Python the whole die fits in a few lines. The standard library also has a ready-made version, random.choices, which takes the same walk along the cumulative sums. This cell uses the pairs counted by the previous one (the cells on this page share one Python session, like a notebook).

import random def next_probs(a): row = {b: n for (x, b), n in counts.items() if x == a} total = sum(row.values()) # how many times a was followed by anything return {b: n / total for b, n in row.items()} def roll(probs): u = random.random() # a random number from 0 to 1 total = 0.0 for letter, p in probs.items(): # walk the cumulative sums total += p if u < total: return letter return letter # u fell into a rounding crack at the very end print(next_probs('t')) print([roll(next_probs('t')) for _ in range(12)]) print(random.choices('abc', weights=[5, 3, 2], k=12))

Letter by letter

Now we have everything we need to write. We start with the mark ◆ and roll the die of row ◆, which gives us the first letter. Then we roll the die for that letter's row, and so on. Every new letter chooses the die for the next roll. When the die comes up ◆, the story is over.

What comes out is babble, but interesting babble. One of our runs began like this: "Frthendd, aced. tre sedsck.. oale, ateyinet thee prerootosal s thu fear frime". The "words" have plausible lengths and are separated by spaces. After a full stop there is a space and often a capital. Quotes open and close, "the" and "he" show up. There is no meaning, of course: the model remembers just one letter, so it doesn't know whether it is in the middle of a word or at the end of a sentence. After an "h", it has no idea whether that "h" came from "th" or from "sh".

Even these short dependencies reveal some habits of the text: common letter pairs, spaces after punctuation, and frequent endings. But the table has not learned “put a capital after a full stop and a space”. By the time it reaches the space, it has forgotten the full stop. Nor can it remember an opening quotation mark until the closing one arrives. Resembling text is not the same as keeping track of its structure.

The whole table in numpy

Dictionaries are fine for a sentence, but for 97 × 97 numbers we want a proper table: a numpy array. The cell below loads the very counts you saw on the heatmap (22 KB of JSON), turns them into probabilities with Laplace's +1 and writes a few hundred letters.

import json import numpy as np try: from pyodide.http import open_url # in the browser data = json.load(open_url('/llm/data/bigram-counts.json')) except ImportError: # on your own computer data = json.load(open('bigram-counts.json')) ALPHABET = data['alphabet'] # '\n' and the 95 printable ASCII characters N = np.array(data['counts']) # 97 x 97; row and column 0 are the start/end mark P = (N + 1) / (N + 1).sum(1, keepdims=True) # +1 in every cell, then each row sums to 1 t, h = ALPHABET.index('t') + 1, ALPHABET.index('h') + 1 print(N.sum(), 'pairs; p(h | t) =', round(P[t, h], 4), '; row sums:', P.sum(1)[:4]) rng = np.random.default_rng() ids = [0] # start with the start mark while len(ids) < 300: nxt = rng.choice(97, p=P[ids[-1]]) # roll the die of the last letter's row if nxt == 0: break # the mark again: the story is over ids.append(nxt) print(''.join(ALPHABET[i - 1] for i in ids[1:]))

The line with P is the whole normalisation. (N + 1).sum(1, keepdims=True) sums every row and keeps the result as a column of 97 numbers; dividing the 97 × 97 table by that column divides each row by its own sum (numpy calls this broadcasting). rng.choice(97, p=…) is our loaded die: inside, it walks the same cumulative sums.

And here is the function that built the real table for Sprout, from the course code snapshots.py. It reads 41.3 million letters, counts all the pairs in a single line with np.add.at (for every position it adds one to the cell "this letter, next letter"), normalises with +1 and saves the result as a model file the browser can run.

def bigram(args): ids = char_corpus(args.data, args.chars) counts = np.zeros((V, V), dtype=np.int64) np.add.at(counts, (ids[:-1], ids[1:]), 1) probs = (counts + 1) / (counts + 1).sum(1, keepdims=True) logits = np.log(probs).astype(np.float32) state = {'embed.weight': torch.from_numpy(logits)} cfg = {'vocab_size': V, 'context': 1} pack(state, cfg, {'kind': 'mlp', 'name': 'bigram-char', 'chars': int(len(ids))}, f'{args.out}/models/bigram-char.bin', quantize=False) with open(f'{args.out}/data/bigram-counts.json', 'w') as f: json.dump({'alphabet': ALPHABET, 'counts': counts.tolist(), 'chars': int(len(ids))}, f, separators=(',', ':')) nll = -np.log(probs[ids[:-1], ids[1:]]).mean() print(f'bigram: {len(ids)} letters, loss {nll:.4f} nats/letter')

Two lines in it still look mysterious. The table is stored as logarithms of probabilities, np.log(probs), and at the end a "loss" of 2.3650 "nats per letter" is printed. Both are the subject of the next chapter, where that number turns out to be the answer to "how good is this model?"

What one letter can't see

Our table is simple and fast, but it has a hard limit: it remembers only one letter. The obvious fix is to count longer contexts. Look at the two previous letters, and the table needs a row for every pair of them: 97 × 97 rows with 97 columns each, 912,673 cells. Three letters of context give 88.5 million cells, already more than the 41.3 million letters we counted. Eight letters give about $7.6 \cdot 10^{17}$ cells.

Table size is only part of the problem. Most long combinations never occur in our corpus, so a new context has no observations of its own to look up. Statistical models can soften this problem with smoothing and by falling back to shorter contexts. A neural network takes another approach: shared parameters let it transfer patterns between similar contexts. After seeing “the cat sat” and “the dog sat”, for example, it may assign a higher probability to a similar construction with “fox”. The next few chapters explore this kind of generalisation.

Why would an eight-character context table still struggle, even with unlimited memory?

Such a table would not fit into the memory of any computer Counting tens of millions of eight-character windows would be too slow Most eight-letter contexts would never be seen even once, so the table would know nothing about them

Memory is a real problem too, but even an infinite memory would not help: with $7.6 \cdot 10^{17}$ cells and only billions of letters of text, almost every cell would stay empty. We need a model that can carry over what it learned from similar contexts, not just look up exact matches.

One more question is left open. We looked at the babble and said "sort of like English". That's an impression, not a measurement. How do we put a number on how good a model is, so that we can compare two models, or watch a model improve during training? That is what the next chapter is about.

Sprout right now

Sprout has its first real model: the table from this chapter, 9,409 probabilities, running right in your browser. It writes letter by letter, rolling a new loaded die every time. Try any beginning you like: only its last letter matters, so "Once upon a time" and "I like" start from the same die, the one for "e". A beginning that ends in "Q" is a good test: nine times out of ten the next letter is "u". In the next chapter we measure exactly how bad this model is, and turn that into a number that training can push down.