Recurrent Networks

Week 7 of 18 · Sequences · 7 days

Full curriculum
Week 07 · Sequences

Recurrent Networks

Week 07 · Day 1 of 7

The Recurrence

A task that needs memory, and the layer that carries state forward

By 1045 words

Images have neighbours in two directions and convolution exploits that. Sequences have one direction and an order that carries meaning, and they have a second property images do not: they vary in length. A recurrent layer handles both by processing one element at a time and carrying a state forward.

A task that needs memory

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
print('training sequences', tuple(X_tr.shape))
print('class balance %.3f' % y_tr.float().mean())
print()
for i in range(4):
seq = X_tr[i].tolist()
print('%s first=%d repeated later: %s'
% (''.join(str(d) for d in seq), seq[0], bool(y_tr[i])))
training sequences (8000, 8)
class balance 0.509

95626647 first=9 repeated later: False
16633531 first=1 repeated later: True
37574514 first=3 repeated later: False
74238582 first=7 repeated later: False
import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
from sklearn.linear_model import LogisticRegression
import numpy as np

# A bag of counts: how many of each digit, order discarded.
def counts(x):
return torch.stack([(x == d).sum(dim=1) for d in range(1, 10)],
dim=1).float().numpy()

model = LogisticRegression(max_iter=1000).fit(counts(X_tr), y_tr.numpy())
print('bag of counts, logistic regression %.4f'
% model.score(counts(X_va), y_va.numpy()))
print('always predicting the majority class %.4f'
% max(y_va.float().mean().item(), 1 - y_va.float().mean().item()))
print('\nthe counts do not say which digit came first, so they cannot')
print('separate the classes. Order is the entire signal here.')
bag of counts, logistic regression 0.4960
always predicting the majority class 0.5020

the counts do not say which digit came first, so they cannot
separate the classes. Order is the entire signal here.

The recurrence, written out

Recurrent layer: A layer applied once per position, carrying a hidden state from one step to the next. The same weights are used at every step, which is the sequence version of the weight sharing that makes convolution small.
import torch

torch.manual_seed(0)
d_in, d_hidden = 4, 3
Wx = torch.randn(d_in, d_hidden) * 0.5
Wh = torch.randn(d_hidden, d_hidden) * 0.5
b = torch.zeros(d_hidden)

def run(sequence):
h = torch.zeros(d_hidden)
for x in sequence:
h = torch.tanh(x @ Wx + h @ Wh + b) # the entire recurrence
return h

a = torch.randn(1, d_in)
c = torch.randn(1, d_in)
print('state after [a, c]', run(torch.cat([a, c])).round(decimals=3).tolist())
print('state after [c, a]', run(torch.cat([c, a])).round(decimals=3).tolist())
print('\nsame two inputs, different order, different state.')
print('that is the whole reason this layer exists.')
state after [a, c] [0.4440000057220459, 0.9139999747276306, -0.7350000143051147]
state after [c, a] [0.8899999856948853, -0.13199999928474426, -0.9919999837875366]

same two inputs, different order, different state.
that is the whole reason this layer exists.

PyTorch does the loop for you

import torch
from torch import nn

torch.manual_seed(0)
rnn = nn.RNN(input_size=4, hidden_size=3, batch_first=True)
x = torch.randn(2, 6, 4) # batch 2, 6 steps, 4 features

output, final = rnn(x)
print('input ', tuple(x.shape))
print('output ', tuple(output.shape), ' the state at every step')
print('final ', tuple(final.shape), ' the state after the last step')
print('\nthey agree:',
bool(torch.allclose(output[:, -1, :], final[0])))
input (2, 6, 4)
output (2, 6, 3) the state at every step
final (1, 2, 3) the state after the last step

they agree: True

batch_first is not the default

PyTorch's recurrent layers expect (sequence, batch, features) unless you pass batch_first=True, which gives you the (batch, sequence, features) that every other layer in the library uses. Forgetting it does not raise an error when your batch size and sequence length happen to be compatible, it just trains on transposed data. Always pass it.

Day 1 takeaway

A recurrent layer applies the same weights at every position and carries a state forward, so order changes the result. It returns the state at every step and the state after the last one. Pass batch_first=True so the shapes match the rest of your code.
Week 07 · Day 2 of 7

