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

Lesson 1 of 5

Sequences and state

A recurrent network reads a sequence one element at a time and carries a hidden state from each step to the next, using the same weights at every step. Unrolled through time, it is a deep network whose layers all share one set of weights.

About 70 minutes
By the end you can
  • Explain why a fixed-size network cannot read text of any length, and what a hidden state adds.

  • Run a recurrent network forward by hand, for a scalar state and for a vector state.

  • Explain why a matrix times a one-hot vector is a table lookup, and what an embedding table is.

  • Count the parameters of a recurrent network and explain why the count does not depend on the sequence length.

  • Implement the forward pass of a character RNN over a batch of sequences, keeping the cache that backpropagation needs.

Here is the first line of speech in the Shakespeare text you will train on in this module:

Before we proceed any further, hear me speak.

Suppose you want a network that reads it one character at a time and, after every character, guesses the next one. After "procee" it should be almost sure of "d". After "hear me " it has many reasonable options. And the right guess depends on more than the current character: in "hello" the first "l" is followed by another "l", the second by "o". Both times the network has just read an "l", so to tell the two apart it has to remember what came before.

Every network in module 6 takes a vector of one fixed size and returns a vector of one fixed size. A line of text has no fixed size, and a whole play certainly does not. This lesson builds the network that handles sequences: the recurrent neural network, or RNN. It reads one element at a time and carries a small vector, its state, from each step to the next. By the end you will have written its forward pass for batches of text, which the rest of this module turns into a trained language model.

Text has no fixed size

Why can we not just use the networks we already have? Two obvious ways to feed text to a fixed-size network both fail, and the ways they fail show what we need.

Feed the whole text at once. Turn each character into a vector (the section on characters as vectors makes this precise) and concatenate them. A 1,000-character passage over a 60-character alphabet becomes a vector with 1,000×60=60,0001{,}000 \times 60 = 60{,}000 entries. Three problems follow. Texts have different lengths, so everything must be padded to the longest one. Every position gets its own weights, so what the network learns about "the" at position 5 tells it nothing about "the" at position 500: it has to learn every pattern again at every position. And the number of weights grows with the length of the text.

Feed a fixed window. Keep only the last kk characters, say k=10k = 10, and predict the next one from those. The window slides along the text, so the same weights serve every position, and any length is fine. This is the idea behind classic n-gram language models; the bigram model in the next lesson is the case k=1k = 1. But anything older than kk characters is invisible. Whether an open quotation still needs closing, or which character in the play is speaking, can depend on something 50 or 500 characters back.

What we want is a model that reads any length, applies the same rule at every position, and can remember what matters from far back.

The idea: carry a state. You already know a machine like that. To add up a list of numbers of any length, keep one number ss, start it at 0, and at every step do st=st−1+xts_t = s_{t-1} + x_t. One rule, repeated; a state of fixed size (one number); any length.

