Machine Learning · Lecture 11

Lecture 11
Going Deep, and Architectures for Structure: Residual Networks, CNNs and RNNs

Part III · Deep learning  |  shattered gradients, residual connections, batch and layer normalisation, convolution, channels, pooling and receptive fields, LeNet to ResNet, recurrent networks, backpropagation through time, vanishing and exploding gradients, LSTM and GRU, state-space models  |  reading: Prince, Understanding Deep Learning, ch. 10–11 (and notebooks 11.1–11.3); Goodfellow, Bengio & Courville, Deep Learning, ch. 9–10

Cartoon: the express laneA long chain of boxes labelled "layer" with a winding path through them, and a straight express lane running alongside, labelled "identity". A stick figure on the express lane says: I'll take the shortcut. Another figure says: and the layers only have to add what's missing. layerlayerlayer identity I'll take theexpress lane. And each layer only addswhat is still missing.
A residual connection gives the signal, and its gradient, a straight path through any number of layers
In this lecture
  1. Why depth is hard: shattered gradients
  2. Residual connections
  3. Normalisation
  4. Convolution: a sliding pattern detector
  5. Pooling, invariance and receptive fields
  6. Convolutional networks in practice
  7. Recurrent networks and the gradient through time
  8. LSTMs at work: forecasting and writing
  9. The limits of recurrence, and its return
  10. Summary, exercises, projects, reading

Lecture 10 trained networks with a handful of layers. This lecture has two halves. The first asks what goes wrong with fifty or a hundred layers, even with good initialisation, and fixes it with the two ideas that made very deep networks routine: residual connections, which let each block add to its input instead of replacing it, and normalisation, which keeps activations at a controlled size. The second half builds the structure of the data into the architecture. Images look the same wherever you shift them, so convolutional networks apply the same small detector at every position. Sequences unfold in time, so recurrent networks apply the same update at every step, and inherit a severe version of the gradient problems of the first half, which the LSTM's gates were invented to solve.

By the end of this lecture you should be able to explain the shattered-gradient problem and why residual networks avoid it; prove that unnormalised residual blocks double the variance and that batch normalisation is invariant to the scale of the weights; define convolution with channels, stride and padding, prove its translation equivariance and count its parameters; compute receptive fields; describe the architectures from LeNet to ResNet; write the backpropagation-through-time gradient as a product of Jacobians and explain vanishing and exploding gradients; and explain how the LSTM's cell state lets gradients survive, and why attention and state-space models replaced or revived recurrence.

1 — Why depth is hard: shattered gradients

He initialisation (Lecture 10b) keeps the size of activations and gradients stable through a deep ReLU network. But size is not everything. Balduzzi et al. (2017) looked at the shape of the gradient: how \(\partial f/\partial x\) varies as the input \(x\) moves along a line. For a shallow network it varies smoothly, so nearby inputs have similar gradients and a gradient step that helps one input helps its neighbours. As a plain network gets deeper, every layer splits the input space into more linear pieces (Lecture 10a), the gradient changes direction at every boundary, and it ends up looking like white noise: the gradient is shattered. A shattered gradient carries almost no information that generalises from one input to the next.

Shattered gradients

The derivative \(df/dx\) of a randomly initialised network's output with respect to its single input, at 256 points in \([-2,2]\). Top: a plain network. Bottom: a residual network of the same depth. Increase the depth.

code — measuring how shattered the gradient is
import numpy as np
import jax, jax.numpy as jnp

xs = jnp.linspace(-2, 2, 256)[:, None]                    # 256 inputs on a line, processed as one batch

def make_net(depth, residual, seed, width=200):
    """He-initialised ReLU network on one input, with batch normalisation before every ReLU
    (as in Balduzzi et al. 2017). Plain: h <- ReLU(BN(h W)). Residual: h <- h + ReLU(BN(h W))."""
    r = np.random.default_rng(seed)
    W_in, b_in = jnp.array(r.normal(0, 1, (1, width))), jnp.array(r.normal(0, 1, width))
    Ws = [jnp.array(r.normal(0, np.sqrt(2 / width), (width, width))) for _ in range(depth)]
    w_out = jnp.array(r.normal(0, np.sqrt(1 / width), (width, 1)))
    def f(x):
        h = jax.nn.relu(x @ W_in + b_in)
        for W in Ws:
            z = h @ W
            mu, sd = jax.lax.stop_gradient(z.mean(0)), jax.lax.stop_gradient(z.std(0))   # batch statistics, held fixed
            z = (z - mu) / (sd + 1e-5)
            h = h + jax.nn.relu(z) if residual else jax.nn.relu(z)
        return (h @ w_out)[:, 0]
    return f

def gradient_curve(depth, residual, seed=0):
    f = make_net(depth, residual, seed)
    return np.array(jax.grad(lambda x: f(x).sum())(xs)[:, 0])   # df/dx at each of the 256 inputs

def autocorr(g, lag=1):
    g = g - g.mean(); return (g[:-lag] * g[lag:]).mean() / g.var()

print('depth   correlation of df/dx at neighbouring inputs (mean of 5 networks)')
print('            plain     residual')
curves = {}
for depth in [1, 2, 4, 8, 16, 32, 50]:
    cp = [autocorr(gradient_curve(depth, False, s)) for s in range(5)]
    cr = [autocorr(gradient_curve(depth, True, s)) for s in range(5)]
    curves[depth] = (gradient_curve(depth, False), gradient_curve(depth, True))
    print(f'{depth:5d}   {np.mean(cp):9.3f}   {np.mean(cr):9.3f}')
depth   correlation of df/dx at neighbouring inputs (mean of 5 networks)
            plain     residual
    1       0.977       0.978
    2       0.947       0.952
    4       0.821       0.921
    8       0.514       0.906
   16      -0.112       0.918
   32      -0.039       0.901
   50       0.024       0.926

The code uses JAX, a library that computes gradients by the reverse-mode automatic differentiation of Lecture 10b (jax.grad) and compiles numerical code for speed; it trains every network in this lecture. The correlation between the gradients at neighbouring inputs is 0.98 for one layer in both kinds of network. For plain networks it falls to 0.51 at depth 8 and to zero (white noise) by depth 16. For residual networks it stays around 0.9 at every depth up to 50.

theorem 11.1 — gradients shatter in deep plain networks (informal)

For a ReLU network with batch normalisation and \(L\) hidden layers acting on one input, the correlation between the gradients at two nearby inputs decays like \(2^{-L}\).

For a residual network with batch normalisation, it decays only like \(1/\sqrt L\) (Balduzzi et al., 2017).

2 — Residual connections

definition 11.1 — residual block

A residual block adds a learned correction to its input instead of replacing it:

$$h_{l+1}=h_l+F_l(h_l),$$

where the residual branch \(F_l\) is a small network (typically two layers with an activation between them, plus normalisation). A residual network (ResNet) stacks many such blocks (He et al., 2016).

If a block's weights are zero, it computes the identity, so adding blocks can never make the best achievable fit worse: a deep residual network can always imitate a shallower one. The deeper reason they train well shows in the gradient. Differentiating \(h_{l+1}=h_l+F_l(h_l)\) gives \(\frac{\partial h_{l+1}}{\partial h_l}=I+\frac{\partial F_l}{\partial h_l}\), and multiplying through the blocks,

$$\frac{\partial h_L}{\partial h_0}=\prod_{l=0}^{L-1}\Big(I+\frac{\partial F_l}{\partial h_l}\Big)=I+\sum_l\frac{\partial F_l}{\partial h_l}+\sum_{l<m}\frac{\partial F_m}{\partial h_m}\frac{\partial F_l}{\partial h_l}+\cdots.$$

The product expands into a sum over all \(2^L\) subsets of blocks: every path that passes through some branches and skips the rest. The identity term guarantees that some gradient reaches every layer however deep the network. Veit, Wilber and Belongie (2016) took this "ensemble of paths" view literally: deleting a single block from a trained 110-layer ResNet barely changes its accuracy, while deleting a layer from a plain network such as VGG destroys it, and most of the gradient during training flows through paths that pass through only about 5 to 17 of the network's 54 blocks. A residual network behaves like a collection of relatively shallow networks sharing weights.

