cheer cheer cheer for for old old notre notre dame dame wake
Unit 03 · Chapter 3

Recurrent Neural Networks

Recurrent Neural Networks01

Sequence Data

Our convolutional network looked at one 32 × 32 photo at a time and said what was in it. Each photo was classified completely on its own, so if we shuffle the 10,000 unseen photos every one of them still gets the same answer.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ airplane ship cat airplane ship truck truck cat photos in order shuffled: same labels words in order cheer cheer for old notre dame shuffled: a different sentence notre cheer for cheer dame old

Text is different. Pictured above, under the photos, is the first line of the Notre Dame Victory March, one word to a box. Shuffled, it becomes notre3 cheer0 for1 cheer0 dame4 old2, which is no longer the fight song. The words only mean something in order, and what comes next depends on what came before (after notre3 comes dame4, in pretty much any text about this university).

Data like this, where the order matters and each piece has to be read in the context of the pieces before it, is called sequence data. Text is the obvious example, but speech, music, stock prices and video are all sequences too. As we saw at the end of the last chapter, a CNN can't take one in. It expects a grid of a fixed size, and a sentence can be any number of words long.

Recurrent Neural Networks · Sequence Data02

Tokenization

Unfortunately, a network only understands numbers. Our photos came as numbers already (0 to 255 for each color of each pixel), but a fight song comes as letters, commas and spaces. Turning language into numbers a computer can use is the central problem of Natural Language Processing (NLP).

The first step is to cut the text into pieces called tokens, which is called tokenization. We'll keep it simple: lowercase everything, turn anything that isn't a letter into a space, and split on the spaces. We'll use the first four lines of the Victory March all the way through this chapter.

