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

Recurrent Neural Networks

Recurrent Neural Networks01

So Far

So far we've seen networks that take in single samples that lack context

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

When our CNN labels a photo, it doesn't matter what photo came before it or comes after. This is not the case for sequence data like language

Recurrent Neural Networks · Sequence Data02

Sequence Data

Examples of sequence data:

cheer cheer for old notre dame 1 2 3 4 5 6 time (t)

How do we handle data where the order of what we're seeing matters? How do we maintain context over time?

Recurrent Neural Networks · Sequence Data03

Language as Input

Computers understand only numbers so we need to somehow convert text into numbers in such a way as to enable computer understanding. We call this subfield of AI: Natural Language Processing (NLP)

Dec Hex Chr 32 20 SP 33 21 ! 34 22 " 35 23 # 36 24 $ 37 25 % 38 26 & 39 27 ' 40 28 ( 41 29 ) 42 2A * 43 2B + 44 2C , 45 2D - 46 2E . 47 2F / Dec Hex Chr 48 30 0 49 31 1 50 32 2 51 33 3 52 34 4 53 35 5 54 36 6 55 37 7 56 38 8 57 39 9 58 3A : 59 3B ; 60 3C < 61 3D = 62 3E > 63 3F ? Dec Hex Chr 64 40 @ 65 41 A 66 42 B 67 43 C 68 44 D 69 45 E 70 46 F 71 47 G 72 48 H 73 49 I 74 4A J 75 4B K 76 4C L 77 4D M 78 4E N 79 4F O Dec Hex Chr 80 50 P 81 51 Q 82 52 R 83 53 S 84 54 T 85 55 U 86 56 V 87 57 W 88 58 X 89 59 Y 90 5A Z 91 5B [ 92 5C \ 93 5D ] 94 5E ^ 95 5F _ Dec Hex Chr 96 60 ` 97 61 a 98 62 b 99 63 c 100 64 d 101 65 e 102 66 f 103 67 g 104 68 h 105 69 i 106 6A j 107 6B k 108 6C l 109 6D m 110 6E n 111 6F o Dec Hex Chr 112 70 p 113 71 q 114 72 r 115 73 s 116 74 t 117 75 u 118 76 v 119 77 w 120 78 x 121 79 y 122 7A z 123 7B { 124 7C | 125 7D } 126 7E ~ 127 7F DEL

NLP starts with two preprocessing steps: tokenization and embedding

Recurrent Neural Networks · Tokenization04

Tokenization

Tokenization is the process of splitting a piece of text into tokens.

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 · Tokenization05

Tokenization Levels

There are several tokenization levels. Our four lines at each one, "Cheer, café" in tiles:

levelone token istokensvocabulary
character-levela character13625

c0h1e2e2r3,4 5c0a12f6é?

word-levela word2622

cheer0 café?

subword-levela word or a piece of one32200,019

Che21294er259,11 café30469

é isn't one of our 25 characters, but it is 2 of the 256 bytes

We want to keep the vocabulary small and keep tokenized sequences short

Recurrent Neural Networks · Tokenization06

Subword Tokenizers

Common words get a token of their own, rarer ones are built from pieces.

Che21294er259,11 cheer38313 for395 old2890 Notre41945 Dame55584,↵412
Wake105694 up869 the290 echoes155883 cheering130848 her1335 name1308,↵412
Send13052 a261 volley174240 cheer38313 on402 high1932,↵412
Shake127498 down1917 the290 thunder63132 from591 the290 sky17307.13

GPT-4o has about 200,000 tokens, so almost every word is a token of its own, with its space. "Cheer" at the start of a line is 2 pieces, Che21294er259, but cheer38313 after a space is one.

This implies that cheer0 at the start of a sentence is pretty rare, but it appears enough within sentences to deserve its own token.

Recurrent Neural Networks · Tokenization07

Tokenization (exercise) - Openai tokenizer

OpenAI actually still has their tokenizer public, and you can play around with it!

Screenshot of OpenAI's tokenizer page (GPT-4o): the sentence Wow I love introduction to artificial intelligence professor bill is so cool and not mean and i can't wait to give him a good cif so he doesn't get fired! is 154 characters and 31 tokens, each token highlighted in its own colour, with the list of token IDs below
Recurrent Neural Networks · Tokenization08

Subword Tokenizers - Text as Bytes

Computers store text as bytes: 8 bits, so 256 possible values. "Cheer" is 5 bytes, one per character, in decimal, hex and binary:

C67h104e101e101r114
decimal67104101101114
hex4368656572
binary0100001101101000011001010110010101110010

bytes starting with a 1 are used in UTF-8 as pieces of longer characters instead:
é is 2 bytes, an emoji is 4

decimalhexbinary
é195 169c3 a911000011 10101001
🍀240 159 141 128f0 9f 8d 8011110000 10011111 10001101 10000000
Recurrent Neural Networks · Tokenization09

Text as Bytes in Python

.encode("utf-8") turns a string into its bytes:

text = "Cheer, café 🍀"
data = text.encode("utf-8")
print(len(text), "characters,", len(data), "bytes")
print(list(data))
print([bytes([b]) for b in data])
print([hex(b) for b in data])
print([bin(b) for b in data])
Output
13 characters, 17 bytes
[67, 104, 101, 101, 114, 44, 32, 99, 97, 102, 195, 169, 32, 240, 159, 141, 128]
[C, h, e, e, r, ,,  , c, a, f, \xc3, \xa9,  , \xf0, \x9f, \x8d, \x80]
['0x43', '0x68', '0x65', '0x65', '0x72', '0x2c', '0x20', '0x63', '0x61', '0x66', '0xc3', '0xa9', '0x20', '0xf0', '0x9f', '0x8d', '0x80']
['0b1000011', '0b1101000', '0b1100101', '0b1100101', '0b1110010', '0b101100', '0b100000', '0b1100011', '0b1100001', '0b1100110', '0b11000011', '0b10101001', '0b100000', '0b11110000', '0b10011111', '0b10001101', '0b10000000']
Recurrent Neural Networks · Tokenization10

Subword Tokenization Algorithm: Byte-Level BPE

Byte-level BPE starts from the 256 bytes (ID = the byte's value), then:

  1. scans the text and counts every pair of neighbouring tokens
  2. adds the most frequent pair to the vocabulary as a new token with the next ID
  3. replaces that pair everywhere in the text, then goes back to 1

Counts of pairs of our four lines: h104e101 8, e101r114 6, e101e101 4, c99h104 4, 32t116 4, t116h104 4 …

IDvocabularytokens
0–255the bytes (C67 is 01000011)
256h104 + e101 → he256128
257e101 + r114 → er257123
258he256 + er257 → heer258119
259 32 + t116 → t259115
260 32 + c99 → c260112
261 c260 + heer258 → cheer261109

136 bytes, 109 tokens after 6 merges. GPT-4o keeps going to about 200,000 tokens

Recurrent Neural Networks · Tokenization11

Token IDs

A token's place in the vocabulary (in order of first appearance) is its token ID

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

tokenIDtokenID
cheer00name1111
for11send1212
old22a1313
notre33volley1414
dame44on1515
wake55high1616
up66shake1717
the77down1818
echoes88thunder1919
cheering99from2020
her1010sky2121

Are we actually gaining anything from this?

The numbers say nothing about meaning of the words

thunder19 isn't more like sky21 than cheer0

Recurrent Neural Networks · Word Embeddings12

Word Embeddings

After tokenization, our next step is to "embed" each token. The embedding table has one row per token ID: for our 22 words, GloVe's is <22, 300>. Embedding a token is simply looking up its row.

tokenID0123…299
cheer000.41−0.15−0.04−0.37…0.19
for11−0.240.120.19−0.27…0.16
old22−0.38−0.07−0.37−0.34…1.12
notre330.010.340.020.32…0.42
dame44−0.090.340.110.26…0.48
⋮⋮⋮⋮⋮⋮⋮⋮
sky2121−0.03−0.220.720.20…−0.08

This gives us a feature vector for each token, similar to the 4,096 features our CNN made for each photo. The embedding is like the "definition" of a token

Recurrent Neural Networks · Word Embeddings13

GloVe Embeddings

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)
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
torch.Size([22, 300])
cheer   cheering 0.61
notre   dame     0.91
up      down     0.75
thunder sky      0.34
Recurrent Neural Networks · Word Embeddings14

Word Embeddings

Converting tokens to embeddings allows us to interpret them as points in high dimensional space, which allows us to compare them against each other!

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

NOTE: In this plot we use PCA to view our embeddings in 2 dimensions but GloVe embeddings are actually <1, 300> for each token

Recurrent Neural Networks · Word Embeddings15

Embeddings

