Unit 03 · Chapter 4

Backpropagation Through Time

Backpropagation Through Time01

Feed-Forward Networks (old exam question)

import torch
import torch.nn as nn
class FFN(nn.Module):
def __init__(self):
super(FFN, self).__init__()
self.F1 = nn.Flatten()
self.L1 = nn.Linear(28*28, 512)
self.R1 = nn.Sigmoid()
self.L2 = nn.Linear(512, 256)
self.R2 = nn.Sigmoid()
self.L3 = nn.Linear(256, 10)
def forward(self, x):
x = self.F1(x)
x = self.L1(x)
x = self.R1(x)
x = self.L2(x)
x = self.R2(x)
x = self.L3(x)
return x
Backpropagation Through Time · Review02

Feed-Forward Networks (old exam question)

Note: You can assume softmax and cross entropy loss are used after the final layer, the two yielding a combined derivative of: ŷ − y

ℒ =ℒ =
\frac{\partial ℒ}{\partial \Omega_1} =\frac{\partial ℒ}{\partial \Omega_1} =
\frac{\partial ℒ}{\partial \Omega_1} =\frac{\partial ℒ}{\partial \Omega_1} =
Backpropagation Through Time · Review03

So Far

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

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   like language

Backpropagation Through Time · Sequence Data04

Tokenization

Tokenization is the process of   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]
Backpropagation Through Time · Sequence Data05

Word Embeddings

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

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

Backpropagation Through Time · Sequence Data06

Recurrent Neural Networks

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> embedding: E[0] cheer 0 tokenize "Cheer, cheer for old Notre Dame"
Backpropagation Through Time · Sequence Data07

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!

Backpropagation Through Time · Sequence Data08

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
Backpropagation Through Time · Sequence Data09

RNNs (Old Exam Questions)

Backpropagation Through Time · Sequence Data10

Backpropagation Through Time

Backpropagation through time (BPTT) is just  , from the last word back to the first

c₀ 0 c₁ x₁ good Ωx Ωc c₂ x₂ luck ŷ₂ Ωx Ωy Ωc ℒ₂ Luke
Backpropagation Through Time · Sequence Data11

Chain Rule - Multiplication and Addition

Along one path the chain rule   the derivatives. When something is used more than once, like ωc at both steps of "Good Luck", we   its paths:

Backpropagation Through Time · Sequence Data12
ℒ =ℒ =
\frac{\partial ℒ}{\partial \Omega_x} =\frac{\partial ℒ}{\partial \Omega_x} =
\frac{\partial ℒ}{\partial \Omega_x} =\frac{\partial ℒ}{\partial \Omega_x} =
Backpropagation Through Time · Sequence Data13

BPTT by Hand - Embedding Layer

Last lecture's classes only went forward. Now each layer gets a backward that takes   and returns  .

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
return self.E[ids] # (B, T, d)
def backward(self, dX): # (B, T, d): dℒ/dx_t
d = self.E.shape[1]
self.dE = torch.zeros_like(self.E)
# each row we looked up gets its x_t's gradient
self.dE.index_add_(0, self.ids.flatten(), dX.reshape(-1, d))
def update(self, lr):
self.E -= lr * self.dE
Backpropagation Through Time · BPTT from Scratch14

BPTT by Hand - Recurrent Layer

The same forward pass as last time, except it also keeps the inputs X for backward.

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):
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
self.X = X # keep the inputs for backward too
c = torch.zeros(B, self.Wc.shape[0]) # c_0
self.states = [c] # every c_t, for BPTT
for t in range(T):
c = self._step(X[:, t], c)
self.states.append(c)
return torch.stack(self.states[1:], dim=1)
Backpropagation Through Time · BPTT from Scratch15

BPTT by Hand - Recurrent Layer Backward

We walk the steps  : each ct gets gradient from   and from  , and the weight gradients are   over every copy.

