ml.lab
Python sleeps until you run code
07 Recurrent networks

Lesson 2 of 5

Predicting the next character

A character language model turns every hidden state into a probability for each possible next character, and it is trained to make the real text probable. The loss is the average cross-entropy, the same objective used to pretrain GPT-style models.

About 70 minutes
By the end you can
  • Write the loss of a character language model and show that it is the negative log-probability of the text, per character.

  • Read any loss as a perplexity, the number of equally likely choices it corresponds to.

  • Build a vocabulary, encode text as ids, and cut training windows whose targets are the inputs shifted by one.

  • Explain teacher forcing and why one forward pass over a window gives a prediction at every position.

  • Compute honest baselines (uniform, unigram and bigram cross-entropy) that a trained model has to beat.

Read this and say what comes next: "to be, or not to b". Almost certainly "e". Now this: "First Citizen:" followed by a newline. Here many characters are possible, although a capital letter is likely. A language model is a machine that answers "what comes next" with probabilities: a number for every possible next character, adding up to 1.

That is all a language model is, and it is also what the largest models do. The big picture described a language model as a function from a sequence to a probability distribution over the next token. This lesson makes that concrete with the RNN from the previous lesson. We turn its outputs into probabilities, define the loss, prepare the Shakespeare text as training data, and measure the baselines a real model has to beat. Writing text with the model is the next lesson, and training it is the one after, backpropagation through time.

A probability for every next character

The RNN gives us a state ht\mathbf{h}_t after every character. A language model needs probabilities, so the first job is to turn a state into a probability for each possible next character.

At step tt the RNN has read the characters up to and including ctc_t (the tt-th character of the text) and holds the state ht\mathbf{h}_t. Its output layer produces one score, a logit, for each of the VV characters in the vocabulary, and a softmax turns the scores into probabilities:

zt=Whyht+by,pt(k)=ezt,k∑j=1Vezt,j.\mathbf{z}_t = \mathbf{W}_{hy}\mathbf{h}_t + \mathbf{b}_y, \qquad p_t(k) = \frac{e^{z_{t,k}}}{\sum_{j=1}^{V} e^{z_{t,j}}} .

Here zt,kz_{t,k} is entry kk of zt\mathbf{z}_t, and pt(k)p_t(k) is the model's probability that the next character, ct+1c_{t+1}, is character kk. Each eze^{z} is positive, and dividing by their sum makes them add up to 1. The softmax, its numerically stable form and its gradient are the subject of softmax and cross-entropy in module 6; nothing about them changes here.

The loss at step tt is the cross-entropy with the character that actually came next: the negative log of the probability the model gave it. Writing yty_t for the id of ct+1c_{t+1}, the target at step tt,

ℓt=−ln⁡pt(yt),L=1T∑t=1Tℓt.\ell_t = -\ln p_t(y_t), \qquad L = \frac{1}{T}\sum_{t=1}^{T} \ell_t .

If the model gave the right character probability 1, ℓt=−ln⁡1=0\ell_t = -\ln 1 = 0. If it gave it 0.01, ℓt=−ln⁡0.01≈4.6\ell_t = -\ln 0.01 \approx 4.6. The loss LL is the average over all TT predictions in the text. Its unit is the nat (because the log is natural); divide by ln⁡2\ln 2 to get bits.

A worked example. After "to b", suppose the model gives five candidates the logits (2,0.5,0.3,−0.5,−1)(2,\allowbreak 0.5,\allowbreak 0.3,\allowbreak -0.5,\allowbreak -1) for (e, a, o, i, y); a real model scores all 60 characters, but five keep the arithmetic short. Exponentiate each logit:

e2=7.3891,e0.5=1.6487,e0.3=1.3499,e−0.5=0.6065,e−1=0.3679.e^{2} = 7.3891, \quad e^{0.5} = 1.6487, \quad e^{0.3} = 1.3499, \quad e^{-0.5} = 0.6065, \quad e^{-1} = 0.3679 .

