Unit 03 · Chapter 4
Backpropagation Through Time
CSE 30124 · Introduction to Artificial Intelligence William Theisen · University of Notre Dame
Feed-Forward Networks (old exam question)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
a.) Draw the computation graph for the network.
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
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 ]
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
Recurrent Neural Networks
xₜ
<1, 2>
Ωx
<2, 2>
cₜ₋₁
<1, 2>
Ωc
<2, 2>
bc
<2>
c t = tanh( x t Ω x ᵀ + c t−1 Ω c ᵀ + b c )
cₜ
<1, 2>
to the next step
Ωy
<22, 2>
by
<22>
ŷ t = softmax( c t Ω y ᵀ + b y )
ŷₜ
<1, 22>
embedding: E[0]
cheer
0
tokenize
"Cheer, cheer for old Notre Dame"
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}
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 wake 5 up 6 the 7 : echoes 8 gets 0.090
This is identical to how an LLM like ChatGPT or Claude creates output too!
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
RNNs (Old Exam Questions)
Old exam question: Draw the computation graph for an RNN , for the sentence "Good Luck", with a word level tokenizer . Only produce output for the final token .
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
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:
b.) Give the loss for our "Good Luck" RNN (output only for the final token) as a single nested equation.
ℒ =
c.) Give the derivative chain for calculating the gradient of the input weights ω x .
\frac{\partial ℒ}{\partial \Omega_x} =
d.) Write the actual equation you’d use to calculate the gradient for the input weights ω x .
\frac{\partial ℒ}{\partial \Omega_x} =
BPTT by Hand - Embedding Layer
Last lecture's classes only went forward . Now each layer gets a backward that takes and returns .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
BPTT by Hand - Recurrent Layer
The same forward pass as last time, except it also keeps the inputs X for backward .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 )
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
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}}
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
BPTT by Hand - Output Layer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
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.
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 ]
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 .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
Text Generation
Predict the next token , then . We call this process autoregressive text generation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 ]
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.25 50 ≈ 8 × 10⁻³¹ times. Tanh's slope reaches 1 , so it only shrinks the gradient where the cell is saturated .
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
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.
Another Issue with RNNs: Long-Term Dependencies
In last chapter's RNN , change the first word from cheer 0 to sky 21 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
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>
Ωy T
<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>
Ωzx T
<2,2>
+
ct−1
<1,2>
Ωzc T
<2,2>
+
bz
<1,2>
Zc̃
<1,2>
=
xt
<1,2>
Ωx T
<2,2>
+
ct−1
<1,2>
Ωc T
<2,2>
+
bc
<1,2>
ct−1
<1,2>
ct
<1,2>
xt
<1,2>
to the next step
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
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>
Ωy T
<h,V>
+
by
<1,V>
)
ct
<1,h>
=
ot
<1,h>
⊙ tanh(
mt
<1,h>
)
ot
<1,h>
= σ(
xt
<1,d>
Ωox T
<d,h>
+
ct−1
<1,h>
Ωoc T
<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>
Ωfx T
<d,h>
+
ct−1
<1,h>
Ωfc T
<h,h>
+
bf
<1,h>
)
it
<1,h>
= σ(
xt
<1,d>
Ωix T
<d,h>
+
ct−1
<1,h>
Ωic T
<h,h>
+
bi
<1,h>
)
m̃t
<1,h>
= tanh(
xt
<1,d>
Ωgx T
<d,h>
+
ct−1
<1,h>
Ωgc T
<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
LSTMs and GRUs
A real gate is its own layer, so the network learns when to hold on and when to let go
LSTM (1997 ): gates and a separate
GRU (2014 ): an and a
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
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}}
Gated Recurrent Units - GRUs (2014)
GRUs are a simpler version of LSTMs that simplify the gate structure
ŷt
<1,V>
= softmax(
ct
<1,h>
Ωy T
<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>
Ωzx T
<d,h>
+
ct−1
<1,h>
Ωzc T
<h,h>
+
bz
<1,h>
)
c̃t
<1,h>
= tanh(
xt
<1,d>
Ωx T
<d,h>
+ (
rt
<1,h>
⊙
ct−1
<1,h>
)
Ωc T
<h,h>
+
bc
<1,h>
)
rt
<1,h>
= σ(
xt
<1,d>
Ωrx T
<d,h>
+
ct−1
<1,h>
Ωrc T
<h,h>
+
br
<1,h>
)
ct−1
<1,h>
ct
<1,h>
xt
<1,d>
to the next step
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, …]
c 1 = [−0.73, 0.76, −0.51, −0.06, …]
cheer
cheer
word 2
[−1.12, 0.66, −0.08, −0.39, …]
c 2 = [−0.95, −0.66, 0.85, −0.99, …]
send
a
volley
cheer
word 17
[−1.12, 0.66, −0.08, −0.39, …]
c 17 = [−0.89, 0.83, 0.84, −0.98, …]
the same every time
different every time
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
Attention Weights
Last chapter's network at the last the 7 , 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 up 6 and the other the 7 s: their hidden states have the biggest with this one. Next chapter: attention with learned weights
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