The Backpropagation Algorithm
Learning Objectives
After reading this page, you should be able to:
- Derive the gradient of the loss with respect to one weight/bias in a feedforward neural network using a computation graph and the single-variable/multivariate chain rule.
- Explain how backpropagation uses dynamic programming to improve efficiency of gradient computations.
- State the recursive backpropagation equations for an \(M\)-layer feedforward network.
- Explain why a forward pass must run before the backward pass during training.
1 Introduction
The Multi-Layer Perceptron chapter focused on inference. We assumed that the weights and biases of the network were already known, and we used them to compute the network’s prediction for a given input. This computation is the forward pass, which moves layer by layer from the input layer to the output layer. During training, the forward pass also computes the loss of the prediction.
What we have not discussed yet is learning, which means finding good weights and biases from the training data. To learn them, we use the same idea as in Gradient Descent. We define a cost, compute partial derivatives of the cost with respect to every parameter, and update weights and biases in the direction that decreases the cost. The difficulty is scale. A network with many layers and units can have millions of parameters, and recomputing each partial derivative from scratch at every step is not feasible.
The backpropagation algorithm resolves this difficulty. It computes every partial derivative at roughly twice the cost of one forward pass. We first examine why training a network with millions of parameters is challenging. We then compute several gradients by hand for a three-layer network. These calculations reveal overlapping subproblems. By computing the gradients in a specific order, we can reuse earlier results and avoid redundant work. This is the dynamic programming view of backpropagation. We apply this approach to compute all gradients for the same network. Finally, we present the algorithm for a network with any number of layers, explain why it requires a forward pass first, and show how to vectorize it.
2 The Challenge of Training a Neural Network
Recall how we trained linear models with Gradient Descent. We start from some initial parameters and repeatedly take a small step in the direction that decreases the cost \(\mathcal{E}\) fastest, which is the direction of the negative gradient. For a model with weights \(\mathbf{w}\) and bias \(b\), each step updates both, where \(\alpha\) is a positive learning rate:
\[ \begin{aligned} & \mathbf{w} \leftarrow \mathbf{w} - \alpha \, \nabla_{\mathbf{w}} \mathcal{E} \\ & b \leftarrow b - \alpha \, \frac{\partial \mathcal{E}}{\partial b} \end{aligned} \]
Conceptually, training a neural network with gradient descent is no different. We compute the partial derivative of the cost with respect to every weight and bias, then apply the same updates. The main challenge is efficiency. A neural network can easily have millions of weights and biases, and computing each partial derivative independently would require millions of computations per update step. That is computationally infeasible in practice.
The backpropagation algorithm solves this problem. By propagating information backward through the network and reusing intermediate computations, backpropagation computes the partial derivatives for all parameters in one backward pass. This pass takes about twice the computation of one forward pass, a small constant multiple no matter how many parameters the network has.
Throughout this page, all derivations are for one training example. This is sufficient because the cost is the average loss over the training examples, so its gradient is the average of the per-example gradients. From here on, \(\mathcal{L}\) denotes the loss for one training example.
3 Gradients for a 3-Layer Neural Network
To motivate backpropagation, we first compute gradients naively, by hand, for a network with two hidden layers and a vector output. This is the smallest architecture that exhibits every chain-rule structure backpropagation must handle. After writing out the forward pass, we derive the partial derivatives of the loss with respect to one weight in each layer: \(W^{(3)}_{1,2}\), \(W^{(2)}_{3,4}\), and \(W^{(1)}_{2,3}\). Comparing the three derivations reveals the redundant computation that backpropagation eliminates.
3.1 The 3-Layer MLP and Notation
We will use the 3-layer MLP and the general notation from the Multi-Layer Perceptron chapter. Recall that \(\mathbf{a}^{(m)}\) denotes the activations for layer \(m\), so \(\mathbf{a}^{(0)}\) is the input and \(\mathbf{a}^{(3)}\) is the output. We assume that the output layer has more than one unit, so that both the output and the target \(\mathbf{t}\) are vectors. Figure 1 shows a concrete example of this network, which we will use for the gradient derivations later in this section.
3.2 Forward Pass Computations
To derive any gradient, we first need to know exactly how each quantity contributes to the loss computation. Recall the forward pass for a 3-layer MLP from the Multi-Layer Perceptron chapter. It proceeds layer by layer, computing pre-activations and activations in order from layer 1 to layer 3, and then computes the loss. Below, we restate these computations for each unit using the general notation.
Layer 1 (hidden). For each unit \(j = 1, \ldots, D^{(1)}\): \[ \begin{aligned} & z^{(1)}_j = \sum_{k=1}^{D^{(0)}} W^{(1)}_{j,k} \, a^{(0)}_k + b^{(1)}_j \\ & a^{(1)}_j = f^{(1)}\!\bigl(z^{(1)}_j\bigr) \end{aligned} \]
Layer 2 (hidden). For each unit \(j = 1, \ldots, D^{(2)}\):
\[ \begin{aligned} & z^{(2)}_j = \sum_{k=1}^{D^{(1)}} W^{(2)}_{j,k} \, a^{(1)}_k + b^{(2)}_j \\ & a^{(2)}_j = f^{(2)}\!\bigl(z^{(2)}_j\bigr) \end{aligned} \]
Layer 3 (output). For each unit \(j = 1, \ldots, D^{(3)}\):
\[ \begin{aligned} & z^{(3)}_j = \sum_{k=1}^{D^{(2)}} W^{(3)}_{j,k} \, a^{(2)}_k + b^{(3)}_j \\ & a^{(3)}_j = f^{(3)}\!\bigl(z^{(3)}_j\bigr) \end{aligned} \]
Loss. \[ \begin{aligned} & \mathcal{L} = \mathcal{L}\!\bigl(\mathbf{a}^{(3)}, \mathbf{t}\bigr) \end{aligned} \]
We will reference these forward-pass computations repeatedly in the derivations below.
3.3 Loss Gradient with Respect to a Layer-3 Weight
Let’s begin with a simple case, the gradient of the loss with respect to an output-layer weight. Consider \(W^{(3)}_{1,2}\), which connects hidden unit 2 in layer 2 to output unit 1.
Before applying the chain rule, we need to see how \(W^{(3)}_{1,2}\) affects the loss during the forward pass. A computation graph records these dependencies, and it is our main tool for deriving gradients.
Definition: A computation graph is a directed graph whose nodes are scalar quantities in the forward pass, such as weights, biases, pre-activations, activations, and the loss. An edge from node \(u\) to node \(v\) means that \(v\) is computed using \(u\) as an input.
Computation graph from \(W^{(3)}_{1,2}\) to the loss
\[ \begin{aligned} \class{bpq-z-3-1}{z^{(3)}_1} & = \class{bpq-W-3-1-2}{W^{(3)}_{1,2}} \, \class{bpq-a-2-2}{a^{(2)}_2} + \cdots \\[0.5em] \class{bpq-a-3-1}{a^{(3)}_1} & = f^{(3)}\!\bigl(\class{bpq-z-3-1}{z^{(3)}_1}\bigr) \\[0.5em] \class{bpq-C}{\mathcal{L}} & = \mathcal{L}\!\bigl(\class{bpq-a-3-1}{a^{(3)}_1}, \ldots\bigr) \end{aligned} \]
Figure 2 shows the forward-pass computations from the weight \(W^{(3)}_{1,2}\) to the loss \(\mathcal{L}\). Reading the graph from left to right, the weight \(W^{(3)}_{1,2}\) and the activation \(a^{(2)}_2\) are used to compute the pre-activation \(z^{(3)}_1\). Applying the activation function \(f^{(3)}\) to \(z^{(3)}_1\) produces the activation \(a^{(3)}_1\), which is then used to compute the loss \(\mathcal{L}\). The equations below the graph show the relevant forward pass computations.
The computation graph in Figure 2 represents every quantity in the forward pass as a node, which is not the case for the network diagram in Figure 1. Two examples illustrate this difference. The network diagram draws the weight \(W^{(3)}_{1,2}\) as an edge, whereas the computation graph draws it as a node. The network diagram also combines the pre-activation \(z^{(3)}_1\) and the activation \(a^{(3)}_1\) into one unit, whereas the computation graph draws them as separate nodes. By making every intermediate quantity explicit, the computation graph lets us apply the chain rule one edge at a time without skipping a step. Libraries such as PyTorch build a computation graph during the forward pass and use it to compute gradients automatically. This technique, called automatic differentiation, is how backpropagation is implemented in practice.
Having drawn the computation graph, we are ready to derive the partial derivative of the loss with respect to the weight. Since the weight \(W^{(3)}_{1,2}\) affects the loss through one path only, the single-variable chain rule is enough to compute the partial derivative.
Definition (single-variable chain rule): Let \(x\), \(u\), and \(y\) be scalars. Suppose \(u = g(x)\) and \(y = h(u)\) for differentiable scalar functions \(g\) and \(h\). Then the chain rule for derivatives states that \[ \begin{aligned} & \frac{\partial y}{\partial x} = \frac{\partial y}{\partial u}\cdot\frac{\partial u}{\partial x}. \end{aligned} \]
Applying the single-variable chain rule to the path, we can write the partial derivative of the loss with respect to the weight as follows:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial W^{(3)}_{1,2}} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_1} \cdot \frac{\partial a^{(3)}_1}{\partial z^{(3)}_1} \cdot \frac{\partial z^{(3)}_1}{\partial W^{(3)}_{1,2}}. \end{aligned} \]
We evaluate each factor in the chain rule separately.
The first factor is the derivative of the loss with respect to the output activation \(a^{(3)}_1\). This factor is determined by our choice of loss function, so we leave it as it is.
The next factor is the derivative of the output activation with respect to its pre-activation. Since this depends on the choice of the activation function, we leave it in the general form shown below:
\[ \begin{aligned} & a^{(3)}_1 = f^{(3)}\!\bigl(z^{(3)}_1\bigr) \qquad \Rightarrow \qquad \frac{\partial a^{(3)}_1}{\partial z^{(3)}_1} = f^{(3)\prime}\!\bigl(z^{(3)}_1\bigr). \end{aligned} \]
The last factor is the derivative of the pre-activation with respect to the weight. Based on the forward pass computation, the derivative is equal to the activation \(a^{(2)}_2\) that the weight multiplies: \[ \begin{aligned} &z^{(3)}_1 = W^{(3)}_{1,2} \, a^{(2)}_2 + \cdots \qquad \Rightarrow \qquad \frac{\partial z^{(3)}_1}{\partial W^{(3)}_{1,2}} = a^{(2)}_2. \end{aligned} \]
Substituting these three factors into the chain rule gives:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial W^{(3)}_{1,2}} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_1} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_1\bigr) \cdot a^{(2)}_2. \end{aligned} \]
Question: Consider the output-layer weight \(W^{(3)}_{2,1}\), which connects hidden unit 1 in layer 2 to output unit 2.
- Draw the computation graph from \(W^{(3)}_{2,1}\) to the loss.
- Write down the forward pass equations for the nodes in the computation graph.
- Derive the partial derivative of the loss with respect to \(W^{(3)}_{2,1}\).
Answer:
- The weight \(W^{(3)}_{2,1}\) is used only to compute the pre-activation \(z^{(3)}_2\). The pre-activation \(z^{(3)}_2\) is used only to compute the activation \(a^{(3)}_2\), which is then used to compute the loss. The computation graph is shown below.
- The forward pass equations for the nodes in the computation graph are:
\[ \begin{aligned} z^{(3)}_2 & = W^{(3)}_{2,1} \, a^{(2)}_1 + \cdots \\[0.5em] a^{(3)}_2 & = f^{(3)}\!\bigl(z^{(3)}_2\bigr) \\[0.5em] \mathcal{L} & = \mathcal{L}\!\bigl(a^{(3)}_2, \ldots\bigr) \end{aligned} \]
- Each variable on this path leads to exactly one downstream variable, so the single-variable chain rule applies:
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W^{(3)}_{2,1}} & = \frac{\partial \mathcal{L}}{\partial a^{(3)}_2} \cdot \frac{\partial a^{(3)}_2}{\partial z^{(3)}_2} \cdot \frac{\partial z^{(3)}_2}{\partial W^{(3)}_{2,1}} \\[0.5em] & = \frac{\partial \mathcal{L}}{\partial a^{(3)}_2} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_2\bigr) \cdot a^{(2)}_1. \end{aligned} \]
The result has the same structure as the gradient for \(W^{(3)}_{1,2}\). The first two factors depend on the output unit that the weight feeds into, and the last factor is the activation that the weight multiplies.
3.4 Loss Gradient with Respect to a Layer-2 Weight
Next, let’s consider a weight one layer deeper: \(W^{(2)}_{3,4}\), connecting hidden unit 4 in layer 1 to hidden unit 3 in layer 2. We want to compute the partial derivative of the loss with respect to \(W^{(2)}_{3,4}\). Let’s start by drawing the computation graph from this weight to the loss, shown in Figure 3. We also show the relevant forward pass equations below the graph.
Computation graph from \(W^{(2)}_{3,4}\) to the loss
\[ \begin{aligned} \class{bpq-z-2-3}{z^{(2)}_3} & = \class{bpq-W-2-3-4}{W^{(2)}_{3,4}} \, \class{bpq-a-1-4}{a^{(1)}_4} + \cdots \\[0.5em] \class{bpq-a-2-3}{a^{(2)}_3} & = f^{(2)}\!\bigl(\class{bpq-z-2-3}{z^{(2)}_3}\bigr) \\[0.5em] \class{bpq-z-3-1 bpq-z-3-2}{z^{(3)}_\ell} & = \class{bpq-W-3-1-3 bpq-W-3-2-3}{W^{(3)}_{\ell,3}} \, \class{bpq-a-2-3}{a^{(2)}_3} + \cdots, \quad \ell = 1, 2 \\[0.5em] \class{bpq-a-3-1 bpq-a-3-2}{a^{(3)}_\ell} & = f^{(3)}\!\bigl(\class{bpq-z-3-1 bpq-z-3-2}{z^{(3)}_\ell}\bigr), \quad \ell = 1, 2 \\[0.5em] \class{bpq-C}{\mathcal{L}} & = \mathcal{L}\!\bigl(\class{bpq-a-3-1}{a^{(3)}_1}, \class{bpq-a-3-2}{a^{(3)}_2}, \ldots\bigr) \end{aligned} \]
The computation graph in Figure 3 differs from the one in Figure 2 in an important way. In Figure 2, there is only one path from the weight to the loss. In Figure 3, the weight \(W^{(2)}_{3,4}\) affects the loss through two paths. The activation \(a^{(2)}_3\) is used to compute both output pre-activations \(z^{(3)}_1\) and \(z^{(3)}_2\), and each of them affects the loss. This is the first time we encounter fan-out in a computation graph, which we now define.
Definition: A node in a computation graph fans out if it has more than one outgoing edge, that is, if its value is used as an input to more than one downstream node.
When a node fans out, it affects the loss through every outgoing path, so the partial derivative of the loss with respect to that node is the sum of the contributions along these paths. The multivariate chain rule formalizes this sum.
Definition (multivariate chain rule): Let \(u\), \(v_1, \ldots, v_m\), and \(y\) be scalars. Suppose each \(v_\ell = g_\ell(u)\) for differentiable functions \(g_1, \ldots, g_m\), and \(y = h(v_1, \ldots, v_m)\) for a differentiable function \(h\). Then \[ \begin{aligned} & \frac{\partial y}{\partial u} = \sum_{\ell=1}^{m} \frac{\partial y}{\partial v_\ell} \cdot \frac{\partial v_\ell}{\partial u}. \end{aligned} \]
We derive the partial derivative by working backward from the loss, one node at a time, until we reach the weight \(W^{(2)}_{3,4}\).
We start with the two output pre-activations. This step repeats the reasoning from Section 3.3, so we leave it as an exercise.
Question: Derive the partial derivatives of the loss with respect to the output pre-activations \(z^{(3)}_1\) and \(z^{(3)}_2\). Show that
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(3)}_\ell} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_\ell\bigr), \quad \ell = 1, 2. \end{aligned} \]
Answer:
Each pre-activation \(z^{(3)}_\ell\) affects the loss through one path only, so the single-variable chain rule applies: \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z^{(3)}_1} & = \frac{\partial \mathcal{L}}{\partial a^{(3)}_1} \cdot \frac{\partial a^{(3)}_1}{\partial z^{(3)}_1}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial z^{(3)}_2} & = \frac{\partial \mathcal{L}}{\partial a^{(3)}_2} \cdot \frac{\partial a^{(3)}_2}{\partial z^{(3)}_2}. \end{aligned} \]
We can write the two equations compactly as follows:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(3)}_\ell} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot \frac{\partial a^{(3)}_\ell}{\partial z^{(3)}_\ell}, \quad \ell = 1, 2. \end{aligned} \]
As in Section 3.3, the first factor in each product is determined by the loss function, so we leave it as it is. The second factor is the derivative of the activation function:
\[ \begin{aligned} & a^{(3)}_\ell = f^{(3)}\!\bigl(z^{(3)}_\ell\bigr) \qquad \Rightarrow \qquad \frac{\partial a^{(3)}_\ell}{\partial z^{(3)}_\ell} = f^{(3)\prime}\!\bigl(z^{(3)}_\ell\bigr), \quad \ell = 1, 2. \end{aligned} \]
Substituting gives: \[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(3)}_\ell} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_\ell\bigr), \quad \ell = 1, 2. \end{aligned} \]
Next, we move back to the activation \(a^{(2)}_3\), where the graph fans out. We apply the multivariate chain rule with \(a^{(2)}_3\) in the role of \(u\), the pre-activations \(z^{(3)}_1\) and \(z^{(3)}_2\) in the role of \(v_1\) and \(v_2\), and \(\mathcal{L}\) in the role of \(y\): \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial a^{(2)}_3} & = \frac{\partial \mathcal{L}}{\partial z^{(3)}_1} \cdot \frac{\partial z^{(3)}_1}{\partial a^{(2)}_3} + \frac{\partial \mathcal{L}}{\partial z^{(3)}_2} \cdot \frac{\partial z^{(3)}_2}{\partial a^{(2)}_3} \\[0.5em] & = \sum_{\ell=1}^{2} \frac{\partial \mathcal{L}}{\partial z^{(3)}_\ell} \cdot \frac{\partial z^{(3)}_\ell}{\partial a^{(2)}_3}. \end{aligned} \]
The partial derivatives of \(\mathcal{L}\) with respect to \(z^{(3)}_1\) and \(z^{(3)}_2\) are given in the exercise above. Each remaining factor is the weight that multiplies \(a^{(2)}_3\) in the corresponding forward pass equation:
\[ \begin{aligned} & z^{(3)}_\ell = W^{(3)}_{\ell,3} \, a^{(2)}_3 + \cdots \qquad \Rightarrow \qquad \frac{\partial z^{(3)}_\ell}{\partial a^{(2)}_3} = W^{(3)}_{\ell,3}, \quad \ell = 1, 2. \end{aligned} \]
Substituting these expressions gives:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial a^{(2)}_3} = \sum_{\ell=1}^{2} \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_\ell\bigr) \cdot W^{(3)}_{\ell,3}. \end{aligned} \]
Finally, we move from \(a^{(2)}_3\) back to the weight. The weight \(W^{(2)}_{3,4}\) is used only to compute \(z^{(2)}_3\), and \(z^{(2)}_3\) is used only to compute \(a^{(2)}_3\). This part of the path does not branch, so the single-variable chain rule applies:
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W^{(2)}_{3,4}} & = \frac{\partial \mathcal{L}}{\partial a^{(2)}_3} \cdot \frac{\partial a^{(2)}_3}{\partial z^{(2)}_3} \cdot \frac{\partial z^{(2)}_3}{\partial W^{(2)}_{3,4}}. \end{aligned} \]
The first factor is the expression we just derived. The other two factors follow from the forward pass equations, as in Section 3.3:
\[ \begin{aligned} & a^{(2)}_3 = f^{(2)}\!\bigl(z^{(2)}_3\bigr) \qquad \Rightarrow \qquad \frac{\partial a^{(2)}_3}{\partial z^{(2)}_3} = f^{(2)\prime}\!\bigl(z^{(2)}_3\bigr), \\[0.5em] & z^{(2)}_3 = W^{(2)}_{3,4} \, a^{(1)}_4 + \cdots \qquad \Rightarrow \qquad \frac{\partial z^{(2)}_3}{\partial W^{(2)}_{3,4}} = a^{(1)}_4. \end{aligned} \]
Substituting all three factors gives the final result:
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W^{(2)}_{3,4}} & = \left(\, \sum_{\ell=1}^{2} \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_\ell\bigr) \cdot W^{(3)}_{\ell,3} \right) \cdot f^{(2)\prime}\!\bigl(z^{(2)}_3\bigr) \cdot a^{(1)}_4. \end{aligned} \]
Written in terms of the chain rule factors only, the same result is:
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W^{(2)}_{3,4}} & = \left(\, \sum_{\ell=1}^{2} \frac{\partial \mathcal{L}}{\partial a^{(3)}_\ell} \cdot \frac{\partial a^{(3)}_\ell}{\partial z^{(3)}_\ell} \cdot \frac{\partial z^{(3)}_\ell}{\partial a^{(2)}_3} \right) \cdot \frac{\partial a^{(2)}_3}{\partial z^{(2)}_3} \cdot \frac{\partial z^{(2)}_3}{\partial W^{(2)}_{3,4}}. \end{aligned} \]
To summarize, the only new feature in this derivation is the fan-out at \(a^{(2)}_3\). Because \(a^{(2)}_3\) affects the loss through both \(z^{(3)}_1\) and \(z^{(3)}_2\), the multivariate chain rule expresses the partial derivative of the loss with respect to \(a^{(2)}_3\) as a sum with one term for each of these pre-activations. Everywhere else, the single-variable chain rule applies as in Section 3.3.
3.5 Loss Gradient with Respect to a Layer-1 Weight
As our final case, let’s consider \(W^{(1)}_{2,3}\), connecting input unit 3 to hidden unit 2 in layer 1. We want to derive the partial derivative of the loss with respect to \(W^{(1)}_{2,3}\). Rather than presenting the detailed derivations, we leave this task as an exercise for the reader. Below, we present the computation graph.
Computation graph from \(W^{(1)}_{2,3}\) to the loss
In Figure 4, the forward path fans out at two depths, first at \(a^{(1)}_2\) and then again at each \(a^{(2)}_\ell\).
Question: Using Figure 4 and the chain rules from Section 3.3 and Section 3.4, derive the partial derivative of the loss with respect to \(W^{(1)}_{2,3}\).
Answer:
We present the derivation in three steps.
Step 1. Partial derivative of \(\mathcal{L}\) with respect to \(a^{(1)}_2\) (first fan-out, multivariate chain rule):
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial a^{(1)}_2} = \sum_{\ell=1}^{D^{(2)}} \frac{\partial \mathcal{L}}{\partial z^{(2)}_\ell} \cdot W^{(2)}_{\ell,2}. \end{aligned} \]
Step 2. Partial derivative of \(\mathcal{L}\) with respect to \(z^{(2)}_\ell\) and \(a^{(2)}_\ell\) (second fan-out, multivariate chain rule):
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial a^{(2)}_\ell} & = \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial z^{(3)}_n} \cdot W^{(3)}_{n,\ell}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial z^{(2)}_\ell} & = \frac{\partial \mathcal{L}}{\partial a^{(2)}_\ell} \cdot f^{(2)\prime}\!\bigl(z^{(2)}_\ell\bigr) \\[0.5em] & = \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial z^{(3)}_n} \cdot W^{(3)}_{n,\ell} \cdot f^{(2)\prime}\!\bigl(z^{(2)}_\ell\bigr). \end{aligned} \]
Step 3. Full gradient with respect to \(W^{(1)}_{2,3}\):
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial W^{(1)}_{2,3}} = \left[\, \sum_{\ell=1}^{D^{(2)}} \left( \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial z^{(3)}_n} \cdot W^{(3)}_{n,\ell} \right) f^{(2)\prime}\!\bigl(z^{(2)}_\ell\bigr) \cdot W^{(2)}_{\ell,2} \,\right] \;\cdot\; f^{(1)\prime}\!\bigl(z^{(1)}_2\bigr) \;\cdot\; a^{(0)}_3. \end{aligned} \]
3.6 Comparing the Three Gradients
Placing the three gradients side by side reveals redundant work in the naive approach. To make the comparison easier, we index the output units by \(n\) and the units in hidden layer 2 by \(\ell\) in all three expressions:
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial W^{(3)}_{1,2}} & = \frac{\partial \mathcal{L}}{\partial a^{(3)}_1} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_1\bigr) \cdot a^{(2)}_2, \\[1em] \frac{\partial \mathcal{L}}{\partial W^{(2)}_{3,4}} & = \left(\, \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial a^{(3)}_n} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_n\bigr) \cdot W^{(3)}_{n,3} \right) \cdot f^{(2)\prime}\!\bigl(z^{(2)}_3\bigr) \cdot a^{(1)}_4, \\[1em] \frac{\partial \mathcal{L}}{\partial W^{(1)}_{2,3}} & = \left[\, \sum_{\ell=1}^{D^{(2)}} \left(\, \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial a^{(3)}_n} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_n\bigr) \cdot W^{(3)}_{n,\ell} \right) \cdot f^{(2)\prime}\!\bigl(z^{(2)}_\ell\bigr) \cdot W^{(2)}_{\ell,2} \,\right] \cdot f^{(1)\prime}\!\bigl(z^{(1)}_2\bigr) \cdot a^{(0)}_3. \end{aligned} \]
Two intermediate quantities appear repeatedly in these expressions. The first is the partial derivative of the loss with respect to each output pre-activation:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(3)}_n} = \frac{\partial \mathcal{L}}{\partial a^{(3)}_n} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_n\bigr). \end{aligned} \]
This product appears in all three gradients, with \(n = 1\) in the layer-3 gradient. Within the layer-1 gradient, it is recomputed for every hidden unit \(\ell\) in layer 2, that is, \(D^{(2)}\) times, even though it does not depend on \(\ell\). The second quantity is the partial derivative of the loss with respect to each layer-2 activation:
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial a^{(2)}_\ell} = \sum_{n=1}^{D^{(3)}} \frac{\partial \mathcal{L}}{\partial a^{(3)}_n} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_n\bigr) \cdot W^{(3)}_{n,\ell}. \end{aligned} \]
This sum appears in parentheses in both the layer-2 gradient, with \(\ell = 3\), and the layer-1 gradient, for every \(\ell\). Because the naive approach computes each gradient independently, both quantities are recomputed from scratch wherever they appear.
In the next section, we will eliminate this redundancy by computing each intermediate quantity once, storing it, and reusing it whenever another gradient needs it. The order of computation will matter. We will start at the loss and work backward, first computing the partial derivatives with respect to the output pre-activations, then using them to compute the partial derivatives with respect to the layer-2 activations, and continuing towards the input. Each weight gradient will then require only a few multiplications involving stored values. We will develop this idea into a systematic procedure.
4 Computing Gradients Efficiently
The three worked examples share overlapping subproblems, and solving them in the right order eliminates the redundancy. The layer-2 gradient reuses the partial derivatives with respect to the output pre-activations from the layer-3 gradient. In turn, the layer-1 gradient reuses the partial derivatives with respect to the layer-2 activations from the layer-2 gradient. Working from the output layer towards the input makes each result a building block for the next, so we obtain every gradient in one backward pass through the computation graph.
Definition: A backward pass is a traversal of the computation graph that starts at the loss \(\mathcal{L}\) and applies the chain rule in the direction opposite to the forward pass.
Computing the gradients in a backward pass is an instance of a general algorithmic technique.
Definition: Dynamic programming is a technique that breaks a problem into overlapping subproblems, solves each subproblem once in an order where its dependencies are solved first, and stores each result for reuse.
Interactive vectorized computation graph
Figure 5 gives a compact view of the entire computation graph. Each node groups one layer’s scalar quantities into a vector or matrix, and the arrows follow the forward computations. In backpropagation, the subproblem at each node is the partial derivative of \(\mathcal{L}\) with respect to that node’s quantity. The backward pass starts at the loss on the right and works towards the weights on the left. At every step, it adds one more component to the chain rule product, namely the local derivative of the node it has just reached.
Whenever the backward pass reaches the pre-activation vector \(\mathbf{z}^{(m)}\) of a layer, it pauses to derive the gradients with respect to that layer’s weights and biases. The gradient with respect to a weight \(W^{(m)}_{j,k}\) is the stored partial derivative of \(\mathcal{L}\) with respect to \(z^{(m)}_j\) multiplied by the activation \(a^{(m-1)}_k\). The gradient with respect to a bias \(b^{(m)}_j\) is the stored partial derivative alone, since the partial derivative of \(z^{(m)}_j\) with respect to \(b^{(m)}_j\) is 1. The backward pass then continues through \(\mathbf{a}^{(m-1)}\) to the pre-activations \(\mathbf{z}^{(m-1)}\) in the previous layer, reusing the stored derivatives along the way. One backward pass therefore produces the gradients for every layer with no redundant computation.
5 Backpropagation for a 3-Layer Network
Let’s consider our 3-layer network again and go through the process of computing all the gradients using one backward pass through the computation graph. We will complete the following steps, in order:
Compute gradients for the output layer weights.
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z^{(3)}_j} &= ?, && j = 1, \ldots, D^{(3)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial W^{(3)}_{j,k}} &= ?, && j = 1, \ldots, D^{(3)},\; k = 1, \ldots, D^{(2)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial b^{(3)}_j} &= ?, && j = 1, \ldots, D^{(3)}. \end{aligned} \]
Compute gradients for hidden layer 2 weights.
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z^{(2)}_j} &= ?, && j = 1, \ldots, D^{(2)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial W^{(2)}_{j,k}} &= ?, && j = 1, \ldots, D^{(2)},\; k = 1, \ldots, D^{(1)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial b^{(2)}_j} &= ?, && j = 1, \ldots, D^{(2)}. \end{aligned} \]
Compute gradients for hidden layer 1 weights.
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z^{(1)}_j} &= ?, && j = 1, \ldots, D^{(1)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial W^{(1)}_{j,k}} &= ?, && j = 1, \ldots, D^{(1)},\; k = 1, \ldots, D^{(0)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial b^{(1)}_j} &= ?, && j = 1, \ldots, D^{(1)}. \end{aligned} \]
We fill in each step below, working backward from the loss.
5.1 Computing Gradients for the Output Layer
We begin at the output layer, where the loss is defined, and then work backward towards the inputs. The derivative of the loss with respect to each output activation \(a^{(3)}_j\) is determined by our choice of loss function. Next, we apply the chain rule to compute the derivative with respect to the pre-activation \(z^{(3)}_j\), multiplying by the derivative of the non-linearity. We store this partial derivative at each unit \(j\) and reuse this intermediate value in the next step. With the derivative with respect to the pre-activation in hand, the weight and bias gradients are immediate. Figure 6 highlights the output-layer nodes in the vectorized graph.
\[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial z^{(3)}_j} &= \frac{\partial \mathcal{L}}{\partial a^{(3)}_j} \cdot f^{(3)\prime}\!\bigl(z^{(3)}_j\bigr), && j = 1, \ldots, D^{(3)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial W^{(3)}_{j,k}} &= \frac{\partial \mathcal{L}}{\partial z^{(3)}_j} \cdot a^{(2)}_k, && j = 1, \ldots, D^{(3)},\; k = 1, \ldots, D^{(2)}, \\[0.5em] \frac{\partial \mathcal{L}}{\partial b^{(3)}_j} &= \frac{\partial \mathcal{L}}{\partial z^{(3)}_j}, && j = 1, \ldots, D^{(3)}. \end{aligned} \]
Output-layer backpropagation nodes
6 The Backpropagation Algorithm
Generalizing the equations we derived for the 3-layer network gives the backward pass equations for an \(M\)-layer network.
Definition: The backward pass equations (non-vectorized) for an \(M\)-layer network compute the gradients of the loss \(\mathcal{L}\) in the following steps.
Compute the gradients for the output layer.
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(M)}_j} = \frac{\partial \mathcal{L}}{\partial a^{(M)}_j} \cdot f^{(M)\prime}\!\bigl(z^{(M)}_j\bigr), \qquad j = 1, \ldots, D^{(M)}. \end{aligned} \]
Compute the gradients for each hidden layer recursively.
For each layer \(m = M-1, \ldots, 1\),
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(m)}_j} = \left( \sum_{\ell=1}^{D^{(m+1)}} \frac{\partial \mathcal{L}}{\partial z^{(m+1)}_\ell} \cdot W^{(m+1)}_{\ell,j} \right) \cdot f^{(m)\prime}\!\bigl(z^{(m)}_j\bigr), \qquad j = 1, \ldots, D^{(m)}. \end{aligned} \]
Compute the gradients for the weights and biases for each layer.
For each layer \(m = M, \ldots, 1\),
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial W^{(m)}_{j,k}} = \frac{\partial \mathcal{L}}{\partial z^{(m)}_j} \cdot a^{(m-1)}_k, && j = 1, \ldots, D^{(m)},\; k = 1, \ldots, D^{(m-1)}, \\ & \frac{\partial \mathcal{L}}{\partial b^{(m)}_j} = \frac{\partial \mathcal{L}}{\partial z^{(m)}_j}, && j = 1, \ldots, D^{(m)}. \end{aligned} \]
6.1 Why Do We Need the Forward Pass?
Look back at the backward pass equations above. Besides the gradients that the backward pass computes along the way, these equations use several other quantities. They include the derivative of the loss, the derivative of each activation function, the weights, the pre-activations, and the activations from each layer. Before we can carry out the backward pass, we need to know where each of these quantities comes from.
Question: Which quantities in the equations above can be prepared before we see a particular input, and which ones depend on the input? Use your answer to explain why the backward pass must be preceded by a forward pass.
Answer:
Three quantities can be prepared in advance. The derivative of the loss with respect to each output activation \(a^{(M)}_j\) is determined once we fix the loss function. The derivative of the non-linearity with respect to each pre-activation \(z^{(m)}_j\) is determined once we fix the activation function for each layer. The weight matrices \(W^{(m)}\) are the quantities backpropagation exists to update, so we always keep track of them.
The activation \(a^{(m-1)}_k\) from the previous layer, which appears in the gradient formula for each weight matrix, cannot be prepared in advance. These activations depend on the specific input, so they differ for every training example.
Fixing the activation function only fixes the form of its derivative, not its value. To evaluate \(f^{(m)\prime}\!\bigl(z^{(m)}_j\bigr)\), we need the value of the pre-activation \(z^{(m)}_j\), which depends on the input. Therefore, the pre-activations must also be available before the backward pass.
This is why the backward pass must be preceded by a forward pass. The forward pass computes and stores the pre-activations and activations at each layer, making them available when the backward pass needs them.
The forward pass computes these input-dependent quantities layer by layer, starting from the input \(\mathbf{a}^{(0)}\).
Definition: The forward pass equations (non-vectorized) for an \(M\)-layer network compute the pre-activations, the activations, and the loss \(\mathcal{L}\) in the following steps.
Compute the pre-activations and activations for each layer.
For each layer \(m = 1, \ldots, M\),
\[ \begin{aligned} & z^{(m)}_j = \sum_{k=1}^{D^{(m-1)}} W^{(m)}_{j,k} \, a^{(m-1)}_k + b^{(m)}_j, && j = 1, \ldots, D^{(m)}, \\ & a^{(m)}_j = f^{(m)}\!\bigl(z^{(m)}_j\bigr), && j = 1, \ldots, D^{(m)}. \end{aligned} \]
Compute the loss.
\[ \begin{aligned} & \mathcal{L} = \mathcal{L}\!\bigl(\mathbf{a}^{(M)}, \mathbf{t}\bigr) \end{aligned} \]
Combining the forward pass, the backward pass, and a gradient descent update gives the complete backpropagation algorithm.
Definition: The backpropagation algorithm (non-vectorized) for an \(M\)-layer network updates the weights and biases for one data point in the following steps.
Perform the forward pass. Compute and store the pre-activations and activations for each layer using the forward pass equations.
Perform the backward pass. Compute the gradients for the weights and biases for each layer using the backward pass equations.
Update the weights and biases through gradient descent.
For each layer \(m = M, \ldots, 1\),
\[ \begin{aligned} & W^{(m)}_{j,k} \leftarrow W^{(m)}_{j,k} - \alpha \cdot \frac{\partial \mathcal{L}}{\partial W^{(m)}_{j,k}}, && j = 1, \ldots, D^{(m)},\; k = 1, \ldots, D^{(m-1)}, \\ & b^{(m)}_j \leftarrow b^{(m)}_j - \alpha \cdot \frac{\partial \mathcal{L}}{\partial b^{(m)}_j}, && j = 1, \ldots, D^{(m)}. \end{aligned} \]
Here, \(\alpha\) is a positive learning rate.
7 Vectorizing the Backpropagation Algorithm
In practice, we will vectorize the backpropagation algorithm to improve efficiency. There are two levels of vectorization. The first level handles one data point. It treats the pre-activations, activations, and biases of each layer as vectors and the weights as matrices, so that the computations become matrix and vector operations. The second level handles a batch of data points at once by stacking their vectors into matrices. Implementations of backpropagation typically use both levels. In this section, we focus on the first level only.
We will present a few exercises to guide you through the vectorization process. Vectorization is a skill that requires considerable practice and experience. We encourage you to take advantage of this great opportunity to practise your vectorization skills.
7.1 Vectorizing the Forward Pass
Let’s start with the forward pass. How would you vectorize the following equation to compute the pre-activations \(\mathbf{z}^{(m)}\) for each layer \(m\)?
Question: What is the vectorized expression for the following equation to compute the pre-activations \(\mathbf{z}^{(m)}\) for each layer \(m\)?
\[ \begin{aligned} & z^{(m)}_j = \sum_{k=1}^{D^{(m-1)}} W^{(m)}_{j,k} \, a^{(m-1)}_k + b^{(m)}_j, \qquad j = 1, \ldots, D^{(m)}. \end{aligned} \]
- \(\mathbf{z}^{(m)} = (\mathbf{W}^{(m)})^\top \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}\)
- \(\mathbf{z}^{(m)} = (\mathbf{a}^{(m-1)})^\top \mathbf{W}^{(m)} + \mathbf{b}^{(m)}\)
- \(\mathbf{z}^{(m)} = \mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}\)
- \(\mathbf{z}^{(m)} = \mathbf{a}^{(m-1)} \mathbf{W}^{(m)} + \mathbf{b}^{(m)}\)
Answer:
The correct answer is (C).
The weight matrix \(\mathbf{W}^{(m)}\) has shape \(D^{(m)} \times D^{(m-1)}\), and the activation vector \(\mathbf{a}^{(m-1)}\) has \(D^{(m-1)}\) entries. The weighted sum \(\mathbf{z}^{(m)}\) is expected to have \(D^{(m)}\) entries. Therefore, the correct way of multiplying them together is \(\mathbf{W}^{(m)} \mathbf{a}^{(m-1)}\). Adding the bias vector \(\mathbf{b}^{(m)}\), which has \(D^{(m)}\) entries, gives the final vectorized expression:
\[ \begin{aligned} & \mathbf{z}^{(m)} = \mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}. \end{aligned} \]
We summarize the vectorized forward pass in Section 7.3, so that you can make a genuine attempt before seeing the solutions.
7.2 Vectorizing the Backward Pass
We are now ready to vectorize the backward pass. First, we will consider the step of computing the gradients for the output layer. How would you vectorize the following equation to compute the gradients of the loss with respect to the pre-activations \(\mathbf{z}^{(M)}\) in the output layer?
Question: What is the vectorized expression for the following equation to compute the gradients of the loss with respect to the pre-activations \(\mathbf{z}^{(M)}\) in the output layer?
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(M)}_j} = \frac{\partial \mathcal{L}}{\partial a^{(M)}_j} \cdot f^{(M)\prime}\!\bigl(z^{(M)}_j\bigr), \qquad j = 1, \ldots, D^{(M)}. \end{aligned} \]
In the choices below, \(\odot\) denotes the element-wise product (also called the Hadamard product), which multiplies two vectors of the same length entry by entry.
- \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (\nabla_{\mathbf{a}^{(M)}} \mathcal{L})^\top (f^{(M)\prime}(\mathbf{z}^{(M)}))\)
- \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (f^{(M)\prime}(\mathbf{z}^{(M)}))^\top (\nabla_{\mathbf{a}^{(M)}} \mathcal{L})\)
- \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (\nabla_{\mathbf{a}^{(M)}} \mathcal{L}) \odot (f^{(M)\prime}(\mathbf{z}^{(M)}))\)
- \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (f^{(M)\prime}(\mathbf{z}^{(M)})) (\nabla_{\mathbf{a}^{(M)}} \mathcal{L})^\top\)
- \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (\nabla_{\mathbf{a}^{(M)}} \mathcal{L}) (f^{(M)\prime}(\mathbf{z}^{(M)}))^\top\)
Answer:
The correct answer is (C).
The gradient of the loss with respect to the activations, \(\nabla_{\mathbf{a}^{(M)}} \mathcal{L}\), is a vector of length \(D^{(M)}\). The derivative of the activation function, \(f^{(M)\prime}(\mathbf{z}^{(M)})\), is also a vector of length \(D^{(M)}\). The result \(\nabla_{\mathbf{z}^{(M)}} \mathcal{L}\) is a vector of length \(D^{(M)}\) as well. Because each index \(j\) contributes independently, the correct combination is the element-wise product:
\[ \begin{aligned} & \nabla_{\mathbf{z}^{(M)}} \mathcal{L} = \nabla_{\mathbf{a}^{(M)}} \mathcal{L} \odot f^{(M)\prime}(\mathbf{z}^{(M)}). \end{aligned} \]
Next, we will consider the step of computing the gradients with respect to the pre-activations \(\mathbf{z}^{(m)}\) in the hidden layers. How would you vectorize the following equation to compute the gradients of the loss with respect to the pre-activations \(\mathbf{z}^{(m)}\) in the hidden layers?
Question: The hidden-layer pre-activation gradient satisfies
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial z^{(m)}_j} = \left( \sum_{\ell=1}^{D^{(m+1)}} \frac{\partial \mathcal{L}}{\partial z^{(m+1)}_\ell} \cdot W^{(m+1)}_{\ell,j} \right) \cdot f^{(m)\prime}\!\bigl(z^{(m)}_j\bigr), \qquad j = 1, \ldots, D^{(m)}. \end{aligned} \]
What is the vectorized expression for the weighted sum in parentheses?
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial a^{(m)}_j} = \sum_{\ell=1}^{D^{(m+1)}} \frac{\partial \mathcal{L}}{\partial z^{(m+1)}_\ell} \cdot W^{(m+1)}_{\ell,j}, \qquad j = 1, \ldots, D^{(m)}. \end{aligned} \]
- \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L})^\top (\mathbf{W}^{(m+1)})^\top\)
- \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L} = (\mathbf{W}^{(m+1)})^\top (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L})\)
- \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}) \odot (\mathbf{W}^{(m+1)})^\top\)
- \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L} = \mathbf{W}^{(m+1)} (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L})\)
- \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}) (\mathbf{W}^{(m+1)})^\top\)
Answer:
The correct answer is (B).
The weight matrix \(\mathbf{W}^{(m+1)}\) has shape \(D^{(m+1)} \times D^{(m)}\). The gradient of the loss with respect to the pre-activations, \(\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}\), is a vector of length \(D^{(m+1)}\). The result is the gradient of the loss with respect to the activations, \(\nabla_{\mathbf{a}^{(m)}} \mathcal{L}\), which is expected to be a vector of length \(D^{(m)}\). Therefore, the correct way of multiplying the matrix and the vector together is:
\[ \begin{aligned} & \nabla_{\mathbf{a}^{(m)}} \mathcal{L} = (\mathbf{W}^{(m+1)})^\top (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}). \end{aligned} \]
In a previous exercise, we vectorized the equation for the output-layer pre-activations \(\mathbf{z}^{(M)}\). The resulting expression uses the element-wise product to multiply by the derivative of the activation function.
Putting it together, the vectorized expression for the gradients of the loss with respect to the pre-activations \(\mathbf{z}^{(m)}\) in the hidden layers is:
\[ \begin{aligned} & \nabla_{\mathbf{z}^{(m)}} \mathcal{L} = (\mathbf{W}^{(m+1)})^\top (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}) \odot f^{(m)\prime}(\mathbf{z}^{(m)}). \end{aligned} \]
Finally, how would you vectorize the following equation to compute the gradients of the loss with respect to the weight matrix \(\mathbf{W}^{(m)}\) for each layer \(m\)?
Question: What is the vectorized expression for the following equation to compute the gradients of the loss with respect to the weight matrix \(\mathbf{W}^{(m)}\) for each layer \(m\)?
\[ \begin{aligned} & \frac{\partial \mathcal{L}}{\partial W^{(m)}_{j,k}} = \frac{\partial \mathcal{L}}{\partial z^{(m)}_j} \cdot a^{(m-1)}_k, \qquad j = 1, \ldots, D^{(m)},\; k = 1, \ldots, D^{(m-1)}. \end{aligned} \]
- \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m)}} \mathcal{L})^\top (\mathbf{a}^{(m-1)})\)
- \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\mathbf{a}^{(m-1)})^\top (\nabla_{\mathbf{z}^{(m)}} \mathcal{L})\)
- \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m)}} \mathcal{L}) \odot (\mathbf{a}^{(m-1)})\)
- \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\mathbf{a}^{(m-1)}) (\nabla_{\mathbf{z}^{(m)}} \mathcal{L})^\top\)
- \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m)}} \mathcal{L}) (\mathbf{a}^{(m-1)})^\top\)
Answer:
The correct answer is (E).
The gradient of the loss with respect to the pre-activations, \(\nabla_{\mathbf{z}^{(m)}} \mathcal{L}\), is a vector of length \(D^{(m)}\). The activations \(\mathbf{a}^{(m-1)}\) form a vector of length \(D^{(m-1)}\). The result \(\nabla_{\mathbf{W}^{(m)}} \mathcal{L}\) is expected to have shape \(D^{(m)} \times D^{(m-1)}\). We want to produce a matrix using two vectors, and a natural way to do this is to use the outer product. Therefore, the correct way of multiplying them together is:
\[ \begin{aligned} & \nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m)}} \mathcal{L}) (\mathbf{a}^{(m-1)})^\top. \end{aligned} \]
It is interesting to note that, although the backpropagation algorithm only has a handful of formulas, the vectorization of these formulas requires us to use all the different operations. These are the matrix-vector product, the element-wise product (or Hadamard product), and the outer product. This is therefore an excellent exercise to practise your vectorization skills.
7.3 Summary of the Vectorized Backpropagation
Combining the results of the exercises above gives the vectorized forward pass and backward pass equations.
Definition: The forward pass equations (vectorized) for an \(M\)-layer network compute the pre-activations, the activations, and the loss \(\mathcal{L}\) in the following steps.
Compute the pre-activations and activations for each layer.
For each layer \(m = 1, \ldots, M\),
\[ \begin{aligned} & \mathbf{z}^{(m)} = \mathbf{W}^{(m)} \mathbf{a}^{(m-1)} + \mathbf{b}^{(m)}, \\ & \mathbf{a}^{(m)} = f^{(m)}(\mathbf{z}^{(m)}). \end{aligned} \]
Compute the loss.
\[ \begin{aligned} & \mathcal{L} = \mathcal{L}\!\bigl(\mathbf{a}^{(M)}, \mathbf{t}\bigr) \end{aligned} \]
Definition: The backward pass equations (vectorized) for an \(M\)-layer network compute the gradients of the loss \(\mathcal{L}\) in the following steps.
Compute the gradients for the output layer.
\[ \begin{aligned} & \nabla_{\mathbf{z}^{(M)}} \mathcal{L} = (\nabla_{\mathbf{a}^{(M)}} \mathcal{L}) \odot f^{(M)\prime}(\mathbf{z}^{(M)}). \end{aligned} \]
Compute the gradients for each hidden layer recursively.
For each layer \(m = M-1, \ldots, 1\),
\[ \begin{aligned} & \nabla_{\mathbf{z}^{(m)}} \mathcal{L} = (\mathbf{W}^{(m+1)})^\top (\nabla_{\mathbf{z}^{(m+1)}} \mathcal{L}) \odot f^{(m)\prime}(\mathbf{z}^{(m)}). \end{aligned} \]
Compute the gradients for the weights and biases for each layer.
For each layer \(m = M, \ldots, 1\),
\[ \begin{aligned} & \nabla_{\mathbf{W}^{(m)}} \mathcal{L} = (\nabla_{\mathbf{z}^{(m)}} \mathcal{L}) (\mathbf{a}^{(m-1)})^\top, \\ & \nabla_{\mathbf{b}^{(m)}} \mathcal{L} = \nabla_{\mathbf{z}^{(m)}} \mathcal{L}. \end{aligned} \]
We can vectorize these equations further to process a batch of data points at once. Doing so requires new notation for the batch dimension, so we leave this extension as an exercise for you.
8 Summary
Backpropagation makes large-scale neural network training feasible. The key insight is dynamic programming. Instead of recomputing each gradient from scratch, the backward pass stores intermediate derivatives at every pre-activation node and reuses them for all weights feeding into that node. One backward pass produces every weight and bias gradient simultaneously. It costs a small constant multiple of one forward pass (about twice as much), instead of one forward pass per parameter.
This chapter illustrates Fundamental Idea #1 (learning is optimization). Training a neural network means minimizing the cost over millions of weights and biases with gradient descent, and backpropagation supplies the gradients that every update step needs. The chapter also shows that how we solve an optimization problem matters, not only how we set it up. The naive approach and backpropagation produce exactly the same gradients. However, the naive approach recomputes the same intermediate derivatives many times and is far too slow for large networks. Backpropagation makes each gradient descent step cheap enough to be practical.
This chapter is also different from the other optimization topics in the course. Most of those ideas are geometric and continuous, such as following the direction of steepest descent on the cost surface. Backpropagation is instead a discrete, algorithmic idea that takes its inspiration from algorithm design. It organizes the chain rule computations so that each overlapping subproblem is solved exactly once.