Why Plain RNNs Forget

The gradient as a product, and what LSTM added to fix it

By 587 words

A plain recurrent layer can, in principle, remember something from a hundred steps ago. In practice it cannot, and the reason is visible in one line of arithmetic.

Why the gradient dies

print('%8s %18s %18s' % ('steps', 'factor 0.8', 'factor 1.2'))
for steps in [5, 10, 25, 50, 100]:
print('%8d %18.8g %18.8g' % (steps, 0.8 ** steps, 1.2 ** steps))
print('\nbackpropagating through t steps multiplies t derivatives.')
print('below one it vanishes; above one it explodes. There is no')
print('setting that is stable for a long sequence.')
steps factor 0.8 factor 1.2
5 0.32768 2.48832
10 0.10737418 6.1917364
25 0.0037778932 95.396217
50 1.4272477e-05 9100.4382
100 2.037036e-10 82817975

backpropagating through t steps multiplies t derivatives.
below one it vanishes; above one it explodes. There is no
setting that is stable for a long sequence.
import torch
from torch import nn

torch.manual_seed(0)
rnn = nn.RNN(1, 16, batch_first=True)

print('%10s %20s' % ('length', 'gradient at step 0'))
for length in [5, 20, 50, 100]:
x = torch.randn(1, length, 1, requires_grad=True)
out, _ = rnn(x)
out[:, -1, :].sum().backward()
print('%10d %20.3e' % (length, x.grad[0, 0].abs().item()))
print('\nthe influence of the first element on the last output')
print('falls away to nothing as the sequence gets longer.')
length gradient at step 0
5 1.438e-02
20 5.273e-07
50 1.087e-14
100 6.320e-28

the influence of the first element on the last output
falls away to nothing as the sequence gets longer.

What LSTM changed

LSTM: A recurrent cell with a separate cell state that is updated by addition rather than by repeated multiplication, plus three learned gates deciding what to forget, what to add and what to output. The additive path is the important part: a sum does not shrink geometrically, so gradients survive far more steps.
import torch
from torch import nn

print('%-12s %12s %s' % ('cell', 'parameters', 'internal transforms'))
for name, layer, transforms in [
('RNN', nn.RNN(16, 32, batch_first=True), 1),
('GRU', nn.GRU(16, 32, batch_first=True), 3),
('LSTM', nn.LSTM(16, 32, batch_first=True), 4)]:
n = sum(p.numel() for p in layer.parameters())
print('%-12s %12d %d' % (name, n, transforms))

torch.manual_seed(0)
lstm = nn.LSTM(1, 16, batch_first=True)
print('\n%10s %20s' % ('length', 'gradient at step 0'))
for length in [5, 20, 50, 100]:
x = torch.randn(1, length, 1, requires_grad=True)
out, _ = lstm(x)
out[:, -1, :].sum().backward()
print('%10d %20.3e' % (length, x.grad[0, 0].abs().item()))
cell parameters internal transforms
RNN 1600 1
GRU 4800 3
LSTM 6400 4

length gradient at step 0
5 3.287e-03
20 3.803e-07
50 3.276e-14
100 8.178e-27
import torch
from torch import nn

torch.manual_seed(0)
lstm = nn.LSTM(4, 8, batch_first=True)
x = torch.randn(2, 5, 4)
output, (h, c) = lstm(x)
print('output ', tuple(output.shape))
print('hidden h ', tuple(h.shape), ' what the layer outputs')
print('cell c ', tuple(c.shape), ' the internal memory')
print('\nLSTM returns a tuple where RNN and GRU return one tensor,')
print('which is the most common source of an unpacking error.')
output (2, 5, 8)
hidden h (1, 2, 8) what the layer outputs
cell c (1, 2, 8) the internal memory

LSTM returns a tuple where RNN and GRU return one tensor,
which is the most common source of an unpacking error.

Day 2 takeaway

Backpropagating through many steps multiplies many derivatives, so a plain recurrent layer forgets. LSTM and GRU add a path where the state is added to rather than multiplied, and gradients survive it. GRU has three internal transforms to LSTM's four and is usually indistinguishable in accuracy.
Week 07 · Day 3 of 7

Building a Sequence Classifier

Embeddings, the three cells, and which state to classify from

By 1100 words