Here is a more interesting one: a counter of open parentheses that adds 1 for "(", subtracts 1 for ")" and ignores everything else. Feed it the 9 characters of f(a, g(b) one at a time. After each character the counter reads

0f, 1(, 1a, 1,, 1space, 1g, 2(, 2b, 1).\underset{\texttt{f}}{0},\ \underset{\texttt{(}}{1},\ \underset{\texttt{a}}{1},\ \underset{\texttt{,}}{1},\ \underset{\text{space}}{1},\ \underset{\texttt{g}}{1},\ \underset{\texttt{(}}{2},\ \underset{\texttt{b}}{2},\ \underset{\texttt{)}}{1} .

It ends at 1, so one closing parenthesis is still owed, however long ago the first one opened. The counter never looks back at the text. Everything it needs about the past is in one number, which it updates with the same rule at every character.

A small figure walks left to right along a row of square tiles, each marked with a different simple shape. It carries one small tablet showing a row of four colored dots. The tablet stays the same size at every tile, but the colors of its dots change after each tile.Reading with a state: one step per element, and a summary of fixed size, updated at every step and carried to the next.

A recurrent network is this idea with two changes: the state is a vector of numbers instead of one counter, and the update rule is learned from data instead of written by hand.

The recurrent step

With the idea in place, we need the actual rule ff. The RNN's rule is a dense layer, the kind from module 6, applied to the previous state and the current input together:

ht=tanh⁡(Whhht−1+Wxhxt+b),zt=Whyht+by.\mathbf{h}_t = \tanh(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t + \mathbf{b}), \qquad \mathbf{z}_t = \mathbf{W}_{hy}\mathbf{h}_t + \mathbf{b}_y .

Every symbol, in words:

  • t=1,2,…,Tt = 1,\allowbreak 2,\allowbreak \ldots,\allowbreak T counts the steps, one per element of the sequence, and TT is the sequence length.
  • xt\mathbf{x}_t is the input at step tt, a column vector with mm entries.
  • ht\mathbf{h}_t is the hidden state after reading xt\mathbf{x}_t, a vector with nn entries; nn is the hidden size. The starting state h0\mathbf{h}_0 is usually all zeros.
  • Whh\mathbf{W}_{hh} (n×nn \times n) says how the previous state feeds the new one. These are the recurrent weights. The subscript reads "from h to h".
  • Wxh\mathbf{W}_{xh} (n×mn \times m, "from x to h") says how the input feeds the new state, and b\mathbf{b} is a bias with nn entries.
  • tanh⁡\tanh acts on each entry separately and squashes it into (−1,1)(-1,\allowbreak 1), as in derivatives as zoom.
  • zt\mathbf{z}_t is the output at step tt, with KK entries, read from the state by Why\mathbf{W}_{hy} (K×nK \times n) and the bias by\mathbf{b}_y. For a language model these are scores (logits) for the next character, which the next lesson turns into probabilities. Many sources call this output yt\mathbf{y}_t; we save y\mathbf{y} for the target, the character that actually comes next.

We will also name the sum inside the tanh. The pre-activation is at=Whhht−1+Wxhxt+b\mathbf{a}_t = \mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t + \mathbf{b}, so that ht=tanh⁡(at)\mathbf{h}_t = \tanh(\mathbf{a}_t).

Why call it a dense layer? The two products can be written as one matrix acting on the previous state and the input stacked into one tall vector:

Whhht−1+Wxhxt=[WhhWxh][ht−1xt].\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t = \begin{bmatrix} \mathbf{W}_{hh} & \mathbf{W}_{xh} \end{bmatrix}\begin{bmatrix} \mathbf{h}_{t-1} \\ \mathbf{x}_t \end{bmatrix}.

On the right, the matrix is Whh\mathbf{W}_{hh} and Wxh\mathbf{W}_{xh} placed side by side, n×(n+m)n \times (n + m), and the vector is ht−1\mathbf{h}_{t-1} stacked on top of xt\mathbf{x}_t, with n+mn + m entries. Multiplying them row by row gives the first nn columns times ht−1\mathbf{h}_{t-1} plus the last mm columns times xt\mathbf{x}_t, which is the left side. So each step is exactly the neuron layer of module 6, whose input happens to include its own previous output. The LSTM in module 8 stacks its inputs the same way.

A scalar RNN

The smallest case lets us watch the state by hand. With n=m=1n = m = 1 every matrix is a single number. Take whh=0.8w_{hh} = 0.8, wxh=1w_{xh} = 1, b=0b = 0 and h0=0h_0 = 0, and feed a single pulse: x=1,0,0,0,0x = 1,\allowbreak 0,\allowbreak 0,\allowbreak 0,\allowbreak 0. Each row of the table does one step: first the pre-activation at=0.8 ht−1+xta_t = 0.8\,h_{t-1} + x_t from the previous row's state, then ht=tanh⁡(at)h_t = \tanh(a_t).

ttxtx_tat=0.8 ht−1+xta_t = 0.8\,h_{t-1} + x_tht=tanh⁡(at)h_t = \tanh(a_t)
110.8×0+1=10.8 \times 0 + 1 = 10.7616
200.8×0.7616+0=0.60930.8 \times 0.7616 + 0 = 0.60930.5436
300.8×0.5436+0=0.43490.8 \times 0.5436 + 0 = 0.43490.4094
400.8×0.4094+0=0.32750.8 \times 0.4094 + 0 = 0.32750.3163
500.8×0.3163+0=0.25300.8 \times 0.3163 + 0 = 0.25300.2478

The state remembers the pulse, but it fades. Each step multiplies it by 0.80.8, and then tanh shrinks it a little more. The ratios of consecutive states show both effects: 0.5436/0.7616=0.7140.5436/0.7616 = 0.714, then 0.7530.753, 0.7730.773 and 0.7830.783. They climb toward 0.80.8 because a small state sits where tanh is nearly a straight line, tanh⁡a≈a\tanh a \approx a, so tanh stops shrinking it.

Now make the recurrent weight larger, whh=2w_{hh} = 2, and feed the same pulse. The states are h1=tanh⁡1=0.7616h_1 = \tanh 1 = 0.7616, then h2=tanh⁡(2×0.7616)=tanh⁡(1.5232)=0.9093h_2 = \tanh(2 \times 0.7616) = \tanh(1.5232) = 0.9093, then h3=tanh⁡(2×0.9093)=tanh⁡(1.8186)=0.9487h_3 = \tanh(2 \times 0.9093) = \tanh(1.8186) = 0.9487, then 0.95600.9560 and 0.95730.9573, settling at 0.95750.9575. That value is where the rule stops changing the state: tanh⁡(2×0.9575)=tanh⁡(1.915)=0.9575\tanh(2 \times 0.9575) = \tanh(1.915) = 0.9575. It is the positive solution of h=tanh⁡(2h)h = \tanh(2h). The state no longer fades.

But feed a pulse of 0.50.5 instead of 11 and the state starts lower, h1=tanh⁡0.5=0.4621h_1 = \tanh 0.5 = 0.4621, then h2=tanh⁡(2×0.4621)=tanh⁡(0.9242)=0.7279h_2 = \tanh(2 \times 0.4621) = \tanh(0.9242) = 0.7279, and it keeps climbing to the same 0.95750.9575. Feed −1-1 and it settles at −0.9575-0.9575. This network remembers the sign of the pulse and forgets its size.

Neither is a good memory. With whh=0.8w_{hh} = 0.8 the memory fades; with whh=2w_{hh} = 2 it latches onto a single bit. Which behavior you get depends on the recurrent weight, applied again at every step. That repeated multiplication is the thread of this whole module, and it is the reason for module 8, the LSTM.

A vector RNN

The same step with vectors is a matrix-vector product, a vector addition and a tanh on each entry. With two hidden units and one input, take

Whh=[0.501−0.5],Wxh=[0.5−1],b=[00.5],ht−1=[1−1],xt=2.\mathbf{W}_{hh} = \begin{bmatrix} 0.5 & 0 \\ 1 & -0.5 \end{bmatrix}, \quad \mathbf{W}_{xh} = \begin{bmatrix} 0.5 \\ -1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 0 \\ 0.5 \end{bmatrix}, \quad \mathbf{h}_{t-1} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \quad x_t = 2 .

Build the pre-activation at\mathbf{a}_t piece by piece. First the recurrent term. Row ii of Whh\mathbf{W}_{hh} says how much unit ii listens to each unit's previous value (the row view from matrices as transformations), so entry ii is row ii dotted with ht−1\mathbf{h}_{t-1}:

Whhht−1=[(0.5)(1)+(0)(−1)(1)(1)+(−0.5)(−1)]=[0.51.5].\mathbf{W}_{hh}\mathbf{h}_{t-1} = \begin{bmatrix} (0.5)(1) + (0)(-1) \\ (1)(1) + (-0.5)(-1) \end{bmatrix} = \begin{bmatrix} 0.5 \\ 1.5 \end{bmatrix}.

Then the input term. The input is a single number, so Wxhxt\mathbf{W}_{xh}x_t is the column Wxh\mathbf{W}_{xh} scaled by 2:

Wxhxt=[0.5×2−1×2]=[1−2].\mathbf{W}_{xh}x_t = \begin{bmatrix} 0.5 \times 2 \\ -1 \times 2 \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \end{bmatrix}.

Add the two terms and the bias entry by entry, then apply tanh to each entry:

at=[0.5+1+01.5−2+0.5]=[1.50],ht=[tanh⁡1.5tanh⁡0]=[0.90510].\mathbf{a}_t = \begin{bmatrix} 0.5 + 1 + 0 \\ 1.5 - 2 + 0.5 \end{bmatrix} = \begin{bmatrix} 1.5 \\ 0 \end{bmatrix}, \qquad \mathbf{h}_t = \begin{bmatrix} \tanh 1.5 \\ \tanh 0 \end{bmatrix} = \begin{bmatrix} 0.9051 \\ 0 \end{bmatrix}.

The stacked form from the start of this section gives the same sum in one product. Place Whh\mathbf{W}_{hh} and Wxh\mathbf{W}_{xh} side by side and stack ht−1\mathbf{h}_{t-1} on top of xtx_t:

[0.500.51−0.5−1][1−12]=[0.5+0+11+0.5−2]=[1.5−0.5],\begin{bmatrix} 0.5 & 0 & 0.5 \\ 1 & -0.5 & -1 \end{bmatrix}\begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix} = \begin{bmatrix} 0.5 + 0 + 1 \\ 1 + 0.5 - 2 \end{bmatrix} = \begin{bmatrix} 1.5 \\ -0.5 \end{bmatrix},

which is the recurrent term plus the input term, (0.5+1, 1.5−2)(0.5 + 1,\allowbreak \ 1.5 - 2). Adding b=(0,0.5)\mathbf{b} = (0,\allowbreak 0.5) gives the same at=(1.5,0)\mathbf{a}_t = (1.5,\allowbreak 0).

To recap: one step is (1) the recurrent term Whhht−1\mathbf{W}_{hh}\mathbf{h}_{t-1}, (2) the input term Wxhxt\mathbf{W}_{xh}\mathbf{x}_t, (3) add them and the bias, (4) tanh each entry. The next step starts again from the ht\mathbf{h}_t you just computed, with the same three weights.

Now run the step yourself. The first part feeds two inputs through a scalar RNN, so you see how the state carries the first input into the second step; the last part is one vector step like the one above.

On paperTwo steps, then a vector step

Work these by hand with ht=tanh⁡(whhht−1+wxhxt+b)h_t = \tanh(w_{hh}h_{t-1} + w_{xh}x_t + b), keeping four decimals in every intermediate value.

  1. A scalar RNN has whh=1w_{hh} = 1, wxh=0.5w_{xh} = 0.5 and b=0b = 0. Starting from h0=0.5h_0 = 0.5, feed x1=1x_1 = 1 and then x2=−2x_2 = -2. Find h1h_1 and h2h_2.
  2. Redo part 1 with x1=3x_1 = 3 instead of 11. Which of h1h_1 and h2h_2 change, and what does that say about what h1h_1 carries?
  3. A two-unit RNN with one input has Whh=[0.5−101]\mathbf{W}_{hh} = \begin{bmatrix} 0.5 & -1 \\ 0 & 1 \end{bmatrix}, Wxh=[10.5]\mathbf{W}_{xh} = \begin{bmatrix} 1 \\ 0.5 \end{bmatrix} and b=[0−0.5]\mathbf{b} = \begin{bmatrix} 0 \\ -0.5 \end{bmatrix}. Find ht\mathbf{h}_t for ht−1=(0.4,0.2)\mathbf{h}_{t-1} = (0.4,\allowbreak 0.2) and xt=2x_t = 2.

To check your work, enter four numbers as a column: h1h_1 and h2h_2 from part 1, then the two entries of ht\mathbf{h}_t from part 3, unit 1 first.

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.

h₁, h₂ (part 1), then the two entries of hₜ (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.

For more practice, here is an unlimited set of steps with fresh numbers: two scalar steps or one vector step each time.

Practice setRNN step reps
3 correct in a row completes the set. A miss starts the count again.

A two-unit RNN computes ht=tanh⁡(Whhht−1+wxhxt+b)\mathbf{h}_t = \tanh(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{w}_{xh}x_t + \mathbf{b}) with tanh⁡\tanh applied to each entry. Use Whh=[−1−0.5−0.5−0.5]\mathbf{W}_{hh} = \begin{bmatrix}-1 & -0.5 \\ -0.5 & -0.5\end{bmatrix}, wxh=[−1−1]\mathbf{w}_{xh} = \begin{bmatrix}-1 \\ -1\end{bmatrix}, b=[00.5]\mathbf{b} = \begin{bmatrix}0 \\ 0.5\end{bmatrix}, the previous state ht−1=[0.5−1]\mathbf{h}_{t-1} = \begin{bmatrix}0.5 \\ -1\end{bmatrix} and the input xt=−1x_t = -1. Find ht\mathbf{h}_t to 3 decimal places.

hₜ

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.

In code, batches are rows

Everything above uses column vectors, one sequence at a time. Code runs BB sequences at once and stores their states as the rows of a (B,n)(B,\allowbreak n) array, as in shapes, transposes and batches. To see what the code must hold, transpose the step for one sequence, turning every column into a row. Three facts do it. The tanh acts on each entry by itself, so it gives the same numbers whether they sit in a column or a row. Transposing a sum transposes each term. And transposing a product reverses its order, (Wh)⊤=h⊤W⊤(\mathbf{W}\mathbf{h})^\top = \mathbf{h}^\top\mathbf{W}^\top. So, writing the input term first as code does,

ht⊤=tanh⁡(xt⊤Wxh⊤+ht−1⊤Whh⊤+b⊤).\mathbf{h}_t^\top = \tanh(\mathbf{x}_t^\top\mathbf{W}_{xh}^\top + \mathbf{h}_{t-1}^\top\mathbf{W}_{hh}^\top + \mathbf{b}^\top).

The states and inputs are now rows, and the matrices are transposed. So in code Wxh holds Wxh⊤\mathbf{W}_{xh}^\top with shape (m, n), Whh holds Whh⊤\mathbf{W}_{hh}^\top with shape (n, n), and Why has shape (n, K). One step for the whole batch is

h = np.tanh(x @ Wxh + h @ Whh + bh)    # x: (B, m), h: (B, n), bh: (n,) added to every row

Check it on the vector example. There Whh is Whh⊤=[0.510−0.5]\mathbf{W}_{hh}^\top = \begin{bmatrix} 0.5 & 1 \\ 0 & -0.5 \end{bmatrix} and the state is the row [1, -1]. Then h @ Whh is [(1)(0.5)+(−1)(0), (1)(1)+(−1)(−0.5)]=[0.5, 1.5]\big[(1)(0.5) + (-1)(0),\allowbreak \ (1)(1) + (-1)(-0.5)\big] = [0.5,\allowbreak \ 1.5], the same two numbers as Whhht−1\mathbf{W}_{hh}\mathbf{h}_{t-1}. Likewise Wxh is the row [0.5, -1], and x @ Wxh with x = [[2]] gives [[1, -2]]. The numbers are the same; only the layout is transposed. The course's reference code in mlref/rnn.py follows this convention, and the lesson formulas keep column vectors.

Unrolling: one network, many layers

We have a rule for one step. What does the whole computation over a sequence look like? Write out the first three steps:

h1=tanh⁡(Whhh0+Wxhx1+b)h2=tanh⁡(Whhh1+Wxhx2+b)h3=tanh⁡(Whhh2+Wxhx3+b)\begin{aligned} \mathbf{h}_1 &= \tanh(\mathbf{W}_{hh}\mathbf{h}_0 + \mathbf{W}_{xh}\mathbf{x}_1 + \mathbf{b}) \\ \mathbf{h}_2 &= \tanh(\mathbf{W}_{hh}\mathbf{h}_1 + \mathbf{W}_{xh}\mathbf{x}_2 + \mathbf{b}) \\ \mathbf{h}_3 &= \tanh(\mathbf{W}_{hh}\mathbf{h}_2 + \mathbf{W}_{xh}\mathbf{x}_3 + \mathbf{b}) \end{aligned}

Now substitute. Replace h2\mathbf{h}_2 in the third line by the right side of the second line:

h3=tanh⁡(Whhtanh⁡(Whhh1+Wxhx2+b)+Wxhx3+b),\mathbf{h}_3 = \tanh\big(\mathbf{W}_{hh}\tanh(\mathbf{W}_{hh}\mathbf{h}_1 + \mathbf{W}_{xh}\mathbf{x}_2 + \mathbf{b}) + \mathbf{W}_{xh}\mathbf{x}_3 + \mathbf{b}\big),

then replace h1\mathbf{h}_1 by the right side of the first line:

h3=tanh⁡(Whhtanh⁡(Whhtanh⁡(Whhh0+Wxhx1+b)+Wxhx2+b)+Wxhx3+b).\mathbf{h}_3 = \tanh\Big(\mathbf{W}_{hh}\tanh\big(\mathbf{W}_{hh}\tanh(\mathbf{W}_{hh}\mathbf{h}_0 + \mathbf{W}_{xh}\mathbf{x}_1 + \mathbf{b}) + \mathbf{W}_{xh}\mathbf{x}_2 + \mathbf{b}\big) + \mathbf{W}_{xh}\mathbf{x}_3 + \mathbf{b}\Big).

Read from the inside out, that is three dense layers applied one after another: a three-layer feed-forward network. Drawing the steps side by side, left to right, is called unrolling the network in time.

The instrument below unrolls a small RNN over the word "hello". It answers two questions: what happens at each step, and which weights each step uses. Each column is one time step. At the bottom of a column is the one-hot input, one row per character of the vocabulary with the row of the character read lit up; above it is the hidden state, 4 units shown as colored cells (coral above 0, blue below 0). Blue arrows carry the input into the state through Wxh\mathbf{W}_{xh}, lime arrows carry the previous state across through Whh\mathbf{W}_{hh}. The weights are fixed random numbers, not trained ones, so the states mean nothing yet; what matters is how they are computed.

The unrolled network is unusual in two ways. First, every layer uses the same weights: Whh\mathbf{W}_{hh}, Wxh\mathbf{W}_{xh} and b\mathbf{b} appear at every step. These are called tied or shared weights. Second, a fresh input enters at every layer, and an output can leave at every layer. A sequence of length TT becomes a network TT layers deep.

Sharing weights across time is the same move a convolutional network makes across space, where one small filter slides over every position of an image (you meet it in module 9). It buys three things:

  • Any length. The same step runs as many times as there are characters.
  • Patterns transfer across positions. What the network learns about "the" at step 5 is used at step 500, because it is the same weights.
  • A fixed number of parameters. Reading ten characters or ten thousand uses the same matrices.

It also costs something. A long sequence makes a very deep network, and every layer multiplies by the same Whh\mathbf{W}_{hh}. You saw in powers, stability and explosion what repeated multiplication by one matrix does, and the last lesson of this module, vanishing and exploding gradients, shows what it does to training.

One more property falls out of the unrolled picture: ht\mathbf{h}_t depends only on x1,…,xt\mathbf{x}_1,\allowbreak \ldots,\allowbreak \mathbf{x}_t. In the widget, the columns to the right of the step shown stay dashed: the state at step tt has not seen the future, which is exactly what a model that predicts the next character needs.

Before moving on, check that the unrolled picture is clear: what it multiplies, what it shares, and what each state can see.

Quick checkWhat unrolling means

An RNN with hidden size 128 is unrolled over a sequence of 50 characters. Which statement is true?

Choose one answer, then check.

Characters as vectors

So far the input xt\mathbf{x}_t has been any vector of numbers. Text is characters, so we need a way to turn a character into a vector, and the way we choose turns out to make the input term almost free to compute.

Each character gets an id: its position in a sorted list of all the characters that occur, the vocabulary. With a vocabulary of VV characters, the one-hot vector of character kk is ek\mathbf{e}_k: VV entries, all 0 except a 1 in position kk. For a vocabulary {a, b, c}, the character b is e2=(0,1,0)\mathbf{e}_2 = (0,\allowbreak 1,\allowbreak 0). (Math counts positions from 1 and Python from 0, so in code the same b has id 1 and its one-hot vector is np.eye(3)[1].)

Now look at what the input term does with a one-hot vector. The column view of a matrix times a vector (matrices as transformations) says Wx\mathbf{W}\mathbf{x} is x1x_1 times column 1 plus x2x_2 times column 2, and so on. With x=ek\mathbf{x} = \mathbf{e}_k, every coefficient is 0 except the kk-th, so

Wxhek=column k of Wxh.\mathbf{W}_{xh}\mathbf{e}_k = \text{column } k \text{ of } \mathbf{W}_{xh}.

For example, take Wxh=[2−10.5031]\mathbf{W}_{xh} = \begin{bmatrix} 2 & -1 & 0.5 \\ 0 & 3 & 1 \end{bmatrix} and feed b, which is e2=(0,1,0)\mathbf{e}_2 = (0,\allowbreak 1,\allowbreak 0). The column view gives

Wxhe2=0[20]+1[−13]+0[0.51]=[−13],\mathbf{W}_{xh}\mathbf{e}_2 = 0\begin{bmatrix} 2 \\ 0 \end{bmatrix} + 1\begin{bmatrix} -1 \\ 3 \end{bmatrix} + 0\begin{bmatrix} 0.5 \\ 1 \end{bmatrix} = \begin{bmatrix} -1 \\ 3 \end{bmatrix},

the second column. No multiplications are needed: a matrix times a one-hot vector is a table lookup. Each character owns one column of Wxh\mathbf{W}_{xh}, and that column is what the character adds to the pre-activation every time it is read. In code, where Wxh has one row per character, the lookup for a whole batch of ids is Wxh[ids], which equals one_hot(ids) @ Wxh without building the one-hot arrays.

Try one full step where the input is a one-hot character: the input term becomes a lookup, and the rest is the vector step you already know.

Work it outA step with a one-hot input

A two-unit RNN reads characters from the vocabulary {a, b, c} as one-hot vectors. Its weights are Whh=[01−10.5]\mathbf{W}_{hh} = \begin{bmatrix} 0 & 1 \\ -1 & 0.5 \end{bmatrix}, Wxh=[10102−1]\mathbf{W}_{xh} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 2 & -1 \end{bmatrix} and b=(−0.5,0)\mathbf{b} = (-0.5,\allowbreak 0). The previous state is ht−1=(0.5,1)\mathbf{h}_{t-1} = (0.5,\allowbreak 1), and the network now reads c. Find ht=tanh⁡(Whhht−1+Wxhxt+b)\mathbf{h}_t = \tanh(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t + \mathbf{b}) to 3 decimal places, and enter it as a column, unit 1 first.

hₜ

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.

Embeddings. Look at what the RNN has already learned in Wxh\mathbf{W}_{xh}: every character owns a column of nn numbers, trained by gradient descent, that stands for that character inside the network. That column is a learned vector for the character.

Larger models make this explicit with a separate embedding table E\mathbf{E}, a V×dV \times d matrix with one row per token: row kk is a learned vector of dd numbers that stands for token kk. Looking a token up is the same one-hot trick from the other side, ek⊤E=\mathbf{e}_k^\top\mathbf{E} = row kk of E\mathbf{E}, and the network then works with those dd-number vectors instead of VV-entry one-hot vectors. The table is trained like every other weight. Tokens that behave alike tend to end up with vectors that point in similar directions, which is why the cosine similarity of length and similarity is the usual way to compare them.

What does an embedding change for the RNN above? Follow one character through it in three moves:

  1. Look up the embedding: E⊤ek\mathbf{E}^\top\mathbf{e}_k, row kk of E\mathbf{E} written as a column of dd numbers.
  2. Multiply by the input weights, which now take dd numbers in, so Wxh\mathbf{W}_{xh} is n×dn \times d: the input term is Wxh(E⊤ek)\mathbf{W}_{xh}(\mathbf{E}^\top\mathbf{e}_k).
  3. Regroup the product: Wxh(E⊤ek)=(WxhE⊤) ek\mathbf{W}_{xh}(\mathbf{E}^\top\mathbf{e}_k) = (\mathbf{W}_{xh}\mathbf{E}^\top)\,\mathbf{e}_k, which is column kk of the n×Vn \times V matrix WxhE⊤\mathbf{W}_{xh}\mathbf{E}^\top.

So it is still one lookup, into a matrix built as the product of two thin ones, and therefore of rank at most dd (inverses, systems and rank). It stores Vd+ndVd + nd numbers instead of nVnV, which is fewer whenever d(V+n)<nVd(V + n) < nV. For V=60V = 60 characters, n=128n = 128 and d=16d = 16: 60×16+128×16=960+2,048=3,00860 \times 16 + 128 \times 16 = 960 + 2{,}048 = 3{,}008 numbers instead of 128×60=7,680128 \times 60 = 7{,}680. The table can also be shared with other parts of the model.

Run the example below. It builds the one-hot vectors for "hello world", checks that the product is a lookup, and runs a small RNN with random weights over the text.

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

The two l's add the same row of Wxh (the same column of Wxh\mathbf{W}_{xh} in the math) but produce different states, because the previous state differs. The state after "hel" carries "he" with it; the state after "hell" carries "hel". This is the effect you saw at steps 3 and 4 of the instrument, now in code.

Counting parameters

One of the promises of weight sharing was a parameter count that does not grow with the text. Here is the count, piece by piece: Wxh\mathbf{W}_{xh} has n×mn \times m entries, Whh\mathbf{W}_{hh} has n×nn \times n, b\mathbf{b} has nn, Why\mathbf{W}_{hy} has K×nK \times n and by\mathbf{b}_y has KK. Group the first three (they all have nn rows) and the last two (they all have KK rows):

nm+n2+n+Kn+K=n(m+n+1)⏟recurrent layer+K(n+1)⏟output layer.nm + n^2 + n + Kn + K = \underbrace{n(m + n + 1)}_{\text{recurrent layer}} + \underbrace{K(n + 1)}_{\text{output layer}} .

For a character model over our Shakespeare text, the inputs and the outputs are both one-hot over V=60V = 60 characters, so m=K=60m = K = 60. With hidden size n=128n = 128:

128×(60+128+1)+60×(128+1)=128×189+60×129=24,192+7,740=31,932.128 \times (60 + 128 + 1) + 60 \times (128 + 1) = 128 \times 189 + 60 \times 129 = 24{,}192 + 7{,}740 = 31{,}932 .

More than half of that is Whh\mathbf{W}_{hh}, with 1282=16,384128^2 = 16{,}384 entries. None of it depends on TT.

Compare the fixed-window alternative. A network that reads the last 100 characters as one-hot vectors has 100×60=6,000100 \times 60 = 6{,}000 inputs, and a first layer of 128 units already needs 6,000×128=768,0006{,}000 \times 128 = 768{,}000 weights, 24 times the entire RNN, while still seeing nothing older than 100 characters.

The work per character is also fixed. Each step costs n2=16,384n^2 = 16{,}384 multiply-adds for Whhht−1\mathbf{W}_{hh}\mathbf{h}_{t-1} (the input term is a lookup) and Kn=60×128=7,680Kn = 60 \times 128 = 7{,}680 for the output: 16,384+7,680=24,06416{,}384 + 7{,}680 = 24{,}064 for this model, whether it has read 10 characters or 10,000. A transformer in module 9 works differently: each new token looks back at every earlier one, so its cost per token grows with the context.

Count one yourself, for a bigger vocabulary and a bigger state.

Work it outCount the parameters

A character RNN reads one-hot characters from a vocabulary of 80, has hidden size 256, and outputs logits over the same 80 characters. How many parameters does it have, biases included? Enter the whole number, without commas.

parameters

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

Write the forward pass

Recap before you code: one step is ht=tanh⁡(Whhht−1+Wxhxt+b)\mathbf{h}_t = \tanh(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t + \mathbf{b}); a one-hot input makes Wxhxt\mathbf{W}_{xh}\mathbf{x}_t a lookup; code stores the transposed matrices and keeps a batch of sequences as rows; the output layer reads logits from every state.

Here is everything the forward pass has to do for a batch, in the code layout:

  1. Look up the input rows for every step at once, Wxh[X].
  2. Loop over time, applying the recurrent step. This loop is the one part that cannot run in parallel, because each state needs the one before it.
  3. Compute the logits for every step with one matrix product.
  4. Keep a cache: every hidden state it produced, the inputs and the starting state. Backpropagation in backpropagation through time needs all of them, just as the layers of module 6 kept their inputs for the backward pass.
Code itThe forward pass for a batch

Write the forward pass of a character RNN for a batch, in the code layout (batches are rows, and Wxh has shape (V, H)).

  1. one_hot(ids, V): one-hot vectors for an array of ids of any shape.
  2. rnn_step(x_onehot, h_prev, params): one step for a batch, tanh(x @ Wxh + h @ Whh + bh).
  3. rnn_forward(params, X, h0=None): run a batch of id sequences of shape (B, T) and return the logits (B, T, V), a cache of everything backpropagation will need, and the last state. Use the lookup Wxh[X] rather than one-hot products, so the only work inside the time loop is the recurrent product.

The tests compare your results with the course's reference implementation in mlref/rnn.py.

⌘+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 finish, put the whole lesson in your own words, as you would for a colleague who knows ordinary networks well.

In your own wordsExplain the recurrent network

A colleague knows multilayer perceptrons well but has never used a recurrent network. Explain how an RNN reads text of any length, what "unrolling" means, and what sharing the weights across time buys and costs.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.

Next: Predicting the next character