They add up to 11.362111.3621. Dividing each by that sum (for e, 7.3891/11.3621=0.65037.3891 / 11.3621 = 0.6503) gives the probabilities (0.6503,0.1451,0.1188,0.0534,0.0324)(0.6503,\allowbreak 0.1451,\allowbreak 0.1188,\allowbreak 0.0534,\allowbreak 0.0324) for (e, a, o, i, y). The target is e, so the loss is ℓ=−ln⁡0.6503=0.4303\ell = -\ln 0.6503 = 0.4303.

The instrument below holds exactly this prediction. The blue bars at the top are the five logits; the white bars under them are the probabilities; the dashed lime box marks the target, e; the amber bars at the bottom are the gradient of the loss with respect to each logit, p−y\mathbf{p} - \mathbf{y}, where y\mathbf{y} is the one-hot vector of the target. The readouts give the loss and p(e)p(\text{e}).

The loss of a whole text

One position gives one loss. A text gives a prediction at every position, and the loss LL averages them. Why this score, the average of −ln⁡p-\ln p, and not some other way of combining the predictions? This section answers that, first with numbers and then in general: it is the one that measures how probable the model finds the whole text.

The diagram below computes the loss of the text "hello" from start to finish. It uses a made-up table of probabilities (a real model would compute each row with the softmax above), so every number can be checked by hand.

Why the average of logs is the right loss

Step 5 of the diagram found that the sum of the four losses is −ln⁡0.09-\ln 0.09, and that 0.090.09 is the probability of the whole continuation. That is not a coincidence, and it is the reason for this loss.

Probability has a chain rule: the probability of a whole sequence is the product of each element's probability given everything before it. For "hello", after the first character h:

P(e, l, l, o∣h)=P(e∣h) P(l∣he) P(l∣hel) P(o∣hell)=0.50×0.80×0.25×0.90=0.09.P(\text{e, l, l, o} \mid \text{h}) = P(\text{e} \mid \text{h})\,P(\text{l} \mid \text{he})\,P(\text{l} \mid \text{hel})\,P(\text{o} \mid \text{hell}) = 0.50 \times 0.80 \times 0.25 \times 0.90 = 0.09 .

The same holds for any text. Write PP for the probabilities the model assigns. Its ptp_t is exactly its probability for the next character given all of c1,…,ctc_1,\allowbreak \ldots,\allowbreak c_t, because the state ht\mathbf{h}_t has read every one of them. So

P(c2,c3,…,cT+1∣c1)=P(c2∣c1) P(c3∣c1,c2)⋯P(cT+1∣c1,…,cT)=∏t=1Tpt(yt),P(c_2, c_3, \ldots, c_{T+1} \mid c_1) = P(c_2 \mid c_1)\,P(c_3 \mid c_1, c_2)\cdots P(c_{T+1} \mid c_1, \ldots, c_T) = \prod_{t=1}^{T} p_t(y_t),

where ∏\prod means "multiply together", the way ∑\sum means "add together". Now rewrite the loss one move at a time:

L=1T∑t=1T(−ln⁡pt(yt))the definition=−1T∑t=1Tln⁡pt(yt)take the minus sign out of the sum=−1Tln⁡∏t=1Tpt(yt)a sum of logs is the log of the product: ln⁡a+ln⁡b=ln⁡(ab)=−1Tln⁡P(text)the chain rule above\begin{aligned} L &= \frac{1}{T}\sum_{t=1}^{T} \big(-\ln p_t(y_t)\big) && \text{the definition} \\ &= -\frac{1}{T}\sum_{t=1}^{T} \ln p_t(y_t) && \text{take the minus sign out of the sum} \\ &= -\frac{1}{T}\ln \prod_{t=1}^{T} p_t(y_t) && \text{a sum of logs is the log of the product: } \ln a + \ln b = \ln(ab) \\ &= -\frac{1}{T}\ln P(\text{text}) && \text{the chain rule above} \end{aligned}