A working sequence classifier needs an embedding at the front, a recurrent layer in the middle, and a decision about which state to hand to the classifier.

Embedding the tokens

import torch
from torch import nn

torch.manual_seed(0)
emb = nn.Embedding(num_embeddings=10, embedding_dim=8)
x = torch.tensor([[1, 5, 9, 0], [2, 2, 3, 4]])

print('input ', tuple(x.shape), ' integers')
print('output ', tuple(emb(x).shape), ' a vector per token')
print('weight ', tuple(emb.weight.shape))
print('\nit is a lookup table, not a matrix multiplication:')
print('row 5 of the table ', emb.weight[5][:4].round(decimals=3).tolist())
print('embedding of token 5', emb(torch.tensor(5))[:4].round(decimals=3).tolist())
input (2, 4) integers
output (2, 4, 8) a vector per token
weight (10, 8)

it is a lookup table, not a matrix multiplication:
row 5 of the table [-0.10199999809265137, 0.7919999957084656, -0.28999999165534973, 0.05299999937415123]
embedding of token 5 [-0.10199999809265137, 0.7919999957084656, -0.28999999165534973, 0.05299999937415123]

Why not one-hot

One-hot encoding a vocabulary of 50,000 words gives every token a 50,000 long vector in which every pair of distinct words is equally dissimilar. An embedding gives each token a short dense vector that is learned, so tokens used in similar ways end up near each other. It is also exactly equivalent to a one-hot vector multiplied by a weight matrix, implemented as a lookup because multiplying by a vector of zeros with a single one in it is a waste of a matrix multiplication.

Which state goes to the classifier

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Classifier(nn.Module):
def __init__(self, pooling='last', cell='lstm', hidden=64):
super().__init__()
self.pooling = pooling
self.emb = nn.Embedding(10, 32)
rnn_cls = {'rnn': nn.RNN, 'gru': nn.GRU, 'lstm': nn.LSTM}[cell]
self.rnn = rnn_cls(32, hidden, batch_first=True)
self.head = nn.Linear(hidden, 2)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
if self.pooling == 'last':
h = out[:, -1, :]
elif self.pooling == 'mean':
h = out.mean(dim=1)
else:
h = out.max(dim=1).values
return self.head(h)

torch.manual_seed(0)
print('%-10s %12s' % ('pooling', 'accuracy'))
for pooling in ['last', 'mean', 'max']:
torch.manual_seed(0)
print('%-10s %12.4f' % (pooling, fit(Classifier(pooling=pooling))))
pooling accuracy
last 0.9960
mean 0.9245
max 0.9820

The three cells on the real task

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Classifier(nn.Module):
def __init__(self, cell='lstm', hidden=64):
super().__init__()
self.emb = nn.Embedding(10, 32)
rnn_cls = {'rnn': nn.RNN, 'gru': nn.GRU, 'lstm': nn.LSTM}[cell]
self.rnn = rnn_cls(32, hidden, batch_first=True)
self.head = nn.Linear(hidden, 2)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out[:, -1, :])

print('%-8s %12s %12s' % ('cell', 'params', 'accuracy'))
for cell in ['rnn', 'gru', 'lstm']:
torch.manual_seed(0)
model = Classifier(cell=cell)
acc = fit(model)
print('%-8s %12d %12.4f'
% (cell, sum(p.numel() for p in model.parameters()), acc))
cell params accuracy
rnn 6722 0.6500
gru 19266 0.9985
lstm 25538 0.9960

Day 3 takeaway

An embedding turns token indices into learned dense vectors and is a lookup table rather than a multiplication. Take the last state when the answer depends on the end of the sequence, and pool over all states when evidence can appear anywhere. Try both, because which one wins depends on the task.
Week 07 · Day 4 of 7

Direction and Length

Bidirectional reading, and the padding that quietly corrupts your state

By 1007 words

Two more architectural choices, and then the practical problem that dominates real sequence work: examples that are not all the same length.

Reading in both directions

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Classifier(nn.Module):
def __init__(self, bidirectional=False, layers=1, hidden=64):
super().__init__()
self.emb = nn.Embedding(10, 32)
self.rnn = nn.LSTM(32, hidden, num_layers=layers,
bidirectional=bidirectional, batch_first=True)
self.head = nn.Linear(hidden * (2 if bidirectional else 1), 2)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out[:, -1, :])