There is a catch, which the next proposition makes precise: if each branch preserves the variance of its input (as He initialisation arranges) and is added to the input, the variance doubles at every block.

proposition 11.2 — unnormalised residual blocks double the variance

Suppose \(F(h)=\mathrm{ReLU}(hW)V\) with \(W\) and \(V\) independent, mean-zero, with variances \(2/n\) and \(1/n\), so that \(\operatorname{Var}F(h)=\operatorname{Var}h\) (Theorem 10.7).

Then

$$\operatorname{Var}\big(h+F(h)\big)=2\operatorname{Var}(h),$$

and after \(L\) blocks the variance is \(2^L\) times the input's.

$$\operatorname{Var}(h+F(h))=\operatorname{Var}h+\operatorname{Var}F(h)+2\operatorname{Cov}(h,F(h)).$$

Each coordinate of \(F(h)\) is \(\sum_jV_{jk}\mathrm{ReLU}(hW)_j\), and \(V\) is independent of \(h\) and \(W\) with mean zero, so

$$\mathbb E[h_kF(h)_k]=\sum_j\mathbb E[V_{jk}]\,\mathbb E[h_k\mathrm{ReLU}(hW)_j]=0:$$

the covariance vanishes. Hence the variance doubles, and by induction it is multiplied by \(2^L\). \(\square\)

3 — Normalisation

definition 11.2 — batch and layer normalisation

Batch normalisation (Ioffe and Szegedy, 2015) standardises each unit across the examples in the minibatch, then applies a learned scale \(\gamma\) and shift \(\beta\):

$$\mathrm{BN}(z)_{ij}=\gamma_j\frac{z_{ij}-\mu_j}{\sqrt{\sigma_j^2+\epsilon}}+\beta_j,\qquad\mu_j=\frac1m\sum_iz_{ij},\quad\sigma_j^2=\frac1m\sum_i(z_{ij}-\mu_j)^2.$$

At test time \(\mu_j,\sigma_j\) are replaced by running averages from training.

Layer normalisation (Ba, Kiros and Hinton, 2016) standardises each example across its units instead (\(\mu_i=\frac1n\sum_jz_{ij}\), and so on), so it needs no batch and behaves identically in training and testing; it is the standard choice in transformers (Lecture 12).

proposition 11.3 — batch normalisation ignores the scale of the weights

For any \(c>0\) (and \(\epsilon=0\)),

$$\mathrm{BN}(X(cW))=\mathrm{BN}(XW).$$

Consequently the loss, as a function of \(W\), is constant along rays \(\{cW:c>0\}\), and its gradient is orthogonal to \(W\) and shrinks like \(1/\|W\|\).

Scaling \(W\) by \(c\) scales every \(z_{ij}\), every \(\mu_j\) and every \(\sigma_j\) by \(c\), so each standardised value is unchanged.

If \(L(cW)=L(W)\) for all \(c\), differentiating in \(c\) at \(c=1\) gives

$$\langle\nabla L(W),W\rangle=0;$$

differentiating \(L(cW)=L(W)\) in \(W\) gives

$$c\nabla L(cW)=\nabla L(W),$$

so the gradient scales like \(1/c\). \(\square\)

So batch normalisation makes each layer's output insensitive to the scale of its weights, removing the knife-edge of Lecture 10b's initialisation, and its effective learning rate becomes \(\eta/\|W\|^2\), adjusted automatically as weights grow. Where it is placed matters for residual networks. Normalising the branch's input ("pre-norm", \(h+F(\mathrm{N}(h))\)) makes each branch add a fixed amount of variance, so the variance grows linearly rather than exponentially; normalising after the addition ("post-norm", \(\mathrm N(h+F(h))\)) holds it constant. The code checks both claims.

code — variance through residual blocks; scale invariance
# Residual blocks double the variance; normalisation fixes it
def residual_stack(depth, norm, seed=0, width=256, n=512):
    r = np.random.default_rng(seed); h = r.normal(size=(n, width)); out = []
    for l in range(depth):
        W, V = r.normal(0, np.sqrt(2 / width), (width, width)), r.normal(0, np.sqrt(1 / width), (width, width))   # each block preserves variance
        f_in = h
        if norm:                                           # batch normalisation of the block's input
            f_in = (h - h.mean(0)) / (h.std(0) + 1e-5)
        h = h + np.maximum(f_in @ W, 0) @ V
        out.append(h.var())
    return out
v_plain, v_bn = residual_stack(20, False), residual_stack(20, True)
print('block:                   ' + ''.join(f'{b:>9d}' for b in [1, 2, 5, 10, 20]))
print('variance, no norm:       ' + ''.join(f'{v_plain[b - 1]:9.3g}' for b in [1, 2, 5, 10, 20]))
print('variance, batch norm:    ' + ''.join(f'{v_bn[b - 1]:9.3g}' for b in [1, 2, 5, 10, 20]))
print('ratio of successive variances (no norm), mean over blocks:', np.mean(np.array(v_plain[1:]) / np.array(v_plain[:-1])).round(3))

# Batch normalisation makes a layer's output independent of the scale of its weights
rng = np.random.default_rng(1); X = rng.normal(size=(64, 10)); W = rng.normal(size=(10, 5))
bn = lambda Z: (Z - Z.mean(0)) / Z.std(0)
print('max |BN(X W) - BN(X (7.3 W))| =', np.abs(bn(X @ W) - bn(X @ (7.3 * W))).max())
block:                           1        2        5       10       20
variance, no norm:            1.99      3.9     33.2 1.01e+03 1.26e+06
variance, batch norm:         1.99        3     5.97     11.1     20.7
ratio of successive variances (no norm), mean over blocks: 2.025
max |BN(X W) - BN(X (7.3 W))| = 9.992007221626409e-16

Variance through thirty blocks

Width 48, 96 random inputs, He-initialised branches \(\mathrm{ReLU}(hW)V\). The variance of the activations after each block, on a log scale, for four designs.

The doubling is exact on average (ratio 2.025 per block), reaching \(10^6\) after 20 blocks. With the branch input normalised the variance grows by about 1 per block (20.7 after 20 blocks), and normalising after the addition holds it at 1. Now train fifty-layer networks on Fashion-MNIST for three epochs.

code — fifty layers on Fashion-MNIST: plain, residual, residual with normalisation
import gzip, time
def idx(path):
    raw = gzip.open(path, 'rb').read(); nd = raw[3]
    dims = [int.from_bytes(raw[4 + 4 * i: 8 + 4 * i], 'big') for i in range(nd)]
    return np.frombuffer(raw, np.uint8, offset=4 + 4 * nd).reshape(dims)
D = '../L10/data/'
Xtr = idx(D + 'train-images-idx3-ubyte.gz').astype(np.float32) / 255; ytr = idx(D + 'train-labels-idx1-ubyte.gz').astype(np.int32)
Xte = idx(D + 't10k-images-idx3-ubyte.gz').astype(np.float32) / 255; yte = idx(D + 't10k-labels-idx1-ubyte.gz').astype(np.int32)
mu, sd = Xtr.mean(), Xtr.std(); Xtr, Xte = (Xtr - mu) / sd, (Xte - mu) / sd

def adam_train(loss_fn, params, data, epochs, lr=1e-3, batch=128, seed=0, eval_fn=None):
    """Minibatch Adam with JAX gradients (Lecture 2's update, Lecture 10b's backprop done by jax.grad)."""
    X, Y = data; m = jax.tree_util.tree_map(jnp.zeros_like, params); v = jax.tree_util.tree_map(jnp.zeros_like, params)
    @jax.jit
    def step(params, m, v, t, xb, yb):
        l, g = jax.value_and_grad(loss_fn)(params, xb, yb)
        m = jax.tree_util.tree_map(lambda a, b: 0.9 * a + 0.1 * b, m, g)
        v = jax.tree_util.tree_map(lambda a, b: 0.999 * a + 0.001 * b * b, v, g)
        params = jax.tree_util.tree_map(lambda p, a, b: p - lr * (a / (1 - 0.9**t)) / (jnp.sqrt(b / (1 - 0.999**t)) + 1e-8), params, m, v)
        return params, m, v, l
    r = np.random.default_rng(seed); t = 0; hist = []
    for ep in range(epochs):
        perm = r.permutation(len(X)); tot = 0.0; nb = 0
        for s in range(0, len(X) - batch + 1, batch):
            t += 1; b = perm[s:s + batch]
            params, m, v, l = step(params, m, v, t, X[b], Y[b]); tot += float(l); nb += 1
        hist.append((ep + 1, tot / nb, eval_fn(params) if eval_fn else None))
    return params, hist

