20 / 27 · Neural Networks
Backpropagation
How the gradient of the loss with respect to every weight of a network is computed in one backward sweep: the computational graph, the chain rule in matrix form with shapes, the full forward and backward pass of a two-layer network with cross-entropy, why reverse mode costs about as much as a forward pass, what autograd in PyTorch computes, and checking gradients by finite differences.
From linear models to networks · Gradient descent · Calculus ↗ · Linear algebra ↗
On this page 13
The previous note built networks with thousands of parameters; the small digit classifier there already had 17,226. Gradient descent needs the gradient of the loss with respect to all of them at every step. For logistic regression the gradient had a closed form. For a network the loss is a composition of many functions, and writing out each partial derivative by hand is hopeless. Backpropagation computes all of them at once by applying the chain rule from the loss backwards, reusing every intermediate result. Its cost is a small constant times the cost of evaluating the loss, whatever the number of parameters. It was popularized for neural networks by Rumelhart, Hinton and Williams (1986), and it is the special case for networks of reverse-mode automatic differentiation, which goes back to Linnainmaa (1976) (Baydin et al., 2018, section 3.3).
Notation. As in the previous note, and , with a scalar loss . For any quantity (a scalar, a vector or a matrix), is the gradient of the loss with respect to it, called its adjoint; it has the same shape as . For a map from to , the Jacobian is the matrix with entries . is the elementwise product and the one-hot vector of class .
Why not differentiate numerically?#
The baseline is the definition of the derivative. Perturb one parameter, rerun the network, and divide:
This costs two forward passes per parameter: 34,452 passes per step for the digit classifier, and impossibly many for a network with millions of weights. The result is also only approximate, as the last section shows. Symbolic differentiation, writing out each as a formula, avoids the approximation but repeats the same subexpressions in every formula.
The computational graph#
Any computation of is a sequence of elementary operations. Drawn as a directed acyclic graph, the nodes are the intermediate values and an edge from to means that is computed from . The forward pass evaluates the nodes in order. The backward pass visits them in reverse order and applies the chain rule: if is used by the nodes , its influence on goes through all of them, and the multivariate chain rule adds the contributions,
Worked example: one unit. A sigmoid unit with squared error, , , , at , , , :
| forward | backward | ||
|---|---|---|---|
| , | , |
The backward column starts from and multiplies by one local derivative per node. The local derivative uses the value stored during the forward pass, which is why the forward values are kept.
The chain rule in matrix form#
For vectors the same rule reads: if with Jacobian , then
The backward pass multiplies by transposed Jacobians, and it never needs to form them as matrices. Three operations cover an MLP.
A linear layer , with . Since , the derivative of with respect to one weight collects only the output it feeds: . In matrix form,
The weight gradient is an outer product of the adjoint arriving from above and the input stored from the forward pass.
An elementwise activation . Its Jacobian is diagonal, , so
For a ReLU, is the mask : the gradient passes through active units unchanged and is blocked at inactive ones.
A mini-batch. With the examples as the rows of , and the loss averaged over the batch,
sums the per-example outer products, which is how the gradients of the examples of a batch add up. A useful check: the adjoint of a quantity has its shape, and for each formula there is only one way to multiply the factors so that the shapes match.
A two-layer network, forward and backward#
Take , a hidden layer of ReLU units and classes:
Through softmax and cross-entropy. Write . Differentiating with respect to , the first term gives and the second gives . Hence
predicted probabilities minus the one-hot target, exactly the gradient of logistic regression with respect to its logits. Then the three rules above, in reverse order of the forward pass:
| quantity | shape | adjoint | shape of the product |
|---|---|---|---|
For a batch of examples with the loss averaged, with the one-hot targets as the rows of , and the batch formulas of the previous section take over.
Worked example. Take , , , zero biases, true class (the first), and
Forward: , so ; , and . Backward:
- ;
- has rows and ;
- ;
- ;
- has rows , and .
The third hidden unit receives the adjoint largest in magnitude, , but it is inactive, so the mask stops it and its incoming weights get zero gradient from this example. A unit that is inactive for every example never learns, which is the dead ReLU of the previous note.
Backpropagation through a two-layer network
- The first layer computes .
- The ReLU keeps the positive entries: , and the forward pass stores the mask .
- The second layer gives the logits , the softmax the probabilities , and the loss is .
- The backward pass starts from ; through softmax and cross-entropy, .
- The second layer gives its weight gradient and passes down.
- The ReLU mask, stored in step 2, zeroes the adjoint of the inactive unit: .
- The first layer gives and .
Why reverse mode costs about one forward pass#
Count the work for one linear layer with a batch of examples. The forward product takes multiply–adds. The backward pass computes two products of the same size, and , so it costs twice the forward pass; the elementwise steps are negligible next to the matrix products. The whole gradient therefore costs about three forward passes, and this ratio does not depend on the number of parameters. In general, for , reverse mode computes the full Jacobian with backward sweeps at a cost of , where is guaranteed and is typically between 2 and 3 (Baydin et al., 2018, section 3.2; Griewank and Walther, 2008). A loss is a single number, , so one sweep gives the whole gradient.
Forward mode applies the chain rule in the other direction. Along with every intermediate value it carries its derivative with respect to one input direction, computing a Jacobian–vector product in one pass. A gradient with respect to parameters then needs passes, at a cost of . Forward mode wins when there are few inputs and many outputs; training has millions of inputs (the parameters) and one output (the loss), which is why every deep learning library is built on reverse mode. The Code section computes the 17 partial derivatives of the worked example both ways: 17 forward-mode passes against one backward pass, with identical results.
The price of reverse mode is memory. The backward pass needs the values of the forward pass, such as for and the ReLU masks, so all activations of all layers must be kept until the backward pass reaches them. For large networks this, not the parameters, fills the accelerator’s memory. Gradient checkpointing stores only some layers and recomputes the rest during the backward pass; for a network of layers it needs memory at the cost of one extra forward pass (Chen et al., 2016).
What autograd computes#
Libraries such as PyTorch implement reverse mode automatically. While the forward pass runs, every operation on a tensor that requires gradients records a node of the computational graph, with a function that maps the adjoint of its output to the adjoints of its inputs. PyTorch rebuilds this graph on every forward pass, the operator-overloading approach to reverse-mode automatic differentiation (Paszke et al., 2019, section 4.3), so ordinary Python control flow is differentiable.
| mathematics | PyTorch |
|---|---|
| parameters | tensors with requires_grad=True (every nn.Parameter) |
| the forward computational graph | the chain of grad_fn nodes attached to each result |
| start the backward pass with | loss.backward() |
| the adjoint | param.grad |
| sum over the users of a node | gradients are added into .grad, so call optimizer.zero_grad() before each step |
| one gradient step | optimizer.step() |
| a vector–Jacobian product for a non-scalar output | out.backward(v) or torch.autograd.grad(out, inputs, grad_outputs=v) |
| a forward pass that records nothing | with torch.no_grad(): |
Three consequences are worth knowing:
- Gradients accumulate. Because
.gradis added to, callingbackward()twice without zeroing doubles the gradient. This is the multivariate chain rule’s sum, and it allows gradient accumulation over several small batches on purpose. - Kinks get a convention. The ReLU has no derivative at 0; PyTorch uses 0 there. Any choice in is a valid subgradient, and exact zeros are rare in practice.
- Shared weights add up. A weight used in several places, such as the same recurrent matrix at every time step, gets the sum of the adjoints from all its uses. Unrolled over time, a recurrent network is just a computational graph with shared weights, and backpropagation through time is this note applied to it; the NLP course shows how the products of Jacobians along the time axis make those gradients vanish or explode.
Autograd computes exact derivatives of the program that was run, up to floating point. It does not decide whether those derivatives are useful: a gradient that is zero or nearly zero (a dead ReLU, a saturated sigmoid) or astronomically large is computed just as faithfully. A discrete decision is different: it has no gradient path at all. torch.argmax returns an integer index that is not attached to the graph (requires_grad is False), so a loss computed from the index alone cannot be backpropagated, and a loss that uses the index to select something passes no gradient to the scores that made the choice. When the choice must be learned, a differentiable surrogate replaces it, such as a softmax with a temperature; the Code section shows both.
Checking gradients by finite differences#
A hand-written backward pass, or a custom autograd function, can be wrong in ways that still let the loss decrease. The standard test compares it with the central difference of the first section, one coordinate at a time, through the relative error
with a small floor such as , so that two zero gradients count as agreement instead of giving .
The central difference is better than the one-sided . By Taylor’s theorem , so the one-sided quotient has error while in the central one the even terms cancel and the error is . A smaller is not always better: each loss value carries a rounding error of about relative in double precision, and dividing by amplifies it.
The error of finite differences against the step
In practice:
- compute in double precision (
torch.float64); in single precision the rounding error is about and the check becomes unreliable; - use around to with central differences; a relative error near or below means agreement, near or above a bug;
- avoid points next to kinks: if a ReLU input is within of zero, the two sides see different slopes;
- check a few random coordinates of each parameter tensor for a large network;
torch.autograd.gradcheckdoes the same for a custom function.
In the Code section, the hand-written backward pass of the worked example agrees with central differences on all 17 parameters to a relative error of . Removing the ReLU mask from the backward pass, a typical bug, raises it to : the third unit’s weights get a nonzero gradient where the true one is zero.
What changed#
| Numerical differentiation | Backpropagation | |
|---|---|---|
| Cost of the full gradient | two forward passes per parameter | about three forward passes in total |
| Accuracy | truncation and rounding error | exact up to floating point |
| Memory | one forward pass | all stored activations (or checkpoints) |
| What must be written | only the forward pass | only the forward pass, with autograd |
| Role today | testing a backward pass | how every network is trained |
Limitations#
- Memory grows with depth and batch size, because the activations of the forward pass are kept for the backward pass.
- It needs differentiable operations. Discrete choices, sampling and
argmaxgive no useful gradient:argmaxreturns an index outside the graph, and a step function has derivative zero almost everywhere. Surrogates such as a softmax with a temperature, and tricks such as the reparameterization trick of the Generative Models course make some of them differentiable. - The gradient is local. Backpropagation computes the derivative at the current weights exactly; it does not say whether gradient descent will reach a good solution, and products of many Jacobians can make the gradient vanish or explode in deep or recurrent networks.
- Sequential in depth. The backward pass of a layer waits for the layer above it, which limits how much the layers of a deep network can be computed in parallel.
What you should remember#
- The adjoint has the shape of ; a node used several times sums the contributions of its users.
- Linear layer: , , ; activation: ; softmax with cross-entropy: .
- Reverse mode costs a small constant times one forward pass (about 3 for an MLP), independent of the number of parameters; forward mode needs one pass per parameter.
- The price is memory: all activations are stored until the backward pass uses them.
- PyTorch records the graph during the forward pass;
loss.backward()fills.gradby adding, hencezero_grad(). - Check a hand-written gradient with central differences in double precision, , by relative error.
Code#
The worked example by hand and by autograd, a gradient check that catches a planted bug, the step size of finite differences, forward against reverse mode, two autograd conventions, and an argmax that has no gradient:
import numpy as np, torch
import torch.autograd.forward_ad as fwAD
# the worked example: x = (1, 2), true class 0 (the first), zero biases
x = np.array([1.0, 2.0]); y = 0
W1 = np.array([[1.0, 0.0], [-1.0, 1.0], [0.5, -1.0]]); b1 = np.zeros(3)
W2 = np.array([[1.0, -1.0, 2.0], [0.5, 1.0, -1.0]]); b2 = np.zeros(2)
def forward(W1, b1, W2, b2):
z1 = W1 @ x + b1; h = np.maximum(z1, 0); z2 = W2 @ h + b2
m = z2.max(); logZ = m + np.log(np.exp(z2 - m).sum())
return z1, h, z2, np.exp(z2 - logZ), logZ - z2[y]
def backward(W1, b1, W2, b2, mask=True):
z1, h, z2, p, L = forward(W1, b1, W2, b2)
dz2 = p - np.eye(2)[y] # softmax + cross-entropy
dW2, db2, dh = np.outer(dz2, h), dz2, W2.T @ dz2
dz1 = dh * (z1 > 0) if mask else dh # mask=False plants a bug: the ReLU is skipped
return np.outer(dz1, x), dz1, dW2, db2
z1, h, z2, p, L = forward(W1, b1, W2, b2)
dW1, db1, dW2, db2 = backward(W1, b1, W2, b2)
print(p.round(3), round(L, 3)) # [0.182 0.818] 1.701
print(dW2.round(3).tolist()) # [[-0.818, -0.818, -0.0], [0.818, 0.818, 0.0]]
print((W2.T @ (p - np.eye(2)[y])).round(3), dW1.round(3).tolist())
# [-0.409 1.635 -2.453] [[-0.409, -0.818], [1.635, 3.27], [-0.0, -0.0]]
# the same gradients from autograd
T = lambda a: torch.tensor(a, requires_grad=True)
tW1, tb1, tW2, tb2 = T(W1), T(b1), T(W2), T(b2)
loss = torch.nn.functional.cross_entropy((tW2 @ torch.relu(tW1 @ torch.tensor(x) + tb1) + tb2)[None], torch.tensor([y]))
loss.backward()
print(np.allclose(tW1.grad.numpy(), dW1), np.allclose(tW2.grad.numpy(), dW2)) # True True
# gradient check: central differences on every parameter, relative error against backprop
def check(mask):
params = [W1.copy(), b1.copy(), W2.copy(), b2.copy()]
grads = backward(*params, mask=mask)
worst, eps = 0.0, 1e-6
for P, G in zip(params, grads):
for i in np.ndindex(P.shape):
old = P[i]
P[i] = old + eps; Lp = forward(*params)[-1]
P[i] = old - eps; Lm = forward(*params)[-1]
P[i] = old
num = (Lp - Lm) / (2 * eps)
worst = max(worst, abs(num - G[i]) / max(abs(num), abs(G[i]), 1e-8))
return worst
print(f'{check(True):.1e} {check(False):.1e}') # 3.6e-10 1.0e+00
# the step of a finite difference: truncation error for large steps, rounding error for tiny ones
f = lambda a: forward(np.array([[a, 0.0], [-1.0, 1.0], [0.5, -1.0]]), b1, W2, b2)[-1]
for eps in (1e-1, 1e-5, 1e-12):
print(eps, f'{abs((f(1 + eps) - f(1 - eps)) / (2 * eps) - dW1[0, 0]):.1e}')
# 0.1 2.0e-05 | 1e-05 7.4e-12 | 1e-12 1.1e-04
# forward mode needs one pass per parameter, reverse mode one pass in total
flat = torch.cat([t.detach().flatten() for t in (tW1, tb1, tW2, tb2)])
def L_of(theta):
A, a, B, b = theta[:6].view(3, 2), theta[6:9], theta[9:15].view(2, 3), theta[15:]
return torch.nn.functional.cross_entropy((B @ torch.relu(A @ torch.tensor(x) + a) + b)[None], torch.tensor([y]))
def directional(v): # one forward-mode pass: the derivative along v
with fwAD.dual_level():
return fwAD.unpack_dual(L_of(fwAD.make_dual(flat, v))).tangent
fwd = torch.stack([directional(torch.eye(17, dtype=flat.dtype)[i]) for i in range(17)])
print(len(fwd), torch.allclose(fwd, torch.cat([t.grad.flatten() for t in (tW1, tb1, tW2, tb2)]))) # 17 True
# autograd details: the ReLU has derivative 0 at 0, and .grad accumulates until it is zeroed
u = torch.tensor(0.0, requires_grad=True); torch.relu(u).backward(); print(u.grad.item()) # 0.0
w = torch.tensor(3.0, requires_grad=True)
for _ in range(2):
(w ** 2).backward()
print(w.grad.item()) # 12.0: two backward calls add 6 + 6
# argmax returns an integer index with no autograd path; a softmax with temperature 0.5 is a differentiable surrogate
s = torch.tensor([1.0, 3.0, 2.0], requires_grad=True)
k = s.argmax(); print(k.item(), k.dtype, k.requires_grad) # 1 torch.int64 False
(torch.softmax(s / 0.5, 0) @ torch.arange(3.0)).backward() # the expected index under the softmax, 1.101
print([round(g, 3) for g in s.grad.tolist()]) # [-0.035, -0.176, 0.211]
Next#
Backpropagation gives exact gradients for a network of any depth. Exact does not mean useful: in a deep stack the gradient is a product of one Jacobian per layer and can shrink or grow geometrically, and a network flexible enough to fit anything fits its training noise too. The next note covers what makes deep networks trainable and keeps them from overfitting: initialization that preserves the scale of signals, dropout, weight decay, learning-rate schedules, data augmentation and residual connections.
References#
- D. E. Rumelhart, G. E. Hinton, R. J. Williams. Learning representations by back-propagating errors. Nature, 323(6088):533–536, 1986.
- S. Linnainmaa. Taylor expansion of the accumulated rounding error. BIT Numerical Mathematics, 16(2):146–160, 1976.
- A. G. Baydin, B. A. Pearlmutter, A. A. Radul, J. M. Siskind. Automatic differentiation in machine learning: a survey. Journal of Machine Learning Research, 18(153):1–43, 2018. Sections 3.1–3.2 (forward and reverse mode, their costs), section 3.3 (history).
- A. Griewank, A. Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed. SIAM, 2008.
- T. Chen, B. Xu, C. Zhang, C. Guestrin. Training deep nets with sublinear memory cost. arXiv:1604.06174, 2016.
- A. Paszke et al. PyTorch: an imperative style, high-performance deep learning library. NeurIPS, 2019. Section 4.3 (automatic differentiation).
- I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. Section 6.5 (back-propagation and other differentiation algorithms).
- C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Section 5.3 (error backpropagation; 5.3.3 on its efficiency and numerical checks).
- PyTorch documentation: Autograd mechanics,
torch.autograd.gradcheck, forward-mode AD. - E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 7: introduction to deep learning, and the class materials on PyTorch tensors, autograd and MLPs.