print('%-22s %12s %12s' % ('', 'params', 'accuracy'))
for label, kwargs in [('one layer', dict()),
('two layers', dict(layers=2)),
('bidirectional', dict(bidirectional=True))]:
torch.manual_seed(0)
model = Classifier(**kwargs)
print('%-22s %12d %12.4f'
% (label, sum(p.numel() for p in model.parameters()),
fit(model)))
params accuracy
one layer 25538 0.9960
two layers 58818 0.7425
bidirectional 50754 0.9920

Bidirectional is not allowed if the future is unknown

Reading the sequence backwards as well as forwards helps a great deal when the whole sequence is available at once, which is true for classifying a finished sentence. It is impossible when you are predicting the next element, or processing a live stream, because the backward pass would need to read input that has not happened yet. Using it in a forecasting model is a leak, and a subtle one, because nothing raises.

Sequences of different lengths

import torch
from torch import nn
from torch.nn.utils.rnn import pad_sequence, pack_padded_sequence

seqs = [torch.tensor([1, 2, 3, 4, 5]),
torch.tensor([6, 7]),
torch.tensor([8, 9, 1])]
lengths = torch.tensor([len(s) for s in seqs])
padded = pad_sequence(seqs, batch_first=True)
print('padded to a rectangle:')
print(padded)

torch.manual_seed(0)
emb = nn.Embedding(10, 4)
lstm = nn.LSTM(4, 5, batch_first=True)

# the naive way: the LSTM walks over the padding too
out, (h_naive, _) = lstm(emb(padded))

packed = pack_padded_sequence(emb(padded), lengths, batch_first=True,
enforce_sorted=False)
_, (h_packed, _) = lstm(packed)

print('\nfinal state for the short sequence [6, 7]:')
print(' padded ', h_naive[0, 1].round(decimals=3).tolist())
print(' packed ', h_packed[0, 1].round(decimals=3).tolist())
print('\nthey differ: the padded version kept processing three zeros')
print('after the sequence ended, so its final state is wrong.')
padded to a rectangle:
tensor([[1, 2, 3, 4, 5],
[6, 7, 0, 0, 0],
[8, 9, 1, 0, 0]])

final state for the short sequence [6, 7]:
padded [-0.06700000166893005, -0.21199999749660492, 0.328000009059906, -0.04399999976158142, -0.08799999952316284]
packed [-0.09700000286102295, -0.15399999916553497, 0.009999999776482582, -0.010999999940395355, -0.1509999930858612]

they differ: the padded version kept processing three zeros
after the sequence ended, so its final state is wrong.

Packing is not an optimisation, it is a correctness fix

It is often described as saving computation, and it does. The reason to use it is that the final hidden state of a padded sequence is the state after processing the padding, not after processing the data. For a model that takes the last state, that is simply the wrong number. Either pack the sequence, or gather the state at each example's real final index yourself.

import torch
from torch import nn
from torch.nn.utils.rnn import pad_sequence

torch.manual_seed(0)
seqs = [torch.tensor([1, 2, 3, 4, 5]), torch.tensor([6, 7]),
torch.tensor([8, 9, 1])]
lengths = torch.tensor([len(s) for s in seqs])
padded = pad_sequence(seqs, batch_first=True)

emb = nn.Embedding(10, 4)
lstm = nn.LSTM(4, 5, batch_first=True)
out, _ = lstm(emb(padded))

# gather the output at each sequence's real last position
idx = (lengths - 1).view(-1, 1, 1).expand(-1, 1, out.size(2))
last = out.gather(1, idx).squeeze(1)
print('states gathered at the real final step:')
print(last.round(decimals=3))
print('\nand for mean pooling, divide by the true length:')
mask = (padded != 0).unsqueeze(-1)
mean = (out * mask).sum(1) / lengths.unsqueeze(1)
print(mean.round(decimals=3))
states gathered at the real final step:
tensor([[-0.1190, -0.1840, -0.0420, 0.0230, -0.1500],
[-0.0970, -0.1540, 0.0100, -0.0110, -0.1510],
[ 0.2020, 0.0690, 0.1850, -0.0380, -0.0780]],
grad_fn=<RoundBackward1>)

