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
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.
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.
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.
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).
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.
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.
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\)
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).
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.
# 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
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.
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.)
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?
Why do transformers use layer normalisation rather than batch normalisation?
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.
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.
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.
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.
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.)
# 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
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.
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\)
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?
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.
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.
# 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.
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.
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.
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.
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.
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.
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$$# 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.
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).
Why does the LSTM's cell state let gradients survive over many steps when a vanilla RNN's hidden state does not?
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.
# 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.
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.
# 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.
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.
Why can a linear state-space model be trained in parallel along the sequence when a vanilla RNN cannot?
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.
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.
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.
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\).
\(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.
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.
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).
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.
Each project uses this lecture's methods and public data, and has a clear result.
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)