Counting letters

In the last chapter we agreed on what a language model does: it looks at some text and gives every possible continuation a probability. Sprout does this with 17 million numbers and a transformer. We are going to start from the other end, with the simplest model that still deserves the name. It has no neurons, no training and no clever maths. It only counts.

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

A computer doesn't know what a letter is. It only knows numbers. So the very first step of every language model, from our little table to GPT, is to agree on an alphabet and give each of its symbols a number.

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 its own number instead. Then the model would see "cat" as one symbol, not three. But a list of all words is huge and never complete. Every name, typo and new word needs its own entry, and a word the list doesn't know cannot be read at all. Letters are the opposite: 97 symbols cover any English text, but the model has to work harder to see the words in them. Sprout's final version uses a compromise, frequent chunks of text called tokens (chapter 6 is about them). For the first chapters, though, letters are perfect: the tables are small enough to look at in full.

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.

The counting itself is almost embarrassingly simple. Here it is in plain Python, on a text short enough to check by eye. Press Run; you can also replace the text with your own.

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

Counts are not a model yet. The pair "th" occurred 829,367 times. Is that a lot? It depends on how many chances it had, that is, how many "t"s there were: 2,702,151. So out of every hundred "t"s, about 31 were followed by an "h". That share is exactly what we call a probability: how often something happens compared with how often it could have happened.

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.

("Bigram" means "two letters": the model only ever looks at pairs. Tables over three letters are called trigrams; in general, 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.

What we need is a loaded die, where every side has its own weight. After "h" the die has 42 sides (that many different symbols ever followed an "h"), and side "e" alone takes up more than half of it. But how does a computer roll such a thing? All it can do is produce a random number $u$, spread evenly between 0 and 1.

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". The bars creep right up to the ticks: over many rolls, how often a side comes up approaches its probability. That is the law of large numbers, and it is also why counting frequencies over 41 million letters gives us trustworthy probabilities in the first place.

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".

Still, pause and appreciate this. Nobody told the table where spaces go, that sentences start with a capital letter, or that "e" is the most common letter. All of this was in the counts.

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.

That is not just a memory problem. Most of those cells would be empty, because most eight-letter combinations never occur in any corpus, even a huge one, and the table would have nothing to say about a sequence it has not seen exactly. What we want is a model that generalises: one that has seen "the cat sat" and "the dog sat" and suspects that "the fox sat" is fine too. Counting cannot do that. Neural networks can, and that is where the next few chapters are heading.

Why can't we simply count a table with eight letters of context, the way we did with one?

Such a table would not fit into the memory of any computer Eight letters are always enough; nothing else is needed 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.