A linear classifier or a linear regression can only produce scores that are affine functions of the input, so it cannot represent a pattern such as exclusive-or. A multilayer perceptron (MLP) composes several affine maps with fixed nonlinear functions, which gives a much larger family of functions, and is trained by gradient descent. The unit on minibatch stochastic gradient descent supplies the training loop; the question answered here is how the gradient of a loss with respect to all weights of a deep composition is computed efficiently and exactly. The answer, backpropagation, is nothing more than the chain rule organized to reuse intermediate quantities.
The network and the loss
Definition 30.1.1
(Feed-forward network)
Fix layer widths and an activation function applied componentwise. For an input , define for
with weight matrices and bias vectors . The network output is ; for a regression output the last activation is often replaced by the identity. Common activations are , the logistic sigmoid and the rectifier . For a training example and a differentiable loss, for instance , the objective is the sum of over training examples.
The parameter count of a network with these widths is . A forward pass costs about as many multiplications as there are weights.
Theorem 30.1.2
(Without a nonlinearity, depth adds nothing)
If is the identity, the network computes an affine function of , for some matrix and vector . In particular no such network represents the exclusive-or function on .
Proof
(Composition of affine maps and a midpoint argument)
A composition of affine maps is affine, so . If an affine scalar function had and , then , because for affine the value at a midpoint pair is the average, and and have the same midpoint . This would read , a contradiction.
Backpropagation
Definition 30.1.3
(Error signal)
At layer , the error signal is , the sensitivity of the loss to the pre-activation vector .
Theorem 30.1.4
(Backpropagation equations)
Suppose is differentiable at every that occurs (for ReLU, away from ). Then
and the gradients with respect to the parameters are
where is the componentwise product. Computing the forward pass and then these formulas for gives the gradient of with respect to all parameters at a total cost proportional to the number of parameters.
Proof
(The chain rule through the layers)
The output depends on componentwise, so . For , the variable influences only through , with . By the chain rule,
which is the stated recursion. Since , and appears only in , we get and . Each recursion step and each gradient formula is a matrix-vector or outer product of the size of the weight matrix it concerns, which gives the cost statement.
Proof X-ray
Why only the next layer matters
The proof has one structural fact and one computation. The structural fact is that influences only through the vector , because the layers feed forward; this is what lets the chain rule be written as a sum over the entries of with no other terms. The computation is the local derivative , and the factor is the place where differentiability of is used. The recursion runs backward because needs and the stored . Each is computed once and used both for and and for the next step; this reuse is what makes the cost proportional to the number of parameters instead of repeating chain-rule factors for every weight. With skip connections, would also influence later layers directly and extra terms would appear in the recursion.
For binary classification the output layer is usually a single sigmoid unit, , trained with the cross-entropy loss for . Here and , so the output error simplifies to . The sigmoid derivative cancels, which is one reason this pairing is preferred over squared error for classification: the error signal does not vanish when the unit is saturated and wrong.
The forward pass must store every and , because the backward pass reuses them. Saving the intermediate is what makes the method cheaper than differentiating each weight separately, which would repeat the common factors of the chain rule. The training objective is generally not convex in the parameters; gradient descent reaches a stationary point, not a guaranteed global minimizer. For the sigmoid, , so the factors in the recursion can shrink the signal geometrically with depth, which is the vanishing gradient effect.
Concept lensAlgorithmic
Backpropagation as a row vector times Jacobians
The loss is a scalar, so is a row vector. The recursion says : it multiplies this row vector by one layer Jacobian at a time, a matrix-vector product per layer. Forming the product of all the Jacobians first would need matrix-matrix products; ordering the multiplications from the scalar end is what makes the method cheap.
Worked examples
Worked example 30.1.5
(An exact gradient for a two-unit ReLU network)
Take input , target , one hidden layer with ReLU and parameters
with output and loss . Forward: , both positive, so and . The loss is .
Backward: the output error is , so and . The hidden error is . Hence
A gradient step of size gives , , , . Then , and the loss is , down from .
Worked example 30.1.6
(A ReLU network that computes exclusive-or)
Take , and output . Evaluating at the four inputs: gives ; and give ; gives . So the network represents exclusive-or exactly, which no affine function can. The first layer maps the four inputs to , and in these coordinates the classes become linearly separable.
Worked example 30.1.7
(Cross-entropy output error, including a saturated wrong output)
Take one sigmoid output unit with , , and target . Then , and the loss is . The output error is , so and . As a check, has at .
For the boundary case keep but let , so the unit is saturated and wrong. Then . Cross-entropy gives : the signal is not damped at all. With the squared error the error signal would be , about times smaller.
Common mistakes and subtle points
Counterexample mode
ReLU at zero has no gradient to back-propagate
A tempting claim is that backpropagation returns the gradient of the loss at every parameter value. Take input , target , a single ReLU unit and loss . For we have , so . For we have , so as . The one-sided derivatives at are therefore and , and no derivative exists there. The recursion returns , which is or according to the convention chosen for . Each value equals one of the one-sided derivatives, and neither is the derivative. The theorem's hypothesis, differentiability at every that occurs, is exactly what fails here.
Common mistake
(Where the derivative is evaluated)
The factor is evaluated at the pre-activation , not at the activation . For the sigmoid one may write using , but for ReLU the derivative is the indicator of , and at a convention must be fixed. A gradient computed by backpropagation should be checked against a finite difference on at least a few parameters.
Common mistake
(Equal initial weights never separate hidden units)
Initializing all weights equal makes hidden units in the same layer receive identical updates, so they never differentiate. Weights are therefore initialized randomly.
Common mistake
(Training loss is not test performance)
A small training loss gives no guarantee about test error. The objective is also not convex in the parameters, so a stationary point reached by gradient descent is not certified as a global minimizer.
Exercises
Quick check
(A network has one ReLU hidden unit and a linear output: . Evaluate it at .)
Recall .
Solution · Answer
At , and . At , and . At , and .
Quick check
(How many parameters does a network with widths have?)
Each layer contributes a weight matrix and a bias vector.
Solution · Answer
.
Quick check
(Let with , , , target and loss . Write the exact gradient with respect to and in terms of , and give approximate values.)
The derivative of is .
Solution · Answer
With , and . Then . For , the derivative of is , so .
Quick check
(Let every hidden layer of a deep network use the sigmoid. Show that the product of the activation-derivative factors along a single path of the recursion is at most in absolute value.)
Bound first.
Solution · Answer
Since and for (the product of two numbers summing to is at most ), each factor is at most . A product of such factors is at most . The weights in the path can offset this, but unless they are large the signal reaching early layers is tiny.