def backward(self, dC): # (B, T, n_h): dℒ/dc_t from ŷ_t
self.dWx = torch.zeros_like(self.Wx)
self.dWc = torch.zeros_like(self.Wc)
self.db = torch.zeros_like(self.b)
dX = torch.zeros_like(self.X)
dc_next = torch.zeros_like(self.states[0])
for t in reversed(range(self.X.shape[1])): # back
dc = dC[:, t] + dc_next # from ŷ_t and from c_t+1
dz = dc * (1 - self.states[t + 1] ** 2) # tanh'
self.dWx += dz.T @ self.X[:, t] # add up the
self.dWc += dz.T @ self.states[t] # gradient of
self.db += dz.sum(dim=0) # every copy
dX[:, t] = dz @ self.Wx # to the embedding
dc_next = dz @ self.Wc # to c_t-1
return dX
RNNLayer.backward = backward # add it to the class
Backpropagation Through Time · BPTT from Scratch16

BPTT by Hand - Updating the Weights

Every copy of the cell shares ωx, ωc and bc

\Omega_{c} \leftarrow \Omega_{c} - \alpha \frac{\partial ℒ}{\partial \Omega_{c}} \Omega_{c} \leftarrow \Omega_{c} - \alpha \frac{\partial ℒ}{\partial \Omega_{c}}
def update(self, lr): # one gradient descent step
self.Wx -= lr * self.dWx
self.Wc -= lr * self.dWc
self.b -= lr * self.db
RNNLayer.update = update # add it to the class
Backpropagation Through Time · BPTT from Scratch17

BPTT by Hand - Output Layer

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
return X @ self.W.T + self.b
def backward(self, dZ): # (B, T, n_out)
self.dW = (dZ.transpose(1, 2) @ self.X).sum(dim=0)
self.db = dZ.sum(dim=1).sum(dim=0)
return dZ @ self.W # dℒ/dc_t
def update(self, lr):
self.W -= lr * self.dW
self.b -= lr * self.db
Backpropagation Through Time · BPTT from Scratch18

BPTT by Hand - Network

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
def backward(self, d):
for layer in reversed(self.layers):
d = layer.backward(d)
def update(self, lr):
for layer in self.layers:
layer.update(lr)

Network.backward runs the layers in   order, each passing its gradient down, and Network.update steps   at once.

Backpropagation Through Time · BPTT from Scratch19

BPTT by Hand - Cross-Entropy

With softmax and cross-entropy together, the gradient of the logits is just   (the review's d.)), averaged over the 25 predictions.

def cross_entropy(logits, y): # (1, T, V), (1, T)
p = torch.softmax(logits[0], dim=1)
rows = torch.arange(y.shape[1])
loss = -torch.log(p[rows, y[0]]).mean()
d = p.clone()
d[rows, y[0]] -= 1 # softmax + CE: ŷ − y
return loss, (d / y.shape[1])[None]
Backpropagation Through Time · BPTT from Scratch20

Running BPTT by Hand

Last lecture's 2 hidden units are too few to remember the song, so we use 16. Each epoch: forward, BPTT, then  .

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))
ids = torch.tensor([[vocab.index(t) for t in tokens]])
X, y = ids[:, :-1], ids[:, 1:] # predict the next token
torch.manual_seed(0)
model = Network([Embedding(22, 8), RNNLayer(8, 16),
LinearLayer(16, 22)])
for epoch in range(200):
loss, d = cross_entropy(model.forward(X), y)
model.backward(d) # BPTT, by hand
model.update(0.5) # one step of gradient descent
if epoch % 50 == 0:
print(f"epoch {epoch} loss: {loss.item():.4f}")
right = (model.forward(X)[0].argmax(dim=1) == y[0]).sum()
print(right.item(), "of", y.shape[1], "next words right")
Output
epoch 0 loss: 3.1958
epoch 50 loss: 0.2203
epoch 100 loss: 0.0775
epoch 150 loss: 0.0457
25 of 25 next words right
Backpropagation Through Time · BPTT from Scratch21

Text Generation

Predict the next token, then  . 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 ]", " ", song.lower()).split() # split song into tokens
num_new_tokens = 4 # generate 10 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 10 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, old, notre, dame, wake, up, the]
Backpropagation Through Time · BPTT from Scratch22

Vanishing/Exploding Gradients

RNNs are particularly vulnerable to the vanishing gradient problem because we have to compute the gradients of the loss  

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ −4 −2 0 2 4 z 0.00 0.25 0.50 0.75 1.00 at most 0.25 at most 1 sigmoid's slope σ′(z) tanh's slope tanh′(z)