import re
text = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the thunder from the sky."""
clean = re.sub(r"[^a-z ]", " ", text.lower())
tokens = clean.split()
vocab = list(dict.fromkeys(tokens)) # first appearance
ids = [vocab.index(t) for t in tokens]
print(len(tokens), "tokens,", len(vocab), "words")
print(tokens[:9])
print(ids[:9])
Output
26 tokens, 22 words
[cheer, cheer, for, old, notre, dame, wake, up, the]
[0, 0, 1, 2, 3, 4, 5, 6, 7]
Recurrent Neural Networks · Tokenization03

Tokenization Levels

Our code does word-level tokenization, one token per word, and it isn't the only choice. Here is how our four lines come out at each level:

levelone token istokensvocabulary
character-levela character13625
word-levela word2622
subword-levela word or a piece of one70512
byte-levela byte of the stored text136256

Our 22-word vocabulary only works because our text is four lines long. Real English needs hundreds of thousands of words, and a word the vocabulary has never seen (a typo, say) can't be tokenized at all. Character-level needs only a few dozen symbols, but our four lines become 136 tokens, each meaning very little on its own. The goal is to keep the vocabulary small while keeping the sequences short.

Recurrent Neural Networks · Tokenization04

Subword Tokenizers

A subword tokenizer gives common words a token of their own and builds rarer ones out of pieces, which keeps both the vocabulary and the sequences reasonably small, and nearly every modern language model uses one. Below is how one splits our first two lines, the tokenizer of irishQwen (the small language model built in CSE 10124), whose 512 tokens were made from Shakespeare.

C67he260er274,44 c283he260er274 for336 o285ld318 N438ot298re267 D434am389e101,44
W87ake429 up468 the270 e335ch325o111es281 c283he260er274ing302 her415 n288am389e101,44

With only 512 tokens to go around, just the most common words ( for336 up468 the270 her415 on376 from495) get one of their own. Even "cheer" is three pieces, c99he260er274, and "cheering" is the same three plus ing302. Tokenizers for real language models have 100,000 or more.

Recurrent Neural Networks · Tokenization05

Token IDs

cheer0 cheer0 for1 old2 notre3 dame4
wake5 up6 the7 echoes8 cheering9 her10 name11
send12 a13 volley14 cheer0 on15 high16
shake17 down18 the7 thunder19 from20 the7 sky21

Above are all 26 of our word-level tokens. There are only 22 different words, since cheer0 and the7 each turn up three times. The list of different tokens is our vocabulary, and a token's position in it (in order of first appearance) is its token ID, written under each tile.

So now every token is a number. Are we actually gaining anything from this? Not much, yet. The IDs are just positions in a list, so if we handed them to a network as they are, it would decide that thunder19 (19) is much more like sky21 (21) than like cheer0 (0), and that the7 is worth seven for1s. The numbers say nothing about the words.

Recurrent Neural Networks · Tokenization06

One-Hot Encoding

The usual fix is a one-hot vector, a list of 22 zeros with a single 1 in the token's position. for1 (ID 1) becomes

\bb{\begin{matrix} 0 & 1 & 0 & 0 & \cdots & 0 \end{matrix}} \bb{\begin{matrix} 0 & 1 & 0 & 0 & \cdots & 0 \end{matrix}}

Now no word is bigger than any other. Unfortunately, every pair of words is also exactly the same distance apart (√2), so cheer0 is as close to cheering9 as it is to sky21, and a one-hot vector says which word it is and nothing else. It doesn't scale well either. A vocabulary of 100,000 words would need vectors 100,000 long, all but one of them zeros.

What we'd like is a short list of numbers for each word, where words that are used in similar ways get similar numbers.

Recurrent Neural Networks · Word Embeddings07

Word Embeddings

Much like our CNN turned each photo into a list of 4,096 learned features, in NLP we turn each token into a short vector called a word embedding, built from the only evidence a computer has about a word, the words around it.

Learning good embeddings takes billions of words, far more than our four lines, so we can borrow some. GloVe (Pennington, Socher and Manning, Stanford, 2014) counted how often every pair of words turns up near each other in 6 billion words of Wikipedia and news, and learned 300 numbers for each of 400,000 words so that words used in similar ways get similar vectors. We only need the rows for our 22 words.

import torch
vocab, rows = [], []
for line in open("glove-victory-march.txt"):
word, *nums = line.split() # a word, 300 numbers
vocab.append(word)
rows.append([float(n) for n in nums])
E = torch.tensor(rows) # our 22 words, in song order
print(E.shape)
Output
torch.Size([22, 300])
Recurrent Neural Networks · Word Embeddings08

Cosine Similarity

To compare two words we scale both vectors to length 1 and take their dot product, the cosine similarity (1 means they point the same way, 0 means unrelated). One matrix product gives us every pair at once, and we can ask which of our 22 words sits closest to each.

E = E / E.norm(dim=1, keepdim=True) # length 1
S = E @ E.T # cosine similarity of every pair
S = S - 2 * torch.eye(22) # not its own neighbor
for w in ["cheer", "notre", "up", "thunder"]:
s = S[vocab.index(w)]
best = vocab[s.argmax()]
print(f"{w!r:9} {best!r:10} {s.max():.2f}")
Output
cheer   cheering 0.61
notre   dame     0.91
up      down     0.75
thunder sky      0.34

cheer0 finds cheering9 and notre3 finds dame4, which is about what we'd hope. thunder19 and sky21 are a weaker match (0.34), and up6 and down18 are the second closest pair in the whole song, which is worth a closer look.

Recurrent Neural Networks · Word Embeddings09

Embedding Space

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ −2 −1 0 1 2 3 4 5 6 first component −3 −2 −1 0 1 2 3 second component notre dame cheer cheering thunder sky volley shake echoes wake send up down high a for on old her the from name

Pictured above is every word in our vocabulary, squashed from 300 numbers to 2 with PCA so we can look at it (only 28% of the spread survives, so this is extremely approximate). notre3 and dame4 sit together, far from everything else, cheer0 and cheering9 are almost on top of each other, and the small words (a, for, on, the) bunch up on the left. Once tokens are points in space, we can compare words by how close they are.

Notice that up6 and down18 mean opposite things, yet they land right next to each other (0.75). Both turn up after the same kinds of words (wake5 up6, shake17 down18), and related only ever means "used next to the same words". Embeddings learned from billions of words pick up whatever patterns the text has.

Recurrent Neural Networks · Word Embeddings10

Bias in Embeddings

Unfortunately, the patterns include the text's biases. If we take the direction from "man" to "woman" in GloVe (the vector for "woman" minus the vector for "man") and see how far along it other words sit, jobs and ideas line up the way the articles talked about them. "nurse", "homemaker" and "receptionist" land far toward "woman", "engineer", "programmer" and "power" toward "man".

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ −1.0 −0.5 0.0 0.5 1.0 1.5 2.0 position along woman − man power football gun engineer money programmer success scientist human politician doctor cooking teacher receptionist homemaker nurse ← nearer "man" nearer "woman" →

None of this was put there on purpose, the embedding only counted which words were used together. Embeddings learned from Google News articles went as far as answering "man is to computer programmer as woman is to ___" with "homemaker" (Bolukbasi and colleagues, 2016, who named their paper after it). A model built on top of embeddings inherits whatever they learned.

Recurrent Neural Networks · Word Embeddings11

Context

Now that words are numbers, let's give a network a job, predicting the next word. A feed-forward network takes one fixed-size input, so the natural thing to give it is the current word's embedding. Given notre3 it would learn to say dame4, since in our song dame4 is the only word that ever follows notre3.

Unfortunately, the7 is followed by echoes8 once, thunder19 once and sky21 once. A network that only sees the7 gets exactly the same input all three times, so the best it can ever do is guess (a third each). One more word back would settle it: up6 the7 is followed by echoes8, down18 the7 by thunder19 and from20 the7 by sky21.

one word of context two words of context the echoes 1/3 thunder 1/3 sky 1/3 up the echoes down the thunder from the sky

We could feed it the last two words instead, but some other text will need three, or ten, and sentences don't come in a fixed length. The words that came before a word are its context, and what we want is a network that reads one word at a time and carries a summary of that context along with it.

Recurrent Neural Networks · Recurrent Neural Networks12

Recurrent Neural Networks

A recurrent neural network (RNN) does exactly that. At step t it takes the word's embedding xt and the numbers it produced at the step before, ct−1, called the hidden state, and combines them into a new hidden state:

c_{t} = \tanh\bp{x_{t} \Omega_{x}\T + c_{t-1} \Omega_{c}\T + b_c} c_{t} = \tanh\bp{x_{t} \Omega_{x}\T + c_{t-1} \Omega_{c}\T + b_c}

ωx weights the new word, ωc weights the old hidden state and bc is a bias, exactly like a fully connected layer except for the middle term. The hidden state starts out as all zeros, c0 = 0. Because each new hidden state is built from the last one, the hidden state after a word depends on every word before it.

Recurrent Neural Networks · Recurrent Neural Networks13

The RNN Cell

xₜ <1, 2> cₜ₋₁ <1, 2> Ωx <2, 2> Ωc <2, 2> @ Ωᵀ @ Ωᵀ + bc <2> tanh cₜ <1, 2> to the next step Ωy <22, 2> @ Ωᵀ + softmax bᵧ <22> ŷₜ <1, 22>

Pictured above is one step of our RNN, drawn as a computation graph in the same colors as our earlier networks. The top half is the equation on the last page, and the hidden state it makes goes on to the next step. The bottom half turns the hidden state into a prediction, which we'll come back to.

The idea goes back to at least 1986 (Michael Irwin Jordan, no relation), and Jeffrey Elman's 1990 network fed back its hidden layer, as ours does. One step like this is usually called a cell, since the same one is used again for every word.

Recurrent Neural Networks · Recurrent Neural Networks14

The Tanh Function

The function wrapped around all of this is tanh (the hyperbolic tangent), which we saw next to the sigmoid and ReLU with feed-forward networks. Like the sigmoid it's S-shaped, but it runs from −1 to 1 instead of 0 to 1, and it gives 0 for an input of 0.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ −4 −2 0 2 4 z −1.0 −0.5 0.0 0.5 1.0 g z ( ) = 1 + 1 e − z Sigmoid −4 −2 0 2 4 z −1.0 −0.5 0.0 0.5 1.0 g z ( ) = e e e e z z z z − + − − Tanh

An RNN feeds its hidden state back into itself once per word, 26 times for our four lines. If each pass through ωc made the hidden state a little bigger, after 26 words it would be enormous. Tanh keeps every number in the hidden state between −1 and 1 no matter how long the text is. Near 0 it's almost a straight line (tanh(0.5) = 0.462) and past ±2 it's almost flat (tanh(2) = 0.964).

Being centered on zero matters too. A sigmoid's outputs are always positive, while a tanh hidden state can push the next one up or down equally easily.

Recurrent Neural Networks · Recurrent Neural Networks15

Unrolling

Because the hidden state loops back into the same cell, an RNN is usually drawn unrolled, with one copy of the cell for each word, side by side. Pictured below are our first four words.

c₀ [0, 0] cell c₁ [0.05, −0.15] cheer [0.10, −0.10] cell c₂ [0.15, −0.20] cheer [0.10, −0.10] cell c₃ [0.68, −0.22] for [0.60, 0.10] cell c₄ [0.15, 0.71] old [−0.50, 0.40]

It's important to remember that this isn't four different layers. Every box uses the same weights, so an RNN that reads 26 words has exactly as many weights as one that reads 4. The numbers under each word are its embedding (from a random table, since our network hasn't been trained) and the numbers above each cell are the hidden state it hands to the next step.

Notice that cheer0 goes in twice with the same embedding and comes out with two different hidden states.

Recurrent Neural Networks · Recurrent Neural Networks16

An RNN by Hand

Let's work out those first two steps ourselves. Our embeddings and hidden state have two numbers each, the embedding table is random (rounded to one decimal), and we picked the weights by hand to keep the arithmetic simple, with the bias at 0:

\Omega_{x} = \bb{\begin{matrix} 1 & 0.5 \\ -0.5 & 1 \end{matrix}} \qquad \Omega_{c} = \bb{\begin{matrix} 0.5 & -0.5 \\ 0.5 & 0.5 \end{matrix}} \Omega_{x} = \bb{\begin{matrix} 1 & 0.5 \\ -0.5 & 1 \end{matrix}} \qquad \Omega_{c} = \bb{\begin{matrix} 0.5 & -0.5 \\ 0.5 & 0.5 \end{matrix}}

The first word is cheer0, with embedding [0.1, −0.1]. There's no hidden state yet (c0 = [0, 0]), so only the first term counts:

c_{1} = \tanh\bp{\bb{\begin{matrix} 0.1 & -0.1 \end{matrix}} \Omega_{x}\T + \bb{\begin{matrix} 0 & 0 \end{matrix}} \Omega_{c}\T} \phantom{c_{1}} = \tanh \bb{\begin{matrix} 0.05 & -0.15 \end{matrix}} = \bb{\begin{matrix} 0.0500 & -0.1489 \end{matrix}} c_{1} = \tanh\bp{\bb{\begin{matrix} 0.1 & -0.1 \end{matrix}} \Omega_{x}\T + \bb{\begin{matrix} 0 & 0 \end{matrix}} \Omega_{c}\T}; \phantom{c_{1}} = \tanh \bb{\begin{matrix} 0.05 & -0.15 \end{matrix}} = \bb{\begin{matrix} 0.0500 & -0.1489 \end{matrix}}

The second cheer0 has the same embedding, so the first term is the same [0.05, −0.15], but now the hidden state adds c1 ωcT = [0.0994, −0.0495]:

c_{2} = \tanh\bb{\begin{matrix} 0.05 + 0.0994 & -0.15 - 0.0495 \end{matrix}} \phantom{c_{2}} = \tanh \bb{\begin{matrix} 0.1494 & -0.1995 \end{matrix}} = \bb{\begin{matrix} 0.1483 & -0.1969 \end{matrix}} c_{2} = \tanh\bb{\begin{matrix} 0.05 + 0.0994 & -0.15 - 0.0495 \end{matrix}}; \phantom{c_{2}} = \tanh \bb{\begin{matrix} 0.1494 & -0.1995 \end{matrix}} = \bb{\begin{matrix} 0.1483 & -0.1969 \end{matrix}}

Same word, same weights, different hidden state. The second cheer0 knows it came after a cheer0.

Recurrent Neural Networks · Recurrent Neural Networks17

The Forward Pass

Running every word through the cell in order is the RNN's forward pass, a loop in PyTorch. Below we print the hidden state at each the7:

import re
import numpy as np
import torch
text = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the thunder from the sky."""
tokens = re.sub(r"[^a-z ]", " ", text.lower()).split()
vocab = list(dict.fromkeys(tokens))
ids = [vocab.index(t) for t in tokens]
rng = np.random.default_rng(0)
E = torch.tensor(rng.normal(size=(22, 2)).round(1),
dtype=torch.float32) # embeddings
W_x = torch.tensor([[1.0, 0.5], [-0.5, 1.0]])
W_c = torch.tensor([[0.5, -0.5], [0.5, 0.5]])
b_c, c = torch.zeros(2), torch.zeros(2) # bias, c₀
for t, i in enumerate(ids):
c = torch.tanh(E[i] @ W_x.T + c @ W_c.T + b_c)
if tokens[t] == "the":
print(tokens[t-2:t+1], c.round(decimals=3))
Output
[wake, up, the] tensor([-0.9790, -0.3550])
[shake, down, the] tensor([-0.9700, -0.2270])
[thunder, from, the] tensor([-0.9770,  0.2170])