def mlp_init(depth, width, seed):
    k = jax.random.split(jax.random.PRNGKey(seed), depth + 2)
    return {'in': jax.random.normal(k[0], (784, width)) * np.sqrt(2 / 784),
            'W': [jax.random.normal(k[i + 1], (width, width)) * np.sqrt(2 / width) for i in range(depth)],
            'out': jax.random.normal(k[-1], (width, 10)) * np.sqrt(1 / width)}
def deep_forward(p, X, kind):
    h = jax.nn.relu(X.reshape(len(X), -1) @ p['in'])
    for W in p['W']:
        if kind == 'plain':
            h = jax.nn.relu(h @ W)
        elif kind == 'residual':
            h = h + jax.nn.relu(h @ W)
        else:                                               # residual with layer normalisation inside the block
            z = (h - h.mean(1, keepdims=True)) / (h.std(1, keepdims=True) + 1e-5)
            h = h + jax.nn.relu(z @ W)
    return h @ p['out']
def xent(logits, y):
    return -jnp.mean(jax.nn.log_softmax(logits)[jnp.arange(len(y)), y])

print('50 hidden layers of width 128, Adam lr 0.001, 3 epochs')
print('architecture                     loss after epoch 1, 2, 3          test accuracy')
for kind in ['plain', 'residual', 'residual + layer norm']:
    p0 = mlp_init(50, 128, 0)
    lf = lambda p, xb, yb, k=kind: xent(deep_forward(p, xb, k), yb)
    acc = lambda p, k=kind: float(jnp.mean(deep_forward(p, Xte, k).argmax(1) == yte))
    t0 = time.time(); p, hist = adam_train(lf, p0, (Xtr, ytr), 3, eval_fn=acc)
    print(f'{kind:30s}   ' + '  '.join(f'{h[1]:9.4g}' for h in hist) + f'   {hist[-1][2]:13.4f}   ({time.time() - t0:.0f} s)')
50 hidden layers of width 128, Adam lr 0.001, 3 epochs
architecture                     loss after epoch 1, 2, 3          test accuracy
plain                                1.637      1.801      1.709          0.2000   (14 s)
residual                         1.027e+09   2.32e+04   2.14e+04          0.3051   (15 s)
residual + layer norm                1.149     0.4985     0.4167          0.8049   (43 s)

The plain fifty-layer network barely learns: 20% test accuracy, two classes in ten, despite He initialisation (its gradients are shattered). The residual network without normalisation is worse in a different way: its activations are \(2^{50}\) times too large at initialisation, the first epoch's loss is \(10^9\), and it never recovers. Adding layer normalisation inside each block gives 80.5% after three epochs and a loss still falling fast. (A three-layer MLP reached 88% in Lecture 10b; the point here is not that fifty layers help on Fashion-MNIST, but that with residual connections and normalisation they can be trained at all.)

spot check 11.1

A residual network has 10 unnormalised blocks, each of whose branches preserves the variance of its input. By what factor does the variance of the activations grow from input to output?

Proposition 11.2.
\(2^{10}=1024\). With the branch input normalised, it would grow only from 1 to about 11.
spot check 11.2

Why do transformers use layer normalisation rather than batch normalisation?

What does each method average over?
Sequences in a batch have different lengths and contents, and at generation time the "batch" may be a single sequence; per-example statistics avoid all of this.

4 — Convolution: a sliding pattern detector

A fully connected layer treats a 28 × 28 image as a list of 784 unrelated numbers: it would have to learn separately what an edge looks like at every position, and it would not know that neighbouring pixels belong together. Images have two kinds of structure that a better layer should use. Patterns are local: an edge, a corner, a texture lives in a small patch. And they are translation-invariant in meaning: an edge is an edge wherever it appears. A convolution uses both. It slides one small filter over the image and records how strongly each patch matches it.

definition 11.3 — convolutional layer