This is why RNNs use tanh, not the sigmoid. The sigmoid's slope is at most 0.25, so 50 steps back shrink the gradient at least 0.2550 ≈ 8 × 10⁻³¹ times. Tanh's slope reaches 1, so it only shrinks the gradient where the cell is saturated.

Backpropagation Through Time · BPTT from Scratch23

Vanishing Gradient

Since you are multiplying increasingly   values with each other during backprop, the gradient eventually trends to  , meaning updates will stop happening.

c₁ c₁₀ c₂₀ c₃₀ c₄₀ c₅₀ ℒ₅₀ × (D Ωc)¹⁰ × (D Ωc)¹⁰ × (D Ωc)¹⁰ × (D Ωc)¹⁰ × (D Ωc)⁹ 9.2×10⁻⁵ 0.0005 0.0033 0.023 0.17 1 size of the gradient
Backpropagation Through Time · BPTT from Scratch24

Exploding Gradient

Almost the opposite of the vanishing gradient, the exploding gradient is when the gradients become  

image/svg+xml Matplotlib v3.11.2, https://matplotlib.org/ 0 200 400 600 800 1000 step 0 1 2 3 4 5 cross-entropy no clipping clipped at 1

An exploding gradient has a simple fix: clip, or put a ceiling on, the size of the gradient we'll accept.

Vanishing gradients are harder: they need a new kind of cell.

Backpropagation Through Time · BPTT from Scratch25

Another Issue with RNNs: Long-Term Dependencies

In last chapter's RNN, change the first word from cheer0 to sky21 and measure how far apart the hidden states are after each word. A word that depends on one far back is a long-term dependency.

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

By the ninth word it's 0.001: the RNN   how the song started. One fix: a   that lets each step choose what to keep

Backpropagation Through Time · Vanishing and Exploding Gradients26

Gates and Computation Graphs

Add a new component called a gate that allows each step choose how much of the   to keep

ŷt <1,22> = softmax( Zy <1,22> ) Zy <1,22> = ct <1,2> ΩyT <2,22> + by <1,22> ct <1,2> = zt <1,2> ⊙ ct−1 <1,2> + (1 − zt <1,2> ) ⊙ c̃t <1,2> zt <1,2> = σ( Zz <1,2> ) c̃t <1,2> = tanh( Zc̃ <1,2> ) Zz <1,2> = xt <1,2> ΩzxT <2,2> + ct−1 <1,2> ΩzcT <2,2> + bz <1,2> Zc̃ <1,2> = xt <1,2> ΩxT <2,2> + ct−1 <1,2> ΩcT <2,2> + bc <1,2> ct−1 <1,2> ct <1,2> xt <1,2> to the next step
Backpropagation Through Time · Vanishing and Exploding Gradients27

Effect of Gates

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
Backpropagation Through Time · LSTMs and GRUs28

Long Short-Term Memory units - LSTMs (1997)

LSTMs introduce the idea of   to help solve the   gradient problem.

ŷt <1,V> = softmax( ct <1,h> ΩyT <h,V> + by <1,V> ) ct <1,h> = ot <1,h> ⊙ tanh( mt <1,h> ) ot <1,h> = σ( xt <1,d> ΩoxT <d,h> + ct−1 <1,h> ΩocT <h,h> + bo <1,h> ) mt <1,h> = ft <1,h> ⊙ mt−1 <1,h> + it <1,h> ⊙ m̃t <1,h> ft <1,h> = σ( xt <1,d> ΩfxT <d,h> + ct−1 <1,h> ΩfcT <h,h> + bf <1,h> ) it <1,h> = σ( xt <1,d> ΩixT <d,h> + ct−1 <1,h> ΩicT <h,h> + bi <1,h> ) m̃t <1,h> = tanh( xt <1,d> ΩgxT <d,h> + ct−1 <1,h> ΩgcT <h,h> + bg <1,h> ) ct−1 <1,h> ct <1,h> mt−1 <1,h> mt <1,h> xt <1,d> to the next step to the next step
Backpropagation Through Time · LSTMs and GRUs29

LSTMs and GRUs

A real gate is its own   layer, so the network learns when to hold on and when to let go

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
Backpropagation Through Time · LSTMs and GRUs30