Three times the network reads the7, with the same embedding, and it ends up somewhere different each time (mostly in the second number, −0.355, −0.227 and 0.217). So a layer reading this hidden state can tell the three apart, which a network that only saw the7 never could.

Recurrent Neural Networks · Recurrent Neural Networks18

Hidden States

Pictured below is the hidden state after every one of our 26 words, its first number in navy and its second in gold, with the three the7s shaded.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ cheer cheer for old notre dame wake up the echoes cheering her name send a volley cheer on high shake down the thunder from the sky −1 0 1 first number second number

It jumps around a lot, since the weights are made up and nothing has asked it to mean anything yet. Notice, though, what happens at the three the7s. Each one pushes the first number down near −1, and the words before it decide the second.

That's the whole job of a hidden state, a summary of everything read so far, small enough to carry from one word to the next. Two numbers can't summarize much. Real RNNs use hundreds, and training decides what they hold on to.

Recurrent Neural Networks · Recurrent Neural Networks19

RNNs in PyTorch

PyTorch has both pieces built in. nn.Embedding is the embedding table, one row per token ID, and nn.RNN runs the whole loop. Below we give them our weights instead of their own random ones and read the four lines again:

import re
import numpy as np
import torch
from torch import nn
text = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the thunder from the sky."""
tokens = re.sub(r"[^a-z ]", " ", text.lower()).split()
vocab = list(dict.fromkeys(tokens))
ids = [vocab.index(t) for t in tokens]
E = np.random.default_rng(0).normal(size=(22, 2))
W_x = torch.tensor([[1.0, 0.5], [-0.5, 1.0]])
W_c = torch.tensor([[0.5, -0.5], [0.5, 0.5]])
emb = nn.Embedding(22, 2)
rnn = nn.RNN(2, 2, batch_first=True)
with torch.no_grad(): # our weights, not random ones
emb.weight.copy_(torch.tensor(E.round(1)))
rnn.weight_ih_l0.copy_(W_x)
rnn.weight_hh_l0.copy_(W_c)
rnn.bias_ih_l0.zero_()
rnn.bias_hh_l0.zero_()
x = emb(torch.tensor([ids])) # 1 song, 26 words
out, c = rnn(x)
print(tuple(x.shape), tuple(out.shape), tuple(c.shape))
print(out[0, 8].round(decimals=3)) # wake up the
Output
(1, 26, 2) (1, 26, 2) (1, 1, 2)
tensor([-0.9790, -0.3550])
Recurrent Neural Networks · Recurrent Neural Networks20

Inside nn.RNN

On the last page, out held the hidden state after every word (what we need to predict every next word) and c only the last one. The weights that made them are stored under names of their own:

from torch import nn
rnn = nn.RNN(2, 2, batch_first=True)
for name, p in rnn.named_parameters():
print(name, tuple(p.shape))
Output
weight_ih_l0 (2, 2)
weight_hh_l0 (2, 2)
bias_ih_l0 (2,)
bias_hh_l0 (2,)

weight_ih_l0 ("input to hidden", layer 0) is our ωx and weight_hh_l0 ("hidden to hidden") is our ωc, which is why the hidden state after wake5 up6 the7 on the last page matched our loop. PyTorch keeps two bias vectors and adds them together, so its bc is bias_ih_l0 + bias_hh_l0, and our cell's 10 numbers are 12 in PyTorch.

Recurrent Neural Networks · Recurrent Neural Networks21

Outputs

To predict the next word, each hidden state goes through one more layer, with a softmax to turn its scores into one probability per word in the vocabulary (as our CNN did for its ten kinds of photo):

\yhat_{t} = \text{softmax}\bp{c_{t} \Omega_{y}\T + b_y} \yhat_{t} = \text{softmax}\bp{c_{t} \Omega_{y}\T + b_y}

For us ωy is 22 × 2, one row per word. Pictured below is what our network says after wake5 up6 the7, with ωy random as well and by = 0.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ the wake from echoes thunder high send notre down her cheer dame a up shake volley sky on cheering name for old 0.00 0.05 0.10 0.15 probability 1/22

It thinks the next word is most likely the7 (0.165) and gives echoes8 0.090. Averaged over the 25 words that have a next word, it gives the right one a probability of 0.051, which is barely better than picking at random (1/22 = 0.045). That's what made-up weights get us.

Recurrent Neural Networks · Recurrent Neural Networks22

An RNN From Scratch

In Backpropagation we wrote each layer of a network as a small class with a forward method, and in CNNs we added a convolutional layer and pooling the same way. An RNN needs two new layers. The first is the embedding layer:

import torch
class Embedding:
def __init__(self, n_tokens, d):
self.E = torch.randn(n_tokens, d) * 0.1
def forward(self, ids): # (B, T) token IDs
self.ids = ids # keep for backward
return self.E[ids] # (B, T, d): one row per ID

It holds the embedding table, one row per token in the vocabulary, and its forward is a lookup: a batch of token IDs, shape (B, T), becomes a batch of vectors, shape (B, T, d). That is the same as multiplying each one-hot vector by the table (One-Hot Encoding), without building the one-hot vectors.

Recurrent Neural Networks · An RNN From Scratch23

The Recurrent Layer

The second is the recurrent layer, our cell run over the words in order:

class RNNLayer:
def __init__(self, n_in, n_h):
self.Wx = torch.randn(n_h, n_in) / n_in**0.5
self.Wc = torch.randn(n_h, n_h) / n_h**0.5
self.b = torch.zeros(n_h)
def step(self, x_t, c_prev): # one word, c_t
return torch.tanh(x_t @ self.Wx.T
+ c_prev @ self.Wc.T + self.b)
def forward(self, X): # (B, T, n_in)
B, T, _ = X.shape
c = torch.zeros(B, self.Wc.shape[0]) # c_0
self.states = [c] # keep every c_t for BPTT
for t in range(T): # one word at a time
c = self.step(X[:, t], c) # same weights
self.states.append(c)
return torch.stack(self.states[1:], dim=1)

The step method is the equation from The RNN Cell, for a whole batch of sequences at once. The forward method is our loop from The Forward Pass: it starts from a hidden state of zeros and calls the same step, with the same Wx and Wc, for every word. It also keeps every hidden state in self.states, since training will need them in the next chapter.

Recurrent Neural Networks · An RNN From Scratch24

The Rest of the Network

The output layer from the last page is a linear layer, and we already have one. LinearLayer and Network are the classes from Backpropagation, with only their forward methods for now:

class LinearLayer:
def __init__(self, n_in, n_out):
self.W = torch.randn(n_out, n_in) * (2/n_in)**0.5
self.b = torch.zeros(n_out)
def forward(self, X): # every c_t at once
self.X = X # keep for backward
return X @ self.W.T + self.b
class Network:
def __init__(self, layers):
self.layers = layers
def forward(self, X):
for layer in self.layers:
X = layer.forward(X)
return X # logits

The recurrent layer hands on a hidden state for every word, shape (B, T, n_h), and @ multiplies the last dimension, so the linear layer scores every word's next word at once. Network doesn't care what kind of layers it holds.

Recurrent Neural Networks · An RNN From Scratch25

Running Our RNN From Scratch

Below we put the four lines through an embedding layer, a recurrent layer with two hidden numbers and a linear layer back out to our 22 words, all with random weights:

import re
text = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the thunder from the sky."""
tokens = re.sub(r"[^a-z ]", " ", text.lower()).split()
vocab = list(dict.fromkeys(tokens))
X = torch.tensor([[vocab.index(t) for t in tokens]])
torch.manual_seed(0)
model = Network([Embedding(22, 2), RNNLayer(2, 2),
LinearLayer(2, 22)])
logits = model.forward(X)
emb, rnn, out = model.layers
print("IDs", tuple(X.shape), "-> logits",
tuple(logits.shape))
print("hidden states:", len(rnn.states))
n = [emb.E, rnn.Wx, rnn.Wc, rnn.b, out.W, out.b]
print("weights:", sum(w.numel() for w in n))
Output
IDs (1, 26) -> logits (1, 26, 22)
hidden states: 27
weights: 120