Given an input with \(C\) channels, \(x[i,j,c]\), and \(C'\) filters of size \(k\times k\times C\), a convolutional layer computes the output channels

$$y[i,j,c']=b_{c'}+\sum_{a=0}^{k-1}\sum_{b=0}^{k-1}\sum_{c=1}^Cx[s\,i+a,\ s\,j+b,\ c]\ w[a,b,c,c'],$$

followed by an activation. \(s\) is the stride; padding with zeros around the border controls the output size ("same" padding keeps it equal to the input's).

Deep-learning libraries compute this cross-correlation and call it convolution; flipping the filter gives the mathematical convolution, and since the filter is learned, the distinction does not matter.

The layer has \(k^2CC'+C'\) parameters, whatever the size of the image.

Convolution playground

Draw on the 16 × 16 input (click and drag). Choose a 3 × 3 filter or type your own weights. The feature map shows the filter's response at every position (sky positive, rose negative); then an optional ReLU and a 2 × 2 max-pool.

The vertical-edge filter responds positively where brightness increases from left to right and negatively where it decreases, and is silent on uniform regions and horizontal strokes. A network's first layer learns filters like these from data (Section 6). The defining mathematical property is that shifting the input shifts the output.

proposition 11.4 — convolution is translation-equivariant

Let \(T_{u,v}\) shift an image by \((u,v)\):

$$(T_{u,v}x)[i,j]=x[i-u,j-v].$$

For a convolution with stride 1 (ignoring the image border, or on an infinite or periodic image),

$$\operatorname{conv}(T_{u,v}x)=T_{u,v}\operatorname{conv}(x).$$

Any entrywise activation preserves this, so a stack of convolutions and activations is translation-equivariant.

$$\operatorname{conv}(T_{u,v}x)[i,j]=\sum_{a,b}x[i+a-u,j+b-v]\,w[a,b]=\operatorname{conv}(x)[i-u,j-v]=\big(T_{u,v}\operatorname{conv}(x)\big)[i,j].$$

An entrywise function \(\sigma\) satisfies \(\sigma(T x)=T\sigma(x)\). \(\square\)

This is the image analogue of the permutation equivariance of graph layers (Lecture 9): the architecture builds in a symmetry of the data, so it does not have to be learned. (Stride and pooling break exact equivariance into equivariance for shifts by multiples of the stride, one reason modern networks remain somewhat sensitive to small shifts; Zhang, 2019.)

code — equivariance, parameter counts and receptive fields
# Convolution commutes with translation; and it needs far fewer parameters than a dense layer
def conv2d(img, k):                                         # 'valid' cross-correlation, as in deep-learning libraries
    H, W = img.shape; a, b = k.shape
    return np.array([[np.sum(img[i:i + a, j:j + b] * k) for j in range(W - b + 1)] for i in range(H - a + 1)])
rng = np.random.default_rng(0)
img = np.asarray(Xtr[0]); k = rng.normal(size=(3, 3))
shift = lambda A, dy, dx: np.roll(np.roll(A, dy, 0), dx, 1)
a = conv2d(shift(img, 2, 3), k)[3:-3, 3:-3]                # convolve the shifted image (ignoring wrapped borders)
b = shift(conv2d(img, k), 2, 3)[3:-3, 3:-3]                # shift the convolved image
print('translation equivariance: max |conv(shift(x)) - shift(conv(x))| =', np.abs(a - b).max())
dense = 28 * 28 * 26 * 26                                   # a dense map from a 28x28 image to a 26x26 feature map
print(f'parameters for a 28x28 -> 26x26 map: dense {dense:,}; one 3x3 convolution {9}; 32 channels {32 * 9 + 32}')
def receptive_field(layers):                                # layers: list of (kernel size, stride)
    r, j = 1, 1                                             # field size and spacing of neighbouring outputs, in pixels
    for k_, s_ in layers:
        r += (k_ - 1) * j; j *= s_
    return r
for L in range(1, 6):
    print(f'{L} stacked 3x3 convolutions see a {receptive_field([(3, 1)] * L)}-pixel-wide patch;'
          f' with a 2x2 max-pool after each, {receptive_field([(3, 1), (2, 2)] * L)} pixels')
translation equivariance: max |conv(shift(x)) - shift(conv(x))| = 0.0
parameters for a 28x28 -> 26x26 map: dense 529,984; one 3x3 convolution 9; 32 channels 320
1 stacked 3x3 convolutions see a 3-pixel-wide patch; with a 2x2 max-pool after each, 4 pixels
2 stacked 3x3 convolutions see a 5-pixel-wide patch; with a 2x2 max-pool after each, 10 pixels
3 stacked 3x3 convolutions see a 7-pixel-wide patch; with a 2x2 max-pool after each, 22 pixels
4 stacked 3x3 convolutions see a 9-pixel-wide patch; with a 2x2 max-pool after each, 46 pixels
5 stacked 3x3 convolutions see a 11-pixel-wide patch; with a 2x2 max-pool after each, 94 pixels

5 — Pooling, invariance and receptive fields

Equivariance says where a pattern is, which is what a segmentation network needs. A classifier needs whether it is there: invariance. Max-pooling takes the maximum over each \(2\times2\) block (stride 2), keeping the strongest response and discarding its exact position, and halves the resolution, which also cuts computation. A final global pooling over all positions makes the output invariant to translation.

Stacking layers grows the receptive field, the patch of the input that can influence one unit. Each \(3\times3\) convolution adds 2 pixels to the width; each stride-2 step doubles the spacing at which later layers sample, so later additions count double.

proposition 11.5 — receptive fields

For a stack of layers with kernel sizes \(k_1,\dots,k_L\) and strides \(s_1,\dots,s_L\), the receptive field of a unit in layer \(L\) has width

$$r_L=1+\sum_{l=1}^L(k_l-1)\prod_{m<l}s_m.$$

Let \(j_l=\prod_{m\le l}s_m\) be the distance, in input pixels, between neighbouring units of layer \(l\). A unit of layer \(l\) sees \(k_l\) neighbouring units of layer \(l-1\), whose receptive fields are offset by \(j_{l-1}\) from one another, so

$$r_l=r_{l-1}+(k_l-1)j_{l-1}$$

with \(r_0=1\), \(j_0=1\). Unrolling gives the formula. \(\square\)

spot check 11.3

A network applies a 3 × 3 convolution (stride 1), a 2 × 2 max-pool (stride 2), then another 3 × 3 convolution (stride 1). How wide is the receptive field of a unit in the last layer, in input pixels?

\(r=1+(3-1)\cdot1+(2-1)\cdot1+(3-1)\cdot2\): after the pool, neighbouring units are 2 pixels apart.
\(1+2+1+4=8\). A second max-pool would add \((2-1)\times2=2\), giving the 10 pixels the code prints for two blocks of convolution and pooling.

6 — Convolutional networks in practice

The classic architectures are stacks of the same three ingredients, convolution, nonlinearity and pooling, followed by a few dense layers. LeNet-5 (LeCun et al., 1998) read handwritten digits with two convolutional layers and about 60,000 parameters. AlexNet (Krizhevsky, Sutskever and Hinton, 2012) scaled the same recipe to 1.2 million ImageNet photographs in 1,000 classes with five convolutional layers, ReLUs, dropout, data augmentation and two GPUs, and cut the top-5 error from 26% to 15%, starting the deep-learning era. VGG (2014) showed that stacks of small \(3\times3\) filters work best. ResNet (He et al., 2016) added residual connections and batch normalisation and trained 152 layers, reaching 3.6% top-5 error, below the estimated human error on the benchmark. Here is a small network of the same kind on Fashion-MNIST.

data — Fashion-MNIST

70,000 28 × 28 grey-scale images of ten kinds of clothing from Zalando's catalogue (Xiao, Rasul and Vollgraf, 2017; MIT licence): 60,000 for training, 10,000 for testing. As in Lecture 10b.

code — a convolutional network for Fashion-MNIST
# A small convolutional network for Fashion-MNIST, trained with Adam (gradients by jax.grad)
Xtr4, Xte4 = np.asarray(Xtr)[..., None], np.asarray(Xte)[..., None]       # images as height x width x 1 channel
def conv(x, w):
    return jax.lax.conv_general_dilated(x, w, (1, 1), 'SAME', dimension_numbers=('NHWC', 'HWIO', 'NHWC'))
def maxpool(x):
    return jax.lax.reduce_window(x, -jnp.inf, jax.lax.max, (1, 2, 2, 1), (1, 2, 2, 1), 'VALID')
k = jax.random.split(jax.random.PRNGKey(0), 6)
cnn0 = {'c1': jax.random.normal(k[0], (3, 3, 1, 32)) * np.sqrt(2 / 9), 'b1': jnp.zeros(32),
        'c2': jax.random.normal(k[1], (3, 3, 32, 64)) * np.sqrt(2 / 288), 'b2': jnp.zeros(64),
        'd1': jax.random.normal(k[2], (7 * 7 * 64, 128)) * np.sqrt(2 / 3136), 'e1': jnp.zeros(128),
        'd2': jax.random.normal(k[3], (128, 10)) * np.sqrt(1 / 128), 'e2': jnp.zeros(10)}
def cnn(p, x):
    h = maxpool(jax.nn.relu(conv(x, p['c1']) + p['b1']))      # 28x28x1 -> 28x28x32 -> 14x14x32
    h = maxpool(jax.nn.relu(conv(h, p['c2']) + p['b2']))      # -> 14x14x64 -> 7x7x64
    h = jax.nn.relu(h.reshape(len(x), -1) @ p['d1'] + p['e1'])
    return h @ p['d2'] + p['e2']
n_par = sum(v.size for v in jax.tree_util.tree_leaves(cnn0))
predict_all = lambda p, X: np.concatenate([np.asarray(cnn(p, X[i:i + 2000]).argmax(1)) for i in range(0, len(X), 2000)])
acc = lambda p: float(np.mean(predict_all(p, Xte4) == yte))
t0 = time.time()
cnn_p, hist = adam_train(lambda p, xb, yb: xent(cnn(p, xb), yb), cnn0, (Xtr4, ytr), 5, eval_fn=acc)
np.save("cnn_filters.npy", np.asarray(cnn_p["c1"]))                # keep the first-layer filters to plot
print(f'{n_par:,} parameters; training took {time.time() - t0:.0f} s')
for ep, l, a in hist:
    print(f'epoch {ep}: training loss {l:.4f}   test accuracy {a:.4f}')
names = ['T-shirt', 'trouser', 'pullover', 'dress', 'coat', 'sandal', 'shirt', 'sneaker', 'bag', 'ankle boot']
pred = predict_all(cnn_p, Xte4)
C = np.zeros((10, 10), int); np.add.at(C, (yte, pred), 1)
off = [(C[i, j], names[i], names[j]) for i in range(10) for j in range(10) if i != j]
print('most common confusions (true -> predicted):', ', '.join(f'{a} -> {b} ({c})' for c, a, b in sorted(off, reverse=True)[:4]))
print('per-class test accuracy:', ', '.join(f'{names[i]} {C[i, i] / C[i].sum():.2f}' for i in range(10)))
421,642 parameters; training took 262 s
epoch 1: training loss 0.4356   test accuracy 0.8678
epoch 2: training loss 0.2785   test accuracy 0.8973
epoch 3: training loss 0.2362   test accuracy 0.9011
epoch 4: training loss 0.2056   test accuracy 0.9088
epoch 5: training loss 0.1823   test accuracy 0.9041
most common confusions (true -> predicted): shirt -> T-shirt (169), shirt -> coat (141), shirt -> pullover (82), pullover -> coat (70)
per-class test accuracy: T-shirt 0.89, trouser 0.98, pullover 0.88, dress 0.95, coat 0.90, sandal 0.98, shirt 0.54, sneaker 0.99, bag 0.98, ankle boot 0.96

After two epochs the convolutional network has passed every multilayer perceptron of Lecture 10b except the best-tuned one, and after four it reaches 90.9% test accuracy. That is about two points better than the same optimiser (Adam) gave the MLP after ten epochs (88.5%), and less than one point better than the best-tuned MLP (AdamW with warm-up and a cosine schedule, 90.2%). A modest gain, and an honest one: Fashion-MNIST images are small, centred and aligned, so the translation equivariance that the convolution builds in has little variation to exploit. Convolutional networks pull far ahead on photographs, where the object can be anywhere, and with longer training and data augmentation they reach about 93–95% on this dataset as well. The fifth epoch is slightly worse than the fourth, a first sign of over-fitting, which the regularisers of Lecture 10b would delay.

The errors are concentrated in one class. Sneakers, trousers, bags and sandals are recognised 98–99% of the time, but shirts only 54% of the time; most shirt errors are called T-shirts (169 of 1,000), coats (141) or pullovers (82). At 28 × 28 pixels the difference between a shirt and a pullover is a collar and a few buttons, and some of these labels are hard for people too. The confusion matrix is worth more than the headline accuracy: it says which distinctions the data supports.

The 32 first-layer filters of the trained network (3 × 3 each; sky positive, rose negative weights), sorted by their weight norm

What has the network learned? Its first layer is directly interpretable: many of the 32 filters are small edge and gradient detectors at various orientations (positive weights on one side, negative on the other), and a few look like spots or centre–surround patterns; at 3 × 3 there is not much room for more. These are the kinds of filter found in the first visual area of the mammalian cortex (Hubel and Wiesel, 1962) and in every image network ever trained. Deeper layers combine these into textures, parts and objects; visualising them needs more machinery (feature visualisation by optimising inputs, Olah et al., 2017), and the patterns become increasingly class-specific.

history — from the visual cortex to ImageNet

David Hubel and Torsten Wiesel found in the late 1950s that neurons in the cat's visual cortex respond to edges at particular orientations and positions ("simple cells") and that others respond to the same edge over a range of positions ("complex cells"); they shared the 1981 Nobel Prize in Physiology or Medicine. Kunihiko Fukushima's neocognitron (1980) built this hierarchy into a network of alternating feature-detecting and pooling layers, trained without gradients. Yann LeCun and colleagues at Bell Labs combined it with backpropagation in 1989 to read handwritten zip codes for the US Postal Service, and by the late 1990s LeNet read a large fraction of the cheques written in the United States. Then progress stalled until data and computing caught up: Fei-Fei Li's ImageNet (2009) supplied labelled photographs by the million, GPUs supplied the arithmetic, and AlexNet's 2012 win made convolutional networks the standard for vision almost overnight.

big picture — convolutional networks today

Convolutional networks read medical images, from diabetic retinopathy screening (Gulshan et al., 2016) to tumour detection in radiology and pathology, where most of the AI devices cleared by the US Food and Drug Administration operate. Every smartphone camera runs convolutional networks for denoising, low-light and portrait effects, and U-Net-style convolutional networks are the denoisers inside image-generating diffusion models. Vision transformers (Lecture 12) now match or beat them on large datasets, but modern convolutional designs (ConvNeXt, Liu et al., 2022) remain competitive, and convolution is still the method of choice when data are limited or computation is tight.

7 — Recurrent networks and the gradient through time

A sentence, a temperature record or a heartbeat is a sequence of variable length, and what matters at time \(t\) may depend on what happened long before. A recurrent network reads the sequence one step at a time, carrying a hidden state that summarises the past, and applies the same weights at every step: the time analogue of convolution's weight sharing across space.

definition 11.4 — recurrent neural network

A (vanilla, or Elman) recurrent network updates a hidden state \(h_t\in\mathbb R^n\) from the input \(x_t\):

$$h_t=\tanh\big(W h_{t-1}+Ux_t+b\big),\qquad\hat y_t=g(Vh_t),$$

with the same \(W,U,V,b\) at every step. It is trained by backpropagation through time: unroll the recurrence into a deep network with one layer per time step and shared weights, and apply Theorem 10.5, adding up the gradients from every step for each shared weight.

Unrolled over \(T\) steps, a recurrent network is a \(T\)-layer network, and the gradient of a loss at time \(T\) with respect to the state at time 0 passes through every step.

proposition 11.6 — vanishing and exploding gradients through time

With \(D_t=\operatorname{diag}\big(1-h_t^2\big)\),

$$\frac{\partial h_T}{\partial h_0}=\prod_{t=T}^{1}D_tW,\qquad\Big\|\frac{\partial h_T}{\partial h_0}\Big\|\le\|W\|^T.$$

So if the largest singular value of \(W\) is below 1, the gradient vanishes exponentially in \(T\); it can grow only if \(\|W\|>1\), and then it may explode (Bengio, Simard and Frasconi, 1994; Pascanu, Mikolov and Bengio, 2013).

By the chain rule, \(\partial h_t/\partial h_{t-1}=D_tW\) (the derivative of \(\tanh\) is \(1-\tanh^2\)), and the Jacobian over \(T\) steps is the product.

Since \(|1-h^2|\le1\), \(\|D_t\|\le1\), and the operator norm is submultiplicative:

$$\|\prod D_tW\|\le\prod\|D_t\|\|W\|\le\|W\|^T.\qquad\square$$
code — the gradient through 100 steps of a vanilla RNN
# Gradients through time: the norm of d h_T / d h_0 for a vanilla tanh RNN
def rnn_jacobian_norms(rho, T=100, n=64, seed=0):
    r = np.random.default_rng(seed)
    W = r.normal(size=(n, n)); W *= rho / np.max(np.abs(np.linalg.eigvals(W)))     # spectral radius rho
    U = r.normal(0, 1 / np.sqrt(4), (4, n)); h = np.zeros(n); J = np.eye(n); norms = []
    for t in range(T):
        h = np.tanh(h @ W + r.normal(size=4) @ U)
        J = J @ (W * (1 - h ** 2)[None, :])               # chain rule: d h_t / d h_{t-1} = W diag(1 - h_t^2)
        norms.append(np.linalg.norm(J, 2))
    return norms
print('spectral radius   ||d h_T / d h_0|| for T = 1, 10, 25, 50, 100')
for rho in [0.5, 0.9, 1.0, 1.5, 3.0]:
    nrm = rnn_jacobian_norms(rho)
    print(f'{rho:15.1f}   ' + '  '.join(f'{nrm[T - 1]:9.2e}' for T in [1, 10, 25, 50, 100]))
spectral radius   ||d h_T / d h_0|| for T = 1, 10, 25, 50, 100
            0.5    8.39e-01   5.33e-05   2.27e-12   1.50e-24   4.84e-49
            0.9    1.51e+00   1.31e-02   2.14e-06   7.45e-13   2.58e-25
            1.0    1.68e+00   3.80e-02   2.55e-05   7.45e-11   2.97e-21
            1.5    2.52e+00   1.51e+00   1.22e-01   1.76e-03   7.11e-08
            3.0    5.03e+00   2.10e+02   8.75e+03   1.05e+06   1.88e+10

The table shows Proposition 11.6 at work. With spectral radius 0.5 or 0.9 the gradient over 100 steps is below \(10^{-24}\): whatever happened 100 steps ago has no effect on learning. The more surprising rows are 1.0 and 1.5. Although \(W\) itself does not shrink vectors, the gradient still vanishes, from 2.5 at one step to \(7\times10^{-8}\) at 100 steps, because the tanh units saturate: when \(|h|\) is near 1 the factor \(1-h^2\) in \(D_t\) is near 0. Only at radius 3 does the gradient explode, to \(10^{10}\). There is no setting of the scale that makes a vanilla RNN carry gradient over a hundred steps.

The two failures need different fixes. Exploding gradients are easy to stop: gradient clipping rescales the gradient whenever its norm exceeds a threshold (Pascanu, Mikolov and Bengio, 2013). Vanishing gradients need a different architecture, one with a path along which the derivative is close to 1.

definition 11.5 — long short-term memory (LSTM)

An LSTM (Hochreiter and Schmidhuber, 1997; with the forget gate of Gers, Schmidhuber and Cummins, 2000) keeps a cell state \(c_t\) alongside \(h_t\), and three gates with values in \((0,1)\):

$$f_t=\sigma(W_f[x_t,h_{t-1}]+b_f),\quad i_t=\sigma(W_i[\cdot]+b_i),\quad o_t=\sigma(W_o[\cdot]+b_o),\quad g_t=\tanh(W_g[\cdot]+b_g),$$ $$c_t=f_t\odot c_{t-1}+i_t\odot g_t,\qquad h_t=o_t\odot\tanh(c_t).$$

The forget gate decides how much of the old cell to keep, the input gate how much new content \(g_t\) to write, and the output gate how much of the cell to reveal.

The GRU (Cho et al., 2014) merges cell and hidden state and uses two gates:

$$h_t=(1-z_t)\odot h_{t-1}+z_t\odot\tilde h_t.$$

The cell update is additive, like a residual connection in time: along the cell path, \(\partial c_t/\partial c_{t-1}=\operatorname{diag}(f_t)\), with no weight matrix and no squashing derivative. If the network learns to set \(f_t\approx1\), the gradient passes through many steps undiminished, Hochreiter's "constant error carousel". Initialising the forget-gate bias to 1 or more, so that remembering is the default, is standard practice (Jozefowicz, Zaremba and Sutskever, 2015).

Gradients through time

Rose: the size of \(\partial h_T/\partial h_0\) for a vanilla tanh RNN with 32 units and random weights scaled to the chosen spectral radius, driven by random inputs. Moss: the product of forget gates along an LSTM's cell path, with gates \(\sigma(b_f+\text{noise})\). Log scale.

spot check 11.4

Why does the LSTM's cell state let gradients survive over many steps when a vanilla RNN's hidden state does not?

Compare \(\partial c_t/\partial c_{t-1}\) with \(\partial h_t/\partial h_{t-1}=D_tW\).
The additive update \(c_t=f_t\odot c_{t-1}+\dots\) is a gated identity path, the same idea as a residual connection (Section 2), discovered for time eighteen years earlier.

8 — LSTMs at work: forecasting and writing

data — daily minimum temperatures, Melbourne

The daily minimum temperature (°C) at Melbourne, Australia, 1981–1990, 3,650 days, from the Australian Bureau of Meteorology, in the copy distributed by Jason Brownlee (originally in Hyndman's Time Series Data Library). The plan for this lecture used the Max Planck Institute's Jena weather record, which could not be downloaded here.

code — forecasting tomorrow's temperature
# Forecasting tomorrow's minimum temperature in Melbourne from the previous 30 days
import pandas as pd
tmp = pd.read_csv('data/daily-min-temperatures.csv', parse_dates=['Date'])
temp = tmp['Temp'].to_numpy(np.float32); dates = tmp['Date']
L = 30
Xw = np.stack([temp[i:i + L] for i in range(len(temp) - L)]); Yw = temp[L:]; dY = dates[L:].reset_index(drop=True)
train = (dY.dt.year <= 1988).to_numpy(); test = (dY.dt.year >= 1989).to_numpy()
rm = lambda p: np.sqrt(np.mean((p - Yw[test]) ** 2))
doy = dY.dt.dayofyear.to_numpy(); clim = pd.Series(Yw[train]).groupby(doy[train]).mean()
clim_s = np.convolve(np.r_[clim.values[-15:], clim.values, clim.values[:15]], np.ones(31) / 31, 'valid')   # smoothed climatology
print(f'{len(temp)} days, {dates.iloc[0].date()} to {dates.iloc[-1].date()}; train 1981-88, test 1989-90')
print(f'persistence (tomorrow = today):              test RMSE {rm(Xw[test, -1]):.3f} °C')
print(f'climatology (average for that day of year):  test RMSE {rm(clim_s[np.minimum(doy[test], 365) - 1]):.3f} °C')
from sklearn.linear_model import Ridge
ar = Ridge(1.0).fit(Xw[train], Yw[train])
print(f'linear autoregression on the 30 days:         test RMSE {rm(ar.predict(Xw[test])):.3f} °C')
# An LSTM reading the 30 days in order
m_, s_ = temp[:2900].mean(), temp[:2900].std()
def lstm_init(n_in, n_h, key):
    k1, k2 = jax.random.split(key)
    p = {'W': jax.random.normal(k1, (n_in + n_h, 4 * n_h)) / np.sqrt(n_in + n_h), 'b': jnp.zeros(4 * n_h),
         'out': jax.random.normal(k2, (n_h, 1)) / np.sqrt(n_h), 'c': jnp.zeros(1)}
    return p.copy() | {'b': p['b'].at[n_h:2 * n_h].set(1.0)}    # forget-gate bias 1: remember by default
def lstm_run(p, xseq):                                        # xseq: (time, batch, features)
    n_h = p['out'].shape[0]
    def cell(carry, x):
        h, c = carry
        z = jnp.concatenate([x, h], 1) @ p['W'] + p['b']
        i, f, o, g = jax.nn.sigmoid(z[:, :n_h]), jax.nn.sigmoid(z[:, n_h:2 * n_h]), jax.nn.sigmoid(z[:, 2 * n_h:3 * n_h]), jnp.tanh(z[:, 3 * n_h:])
        c = f * c + i * g; h = o * jnp.tanh(c)                # forget, write, read
        return (h, c), h
    B = xseq.shape[1]
    (h, c), hs = jax.lax.scan(cell, (jnp.zeros((B, n_h)), jnp.zeros((B, n_h))), xseq)
    return h, hs
def temp_model(p, xb):
    h, _ = lstm_run(p, ((xb - m_) / s_).T[:, :, None])
    return (h @ p['out'] + p['c'])[:, 0] * s_ + m_
lp, lh = adam_train(lambda p, xb, yb: jnp.mean((temp_model(p, xb) - yb) ** 2), lstm_init(1, 32, jax.random.PRNGKey(1)),
                    (Xw[train], Yw[train]), 60, lr=3e-3, batch=64)
print(f'LSTM (32 units, 60 epochs):                   test RMSE {rm(np.asarray(temp_model(lp, Xw[test]))):.3f} °C')
3650 days, 1981-01-01 to 1990-12-31; train 1981-88, test 1989-90
persistence (tomorrow = today):              test RMSE 2.481 °C
climatology (average for that day of year):  test RMSE 2.570 °C
linear autoregression on the 30 days:         test RMSE 2.211 °C
LSTM (32 units, 60 epochs):                   test RMSE 2.214 °C

The LSTM learns, but it learns nothing that a linear model does not. Persistence ("tomorrow will be like today") has an error of 2.48 °C and the climatological average for the date 2.57 °C; a linear autoregression on the last 30 days, fitted by ridge regression in a fraction of a second, gets 2.21 °C, and the LSTM, after 60 epochs, gets 2.21 °C as well. The day-to-day weather at one station is mostly a linear, seasonal signal plus noise that its own past cannot predict, so there is nothing nonlinear for the LSTM to find. This is a common result, not an accident of our set-up. In the M4 forecasting competition (100,000 series, 2018), the pure machine-learning entries did worse than simple statistical methods, and the winners combined the two; in M5 (Walmart sales, 2020) gradient-boosted trees with hand-made features won. Deep sequence models earn their keep when there are many related series to learn from, many input variables, or long nonlinear dependencies, as in the next example. Always fit the simple baseline first.

data — Tiny Shakespeare

About 1.1 million characters from Shakespeare's plays, concatenated (40,000 lines), assembled by Andrej Karpathy for his char-rnn experiments (2015). It is the standard small corpus for character-level language models, and Lecture 12 uses it again for a transformer.

code — a character-level LSTM learns to write like Shakespeare
# A character-level LSTM on the works of Shakespeare (Karpathy's Tiny Shakespeare)
text = open('data/tinyshakespeare.txt').read()
chars = sorted(set(text)); stoi = {c: i for i, c in enumerate(chars)}; V = len(chars)
ids = np.array([stoi[c] for c in text], np.int32); n_tr = int(0.9 * len(ids))
print(f'{len(text):,} characters, {V} distinct; train on the first 90%, validate on the last 10%')
H = 256
def char_init(key):
    k1, k2, k3 = jax.random.split(key, 3)
    p = lstm_init(V, H, k1); p['emb'] = jnp.eye(V); p['out'] = jax.random.normal(k2, (H, V)) / np.sqrt(H); p['c'] = jnp.zeros(V)
    return p
def char_loss(p, xb, yb):                                     # xb, yb: (batch, time) of character ids
    _, hs = lstm_run(p, p['emb'][xb.T])
    logits = hs @ p['out'] + p['c']                           # (time, batch, V)
    return -jnp.mean(jnp.take_along_axis(jax.nn.log_softmax(logits), yb.T[..., None], 2))
def batches(split, n, T=100, seed=0):
    r = np.random.default_rng(seed); lo, hi = (0, n_tr - T - 1) if split == 'train' else (n_tr, len(ids) - T - 1)
    s = r.integers(lo, hi, n); return np.stack([ids[i:i + T] for i in s]), np.stack([ids[i + 1:i + T + 1] for i in s])
Xv, Yv = batches('val', 256, seed=99)
def sample(p, prompt, n=200, temp=0.8, seed=0):
    r = np.random.default_rng(seed); n_h = H; h = jnp.zeros((1, n_h)); c = jnp.zeros((1, n_h)); out = prompt
    def step(h, c, x):
        z = jnp.concatenate([p['emb'][x][None], h], 1) @ p['W'] + p['b']
        i, f, o, g = jax.nn.sigmoid(z[:, :n_h]), jax.nn.sigmoid(z[:, n_h:2 * n_h]), jax.nn.sigmoid(z[:, 2 * n_h:3 * n_h]), jnp.tanh(z[:, 3 * n_h:])
        c = f * c + i * g; h = o * jnp.tanh(c); return h, c, (h @ p['out'] + p['c'])[0]
    step = jax.jit(step)
    for ch in prompt: h, c, logit = step(h, c, stoi[ch])
    for _ in range(n):
        pr = np.asarray(jax.nn.softmax(logit / temp)); nxt = r.choice(V, p=pr / pr.sum()); out += chars[nxt]
        h, c, logit = step(h, c, nxt)
    return out
p = char_init(jax.random.PRNGKey(0)); m = jax.tree_util.tree_map(jnp.zeros_like, p); v = jax.tree_util.tree_map(jnp.zeros_like, p)
@jax.jit
def char_step(p, m, v, t, xb, yb):
    l, g = jax.value_and_grad(char_loss)(p, xb, yb)
    g = jax.tree_util.tree_map(lambda a: jnp.clip(a, -5, 5), g)               # gradient clipping
    m = jax.tree_util.tree_map(lambda a, b: 0.9 * a + 0.1 * b, m, g); v = jax.tree_util.tree_map(lambda a, b: 0.999 * a + 0.001 * b * b, v, g)
    p = jax.tree_util.tree_map(lambda q, a, b: q - 2e-3 * (a / (1 - 0.9 ** t)) / (jnp.sqrt(b / (1 - 0.999 ** t)) + 1e-8), p, m, v)
    return p, m, v, l
val = jax.jit(char_loss); t0 = time.time()
print(f'step     0: validation loss {float(val(p, Xv, Yv)):.3f} nats/char (uniform guessing: {np.log(V):.3f})')
for t in range(1, 3001):
    xb, yb = batches('train', 32, seed=t); p, m, v, l = char_step(p, m, v, t, xb, yb)
    if t in [100, 500, 1500, 3000]:
        print(f'step {t:5d}: validation loss {float(val(p, Xv, Yv)):.3f} nats/char ({time.time() - t0:.0f} s)')
        print('   | ' + sample(p, 'ROMEO:\n', 160, seed=t).replace('\n', '\n   | '))
char_lstm_val = float(val(p, Xv, Yv))
1,115,394 characters, 65 distinct; train on the first 90%, validate on the last 10%
step     0: validation loss 4.181 nats/char (uniform guessing: 4.174)
step   100: validation loss 2.452 nats/char (10 s)
   | ROMEO:
   | The yous dy pisey thyom toug bo go tein wipseadond bire san the leanee sot vilgis hit coutt tiwere whe  her tourcous wyeonde ing ind fortnVercan lor touk yirwit
step   500: validation loss 1.977 nats/char (48 s)
   | ROMEO:
   | My lnother, mont the lead, and thewe love in it a, wath our sare to mais here ou all the grood.
   | 
   | ANELY TIS:
   | Ay, fortust his spall's they shill strigsees.
   | Suncou
step  1500: validation loss 1.729 nats/char (152 s)
   | ROMEO:
   | A mean, still a word the lable in me this been death
   | That felst then wombe any safes the enjed of a than ear it
   | the contsing this brother see the master of milk
step  3000: validation loss 1.621 nats/char (295 s)
   | ROMEO:
   | I know you tears to kill him,
   | First be; and so said night, that that no live to country.
   | 
   | KING RICHARD III:
   | Well, service is so see findness, but early actice;
   | 

Language is where recurrence pays off. Guessing uniformly among the 65 characters costs \(\ln65=4.17\) nats per character, and the untrained network is exactly there. After 100 steps (10 seconds) it has learned the character frequencies and that words are separated by spaces (2.45 nats); after 500 it has learned the format of a play, with speakers' names in capitals followed by a colon and a line break, and short common words (1.98). After 3,000 steps, five minutes on two CPU cores, it reaches 1.62 nats per character (2.34 bits) on text it has never seen, writes mostly real words, pentameter-length lines, plausible names ("KING RICHARD III") and punctuation, and produces no sense at all beyond a few words. To know whether a line makes sense the model would need to keep track of who is speaking and about what, over hundreds of characters, and a 256-number state updated one character at a time does that badly. Lecture 12 trains a small transformer on exactly the same split, so the two numbers can be compared.

9 — The limits of recurrence, and its return

Recurrent networks have two built-in limitations. They are sequential: \(h_t\) cannot be computed before \(h_{t-1}\), so a sequence of length \(T\) needs \(T\) steps one after another, and training cannot use the parallelism of modern hardware along the sequence. And everything the network knows about the past must pass through a fixed-size state: to translate a long sentence, the encoder must squeeze it into one vector, a bottleneck (Lecture 12, Section 2). Attention removes both: every position looks directly at every other position, in parallel. Lecture 12 builds the transformer from this idea, and for most of the 2018–2023 period it displaced recurrence almost everywhere.

Recurrence has since returned in a new form. A linear state-space model drops the nonlinearity from the recurrence, \(h_t=Ah_{t-1}+Bx_t\), \(y_t=Ch_t\). Unrolled, \(y_t=\sum_{s\le t}CA^{t-s}Bx_s\): a convolution of the input with the kernel \(CA^kB\), which can be computed in parallel during training, while generation still runs as a cheap recurrence with a fixed-size state. S4 (Gu, Goel and Ré, 2022) parameterised \(A\) so that the state remembers long histories stably; Mamba (Gu and Dao, 2023) made \(A\), \(B\) and \(C\) depend on the input ("selective" state spaces), so the model can decide what to remember, much as an LSTM's gates do. Such models match transformers of similar size on language with time and memory linear rather than quadratic in sequence length, and hybrid models that interleave them with attention layers are now in production.

spot check 11.5

Why can a linear state-space model be trained in parallel along the sequence when a vanilla RNN cannot?

Unroll \(h_t=Ah_{t-1}+Bx_t\).
\(h_t=\sum_{s\le t}A^{t-s}Bx_s\) is linear in the inputs with coefficients that depend only on \(t-s\): a convolution. With a tanh in the recurrence the coefficients depend on the data and there is no such shortcut.
quantum — quantum convolutional neural networks

Cong, Choi and Lukin (2019) translated the convolutional architecture to quantum circuits. A quantum convolutional neural network applies the same small two-qubit unitary ("quantum convolution") across neighbouring qubits, then measures half the qubits and uses the results to control gates on the rest ("pooling"), halving the number of qubits per layer. With \(O(\log N)\) layers and only \(O(\log N)\) parameters for \(N\) input qubits, it recognised quantum phases of matter (a symmetry-protected topological phase) from quantum states directly, and its structure mirrors the multiscale entanglement renormalisation ansatz of physics and the syndrome measurements of quantum error correction. Like their classical counterparts they build a symmetry and locality into the architecture, and Pesah et al. (2021) proved that, unlike many generic variational circuits, they do not suffer from barren plateaus (Lecture 10b): the gradients shrink only polynomially with the number of qubits.

10 — Summary, exercises, projects, reading

summary

Next: Lecture 12 removes recurrence altogether: attention lets every position look at every other, and the transformer built from it underlies today's language models.

exercises
  1. A residual network has blocks \(x_{k+1}=x_k+F_k(x_k)\). Show that \(\dfrac{\partial x_L}{\partial x_0}=\prod_{k=L-1}^{0}\big(I+J_k\big)\), where \(J_k\) is the Jacobian of \(F_k\), and expand the product to explain the "ensemble of paths" view. How many paths are there through \(L\) blocks, and how many pass through exactly \(m\) blocks?

    By the chain rule, \(\partial x_{k+1}/\partial x_k=I+J_k\), and the Jacobian of the composition is the product. Expanding, each term chooses \(I\) or \(J_k\) at every block: one term per subset of blocks, \(2^L\) paths in all, and \(\binom Lm\) paths pass through exactly \(m\) residual branches. With \(L=54\) the path lengths are binomial with mean 27, but Veit et al. found that almost all of the gradient comes from paths through 5 to 17 branches, because each \(J_k\) shrinks the gradient.

  2. Prove that layer normalisation of a single vector \(x\in\mathbb R^d\) (before the learned scale and shift) is invariant to \(x\mapsto ax+b\mathbf 1\) for \(a>0\), and that its output always has squared norm \(d\) (ignoring \(\varepsilon\)).

    The mean becomes \(a\mu+b\) and the standard deviation \(a\sigma\), so \((ax_i+b-a\mu-b)/(a\sigma)=(x_i-\mu)/\sigma\). The output \(z\) has mean 0 and \(\frac1d\sum z_i^2=1\), so \(\|z\|^2=d\): layer normalisation projects onto a sphere of radius \(\sqrt d\) in the subspace orthogonal to \(\mathbf 1\).

  3. Count the parameters of the CNN in the code box: a \(3\times3\) convolution from 1 to 32 channels, a \(3\times3\) convolution from 32 to 64, each padded ("same") and followed by \(2\times2\) max-pooling, a dense layer from the flattened map to 128 units and a dense layer to 10, all with biases. Where are most of the parameters?

    \(9\cdot32+32=320\); \(9\cdot32\cdot64+64=18{,}496\). The padded convolutions keep the size, and pooling halves it twice, \(28\to14\to7\), so the flattened map has \(7\cdot7\cdot64=3{,}136\) entries and the first dense layer has \(3{,}136\cdot128+128=401{,}536\) parameters; the last has \(1{,}290\). Total 421,642, as printed. 95% of the parameters are in the first dense layer, and only 4.5% in the convolutions that do the feature extraction, which is why later architectures (from Network in Network and GoogLeNet on) replaced it with global average pooling.

  4. Show that a \(1\times1\) convolution with \(C_{\text{in}}\) input and \(C_{\text{out}}\) output channels is a dense layer applied separately at each pixel, and that a \(3\times3\) convolution followed by a \(3\times3\) convolution has the same receptive field as one \(5\times5\) convolution with fewer parameters when the channel count \(C\) is the same throughout.

    A \(1\times1\) kernel sees only the pixel itself: \(y_{ij}=Wx_{ij}+b\) with \(W\in\mathbb R^{C_{\text{out}}\times C_{\text{in}}}\), the same matrix at every pixel. Two \(3\times3\) layers see \(3+2=5\) pixels across (Proposition 11.5) with \(2\cdot9C^2=18C^2\) weights, against \(25C^2\) for one \(5\times5\) layer, and they add a nonlinearity between them. This is VGG's argument for small filters.

  5. For the scalar linear RNN \(h_t=wh_{t-1}+x_t\) with loss \(\ell(h_T)\), show that \(\partial\ell/\partial h_0=w^T\ell'(h_T)\). For the LSTM cell state with the input and output gates ignored, \(c_t=f_tc_{t-1}+\dots\), show that \(\partial c_T/\partial c_0=\prod_tf_t\) (treating the gates as constants), and compute it for \(T=100\) with \(f_t=0.99\) and with \(f_t=0.9\).

    Each step multiplies by \(\partial h_t/\partial h_{t-1}=w\). For the cell, \(\partial c_t/\partial c_{t-1}=f_t\), so the product is \(\prod f_t\): \(0.99^{100}=0.366\) and \(0.9^{100}=2.66\times10^{-5}\). The network controls its own memory span through the forget gate, which is why the forget bias is initialised to 1 (so \(f_t\approx0.73\) at first, and learning can push it towards 1).

  6. Unroll the linear state-space model \(h_t=Ah_{t-1}+Bx_t\), \(y_t=Ch_t\), \(h_0=0\), and show that \(y=k*x\) for the kernel \(k_j=CA^jB\). If \(A\) is diagonal with entries \(\lambda_i\), what condition on the \(\lambda_i\) keeps the kernel from blowing up, and what determines how far back the model remembers?

    By induction \(h_t=\sum_{s=1}^tA^{t-s}Bx_s\), so \(y_t=\sum_sCA^{t-s}Bx_s=\sum_jk_jx_{t-j}\). With \(A\) diagonal, \(k_j=\sum_iC_iB_i\lambda_i^j\): a sum of geometric sequences, bounded if every \(|\lambda_i|\le1\). A mode with \(|\lambda_i|=1-\delta\) remembers for about \(1/\delta\) steps, so modes close to the unit circle give long memory; S4 and Mamba parameterise the \(\lambda_i\) to stay inside it.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Does deep learning beat simple baselines for New York's electricity load?

question
For forecasting the New York grid's load one hour and one day ahead, how much do an LSTM, a small temporal convolutional network and a linear state-space model gain over seasonal naive forecasts, linear autoregression and gradient-boosted trees (Lecture 8)?
data
NYISO's public hourly load by zone (since 2001), with hourly weather for New York City from NOAA's Integrated Surface Database.
method
Rolling-origin evaluation over several years; the same features and history length for every model; error by season, hour and holiday; a Diebold–Mariano test for differences.
outcome
A careful, reproducible comparison for a real utility problem, with an answer to when the extra complexity pays, of the kind energy-forecasting journals publish.

2. What do filters learn on handwritten mathematics?

question
Do CNNs trained on handwritten mathematical symbols learn different first-layer filters from those trained on digits or clothing, and do the filters reveal which symbols are confused?
data
HASYv2 (Thoma, 2017): 168,000 32 × 32 images of 369 handwritten LaTeX symbols, with MNIST and Fashion-MNIST for comparison.
method
Train small CNNs with several seeds; cluster first-layer filters across runs; measure orientation and frequency statistics; relate the confusion matrix to visual similarity of symbols (for example \(\in\) and \(\epsilon\)).
outcome
A characterisation of learned features across domains and a symbol-recognition baseline for a mathematics-education tool.

3. Residual networks as ensembles, measured

question
Does the "ensemble of shallow paths" picture hold for the residual networks trained in this lecture, and does it change with normalisation and depth?
data
Fashion-MNIST and CIFAR-10.
method
Repeat Veit et al.'s experiments: delete or reorder individual blocks at test time, and measure the gradient carried by paths of each length by sampling which branches are kept; compare pre- and post-norm networks.
outcome
A replication with new variations, a good first research experience.

Reading and sources

Data. Fashion-MNIST: H. Xiao, K. Rasul, R. Vollgraf, arXiv:1708.07747 (2017), from github.com/zalandoresearch/fashion-mnist (MIT licence). Daily minimum temperatures, Melbourne, 1981–1990: Australian Bureau of Meteorology, via R. J. Hyndman's Time Series Data Library, copy at github.com/jbrownlee/Datasets. Tiny Shakespeare: A. Karpathy, github.com/karpathy/char-rnn (2015).

numbers in the text not printed by a code box are computed in verify_L11.py, figures in figs_L11.py; code-box outputs are pasted from actual runs (JAX on two CPU cores)