GloVe embeddings are based on co-occurrences, even though up6 and down18 mean opposite things, they appear next to the same words, so they sit close together (0.75).

Embeddings learn whatever patterns the text has, biases included.

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" →
Recurrent Neural Networks · Word Embeddings16

Exploration of Biases in Embeddings

import numpy as np
import torch
import matplotlib.pyplot as plt
# type any words here, then Run,
# NOTE: it will only work if GloVe knows the word
words = ["nurse", "engineer", "teacher", "football"]
vocab = open("glove-20k-words.txt").read().split()
E = torch.tensor(np.load("glove-20k.npy")).float()
def vec(w):
return E[vocab.index(w)]
axis = vec("woman") - vec("man")
axis = axis / axis.norm() # the man-to-woman direction
words = [w for w in words if w in vocab] # 20,002 words
pos = [float(vec(w) @ axis) for w in words]
for w, p in sorted(zip(words, pos), key=lambda t: t[1]):
print(f"{w:12} {p:6.2f}")
cols = ["#002B5B" if p < 0 else "#DCB439" for p in pos]
plt.figure(figsize=(7, 0.4 * len(words) + 1))
plt.barh(words, pos, color=cols)
plt.axvline(0, color="gray")
plt.xlabel('man woman')
plt.show()
Output
football      -0.61
engineer      -0.56
teacher        1.20
nurse          1.86
Plot from the code above
Recurrent Neural Networks · Word Embeddings17

Python RNN by Hand - Embedding Layer

An embedding layer is just a table lookup

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

Basically all NLP models, including LLMs like Claude and ChatGPT share the same two preprocessing steps: tokenization and embedding

Recurrent Neural Networks · RNN from Scratch18

NLP Tasks

Tokenization and embedding are only the preprocessing steps we need before we use an NLP model, they only give us the input for our model.

many to one: label a sentence shake down the thunder positive σ = 0.91 many to many: predict every next word cheer cheer for old notre cheer for old notre dame generation: write one word at a time cheer cheer for old notre cheer for old notre dame encoder-decoder: translation from the sky du ciel reads English writes French

Some tasks we've seen so far are regression and classification, but NLP has some new tasks of its own.

Recurrent Neural Networks · RNN from Scratch19

NLP Task: Generation

All four of the NLP tasks require context. If we are predicting the next token after the current one, after notre3 always comes dame4, but picking the next token after the7 is harder

one token of context two tokens of context the echoes 1/3 thunder 1/3 sky 1/3 up the echoes down the thunder from the sky

We need a model that reads one token at a time but also maintains the context of what we've seen so far over time

Recurrent Neural Networks · RNNs20

Sequence Networks - RNNs (1986)

We can begin to solve the problem of context by using a new model, called a Recurrent Neural Network (RNN)

RNN cell ŷ₁ ŷ1 = softmax(c1Ωyᵀ + by) c1 = tanh(x1Ωxᵀ + c0Ωcᵀ + bc) x₁ = [0.10, −0.10] embedding: E[0] cheer 0 RNN cell ŷ₂ ŷ2 = softmax(c2Ωyᵀ + by) c2 = tanh(x2Ωxᵀ + c1Ωcᵀ + bc) x₂ = [0.10, −0.10] embedding: E[0] cheer 0 c₀ [0, 0] c₁ [0.05, −0.15] c₂ [0.15, −0.20] to the next token tokenize "Cheer, cheer for old Notre Dame"
Recurrent Neural Networks · RNNs21

Exploring the RNN

xₜ <1, 2> Ωx <2, 2> cₜ₋₁ <1, 2> Ωc <2, 2> bc <2> ct = tanh(xtΩxᵀ + ct−1Ωcᵀ + bc) cₜ <1, 2> to the next step Ωy <22, 2> by <22> ŷt = softmax(ctΩyᵀ + by) ŷₜ <1, 22>
Recurrent Neural Networks · RNNs22

Fully Connected Layers vs. RNNs (Old Exam Question)

Recurrent Neural Networks · RNNs23

Activation Functions - tanh

While we've seen the sigmoid and RELU, in RNNs the tanh function is used.

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

Why we use the tanh function will become clear when we starting training RNNs next lecture

Recurrent Neural Networks · RNNs24

Time After Time

Most RNN diagrams depict them in their "unrolled" state, which can be confusing

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

Unlike an FFN, this isn't four different layers:
every RNN cell and output layer shares the same weights.

Recurrent Neural Networks · RNNs25

RNNs (Old Exam Questions)