One song of 26 words comes out as 26 rows of 22 scores, one for each next word, and the recurrent layer kept 27 hidden states. The network has 120 weights: 44 in the embedding table, 10 in the cell and 66 in the output layer. None of them depend on how long the song is.

Recurrent Neural Networks · An RNN From Scratch26

Our Weights, From Scratch

To check our classes, we can give them the weights from the earlier pages (the same seed for the embedding table and ωy, our ωx and ωc, and zero biases) and run the song again:

import numpy as np
rng = np.random.default_rng(0) # earlier slides' weights
E = rng.normal(size=(22, 2)).round(1)
W_y = rng.normal(size=(22, 2)).round(1)
emb.E = torch.tensor(E, dtype=torch.float32)
rnn.Wx = torch.tensor([[1.0, 0.5], [-0.5, 1.0]])
rnn.Wc = torch.tensor([[0.5, -0.5], [0.5, 0.5]])
rnn.b = torch.zeros(2)
out.W = torch.tensor(W_y, dtype=torch.float32)
out.b = torch.zeros(22)
p = torch.softmax(model.forward(X), dim=-1)
c = rnn.states[9] # after "wake up the"
print("c:", c.round(decimals=3))
echoes = p[0, 8, vocab.index("echoes")]
print("p('echoes'):", echoes.round(decimals=3))
Output
c: tensor([[-0.9790, -0.3550]])
p(echoes): tensor(0.0900)