and for mean pooling, divide by the true length:
tensor([[ 0.0210, -0.0560, 0.0650, -0.0510, -0.0560],
[-0.0670, -0.1310, 0.0260, -0.0080, -0.1290],
[ 0.1580, 0.0440, 0.1230, 0.0620, -0.0950]],
grad_fn=<RoundBackward1>)

Day 4 takeaway

Bidirectional layers help when the whole sequence is available and are a leak when it is not. Pad to a rectangle, then either pack the batch or gather the state at each real final index, because the state after the padding is not the state after the data.
Week 07 · Day 5 of 7

Recurrent Failure Modes

Clipping, sequence length, and the dropout argument that does nothing

By 1254 words

Recurrent models fail in ways that are specific to them, and all three are avoidable once you know the shape of the failure.

Exploding gradients, and the one-line fix

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Classifier(nn.Module):
def __init__(self, hidden=64):
super().__init__()
self.emb = nn.Embedding(10, 32)
self.rnn = nn.RNN(32, hidden, batch_first=True)
self.head = nn.Linear(hidden, 2)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out[:, -1, :])

# Clipping bounds the size of a step, so measure the steps rather
# than the final accuracy, which barely moves on a task this easy.
for clip in [None, 1.0]:
torch.manual_seed(0)
model = Classifier()
opt = torch.optim.Adam(model.parameters(), lr=0.02)
loss_fn = nn.CrossEntropyLoss()
worst = 0.0
for _ in range(3):
model.train()
for xb, yb in train_loader:
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
# measured AFTER clipping, so this is the step actually taken
used = torch.cat([prm.grad.flatten()
for prm in model.parameters()]).norm()
worst = max(worst, used.item())
opt.step()
print('%-18s largest step actually taken %8.2f'
% ('without clipping' if clip is None else 'with clipping',
worst))
without clipping largest step actually taken 4.29
with clipping largest step actually taken 1.00

Without clipping the largest step the optimiser took was several times the ceiling clipping imposes. That is the whole mechanism: the gradient computed is the same either way, and clipping shortens the step before it is applied while leaving its direction alone. A maximum norm of 1.0 is the standard starting point. On a task this small the model survives either way; on a long sequence model or a transformer, leaving it out is how a run that was going well becomes nan at step forty thousand.

Sequence length is a hyperparameter

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Classifier(nn.Module):
def __init__(self, cell, hidden=64):
super().__init__()
self.emb = nn.Embedding(10, 32)
self.rnn = {'rnn': nn.RNN, 'lstm': nn.LSTM}[cell](
32, hidden, batch_first=True)
self.head = nn.Linear(hidden, 2)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out[:, -1, :])

print('%8s %14s %14s' % ('length', 'plain RNN', 'LSTM'))
for length in [6, 10, 16]:
Xa, ya = make_sequences(8000, length=length, seed=0)
Xb, yb = make_sequences(2000, length=length, seed=1)
tl = DataLoader(TensorDataset(Xa, ya), batch_size=64, shuffle=True)
vl = DataLoader(TensorDataset(Xb, yb), batch_size=512)
row = []
for cell in ['rnn', 'lstm']:
torch.manual_seed(0)
row.append(fit(Classifier(cell), epochs=10, clip=1.0,
loader=tl, val=vl))
print('%8d %14.4f %14.4f' % (length, row[0], row[1]))
length plain RNN LSTM
6 0.7815 1.0000
10 0.5555 0.8760
16 0.4930 0.5225

Recurrent dropout is not ordinary dropout

import torch
from torch import nn

torch.manual_seed(0)
stacked = nn.LSTM(16, 32, num_layers=2, dropout=0.3, batch_first=True)
print('num_layers=2 with dropout=0.3: applied between the two layers')

single = nn.LSTM(16, 32, num_layers=1, dropout=0.3, batch_first=True)
x = torch.randn(2, 5, 16)
single.train()
a, _ = single(x)
b, _ = single(x)
print('one layer with dropout=0.3, two forward passes identical:',
bool(torch.allclose(a, b)))
print('\nthe dropout argument only acts between stacked layers, so on a')
print('single layer it silently does nothing at all.')
num_layers=2 with dropout=0.3: applied between the two layers
one layer with dropout=0.3, two forward passes identical: True