Recurrent Neural Networks · RNNs26

Python RNN by Hand - Recurrent Layer

One step is the RNN equation: ct = tanh(xt ωxT + ct−1 ωcT + bc)

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 token at a time
c = self._step(X[:, t], c) # same weights, C is our "context"
self.states.append(c)
return torch.stack(self.states[1:], dim=1)

The forward pass is a loop over the tokens, reusing the same weights

Recurrent Neural Networks · RNNs27

What Makes Them "Recurrent"? (Old Exam Question)

Recurrent Neural Networks · RNNs28

The Forward Pass

Our tokens, a random embedding table and output layer, and our two weight matrices:

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_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]])
Recurrent Neural Networks · RNNs29

The Forward Pass

Every word through the RNN, in order: a loop

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])

The three the7s have different context, so a later _step can tell them apart

Recurrent Neural Networks · RNNs30

Context of a Token

Our simple RNN's context matrix is a <1, 2> matrix

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

NOTE: The context of what we've seen so far is often called the hidden state

Recurrent Neural Networks · RNNs31

RNNs in PyTorch

nn.Embedding is the embedding table, nn.RNN runs the whole loop, nn.Linear is the output layer:

from torch import nn
emb = nn.Embedding(22, 2) # Embedding layer
rnn = nn.RNN(2, 2, batch_first=True) # RNN block
fc = nn.Linear(2, 22) # the output layer
with torch.no_grad(): # our weights, not random ones
emb.weight.copy_(E)
rnn.weight_ih_l0.copy_(W_x)
rnn.weight_hh_l0.copy_(W_c)
rnn.bias_ih_l0.zero_()
rnn.bias_hh_l0.zero_()
fc.weight.copy_(W_y)
fc.bias.zero_()
x = emb(torch.tensor([ids])) # 1 song, 26 words
out, c = rnn(x)
y_hat = fc(out).softmax(dim=-1)
print(tuple(out.shape), tuple(y_hat.shape))
print(out[0, 8].round(decimals=3)) # wake up the
e = vocab.index("echoes") # the real next word
print(y_hat[0, 8, e].round(decimals=3))
Output
(1, 26, 2) (1, 26, 22)
tensor([-0.9790, -0.3550])
tensor(0.0900)
Recurrent Neural Networks · RNNs32

Output from an RNN

For our task of predicting the next token in a sequence, the output from our RNNs output layer is a probability of every token in our vocabulary being the next token

\yhat_{t} = \text{softmax}\bp{c_{t} \Omega_{y}\T + b_y} \yhat_{t} = \text{softmax}\bp{c_{t} \Omega_{y}\T + b_y} 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

After wake5 up6 the7: echoes8 gets 0.090

This is identical to how an LLM like ChatGPT or Claude creates output too!

Recurrent Neural Networks · RNNs33

Output from an RNN

To train a text generation model, we can re-use cross entropy loss and think of text generation almost as a classification task.

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ 0.00 0.05 0.10 0.15 ŷ (prediction) ŷ[notre] = 0.013 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 0 1 y (truth) ℒ = −log ŷ[notre] = −log 0.013 = 4.32 cheer for old notre dame wake up the echoes cheering her name send a volley on high shake down thunder from sky token ID token
Recurrent Neural Networks · RNNs34

Python RNN by Hand - Linear Output Layer and Network

We can use the same LinearLayer and Network as last time.

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
Recurrent Neural Networks · RNNs35

Running Our RNN by Hand

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

The number of weights doesn't depend on how long the input sequence is.

Recurrent Neural Networks · RNNs36

Text Generation

Predict the next token, then feed it back in as the next input. We call this process autoregressive text generation

import re
import torch
song = """Cheer, cheer for old Notre Dame,
Wake up the echoes cheering her name,
Send a volley cheer on high,
Shake down the"""
split_song = re.sub(r"[^a-z ]", " ", text.lower()).split() # split song into tokens
num_new_tokens = 10 # generate 3 new tokens
for t in range(num_new_tokens):
# get the token IDs for each token in our song
X = torch.tensor([[vocab.index(token) for token in split_song]])
logits = model.forward(X) # run our RNN on the token IDs to produce prediction logits
split_song.append(vocab[logits[0, -1].argmax()]) # append the most likely next token to the song
print(split_song) # print original song with the 5 new predicted tokens on the end
Output
[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, the, name, the, name, the, name, the, name, the, name]
Recurrent Neural Networks · RNNs37