After wake up the we get the hidden state from The Forward Pass and the 0.090 for echoes from Outputs, so our classes compute the same network as the loop.

Recurrent Neural Networks · An RNN From Scratch27

Checking Against PyTorch

We can check against PyTorch the same way we did for the loop, by copying our weights into nn.Embedding, nn.RNN and nn.Linear:

from torch import nn
emb_t = nn.Embedding(22, 2)
rnn_t = nn.RNN(2, 2, batch_first=True)
out_t = nn.Linear(2, 22)
with torch.no_grad(): # copy our weights in
emb_t.weight.copy_(emb.E)
rnn_t.weight_ih_l0.copy_(rnn.Wx)
rnn_t.weight_hh_l0.copy_(rnn.Wc)
rnn_t.bias_ih_l0.copy_(rnn.b)
rnn_t.bias_hh_l0.zero_() # PyTorch has two biases
out_t.weight.copy_(out.W)
out_t.bias.copy_(out.b)
hidden, _ = rnn_t(emb_t(X))
logits_t = out_t(hidden)
diff = (logits_t - model.forward(X)).abs().max()
print("largest difference:", diff)
Output
largest difference: tensor(0.)

The scores are identical. PyTorch keeps a second bias in the cell (Inside nn.RNN), which we set to zero, and otherwise nn.RNN is our loop, written in faster code. When we train an RNN in the next chapter, our classes will need a backward method, while PyTorch will work the gradients out for us.