Here P(text)P(\text{text}) is the probability of everything after the first character. Lowering the average loss is exactly raising the probability the model assigns to the training text. Nothing else is being optimized. Everything the model ends up knowing about spelling, words, grammar and who speaks when, it learns because that knowledge makes the real next character more probable.

The log also explains step 4 of the diagram. A probability of 0.25 on the truth costs 1.38631.3863, while raising a good prediction from 0.8 to 0.9 saves only 0.2231−0.1054=0.11770.2231 - 0.1054 = 0.1177. The log punishes a low probability on the truth far more than it rewards a high one, so the cheapest way to lower the loss is to stop being confidently wrong.

Perplexity

A loss of 0.6020 nats is hard to picture. Perplexity turns a loss back into something you can:

perplexity=eL.\text{perplexity} = e^{L}.

Start with a model that spreads its probability evenly over kk characters. Every prediction costs −ln⁡(1/k)=ln⁡k-\ln(1/k) = \ln k, so its loss is L=ln⁡kL = \ln k and its perplexity is eln⁡k=ke^{\ln k} = k. Reading that backwards: a perplexity of kk says that, on average, the model is as uncertain as if it were choosing uniformly among kk characters. For "hello", e0.6020=1.826e^{0.6020} = 1.826: the model does about as well as one choosing uniformly among 1.8 characters at every step.

There is a second way to see the same number. Put L=−1Tln⁡P(text)L = -\frac{1}{T}\ln P(\text{text}) into the exponent and use eab=(ea)be^{ab} = (e^{a})^{b}:

eL=eln⁡P(text)⋅(−1/T)=(eln⁡P(text))−1/T=P(text)−1/T,e^{L} = e^{\ln P(\text{text}) \cdot (-1/T)} = \big(e^{\ln P(\text{text})}\big)^{-1/T} = P(\text{text})^{-1/T},

the TT-th root of 1/P(text)1/P(\text{text}). For "hello" that is 1/0.09=11.111/0.09 = 11.11, and the fourth root of 11.1111.11 is 1.8261.826: the geometric mean of the four inverse probabilities 1/0.51/0.5, 1/0.81/0.8, 1/0.251/0.25 and 1/0.91/0.9.

To recap this section: a text's loss is the average of −ln⁡-\ln (probability of the true next character); that average is −1Tln⁡P(text)-\frac{1}{T}\ln P(\text{text}); and eLe^{L} reads it as an effective number of choices.

Now do the whole computation yourself on a three-character text: the losses, the product, the perplexity, and a uniform model for comparison.

On paperThe loss of a short text

A language model reads "the " (with a trailing space) one character at a time. After "t" it gives the next character "h" probability 0.4, after "th" it gives "e" probability 0.8, and after "the" it gives the space probability 0.5.

  1. Compute the three losses −ln⁡p-\ln p and their average, LL.
  2. Check that the sum of the losses equals −ln⁡-\ln of the product of the three probabilities.
  3. Compute the perplexity eLe^{L} and say in words what it means.
  4. A uniform model over 27 characters (26 letters and a space) gives every character probability 1/271/27. What are its loss and its perplexity?

To check your work, enter two numbers as a column: LL from part 1 (4 decimals), then the perplexity from part 3 (3 decimals).

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

L (part 1), then the perplexity (part 3)

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

From text to training pairs

The diagram worked on one five-character word. To train, we need the same inputs and targets for the whole Shakespeare text, in pieces a network can process. The text becomes numbers in three steps.