the dropout argument only acts between stacked layers, so on a
single layer it silently does nothing at all.

Dropout inside a recurrent layer needs the same mask every step

Applying an independent dropout mask at each time step injects fresh noise into the state on every step, and over twenty steps that destroys the memory the layer exists to maintain. Correct recurrent dropout uses the same mask at every step of a sequence. PyTorch's dropout argument sidesteps the question by only applying between stacked layers. If you want it on the input or the output, add an ordinary nn.Dropout there yourself.

Day 5 takeaway

Clip the gradient norm at 1.0 for anything recurrent. Expect a plain RNN to fall apart as sequences lengthen while an LSTM holds up. And know that the dropout argument does nothing on a single layer.
Week 07 · Day 6 of 7

Predicting the Next Element

One output per position, and generating by feeding the model itself

By 772 words

Classifying a sequence uses one output. Predicting the next element uses one output per position, and the difference changes how you build the batch, the loss and the evaluation.

One prediction per position

import torch
from torch import nn

torch.manual_seed(0)

class NextToken(nn.Module):
def __init__(self, vocab=10, hidden=32):
super().__init__()
self.emb = nn.Embedding(vocab, 16)
self.rnn = nn.LSTM(16, hidden, batch_first=True)
self.head = nn.Linear(hidden, vocab)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out) # a score per position per token

model = NextToken()
x = torch.randint(0, 10, (4, 12))
logits = model(x)
print('input ', tuple(x.shape))
print('output', tuple(logits.shape), '= (batch, position, vocabulary)')

# the target at each position is the next token
inputs, targets = x[:, :-1], x[:, 1:]
logits = model(inputs)
loss = nn.CrossEntropyLoss()(logits.reshape(-1, 10), targets.reshape(-1))
print('\nloss over %d positions: %.4f'
% (targets.numel(), loss.item()))
print('CrossEntropyLoss wants (N, classes), so both are flattened.')
input (4, 12)
output (4, 12, 10) = (batch, position, vocabulary)

loss over 44 positions: 2.2874
CrossEntropyLoss wants (N, classes), so both are flattened.

The shift is the whole task

Feed the model positions 0 to n-1 and ask it to predict positions 1 to n. Every position is a training example, so a batch of 32 sequences of length 128 gives you roughly four thousand predictions rather than 32. That efficiency is why language models are trained this way, and week 11 builds on it directly.

Learning a real pattern

import torch
from torch import nn

torch.manual_seed(0)

# A repeating pattern with a period of 5, plus noise the model cannot
# predict, so a perfect score is impossible and progress is meaningful.
g = torch.Generator().manual_seed(0)
base = torch.tensor([1, 2, 3, 4, 5])
seq = base.repeat(400).clone()
noise = torch.rand(seq.shape, generator=g) < 0.1
seq[noise] = torch.randint(1, 6, (int(noise.sum()),), generator=g)
data = seq.view(-1, 20)

class NextToken(nn.Module):
def __init__(self, vocab=6, hidden=32):
super().__init__()
self.emb = nn.Embedding(vocab, 16)
self.rnn = nn.LSTM(16, hidden, batch_first=True)
self.head = nn.Linear(hidden, vocab)

def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out)

model = NextToken()
opt = torch.optim.Adam(model.parameters(), lr=5e-3)
loss_fn = nn.CrossEntropyLoss()
for epoch in range(1, 61):
inputs, targets = data[:, :-1], data[:, 1:]
opt.zero_grad()
loss = loss_fn(model(inputs).reshape(-1, 6), targets.reshape(-1))
loss.backward()
torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
opt.step()
if epoch % 20 == 0:
acc = (model(inputs).argmax(-1) == targets).float().mean()
print('epoch %2d loss %.4f next-token accuracy %.4f'
% (epoch, loss.item(), acc.item()))
print('\n10 percent of the tokens are random, so about 0.90 is the ceiling.')
epoch 20 loss 0.8798 next-token accuracy 0.8516
epoch 40 loss 0.4998 next-token accuracy 0.8858
epoch 60 loss 0.4304 next-token accuracy 0.9074

10 percent of the tokens are random, so about 0.90 is the ceiling.

Generating from it

import torch
from torch import nn

