Part III · Deep learning | backpropagation by hand and in matrix form, computation graphs and reverse-mode automatic differentiation, a micro-autograd engine, initialisation and the propagation of variance, SGD, momentum, Adam and AdamW, learning-rate schedules, weight decay, dropout, early stopping, label smoothing, loss landscapes, Monte Carlo dropout | reading: Prince, Understanding Deep Learning, ch. 6–7 and 9 (and notebooks 7.1–7.3); Goodfellow, Bengio & Courville, Deep Learning, ch. 6.5, 7 and 8
Lecture 10a showed what networks can represent. This lecture is about finding the weights. The recipe is the one from Lecture 2: define a loss, compute its gradient with respect to every parameter, and take a step downhill, usually with stochastic minibatches and Adam. Two things make this harder for networks than for logistic regression. There may be millions or billions of parameters, so the gradient must be computed cleverly; that is backpropagation, the chain rule organised so that one backward sweep through the network costs about as much as one forward sweep. And the gradient has to survive the trip through many layers, which depends on how the weights are initialised. Once training works, the remaining problem is the old one of overfitting, now with models that can memorise anything (Lecture 6), and the regularisers of deep learning: weight decay, dropout, early stopping and others.
By the end of this lecture you should be able to backpropagate by hand through a small computation and check the result numerically; write the backpropagation equations for a multilayer network in matrix form; explain reverse-mode automatic differentiation and why it is cheap; derive He initialisation from the propagation of variance; train a network with SGD, momentum, Adam or AdamW and a learning-rate schedule; use and explain weight decay, dropout, early stopping and label smoothing; and estimate a network's uncertainty with Monte Carlo dropout.
Start with a chain of simple functions with one input and eight parameters, the toy model of Prince's notebook 7.1:
$$f(x)=\beta_3+\omega_3\cos\!\Big(\beta_2+\omega_2\exp\big(\beta_1+\omega_1\sin(\beta_0+\omega_0x)\big)\Big),\qquad\ell=(f-y)^2.$$Name every intermediate quantity: \(z_0=\beta_0+\omega_0x\), \(h_1=\sin z_0\), \(z_1=\beta_1+\omega_1h_1\), \(h_2=e^{z_1}\), \(z_2=\beta_2+\omega_2h_2\), \(h_3=\cos z_2\), \(f=\beta_3+\omega_3h_3\). The forward pass computes these in order and stores them. The backward pass computes \(\partial\ell/\partial(\cdot)\) for each of them in reverse order, each from the one after it:
$$\frac{\partial\ell}{\partial f}=2(f-y),\quad\frac{\partial\ell}{\partial h_3}=\frac{\partial\ell}{\partial f}\,\omega_3,\quad\frac{\partial\ell}{\partial z_2}=\frac{\partial\ell}{\partial h_3}\,(-\sin z_2),\quad\frac{\partial\ell}{\partial h_2}=\frac{\partial\ell}{\partial z_2}\,\omega_2,\quad\dots$$and each parameter's derivative comes from the node it feeds: \(\partial\ell/\partial\omega_2=(\partial\ell/\partial z_2)\,h_2\), \(\partial\ell/\partial\beta_2=\partial\ell/\partial z_2\). Every step multiplies by one local derivative, and every intermediate value the backward pass needs was stored by the forward pass.
import numpy as np # A toy model with one input, written as a chain of simple steps (after Prince, notebook 7.1): # f(x) = b3 + w3 cos(b2 + w2 exp(b1 + w1 sin(b0 + w0 x))), loss = (f - y)^2 b0, w0, b1, w1, b2, w2, b3, w3 = 1.0, 0.1, -0.4, 1.0, 0.3, -0.2, 1.1, 2.0 x, y = 2.3, 2.0 # Forward pass: keep every intermediate value z0 = b0 + w0 * x; h1 = np.sin(z0) z1 = b1 + w1 * h1; h2 = np.exp(z1) z2 = b2 + w2 * h2; h3 = np.cos(z2) f = b3 + w3 * h3; loss = (f - y) ** 2 print(f'forward: z0={z0:.4f} h1={h1:.4f} z1={z1:.4f} h2={h2:.4f} z2={z2:.4f} h3={h3:.4f} f={f:.4f} loss={loss:.4f}') # Backward pass: the chain rule, from the loss back to the input, one step at a time dl_df = 2 * (f - y) dl_dh3 = dl_df * w3; dl_dz2 = dl_dh3 * (-np.sin(z2)) dl_dh2 = dl_dz2 * w2; dl_dz1 = dl_dh2 * np.exp(z1) dl_dh1 = dl_dz1 * w1; dl_dz0 = dl_dh1 * np.cos(z0) grads = {'b3': dl_df, 'w3': dl_df * h3, 'b2': dl_dz2, 'w2': dl_dz2 * h2, 'b1': dl_dz1, 'w1': dl_dz1 * h1, 'b0': dl_dz0, 'w0': dl_dz0 * x} # Check every derivative against a finite difference def loss_at(**p): q = dict(b0=b0, w0=w0, b1=b1, w1=w1, b2=b2, w2=w2, b3=b3, w3=w3); q.update(p) ff = q['b3'] + q['w3'] * np.cos(q['b2'] + q['w2'] * np.exp(q['b1'] + q['w1'] * np.sin(q['b0'] + q['w0'] * x))) return (ff - y) ** 2 eps = 1e-6 print('parameter backprop finite difference') for name, gval in grads.items(): v = {'b0': b0, 'w0': w0, 'b1': b1, 'w1': w1, 'b2': b2, 'w2': w2, 'b3': b3, 'w3': w3}[name] fd = (loss_at(**{name: v + eps}) - loss_at(**{name: v - eps})) / (2 * eps) print(f'{name:9s} {gval:12.6f} {fd:15.6f}')
forward: z0=1.2300 h1=0.9425 z1=0.5425 h2=1.7203 z2=-0.0441 h3=0.9990 f=3.0981 loss=1.2057 parameter backprop finite difference b3 2.196119 2.196119 w3 2.193988 2.193988 b2 0.193444 0.193444 w2 0.332779 0.332779 b1 -0.066556 -0.066556 w1 -0.062728 -0.062728 b0 -0.022245 -0.022245 w0 -0.051165 -0.051165
All eight derivatives agree with central finite differences to six decimal places. Notice how they shrink toward the input: \(\partial\ell/\partial\beta_3=2.20\) but \(\partial\ell/\partial\beta_0=-0.022\). Several backward steps multiply by a small local derivative (here \(-\sin z_2\approx0.044\) does most of the damage, helped by \(\omega_2e^{z_1}\approx-0.34\) and \(\cos z_0\approx0.33\)). In a deep network the same effect, multiplied over many layers, makes gradients vanish or explode, the subject of Section 3.
Why does backpropagation run the forward pass first and store its intermediate values?
For the network of Definition 10.2 the same procedure works with vectors and matrices. Process a minibatch at once: rows of \(H_{k}\) are the hidden vectors of the examples, \(Z_k=H_{k-1}W_k+\mathbf 1b_k^\top\) the pre-activations, \(H_k=a(Z_k)\).
Let \(\Delta_k=\partial L/\partial Z_k\) (same shape as \(Z_k\)). Then \(\Delta_{K+1}\) is the derivative of the loss with respect to the outputs (for softmax with cross-entropy averaged over \(m\) examples, \((P-Y)/m\), Lecture 4), and for \(k=K+1,K,\dots,1\):
$$\frac{\partial L}{\partial W_k}=H_{k-1}^\top\Delta_k,\qquad\frac{\partial L}{\partial b_k}=\Delta_k^\top\mathbf 1,\qquad\Delta_{k-1}=\big(\Delta_kW_k^\top\big)\odot a'(Z_{k-1}),$$where \(\odot\) is the entrywise product.
Entry \((i,j)\) of \(Z_k\) is
$$\sum_rH_{k-1,ir}W_{k,rj}+b_{k,j}.$$By the chain rule,
$$\partial L/\partial W_{k,rj}=\sum_i\Delta_{k,ij}H_{k-1,ir},$$the \((r,j)\) entry of \(H_{k-1}^\top\Delta_k\), and similarly for \(b_k\).
Each \(H_{k-1,ir}\) affects \(Z_{k,ij}\) for every \(j\) with coefficient \(W_{k,rj}\), so
$$\partial L/\partial H_{k-1,ir}=\sum_j\Delta_{k,ij}W_{k,rj}=(\Delta_kW_k^\top)_{ir}.$$Finally \(H_{k-1}=a(Z_{k-1})\) entrywise, so
$$\Delta_{k-1}=(\Delta_kW_k^\top)\odot a'(Z_{k-1}).\qquad\square$$The backward pass is one matrix product per layer for \(\Delta\) and one for the weight gradient, the same work as the forward pass's one product per layer, twice. Here it is for a 784–256–256–10 network, checked against finite differences, with a timing.
import time # Backpropagation for a whole MLP in matrix form, checked against finite differences def init(sizes, rng): return [(rng.normal(0, np.sqrt(2 / m), (m, n)), np.zeros(n)) for m, n in zip(sizes[:-1], sizes[1:])] def forward_backward(params, X, Y): hs, zs = [X], [] for k, (W, b) in enumerate(params): # forward: store pre- and post-activations z = hs[-1] @ W + b; zs.append(z) hs.append(np.maximum(z, 0) if k < len(params) - 1 else z) Z = hs[-1]; P = np.exp(Z - Z.max(1, keepdims=True)); P /= P.sum(1, keepdims=True) loss = -np.mean(np.log(P[np.arange(len(Y)), Y])) g = P.copy(); g[np.arange(len(Y)), Y] -= 1; g /= len(Y) # dL/dZ for softmax + cross-entropy grads = [None] * len(params) for k in range(len(params) - 1, -1, -1): # backward: one matrix product per step W, b = params[k] grads[k] = (hs[k].T @ g, g.sum(0)) # dL/dW_k = h_{k-1}^T delta_k if k > 0: g = (g @ W.T) * (zs[k - 1] > 0) # delta_{k-1} = (delta_k W_k^T) * a'(z_{k-1}) return loss, grads rng = np.random.default_rng(0) params = init([20, 32, 32, 5], rng); Xs = rng.normal(size=(64, 20)); Ys = rng.integers(0, 5, 64) loss, grads = forward_backward(params, Xs, Ys) worst = 0 for k in range(3): for (i, j) in [(0, 0), (3, 4), (7, 1)]: W = params[k][0]; old = W[i, j] W[i, j] = old + 1e-6; lp = forward_backward(params, Xs, Ys)[0] W[i, j] = old - 1e-6; lm = forward_backward(params, Xs, Ys)[0]; W[i, j] = old worst = max(worst, abs((lp - lm) / 2e-6 - grads[k][0][i, j])) print(f'largest difference from finite differences: {worst:.1e}') big = init([784, 256, 256, 10], rng); Xb = rng.normal(size=(512, 784)); Yb = rng.integers(0, 10, 512) def forward_only(params, X): h = X for k, (W, b) in enumerate(params): h = h @ W + b if k < len(params) - 1: h = np.maximum(h, 0) return h t0 = time.perf_counter(); [forward_only(big, Xb) for _ in range(20)]; tf = time.perf_counter() - t0 t0 = time.perf_counter(); [forward_backward(big, Xb, Yb) for _ in range(20)]; tb = time.perf_counter() - t0 print(f'784-256-256-10 network, batch 512: forward + backward takes {tb / tf:.1f} times as long as forward alone,' f' and gives all {sum(W.size + b.size for W, b in big):,} partial derivatives')
largest difference from finite differences: 2.1e-10 784-256-256-10 network, batch 512: forward + backward takes 2.4 times as long as forward alone, and gives all 269,322 partial derivatives
Backpropagation agrees with finite differences to \(2\times10^{-10}\), and computing all 269,322 partial derivatives costs 2.4 times as much as just computing the outputs. Finite differences would need 269,323 forward passes. This is not a lucky property of networks.
Let \(f:\mathbb R^n\to\mathbb R\) be computed by a program that executes a sequence of elementary operations (sums, products, and differentiable functions of one variable) costing \(C\).
Then reverse-mode automatic differentiation, which runs the program forward recording the operations and then propagates \(\partial f/\partial(\cdot)\) backward through the record, computes all \(n\) partial derivatives with cost at most a small constant times \(C\) (at most 5 in the standard operation-counting model), whatever \(n\) is (Baur and Strassen, 1983; Griewank and Walther, 2008).
Each elementary operation \(v=\psi(u_1,u_2)\) has at most two inputs. In the backward sweep it is visited once, and adds
$$\frac{\partial\psi}{\partial u_i}\cdot\bar v$$to each input's accumulated derivative \(\bar u_i\) (the chain rule summed over all paths, the sum arising because a value used in several places receives a contribution from each). Each visit costs a bounded number of operations: evaluate at most two local derivatives, multiply, add. So the backward sweep costs at most a constant multiple of the forward sweep.
By contrast, forward-mode differentiation pushes the derivative with respect to one input through the program, so getting all \(n\) partial derivatives costs about \(nC\). \(\square\)
Reverse mode is efficient when there are many inputs and one output, exactly the shape of "loss as a function of all the weights". Forward mode wins in the opposite case, few inputs and many outputs (Exercise 3). PyTorch, JAX and TensorFlow are reverse-mode systems: they record the operations your code performs into a computation graph and then sweep backward through it. The idea fits in a few dozen lines.
# A micro-autograd engine: scalars that remember how they were computed (after Karpathy's micrograd) class Value: def __init__(self, data, parents=(), local_grads=()): self.data, self.grad = float(data), 0.0 self.parents, self.local_grads = parents, local_grads # d(self)/d(parent) for each parent def __add__(self, o): o = o if isinstance(o, Value) else Value(o) return Value(self.data + o.data, (self, o), (1.0, 1.0)) def __mul__(self, o): o = o if isinstance(o, Value) else Value(o) return Value(self.data * o.data, (self, o), (o.data, self.data)) __radd__, __rmul__ = __add__, __mul__ def __neg__(self): return self * -1 def __sub__(self, o): return self + (-o) def relu(self): return Value(max(0.0, self.data), (self,), (float(self.data > 0),)) def log(self): return Value(np.log(self.data), (self,), (1 / self.data,)) def exp(self): e = np.exp(self.data); return Value(e, (self,), (e,)) def backward(self): order, seen = [], set() def visit(v): # topological order of the computation graph if id(v) not in seen: seen.add(id(v)) for p in v.parents: visit(p) order.append(v) visit(self); self.grad = 1.0 for v in reversed(order): # reverse mode: one sweep from output to inputs for p, lg in zip(v.parents, v.local_grads): p.grad += lg * v.grad # chain rule, summing over paths class MLP: def __init__(self, sizes, rng): self.W = [[[Value(rng.normal(0, np.sqrt(2 / m))) for _ in range(m)] for _ in range(n)] for m, n in zip(sizes[:-1], sizes[1:])] self.b = [[Value(0.0) for _ in range(n)] for n in sizes[1:]] def __call__(self, x): h = [Value(v) for v in x] for k, (W, b) in enumerate(zip(self.W, self.b)): h = [sum((wi * hi for wi, hi in zip(row, h)), bj) for row, bj in zip(W, b)] if k < len(self.W) - 1: h = [v.relu() for v in h] return h[0] def params(self): return [p for W in self.W for row in W for p in row] + [p for b in self.b for p in b] from sklearn.datasets import make_moons Xm, ym = make_moons(100, noise=0.15, random_state=0) rng = np.random.default_rng(0); net = MLP([2, 8, 8, 1], rng) def bce(score, label): # logistic loss, log(1 + exp(-y s)) with y = +-1 return (Value(1.0) + (score * (-(2 * label - 1))).exp()).log() print(f'{len(net.params())} parameters') for step in range(201): for p in net.params(): p.grad = 0.0 scores = [net(x) for x in Xm] loss = sum((bce(s, l) for s, l in zip(scores, ym)), Value(0.0)) * (1 / len(ym)) loss.backward() for p in net.params(): p.data -= 0.3 * p.grad # gradient descent if step in [0, 50, 100, 200]: acc = np.mean([(s.data > 0) == l for s, l in zip(scores, ym)]) print(f'step {step:3d}: loss {loss.data:.4f} training accuracy {acc:.2f}')
105 parameters step 0: loss 0.7159 training accuracy 0.50 step 50: loss 0.2535 training accuracy 0.89 step 100: loss 0.1939 training accuracy 0.92 step 200: loss 0.0768 training accuracy 0.98
Each Value remembers its parents and the local derivative with respect to each. backward sorts the graph so that every node comes after its parents, then walks it in reverse, adding local derivative times downstream derivative into each parent. That is all of Theorem 10.6. With it, a 2–8–8–1 network with 105 parameters learns two moons from 50% to 98% training accuracy in 200 gradient steps. The engine is very slow, because it handles every multiplication as a separate Python object; real frameworks apply the same idea to whole matrices, as in Theorem 10.5.
Many people, in different fields. The gradient of a multistage process by working backward appears in optimal control in the early 1960s (Kelley, 1960; Bryson, 1961). Seppo Linnainmaa described general reverse-mode automatic differentiation, with code, in his 1970 master's thesis at the University of Helsinki. Paul Werbos proposed applying it to neural networks in his 1974 Harvard PhD thesis. The method became famous with David Rumelhart, Geoffrey Hinton and Ronald Williams's 1986 Nature paper "Learning representations by back-propagating errors", which showed hidden units learning useful internal features. Yann LeCun's convolutional networks for reading handwritten digits at Bell Labs (1989) were among the first large applications. Today's frameworks descend from Theano (2007), Torch, TensorFlow (2015), PyTorch (2016) and JAX (2018).
The backward recursion \(\Delta_{k-1}=(\Delta_kW_k^\top)\odot a'(Z_{k-1})\) multiplies by a weight matrix and a derivative at every layer, and the forward pass multiplies by weight matrices too. If each multiplication shrinks the typical size of a vector by a factor of 0.9, fifty layers shrink it by \(0.9^{50}\approx0.005\); if each grows it by 1.1, by \(1.1^{50}\approx117\). Training needs both the activations and the gradients to keep a stable size through all the layers, at least at the start. Before any data are seen, the only lever is the scale of the random initial weights.
Consider a layer
$$z_j=\sum_{i=1}^nW_{ij}h_i$$with \(h_i=\mathrm{ReLU}(z_i')\), where the weights are independent with mean 0 and variance \(\sigma^2/n\), independent of the inputs, and the previous pre-activations \(z_i'\) are symmetric about 0. Then
$$\mathbb E\big[z_j^2\big]=\frac{\sigma^2}2\,\mathbb E\big[z_i'^2\big].$$So the second moment of the pre-activations stays constant from layer to layer if and only if \(\sigma^2=2\): weights with variance \(2/n_{\text{in}}\) (He et al., 2015).
The same calculation for the backward pass gives variance \(2/n_{\text{out}}\). For tanh, which is close to the identity near 0, the analogous condition is variance \(1/n\); Glorot and Bengio (2010) compromised between the forward and backward conditions with \(2/(n_{\text{in}}+n_{\text{out}})\).
The terms \(W_{ij}h_i\) have mean zero (the weights are independent of \(h\) with mean 0) and are uncorrelated for different \(i\), so
$$\mathbb E[z_j^2]=\sum_i\mathbb E[W_{ij}^2]\,\mathbb E[h_i^2]=n\cdot\frac{\sigma^2}n\,\mathbb E[h^2].$$For \(z'\) symmetric about 0,
$$\mathbb E[\mathrm{ReLU}(z')^2]=\mathbb E[z'^2\mathbb 1(z'>0)]=\frac12\mathbb E[z'^2].$$Combining,
$$\mathbb E[z_j^2]=\frac{\sigma^2}2\mathbb E[z'^2].$$Backward,
$$\Delta_{k-1,i}=a'(z_i)\sum_j\Delta_{k,j}W_{ij}$$sums over the \(n_{\text{out}}\) units of the next layer, and \(a'\) is 0 or 1 with probability ½ each, giving the factor \(\sigma^2n_{\text{out}}/(2n)\). \(\square\)
# How activations and gradients propagate through 50 layers of width 256 at initialisation def propagate(act, gain, depth=50, width=256, n=500, seed=0): r = np.random.default_rng(seed) h = r.normal(size=(n, width)); zs, Ws, hs = [], [], [h] for _ in range(depth): W = r.normal(0, np.sqrt(gain / width), (width, width)) z = hs[-1] @ W; zs.append(z); Ws.append(W) hs.append(np.maximum(z, 0) if act == 'relu' else np.tanh(z)) g = r.normal(size=(n, width)); gstd = [] # backpropagate a random gradient for k in range(depth - 1, -1, -1): g = g * ((zs[k] > 0) if act == 'relu' else 1 - np.tanh(zs[k]) ** 2) gstd.append(g.std()); g = g @ Ws[k].T return [hs[k].std() for k in [1, 10, 25, 50]], gstd[::-1] print('activation weight variance std of activations at layer 1, 10, 25, 50 std of gradients at layer 1') for act, gain, label in [('relu', 1.0, '1/n'), ('relu', 2.0, '2/n (He)'), ('relu', 3.0, '3/n'), ('tanh', 1.0, '1/n (Xavier)'), ('tanh', 0.5, '0.5/n')]: a, gs = propagate(act, gain) print(f'{act:10s} {label:15s} ' + ' '.join(f'{v:9.2e}' for v in a) + f' {gs[0]:9.2e}')
activation weight variance std of activations at layer 1, 10, 25, 50 std of gradients at layer 1 relu 1/n 5.85e-01 3.14e-02 1.78e-04 2.96e-08 2.57e-08 relu 2/n (He) 8.27e-01 1.00e+00 1.03e+00 9.95e-01 6.10e-01 relu 3/n 1.01e+00 7.62e+00 1.64e+02 2.51e+04 1.26e+04 tanh 1/n (Xavier) 6.28e-01 2.29e-01 1.39e-01 8.58e-02 1.07e-01 tanh 0.5/n 5.23e-01 1.89e-02 1.02e-04 1.50e-08 2.28e-08
With ReLU and the "natural-looking" variance \(1/n\), the signal halves its second moment at every layer: after 50 layers activations are \(3\times10^{-8}\) and so are the gradients reaching the first layer, which therefore never learns. With \(3/n\) both explode to around \(10^4\). He initialisation, \(2/n\), keeps the activations at a standard deviation of about 1 for all 50 layers and delivers gradients of a sensible size (0.6) to the first layer. The widget uses width 64 rather than 256, and there the He curve wanders from run to run (press "new random weights"): across 20 random draws, the standard deviation at layer 30 had median 0.47, with 10% of draws below 0.2 and 10% above 1.4. The variance argument is about averages, and at finite width each layer multiplies the signal by a random factor whose fluctuations accumulate with the ratio of depth to width (Hanin and Nica, 2020). These are factors of a few, against factors of \(10^{4}\) for the wrong scale. For tanh, \(1/n\) decays slowly, because tanh shrinks large inputs; PyTorch's recommended "gain" for tanh scales the weights' standard deviation by \(5/3\) to compensate. This is the knife-edge that made deep networks so hard to train before 2010, and Lecture 11 adds the remaining fixes: normalisation layers and residual connections, which make the signal's survival much less dependent on getting the initial scale exactly right.
ReLU layers of width 256 are initialised with weight variance \(1/256\) instead of \(2/256\). By what factor does the second moment of the pre-activations change over 7 layers?
70,000 grey-scale 28 × 28 images of clothing in 10 classes (T-shirt, trouser, pullover, dress, coat, sandal, shirt, sneaker, bag, ankle boot), 6,000 training and 1,000 test images per class, from product photographs on Zalando's website (Xiao, Rasul and Vollgraf, 2017; MIT licence). It was designed as a drop-in replacement for MNIST that is harder to solve.
Lecture 2 introduced the optimisers: stochastic gradient descent on minibatches, momentum (a running average of gradients), and Adam (momentum plus a per-parameter step size from a running average of squared gradients, with bias correction). Two further ingredients are standard for networks.
AdamW (Loshchilov and Hutter, 2019) applies weight decay separately from the gradient step: after the Adam update, every weight is shrunk by \(\eta\lambda w\). Adding \(\lambda w\) to the gradient instead (the "L2 penalty") would pass the decay through Adam's per-parameter normalisation and weaken it for weights with large gradients.
A learning-rate schedule varies \(\eta\) during training; the common choice is a linear warm-up from 0 over the first few hundred or thousand steps (Adam's second-moment estimates are unreliable at first), then cosine decay,
$$\eta_t=\frac{\eta_{\max}}2\big(1+\cos(\pi t/T)\big),$$to near 0 at the end.
import gzip def idx(path): with gzip.open(path, 'rb') as fh: raw = fh.read() ndim = raw[3]; dims = [int.from_bytes(raw[4 + 4 * i: 8 + 4 * i], 'big') for i in range(ndim)] return np.frombuffer(raw, np.uint8, offset=4 + 4 * ndim).reshape(dims) Xtr = idx('../data/train-images-idx3-ubyte.gz').reshape(-1, 784).astype(np.float32) / 255 ytr = idx('../data/train-labels-idx1-ubyte.gz').astype(int) Xte = idx('../data/t10k-images-idx3-ubyte.gz').reshape(-1, 784).astype(np.float32) / 255 yte = idx('../data/t10k-labels-idx1-ubyte.gz').astype(int) mu, sd = Xtr.mean(), Xtr.std(); Xtr, Xte = (Xtr - mu) / sd, (Xte - mu) / sd print(Xtr.shape, Xte.shape, 'classes:', np.bincount(ytr)) def run(X, Y, track, opt='adam', lr=1e-3, epochs=10, wd=0.0, decoupled=False, p_drop=0.0, smooth=0.0, warmup=0, cosine=False, batch=128, sizes=(784, 256, 256, 10), seed=0, verbose=()): r = np.random.default_rng(seed) P = [(r.normal(0, np.sqrt(2 / m), (m, n)).astype(np.float32), np.zeros(n, np.float32)) for m, n in zip(sizes[:-1], sizes[1:])] M = [(np.zeros_like(W), np.zeros_like(b)) for W, b in P]; V = [(np.zeros_like(W), np.zeros_like(b)) for W, b in P] steps_per = int(np.ceil(len(X) / batch)); total = epochs * steps_per; t = 0; hist = [] for ep in range(1, epochs + 1): perm = r.permutation(len(X)); run_loss = 0.0 for s in range(steps_per): idx_ = perm[s * batch:(s + 1) * batch]; h = X[idx_]; hs, zs, masks = [h], [], [] for k, (W, b) in enumerate(P): # forward with dropout on hidden layers z = hs[-1] @ W + b; zs.append(z) if k < len(P) - 1: a = np.maximum(z, 0) m_ = (r.random(a.shape) > p_drop).astype(np.float32) / (1 - p_drop) if p_drop else 1.0 masks.append(m_); hs.append(a * m_) else: hs.append(z) Z = hs[-1]; Pr = np.exp(Z - Z.max(1, keepdims=True)); Pr /= Pr.sum(1, keepdims=True) T = np.full_like(Pr, smooth / 10); T[np.arange(len(idx_)), Y[idx_]] += 1 - smooth # (smoothed) targets run_loss += -np.mean((T * np.log(Pr + 1e-12)).sum(1)) g = (Pr - T) / len(idx_) t += 1 sched = min(1.0, t / warmup) if warmup else 1.0 if cosine: sched *= 0.5 * (1 + np.cos(np.pi * t / total)) for k in range(len(P) - 1, -1, -1): W, b = P[k]; gW, gb = hs[k].T @ g, g.sum(0) if k > 0: g = (g @ W.T) * masks[k - 1] * (zs[k - 1] > 0) if wd and not decoupled: gW = gW + wd * W # L2 penalty: part of the gradient if opt == 'sgd': W -= lr * sched * gW; b -= lr * sched * gb elif opt == 'momentum': for arr, grad, j in [(W, gW, 0), (b, gb, 1)]: M[k][j][...] = 0.9 * M[k][j] + grad; arr -= lr * sched * M[k][j] else: # Adam / AdamW for arr, grad, j in [(W, gW, 0), (b, gb, 1)]: M[k][j][...] = 0.9 * M[k][j] + 0.1 * grad; V[k][j][...] = 0.999 * V[k][j] + 0.001 * grad * grad arr -= lr * sched * (M[k][j] / (1 - 0.9**t)) / (np.sqrt(V[k][j] / (1 - 0.999**t)) + 1e-8) if wd and decoupled: W -= lr * sched * wd * W # AdamW: decay the weights directly hist.append((ep, run_loss / steps_per, [accuracy(P, Xe, Ye) for Xe, Ye in track])) return P, hist def predict(P, X): h = X for k, (W, b) in enumerate(P): h = h @ W + b if k < len(P) - 1: h = np.maximum(h, 0) return h def accuracy(P, X, Y): return np.mean(predict(P, X).argmax(1) == Y) import time results = {} for name, kw in [('SGD, lr 0.1', dict(opt='sgd', lr=0.1)), ('SGD + momentum 0.9, lr 0.01', dict(opt='momentum', lr=0.01)), ('Adam, lr 0.001', dict(opt='adam', lr=1e-3)), ('AdamW, lr 0.002, decay 0.05, warm-up + cosine', dict(opt='adam', lr=2e-3, wd=0.05, decoupled=True, warmup=500, cosine=True))]: t0 = time.time(); P, hist = run(Xtr, ytr, [(Xte, yte)], epochs=10, **kw); results[name] = (P, hist) print(f'{name:46s} ' + ' '.join(f'ep{e}: loss {l:.3f} test {a[0]:.4f}' for e, l, a in hist if e in (1, 5, 10)) + f' ({time.time() - t0:.0f} s)')
(60000, 784) (10000, 784) classes: [6000 6000 6000 6000 6000 6000 6000 6000 6000 6000] SGD, lr 0.1 ep1: loss 0.509 test 0.8213 ep5: loss 0.269 test 0.8800 ep10: loss 0.202 test 0.8816 (10 s) SGD + momentum 0.9, lr 0.01 ep1: loss 0.492 test 0.8320 ep5: loss 0.265 test 0.8832 ep10: loss 0.194 test 0.8809 (12 s) Adam, lr 0.001 ep1: loss 0.459 test 0.8328 ep5: loss 0.258 test 0.8813 ep10: loss 0.192 test 0.8848 (18 s) AdamW, lr 0.002, decay 0.05, warm-up + cosine ep1: loss 0.637 test 0.8245 ep5: loss 0.252 test 0.8839 ep10: loss 0.144 test 0.9017 (25 s)
All four reach 88–90% test accuracy in ten passes through the data, a few seconds each. SGD with step 0.1 and momentum with step 0.01 behave almost identically: with \(\beta=0.9\), momentum accumulates about \(1/(1-\beta)=10\) gradients, so its effective step is also 0.1 (Exercise 9). Adam is a little faster at the start. The best result, 90.2%, comes from AdamW with warm-up and cosine decay, and most of its advantage arrives in the last epochs, as the learning rate falls toward zero and the weights settle into a minimum instead of bouncing around it. This pattern, large steps to make progress and small steps to finish, is why nearly every large model is trained with a decaying schedule.
The playground below puts the pieces together on two-dimensional problems, with full-batch Adam running live in your browser.
Why is weight decay applied separately from the Adam update in AdamW, rather than as an L2 term in the loss?
A network that can fit random labels (Lecture 6) can fit the noise in real ones. The regularisers below are the standard defences; most were met earlier in a different form.
Minimising
$$\sum_i\ell(y_i,f(x_i;w))+\frac\lambda2\|w\|^2,$$where \(\ell\) is a negative log-likelihood, gives the maximum a posteriori (MAP) estimate under the prior \(w\sim\mathcal N(0,\lambda^{-1}I)\).
The log posterior is
$$\log p(w\mid\text{data})=\sum_i\log p(y_i\mid x_i,w)+\log p(w)+\text{const}$$ $$=-\sum_i\ell(y_i,f(x_i;w))-\frac\lambda2\|w\|^2+\text{const}.$$Maximising it is minimising the penalised loss. This is Theorem 3.7 (ridge regression as MAP) for any model. \(\square\)
During training, dropout sets each hidden unit to zero independently with probability \(p\) at every step, and scales the survivors by \(1/(1-p)\) so that each unit's expected value is unchanged ("inverted dropout"); at test time all units are kept (Srivastava et al., 2014).
Each step therefore trains a randomly thinned subnetwork, and the full network approximately averages an exponentially large ensemble of them. Units cannot rely on particular partners being present, which discourages fragile co-adaptations.
Three more are common. Early stopping monitors loss on a validation set and keeps the weights from the best epoch; for linear least squares trained by gradient descent from zero it behaves like a ridge penalty that weakens as training continues (Exercise 7). Label smoothing (Szegedy et al., 2016) trains toward targets \(1-\epsilon+\epsilon/K\) and \(\epsilon/K\) instead of 1 and 0, so the network is not rewarded for pushing logits to infinity. Data augmentation trains on transformed copies of the data (crops, flips, small rotations, noise) that should not change the label, building invariances into the model directly; for images it is often the most effective regulariser of all (Lecture 11). The comparison below uses only 2,000 training images, where overfitting is severe.
# Regularisation when data are scarce: 2,000 training images, 80 epochs Xs, ys = Xtr[:2000], ytr[:2000] Xval, yval = Xtr[50000:], ytr[50000:] # validation images, not used for training print('method train acc. test acc. (last epoch) early stopping: best val. epoch, test acc.') for name, kw in [('none', {}), ('L2 weight decay 1e-3', dict(wd=1e-3)), ('dropout 0.5', dict(p_drop=0.5)), ('label smoothing 0.1', dict(smooth=0.1)), ('dropout 0.5 + weight decay', dict(p_drop=0.5, wd=1e-3))]: P, hist = run(Xs, ys, [(Xs, ys), (Xval, yval), (Xte, yte)], epochs=80, **kw) best = max(hist, key=lambda h: h[2][1]) print(f'{name:30s} {hist[-1][2][0]:10.3f} {hist[-1][2][2]:21.4f} epoch {best[0]:2d}, {best[2][2]:.4f}')
method train acc. test acc. (last epoch) early stopping: best val. epoch, test acc. none 1.000 0.8256 epoch 52, 0.8263 L2 weight decay 1e-3 1.000 0.8232 epoch 71, 0.8264 dropout 0.5 0.989 0.8276 epoch 67, 0.8315 label smoothing 0.1 1.000 0.8222 epoch 19, 0.8297 dropout 0.5 + weight decay 0.989 0.8298 epoch 49, 0.8316
Every variant reaches (nearly) 100% training accuracy against about 82–83% on the test set: a gap of 17 points. The regularisers help only a little here, about half a point for dropout, and L2 weight decay used inside Adam does essentially nothing (the AdamW point of Section 4). Early stopping picks a validation-best epoch with similar test accuracy. The honest message is that with 2,000 images the cure is more data, or architecture that knows images (convolutions and augmentation, Lecture 11): the same network trained on all 60,000 images reached 88–90%.
Why does training work at all? The loss of a network is highly non-convex, with many minima and saddle points, yet gradient descent from a random start reliably finds low training loss in large networks. Several facts are understood. Wide networks have few bad local minima: most critical points with high loss are saddles, which noise helps escape (Dauphin et al., 2014). Minima found from different initialisations are typically connected by paths of low loss (Garipov et al., 2018; Draxler et al., 2018). In the very wide limit, training is close to the convex problem of kernel regression with the neural tangent kernel (Lecture 7). And the noise of stochastic minibatches pushes optimisers toward wide, flat minima, which are associated with better generalisation (Keskar et al., 2017), a form of implicit regularisation by the algorithm itself, as in Lecture 6's double descent.
With inverted dropout at rate \(p\), why is nothing rescaled at test time?
A trained classifier outputs probabilities, and on images unlike anything it was trained on it may output confident nonsense. Train the Fashion-MNIST network (with dropout 0.3) and show it handwritten digits from MNIST, which are not clothing at all.
import pickle # Monte Carlo dropout: keep dropout on at test time and average many stochastic predictions P_d, _ = run(Xtr, ytr, [], epochs=10, p_drop=0.3, seed=1) with gzip.open('../../L04/data/mnist.pkl.gz', 'rb') as fh: _, _, (Xmn, ymn) = pickle.load(fh, encoding='latin1') Xood = ((Xmn.astype(np.float32) - mu) / sd) # handwritten digits: never seen in training def softmax(Z): E = np.exp(Z - Z.max(1, keepdims=True)); return E / E.sum(1, keepdims=True) def mc_probs(P, X, T=30, p=0.3, seed=0): r = np.random.default_rng(seed); out = [] for _ in range(T): h = X for k, (W, b) in enumerate(P): h = h @ W + b if k < len(P) - 1: h = np.maximum(h, 0) * (r.random(h.shape) > p) / (1 - p) out.append(softmax(h)) return np.array(out) # T x n x 10 entropy = lambda p: -(p * np.log(p + 1e-12)).sum(-1) from sklearn.metrics import roc_auc_score det_in, det_out = softmax(predict(P_d, Xte)), softmax(predict(P_d, Xood)) mc_in, mc_out = mc_probs(P_d, Xte), mc_probs(P_d, Xood) print(f'test accuracy: dropout off {np.mean(det_in.argmax(1) == yte):.4f}, MC average of 30 {np.mean(mc_in.mean(0).argmax(1) == yte):.4f}') for name, s_in, s_out in [('max softmax probability, dropout off', -det_in.max(1), -det_out.max(1)), ('predictive entropy, dropout off', entropy(det_in), entropy(det_out)), ('predictive entropy, MC dropout', entropy(mc_in.mean(0)), entropy(mc_out.mean(0))), ('mutual information, MC dropout', entropy(mc_in.mean(0)) - entropy(mc_in).mean(0), entropy(mc_out.mean(0)) - entropy(mc_out).mean(0))]: auc = roc_auc_score(np.r_[np.zeros(len(s_in)), np.ones(len(s_out))], np.r_[s_in, s_out]) print(f'{name:38s} AUROC for flagging MNIST digits as unfamiliar: {auc:.3f}') print(f'share of MNIST digits classified with probability > 0.9 (dropout off): {np.mean(det_out.max(1) > 0.9):.1%}')
test accuracy: dropout off 0.8777, MC average of 30 0.8764 max softmax probability, dropout off AUROC for flagging MNIST digits as unfamiliar: 0.773 predictive entropy, dropout off AUROC for flagging MNIST digits as unfamiliar: 0.802 predictive entropy, MC dropout AUROC for flagging MNIST digits as unfamiliar: 0.881 mutual information, MC dropout AUROC for flagging MNIST digits as unfamiliar: 0.940 share of MNIST digits classified with probability > 0.9 (dropout off): 25.0%
A quarter of the handwritten digits are classified as some item of clothing with probability above 0.9. Ranking inputs by the softmax's own confidence separates digits from clothing only moderately (AUROC 0.77; 0.5 is chance, 1 is perfect). Monte Carlo dropout keeps dropout switched on at test time and averages 30 stochastic forward passes. Its predictive entropy does better (0.88), and the mutual information between the prediction and the dropout mask (how much the 30 passes disagree, as opposed to how uncertain each one is) does much better, 0.94. Test accuracy is unchanged (87.8% against 87.6%). Disagreement among plausible models is the signature of inputs the model has not learned about.
Proposition 10.8 makes weight decay a Gaussian prior and training a MAP estimate: one point of the posterior. A Bayesian prediction would average over the whole posterior, $$p(y\mid x,\text{data})=\int p(y\mid x,w)\,p(w\mid\text{data})\,dw,$$ which is intractable for networks. Gal and Ghahramani (2016) showed that training with dropout and weight decay is variational inference: it fits an approximate posterior \(q(w)\) in which each unit's outgoing weights are either present or zero, by minimising a bound on the KL divergence to the true posterior. Monte Carlo dropout is then a Monte Carlo estimate of the posterior predictive. The approximation is crude, and deep ensembles, a handful of networks trained from different initialisations and averaged (Lakshminarayanan et al., 2017), usually give better uncertainty; the mutual information above is the same "disagreement" measure for any ensemble.
Lecture 8's T-learner fitted separate models to the treated and the controls. TARNet (Shalit, Johansson and Sontag, 2017) does this inside one network: shared layers learn a representation \(\Phi(x)\) of the covariates, and two output heads predict the outcome under treatment and under control, each trained only on the units that received it. Sharing the representation lets the two outcome models borrow strength from all the data. Shalit et al.'s CFR adds a penalty that makes the distributions of \(\Phi(x)\) for treated and controls similar (measured by the maximum mean discrepancy of Lecture 7), and they prove the error in estimated individual effects is bounded by the factual prediction error plus this imbalance. Dragonnet (Shi, Blei and Veitch, 2019) adds a third head predicting the propensity score (Lecture 4), so the representation keeps exactly the information needed for adjustment.
A variational quantum circuit applies gates with adjustable angles \(\theta\) to an input-encoding state and measures an observable \(H\); the expectation \(f(\theta)=\langle H\rangle_\theta\) plays the role of a network's output, and such circuits are often called quantum neural networks. They cannot be backpropagated through, because the intermediate quantum state cannot be read out without destroying it. Instead, for gates of the form \(e^{-i\theta P/2}\) with \(P\) a Pauli operator, the parameter-shift rule gives the exact derivative from two more runs of the circuit:
$$\frac{\partial f}{\partial\theta}=\tfrac12\Big[f\big(\theta+\tfrac\pi2\big)-f\big(\theta-\tfrac\pi2\big)\Big]$$(Mitarai et al., 2018; Schuld et al., 2019; Exercise 8). That costs two circuit runs per parameter, like forward-mode differentiation rather than backpropagation, and each run is itself estimated from many measurement shots. The deeper obstacle is the barren plateau (McClean et al., 2018): for sufficiently random circuits on \(n\) qubits, the gradient's variance shrinks exponentially in \(n\), the quantum analogue of vanishing gradients, but with no known equivalent of He initialisation that cures it in general. Designing circuits and costs that avoid barren plateaus (Lecture 5's quantum box) is one of the central problems of quantum machine learning.
Everything in this lecture runs, essentially unchanged, inside the training of the largest models. They are trained by backpropagation computed by reverse-mode automatic differentiation in PyTorch or JAX, with AdamW, linear warm-up and cosine (or similar) decay, careful initialisation scaled by width and depth, weight decay and, in older or smaller models, dropout. What changes at scale is engineering: mixed-precision arithmetic (16-bit or 8-bit numbers with 32-bit accumulators), activation checkpointing to trade compute for the memory backpropagation needs (Section 1), and splitting the model and the minibatch across thousands of accelerators. A trillion-parameter model's training run is, in its mathematics, the loop in this lecture's code boxes.
Next: Lecture 11 asks why very deep networks still train badly with all of this, fixes it with residual connections and normalisation, and builds the symmetries of images and sequences into the architecture with convolutional and recurrent networks.
\(\partial\ell/\partial p=2(p-y)\), \(\partial p/\partial z=p(1-p)\), \(\partial z/\partial w=x\), so \(\partial\ell/\partial w=2(p-y)\,p(1-p)\,x\). If \(z\) is large and positive, \(p\approx1\) and \(p(1-p)\approx0\): a confident wrong answer barely moves. Cross-entropy loss cancels the \(p(1-p)\) factor, giving \((p-y)x\), one reason it is preferred (Lecture 4).
\(L=-Z_c+\log\sum_je^{Z_j}\) for the true class \(c\), so \(\partial L/\partial Z_k=-\mathbb 1[k=c]+e^{Z_k}/\sum_je^{Z_j}=P_k-Y_k\).
Forward mode needs \(n=3\) passes, reverse mode \(m=1000\): use forward mode. Training has one output (the loss) and millions of inputs (the weights): reverse mode, one backward pass.
For symmetric \(z\), \(\mathbb E[a(z)^2]=\tfrac12\mathbb E[z^2]+\tfrac12\alpha^2\mathbb E[z^2]=\tfrac{1+\alpha^2}2\mathbb E[z^2]\). Requiring \(n\cdot\frac{\sigma^2}n\cdot\frac{1+\alpha^2}2=1\) gives \(\sigma^2=2/(1+\alpha^2)\), so variance \(2/((1+\alpha^2)n)\). With \(\alpha=1\) (a linear network) this is \(1/n\).
Forward: \(\operatorname{Var}(z_j)=n_{\text{in}}\operatorname{Var}(W)\operatorname{Var}(h)\). Backward: \(\operatorname{Var}(\delta_i)=n_{\text{out}}\operatorname{Var}(W)\operatorname{Var}(\delta)\). Both cannot hold unless the widths are equal, so they used the harmonic compromise \(\operatorname{Var}(W)=2/(n_{\text{in}}+n_{\text{out}})\).
Adam divides the (decay-augmented) gradient by \(\sqrt{v}\), the root-mean-square of past gradients. A weight with large gradients has large \(\sqrt v\), so its decay term \(\lambda w/\sqrt v\) is small. AdamW subtracts \(\eta\lambda w\) after the normalisation, the same relative shrinkage for every weight.
In the singular basis the iteration decouples: \(c_{t+1}=c_t-\eta(s^2c_t-s\,u^\top y)\), with fixed point \(c^*=u^\top y/s\), so \(c^*-c_t=(1-\eta s^2)^t(c^*-c_0)\) and \(c_0=0\). Directions with large \(s\) are fitted quickly and those with small \(s\) slowly, just as ridge shrinks small-\(s\) directions most: stopping at step \(t\) acts like \(\lambda\approx1/(\eta t)\).
\(\tfrac12[\cos(\theta+\tfrac\pi2)-\cos(\theta-\tfrac\pi2)]=\tfrac12[-\sin\theta-\sin\theta]=-\sin\theta=f'(\theta)\). Unlike a finite difference, the shift is large and the formula is exact.
\(m_t=g(1+\beta+\dots+\beta^{t-1})\to g/(1-\beta)\). With \(\beta=0.9\) and \(\eta=0.01\), the step tends to \(0.1g\), the same as SGD with \(\eta=0.1\). Momentum's benefit is in curved, ill-conditioned valleys (Lecture 2), not in the long-run step size.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Fashion-MNIST: H. Xiao, K. Rasul, R. Vollgraf, "Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms", arXiv:1708.07747 (2017), files from github.com/zalandoresearch/fashion-mnist (MIT licence). MNIST: as in Lecture 4. Two moons: scikit-learn's make_moons.
every number in the text and widgets is computed in verify_L10b.py; code-box outputs are pasted from actual runs (numpy only; no deep-learning framework was available in this environment)