The vocabulary. Collect the distinct characters and sort them, so the ids do not depend on the order in which characters first appear. Our Shakespeare excerpt has 100,020 characters and 60 distinct ones: newline, space, eight punctuation marks (! ' , - . : ; ?), 24 capital letters (there is no X or Z) and all 26 lowercase letters. Sorting by character code puts newline at id 0 and space at id 1. Two dictionaries go with it: stoi from character to id ("string to integer") and itos back.

Encoding. Replace every character by its id. The whole text becomes one long array of integers from 0 to 59, and decoding reverses it.

Windows and targets. Training uses short windows of the text. A window of length TT starting at position ss gives inputs and targets

X=ids[s:s+T],Y=ids[s+1:s+T+1].\mathbf{X} = \texttt{ids}[s : s + T], \qquad \mathbf{Y} = \texttt{ids}[s + 1 : s + T + 1].

Python slices include the start and exclude the end, so X\mathbf{X} holds positions ss to s+T−1s + T - 1 and Y\mathbf{Y} holds positions s+1s + 1 to s+Ts + T: the targets are the inputs shifted by one character, exactly as in step 2 of the diagram. With the text "First Citizen", T=5T = 5 and s=0s = 0, the inputs are "First" (positions 0 to 4) and the targets are "irst " with a trailing space (positions 1 to 5): after "F" predict "i", after "Fi" predict "r", and so on. One window is TT training examples, each with a different amount of context, from one character up to TT. The last target is ids[s + T], so a start ss is valid only if s+Ts + T is still inside the text: a classic off-by-one.

A batch stacks BB windows from random starts into (B,T)(B,\allowbreak T) arrays. We hold out the last 10% of the text (10,002 characters) as a validation set and train on the first 90,018 characters, so we can tell learning from memorizing.

Two panels side by side, each with a row of five identical boxes, one per step. Left: under every box is a tile from a given row of shapes, and above every box sits a tile that matches the next shape in that row, all five produced at once. Right: only the first box has a given tile underneath; each box's output tile is carried by a curved arrow down to become the input of the box to its right.Training reads the true text at every step and checks every prediction at once; generation feeds each chosen character back in, one at a time.

Run this to see the data. It builds the vocabulary, counts the characters and cuts three random windows.

⌘+Enter runs · edit freelyPython sleeps until you run code

In every printed pair the second string is the first moved one character to the left, with one new character at the end. Check that you can cut a window by hand, including the last valid start.

Quick checkInputs and targets

The text is "to be or": 8 characters at positions 0 to 7. You cut a training window of length T=4T = 4 starting at position s=3s = 3. What are the inputs X and the targets Y?

Choose one answer, then check.

Now write the pipeline in code: the vocabulary, encoding and decoding, and the windows with their shifted targets, including the off-by-one check at the end of the text.

Code itFrom text to training pairs

Turn the Shakespeare text into training data.

  1. build_vocab(text) returns the sorted distinct characters and the two lookup tables.
  2. encode(s, stoi) and decode(ids, itos) convert between strings and integer arrays. encode raises ValueError for a character that is not in the vocabulary.
  3. make_windows(ids, seq_len, starts) cuts one window per start, with the targets shifted by one, and raises ValueError for a start that is negative or would need a target past the end of the text.
⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

Baselines: how good is good

A loss number means little on its own. Is 2.5 good? Before training anything, compute what simple models score on the same validation text. A trained RNN has to beat all of them, or it has learned nothing worth its parameters.

Uniform. Give every character probability 1/V1/V. Every prediction costs −ln⁡(1/V)=ln⁡V-\ln(1/V) = \ln V, so L=ln⁡60=4.094L = \ln 60 = 4.094 and the perplexity is 60. An untrained network with small random weights produces nearly equal logits, so its loss starts close to this value. That is the sanity check from module 6: at step 0, expect ln⁡V\ln V.

Unigram. Ignore the context and predict each character with its overall frequency in the training text, p(k)=count(k)/Np(k) = \text{count}(k)/N, where NN is the number of training characters. Space is the most common character (14,710 of the 100,020 in the whole text, about 14.7%), then "e" (8,900). On the validation text this model scores L≈3.323L \approx 3.323, a perplexity of about 27.7. (The exercise below adds 1 to every count before dividing, the smoothing explained next; with 90,018 training characters that changes only the fourth decimal.) Knowing that spaces and vowels are common is worth 4.094−3.323=0.7714.094 - 3.323 = 0.771 nats per character.

Bigram. Predict each character from the one before it:

P(b∣a)=count(a b)+αcount(a ⋅)+αV,P(b \mid a) = \frac{\text{count}(a\,b) + \alpha}{\text{count}(a\,\cdot) + \alpha V},

where count(a b)\text{count}(a\,b) is how often bb directly follows aa in the training text, count(a ⋅)\text{count}(a\,\cdot) is how often aa is followed by anything, and α\alpha is a small smoothing count added to every pair.

A tiny example makes the formula concrete. Take the five-character "text" a b a b b, whose vocabulary has only the two characters a and b, so V=2V = 2, and take α=1\alpha = 1. Its adjacent pairs are ab, ba, ab, bb. The character a is followed by something twice, both times by b, so count(a ⋅)=2\text{count}(a\,\cdot) = 2, count(a b)=2\text{count}(a\,b) = 2 and count(a a)=0\text{count}(a\,a) = 0:

P(b∣a)=2+12+1×2=34,P(a∣a)=0+12+2=14.P(\text{b} \mid \text{a}) = \frac{2 + 1}{2 + 1 \times 2} = \frac{3}{4}, \qquad P(\text{a} \mid \text{a}) = \frac{0 + 1}{2 + 2} = \frac{1}{4}.

The pair aa never occurs, yet it gets probability 1/41/4, not 0. That is what smoothing is for. Without it, any pair that happens never to occur in the training text gets probability 0, and a single such pair in the validation text makes the loss infinite, because −ln⁡0=∞-\ln 0 = \infty. Our validation text has 12 places where that happens (11 different pairs, such as "Ke" and "xs").

With α=1\alpha = 1 (add-one smoothing) the bigram model scores L≈2.382L \approx 2.382 on validation, a perplexity of about 10.8.

modelcontext usedvalidation lossperplexity
uniformnone4.09460
unigramnone3.32327.7
bigram1 character2.38210.8

A bigram model is the simplest language model with a state: its state is the previous character, and its "weights" are a V×VV \times V table of probabilities. An RNN replaces that state with a learned vector that can summarize everything it has read. To show that it uses more than the last character, it has to get below 2.38. The one you train in backpropagation through time does.

The uniform baseline is the one you will use most, as the sanity check for every freshly initialized model. Compute it for a different vocabulary size.

Work it outThe loss before training

A character model over a vocabulary of 65 characters has just been initialized, and its logits are nearly all equal. What loss should it report on its first training batch? Give 3 decimal places.

loss (nats)

Type a number: 0.25, -2, 3/4 and sqrt(2) all work. Enter checks.

Then compute the other two baselines on the real text. Counting is all the training these models need.

Code itUnigram and bigram baselines

Compute the lesson's baselines on the Shakespeare text.

  1. unigram_probs(ids, V, alpha) and bigram_probs(ids, V, alpha): probabilities from counts, with add-alpha smoothing.
  2. unigram_loss(p, ids) and bigram_loss(P, ids): the average cross-entropy of predicting every character after the first.

The code at the bottom trains on the first 90% of the text and prints the three validation losses. You should see about 4.094, 3.323 and 2.382.

⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

To recap the lesson: the model outputs a softmax over the next character at every position; the loss is the average −ln⁡-\ln probability of the true next character, which is −1Tln⁡P(text)-\frac{1}{T}\ln P(\text{text}); training windows pair each input with the character after it; and a loss means something only against baselines on the same text. The next lesson uses the model's probabilities for the other half of the job: writing text. First, explain the objective in plain words.

In your own wordsWhat next-token prediction learns

A client asks what "next-token prediction" has to do with how a large language model learns. Using the character model of this lesson, explain what the model outputs at each position, what the loss measures and why minimizing it makes the training text probable, and what a loss number can and cannot tell them.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.

Next: Generating text