torch.manual_seed(0)
g = torch.Generator().manual_seed(0)
base = torch.tensor([1, 2, 3, 4, 5])
seq = base.repeat(400).clone()
noise = torch.rand(seq.shape, generator=g) < 0.1
seq[noise] = torch.randint(1, 6, (int(noise.sum()),), generator=g)
data = seq.view(-1, 20)

class NextToken(nn.Module):
def __init__(self, vocab=6, hidden=32):
super().__init__()
self.emb = nn.Embedding(vocab, 16)
self.rnn = nn.LSTM(16, hidden, batch_first=True)
self.head = nn.Linear(hidden, vocab)
def forward(self, x, state=None):
out, state = self.rnn(self.emb(x), state)
return self.head(out), state

model = NextToken()
opt = torch.optim.Adam(model.parameters(), lr=5e-3)
loss_fn = nn.CrossEntropyLoss()
for _ in range(60):
opt.zero_grad()
logits, _ = model(data[:, :-1])
loss_fn(logits.reshape(-1, 6), data[:, 1:].reshape(-1)).backward()
opt.step()

model.eval()
for temperature in [0.2, 1.0, 2.0]:
torch.manual_seed(0)
token = torch.tensor([[1]])
state, produced = None, [1]
with torch.no_grad():
for _ in range(19):
logits, state = model(token, state)
probs = (logits[0, -1] / temperature).softmax(-1)
token = torch.multinomial(probs, 1).view(1, 1)
produced.append(token.item())
print('temperature %.1f: %s'
% (temperature, ''.join(str(t) for t in produced)))
temperature 0.2: 12345123451234512345
temperature 1.0: 12345123544223451234
temperature 2.0: 12345125544122453425

Low temperature sharpens the distribution and the model repeats the pattern cleanly. High temperature flattens it and the output drifts into noise. That single parameter is the same one every text generation interface exposes, and week 11 uses it again on real language.

Day 6 takeaway

For next-element prediction, feed positions 0 to n-1 and target 1 to n, then flatten both for the loss. Every position becomes a training example. Generate by feeding the model its own output and carrying the state forward, and use temperature to trade faithfulness against variety.
Week 07 · Day 7 of 7

Where Recurrence Stands

The full model, the baselines, and an honest account of what replaced it

By 1167 words

The week assembled, and an honest account of where recurrent models stand now that attention exists.

The complete classifier

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
import time

class SequenceClassifier(nn.Module):
def __init__(self, vocab=10, embed=32, hidden=64, layers=1,
bidirectional=True, dropout=0.2):
super().__init__()
self.emb = nn.Embedding(vocab, embed)
self.drop = nn.Dropout(dropout)
self.rnn = nn.LSTM(embed, hidden, num_layers=layers,
bidirectional=bidirectional, batch_first=True)
self.head = nn.Linear(hidden * (2 if bidirectional else 1), 2)

def forward(self, x):
out, _ = self.rnn(self.drop(self.emb(x)))
pooled = torch.cat([out.max(dim=1).values, out.mean(dim=1)], dim=1)
return self.head(self.drop(pooled[:, :out.size(2)]))

torch.manual_seed(0)
model = SequenceClassifier()
start = time.time()
acc = fit(model, epochs=8, clip=1.0)
print('parameters %d' % sum(p.numel() for p in model.parameters()))
print('accuracy %.4f' % acc)
print('time %.0fs' % (time.time() - start))
parameters 50754
accuracy 0.9440
time 8s

The comparison

import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

def make_sequences(n, length=8, seed=0):
"""Sequences of digits 1 to 9, balanced by construction.

The label is 1 if the digit at position 0 appears again later. The
rest of the sequence is drawn from the other eight digits, and for
the positive half the first digit is planted at one random later
position, so the classes are exactly balanced.

A bag of counts cannot answer it. Both classes contain repeated
digits, and counts never record which digit came first. Answering it
means holding position 0 in memory until the sequence ends."""
g = torch.Generator().manual_seed(seed)
first = torch.randint(1, 10, (n, 1), generator=g)
rest = torch.randint(1, 9, (n, length - 1), generator=g)
rest = rest + (rest >= first).long() # 1 to 9, excluding first
y = torch.randint(0, 2, (n,), generator=g)
where = torch.randint(0, length - 1, (n, 1), generator=g)
idx = torch.arange(length - 1).unsqueeze(0)
plant = (y.unsqueeze(1) == 1) & (idx == where)
rest = torch.where(plant, first.expand_as(rest), rest)
return torch.cat([first, rest], dim=1), y