Recurrent Neural Networks · An RNN From Scratch28

Uses of RNNs

Our network gives an output after every word, a guess at the next one. That isn't the only way to wire an RNN up, and which outputs we keep (and what we feed in) decides what it can be used for.

many to one: label a sentence many to many: predict every next word generation: write one word at a time encoder-decoder: translation reads writes

Pictured above, many to one reads a whole sequence and only answers at the end, using the last hidden state, which is how an RNN labels a sentence (is this review positive?). Many to many answers after every word, like our next-word predictions. The bottom two are the uses that made RNNs famous, writing text and translating it.

Recurrent Neural Networks · Uses of RNNs29

Text Generation

A network that predicts the next word can also write. We give it a first word, take the word it thinks is likeliest, and feed that back in as the next input, one word at a time:

import re
import numpy as np
import torch
text = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the thunder from the sky."""
tokens = re.sub(r"[^a-z ]", " ", text.lower()).split()
vocab = list(dict.fromkeys(tokens))
rng = np.random.default_rng(0)
E = torch.tensor(rng.normal(size=(22, 2)).round(1),
dtype=torch.float32) # embeddings
W_y = torch.tensor(rng.normal(size=(22, 2)).round(1),
dtype=torch.float32) # output layer
W_x = torch.tensor([[1.0, 0.5], [-0.5, 1.0]])
W_c = torch.tensor([[0.5, -0.5], [0.5, 0.5]])
c = torch.zeros(2)
word, song = "cheer", ["cheer"]
for t in range(9):
i = vocab.index(word)
c = torch.tanh(E[i] @ W_x.T + c @ W_c.T)
p = torch.softmax(c @ W_y.T, dim=0)
word = vocab[p.argmax()] # the likeliest next word
song.append(word)
print(song[:5])
print(song[5:])
Output
[cheer, send, on, shake, shake]
[for, old, shake, shake, for]

Not exactly the fight song, but that's what made-up weights write.

Recurrent Neural Networks · Uses of RNNs30

Sampling

Always taking the likeliest word tends to get stuck in loops (shake17 shake17 for1), so in practice the next word is drawn at random from the probabilities instead, which is called sampling. How random is set by the temperature T, which divides the scores before the softmax:

\yhat_{t} = \text{softmax}\bp{\frac{c_{t} \Omega_{y}\T + b_y}{T}} \yhat_{t} = \text{softmax}\bp{\frac{c_{t} \Omega_{y}\T + b_y}{T}}

After cheer0, the likeliest word for our network is send12, at 0.064. At T = 0.5 it gets 0.087 and at T = 2 only 0.054, closer to 1/22 = 0.045. A low temperature sharpens the guesses toward the likeliest word, a high one flattens them toward picking at random.

Trained on enough text, a generating RNN gets surprisingly good. Andrej Karpathy's 2015 RNNs, which read and wrote one character at a time, produced passable fake Shakespeare and Wikipedia articles.

Recurrent Neural Networks · Uses of RNNs31

Machine Translation

Translation is harder, since a sentence and its translation rarely have the same number of words, or put them in the same order. The answer, from two groups in 2014 (Sutskever, Vinyals and Le at Google, and Cho and colleagues in Montreal), was to use two RNNs. The first, the encoder, reads the whole sentence and produces no outputs at all. Its last hidden state is handed to the second, the decoder, as its starting hidden state, and the decoder generates the translation one word at a time, like the last page, until it predicts a special end-of-sentence token.

Everything the decoder knows about the original sentence is in that one hidden state, which is why it's often called the context vector. It's also called an encoder-decoder (or sequence-to-sequence) model, and with LSTMs in place of our plain cells, plus the attention of a few pages on, it was good enough that in 2016 Google Translate switched to one.

Recurrent Neural Networks · Uses of RNNs32

Pros and Cons of RNNs

An RNN reads a sequence of any length with one fixed set of weights. Ours has 120 numbers to learn (44 in the embedding table, 10 in the cell and 66 in the output layer), whether it reads four words or four thousand. Its hidden state carries along the context a feed-forward network never sees, and it can give an output after every word, or only after the last one (to label a whole sentence, say).

Unfortunately, it can only read one word at a time. Each step needs the hidden state from the step before, so 26 words means 26 steps, one after another. Our CNN can label a thousand photos at once, because none of them needs the others' answers, but an RNN can't start on word 10 until it has finished word 9. On long texts and big GPUs that makes RNNs slow to train.

Recurrent Neural Networks · Pros and Cons33

Long-Term Dependencies

Worse, it forgets. Below we run the forward pass twice, on the song as written and with sky21 in place of the first cheer0, and measure how far apart the two hidden states are after each word.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ cheer cheer for old notre dame wake up the echoes cheering her 0.0 0.5 1.0 distance between hidden states 0.93 0.63 0.42 0.26 0.07 0.05 0.02 0.00 0.00 0.00 0.00 0.00 sky

The gap is 0.93 after the first word, 0.26 by old2 and 0.02 by wake5. By the7, the ninth word, it's down to 0.001, so it effectively has no idea how the song started. Each step mixes the old hidden state with a new word and squashes the result, and our ωc shrinks the old part by about 30% every time.

A word that depends on another word far back is called a long-term dependency, and RNNs are bad at them. A trained network holds on for longer than our made-up one, but every RNN has this problem to some degree.

Recurrent Neural Networks · Pros and Cons34

Gates

Our network forgets because every step replaces the hidden state with a mix of the new word and the old state, squashed. What if each step could choose how much of the old hidden state to keep? Write c̃t for the new hidden state our cell would make, and let a vector zt of numbers between 0 and 1 blend the two:

c_{t} = z_{t} \odot c_{t-1} + \bp{1 - z_{t}} \odot \tilde{c}_{t} c_{t} = z_{t} \odot c_{t-1} + \bp{1 - z_{t}} \odot \tilde{c}_{t}

A vector like zt that multiplies something number by number (⊙) is called a gate. Pictured below is our forgetting experiment again, with a gate that always keeps 0.9 of the old state:

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ cheer cheer for old notre dame wake up the echoes cheering her name send a volley cheer on high shake down the thunder from the sky 0.0 0.2 0.4 0.6 0.8 1.0 first word still left plain RNN gate keeping 0.9 of the old state

By the ninth word the plain RNN has 0.1% of the first word left, the gated one 59%, and at the end of the song still 21%.

Recurrent Neural Networks · Gating35

LSTMs and GRUs

Of course a gate stuck at 0.9 isn't much use, since it remembers everything just as hard, the words that matter and the ones that don't. In a real network the gate is a layer of its own, a sigmoid looking at the new word and the old hidden state, zt = σ(xt ωzxT + ct−1 ωzcT + bz), so the network learns when to hold on and when to let go.

That's (most of) a Gated Recurrent Unit (GRU, Cho and colleagues, 2014), which adds a second gate deciding how much of the old state goes into c̃t. The older Long Short-Term Memory (LSTM, Hochreiter and Schmidhuber, 1997) uses three gates and keeps a second memory vector, the cell state, alongside the hidden state. Every gate is one more layer of weights:

from torch import nn
for cell in [nn.RNN(2, 2), nn.GRU(2, 2), nn.LSTM(2, 2)]:
n = sum(p.numel() for p in cell.parameters())
print(type(cell).__name__, n)
Output
RNN 12
GRU 36
LSTM 48

In PyTorch either one is a drop-in replacement for nn.RNN, three and four times its size. Why gates make these networks so much easier to train is a story about gradients, and the next chapter's.

Recurrent Neural Networks · Gating36

The Bottleneck

Gates help an RNN hold on, but it still has to fit everything into one hidden state of a fixed size. For a translation that's the context vector, and every word of the original sentence has to survive in it until the decoder needs it, however long the sentence is. Ours has two numbers to carry the whole song.

This is called the bottleneck problem, and it showed. Cho and colleagues found in 2014 that their encoder-decoder's translations got steadily worse as the sentences got longer.

The encoder did make a hidden state after every word, though, and each one is a summary of the sentence up to that word. Rather than throwing all but the last one away, the decoder could keep them all and, at each word it writes, look back at whichever ones it needs.

Recurrent Neural Networks · Attention37

Attention

That's what Bahdanau, Cho and Bengio did in 2014, and they called it attention. Before writing each word, the decoder scores every one of the encoder's hidden states against its own current hidden state s (the simplest score is a dot product), turns the scores into weights with a softmax, and adds up the encoder's hidden states with those weights:

e_j = s \cdot c_{j} \alpha = \text{softmax}\bp{e} v = \sum_j \alpha_j\, c_{j} e_j = s \cdot c_{j}; \alpha = \text{softmax}\bp{e}; v = \sum_j \alpha_j\, c_{j}

So every word the decoder writes gets its own context vector, built mostly from the hidden states it gave the most weight. Translating into French, the weights for each French word mostly picked out the English word it came from, and the translations stopped falling apart on long sentences.

Recurrent Neural Networks · Attention38

Attention Weights

We have no decoder, but we can let our network look back the same way. At the last the7 (word 25) we score its hidden state against the hidden states after each of the 24 words before it:

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ cheer cheer for old notre dame wake up the echoes cheering her name send a volley cheer on high shake down the thunder from 0.00 0.02 0.04 0.06 0.08 attention weight 1/24

The biggest weights go to up6 (0.084) and the other two the7s (0.071 and 0.070), against 1/24 = 0.042 if every word counted the same, because their hidden states are the most like this one. Its context vector, [−0.49, 0.08], is mostly those words.

Unfortunately, with made-up weights that's as far as we can get. Every weight, gate and score in this chapter needs to be learned from data, and every weight in an RNN is used at every step, so training one means following the loss back through every step of the loop, which is where we pick up next. (Attention will be back too, without the RNN at all.)

Recurrent Neural Networks · Attention39