Breaking Down LSTMs

f_{t} = \sigma\bp{x_{t} \Omega_{fx}\T + c_{t-1} \Omega_{fc}\T + b_f} i_{t} = \sigma\bp{x_{t} \Omega_{ix}\T + c_{t-1} \Omega_{ic}\T + b_i} \tilde{m}_{t} = \tanh\bp{x_{t} \Omega_{gx}\T + c_{t-1} \Omega_{gc}\T + b_g} o_{t} = \sigma\bp{x_{t} \Omega_{ox}\T + c_{t-1} \Omega_{oc}\T + b_o} m_{t} = f_{t} \odot m_{t-1} + i_{t} \odot \tilde{m}_{t} c_{t} = o_{t} \odot \tanh\bp{m_{t}} f_{t} = \sigma\bp{x_{t} \Omega_{fx}\T + c_{t-1} \Omega_{fc}\T + b_f}; i_{t} = \sigma\bp{x_{t} \Omega_{ix}\T + c_{t-1} \Omega_{ic}\T + b_i}; \tilde{m}_{t} = \tanh\bp{x_{t} \Omega_{gx}\T + c_{t-1} \Omega_{gc}\T + b_g}; o_{t} = \sigma\bp{x_{t} \Omega_{ox}\T + c_{t-1} \Omega_{oc}\T + b_o}; m_{t} = f_{t} \odot m_{t-1} + i_{t} \odot \tilde{m}_{t}; c_{t} = o_{t} \odot \tanh\bp{m_{t}}
Backpropagation Through Time · LSTMs and GRUs31

Gated Recurrent Units - GRUs (2014)

GRUs are a simpler version of LSTMs that simplify the gate structure

ŷt <1,V> = softmax( ct <1,h> ΩyT <h,V> + by <1,V> ) ct <1,h> = zt <1,h> ⊙ ct−1 <1,h> + (1 − zt <1,h> ) ⊙ c̃t <1,h> zt <1,h> = σ( xt <1,d> ΩzxT <d,h> + ct−1 <1,h> ΩzcT <h,h> + bz <1,h> ) c̃t <1,h> = tanh( xt <1,d> ΩxT <d,h> + ( rt <1,h> ⊙ ct−1 <1,h> ) ΩcT <h,h> + bc <1,h> ) rt <1,h> = σ( xt <1,d> ΩrxT <d,h> + ct−1 <1,h> ΩrcT <h,h> + br <1,h> ) ct−1 <1,h> ct <1,h> xt <1,d> to the next step
Backpropagation Through Time · LSTMs and GRUs32

Static Embeddings

So far, the inputs to our model are what are called static embeddings, embeddings that are  

what came before the embedding of cheer the hidden state after it cheer word 1 [−1.12, 0.66, −0.08, −0.39, …] c1 = [−0.73, 0.76, −0.51, −0.06, …] cheer cheer word 2 [−1.12, 0.66, −0.08, −0.39, …] c2 = [−0.95, −0.66, 0.85, −0.99, …] send a volley cheer word 17 [−1.12, 0.66, −0.08, −0.39, …] c17 = [−0.89, 0.83, 0.84, −0.98, …] the same every time different every time
Backpropagation Through Time · Toward Attention33

Attention

Bahdanau, Cho and Bengio (2014): before each token it writes, the decoder looks back at every encoder  

from c₁ the c₂ sky c₃ score each: s · cⱼ softmax e₁ e₂ e₃ weighted sum: Σ αⱼ cⱼ α₁ α₂ α₃ v s cielo encoder decoder context vector

Every word written gets  

Backpropagation Through Time · Toward Attention34

Attention Weights

Last chapter's network at the last the7, looking back at 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

Most weight on up6 and the other the7s: their hidden states have the biggest   with this one. Next chapter: attention with learned weights

Backpropagation Through Time · Toward Attention35

Attention

Some parts of our context are more important than others! Attention is a mechanism through which we can  

RNN c1 cheer c2 cheer c3 for c49 on c50 to 49 steps from the first word to the last attention c1 cheer c2 cheer c3 for c49 on c50 to · · · one step from every word
Backpropagation Through Time · Toward Attention36