X_tr, y_tr = make_sequences(8000, seed=0)
X_va, y_va = make_sequences(2000, seed=1)
train_loader = DataLoader(TensorDataset(X_tr, y_tr), batch_size=64,
shuffle=True)
val_loader = DataLoader(TensorDataset(X_va, y_va), batch_size=512)
def fit(model, epochs=10, lr=3e-3, clip=None, loader=None, val=None):
torch.manual_seed(0)
opt = torch.optim.Adam(model.parameters(), lr=lr)
loss_fn = nn.CrossEntropyLoss()
for _ in range(epochs):
model.train()
for xb, yb in (loader or train_loader):
opt.zero_grad()
loss_fn(model(xb), yb).backward()
if clip:
torch.nn.utils.clip_grad_norm_(model.parameters(), clip)
opt.step()
model.eval()
right = seen = 0
with torch.no_grad():
for xb, yb in (val or val_loader):
right += (model(xb).argmax(1) == yb).sum().item()
seen += yb.numel()
return right / seen
class Simple(nn.Module):
def __init__(self, cell, bidirectional=False):
super().__init__()
self.emb = nn.Embedding(10, 32)
self.rnn = {'rnn': nn.RNN, 'gru': nn.GRU, 'lstm': nn.LSTM}[cell](
32, 64, bidirectional=bidirectional, batch_first=True)
self.head = nn.Linear(64 * (2 if bidirectional else 1), 2)
def forward(self, x):
out, _ = self.rnn(self.emb(x))
return self.head(out[:, -1, :])

class BagOfEmbeddings(nn.Module):
def __init__(self):
super().__init__()
self.emb = nn.Embedding(10, 32)
self.head = nn.Sequential(nn.Linear(32, 64), nn.ReLU(),
nn.Linear(64, 2))
def forward(self, x):
return self.head(self.emb(x).mean(dim=1))

print('%-28s %10s %10s' % ('', 'params', 'accuracy'))
for label, maker in [('bag of embeddings', BagOfEmbeddings),
('plain RNN', lambda: Simple('rnn')),
('GRU', lambda: Simple('gru')),
('LSTM', lambda: Simple('lstm')),
('bidirectional LSTM',
lambda: Simple('lstm', bidirectional=True))]:
torch.manual_seed(0)
model = maker()
print('%-28s %10d %10.4f'
% (label, sum(p.numel() for p in model.parameters()),
fit(model, epochs=8, clip=1.0)))
params accuracy
bag of embeddings 2562 0.6315
plain RNN 6722 0.6085
GRU 19266 0.9820
LSTM 25538 0.8120
bidirectional LSTM 50754 0.8800

Recurrent models have been largely replaced, and are not obsolete

The reason is structural. A recurrent layer must process position 500 after position 499, so it cannot use a GPU's parallelism along the sequence, and training time grows linearly with length. Attention computes every position at once. That single difference is most of why transformers took over, and it is the subject of the next two weeks.

Where recurrence still wins: very long or unbounded streams, where attention's cost grows with the square of the length; small models on small devices; and anything genuinely online, where you receive one element at a time and must respond before the next arrives. A carried state is exactly the right shape for that, and an attention window is not.

The checklist

  1. batch_first=True, every time.
  2. Embedding at the front, not one-hot.
  3. Pack the batch or gather at the true final index; never take the last state of a padded sequence.
  4. Clip the gradient norm at 1.0.
  5. LSTM or GRU rather than a plain RNN for anything longer than about twenty steps.
  6. Bidirectional only when the whole sequence is available, never for forecasting.
  7. Try last-state and pooled representations; the answer varies by task.
  8. Fit a bag-of-embeddings baseline, because on many real tasks order matters far less than people assume.

Day 7 takeaway

Recurrent layers carry a state, which makes them the natural shape for streaming and unbounded input, and inherently sequential, which is why attention replaced them almost everywhere else. Get the padding and the clipping right and they are reliable. Always check them against a model that ignores order entirely.