# Backpropagation *Chapter 7 · Gradients and initialization* Chapter 6 introduced iterative optimization algorithms. These are general-purpose methods for finding the minimum of a function. In the context of neural networks, they find parameters that minimize the loss so that the model accurately predicts the training outputs from the inputs. The basic approach is to choose initial parameters randomly and then make a series of small changes that decrease the loss on average. Each change is based on the gradient of the loss with respect to the parameters at the current position. This chapter discusses two issues that are specific to neural networks. First, we consider how to calculate the gradients efficiently. This is a serious challenge since the largest models at the time of writing have ∼10 12 parameters, and the gradient needs to be computed for every parameter at every iteration of the training algorithm. Second, we consider how to initialize the parameters. If this is not done carefully, the initial losses and their gradients can be extremely large or small. In either case, this impedes the training process. ## 7.1 Problem definitions Consider a network f[x, ϕ] with multivariate input x, parameters ϕ, and three hidden layers h 1 , h 2 , and h 3 : where the function a[•] applies the activation function separately to every element of the input. The model parameters ϕ = {β 0 , Ω 0 , β 1 , Ω 1 , β 2 , Ω 2 , β 3 , Ω 3 } consist of the bias vectors β k and weight matrices Ω k between every layer (figure 7.1). $$ \begin{aligned}h_1&=a[\beta_0+\Omega_0x]\\h_2&=a[\beta_1+\Omega_1h_1]\\h_3&=a[\beta_2+\Omega_2h_2]\\f[x,\phi]&=\beta_3+\Omega_3h_3\end{aligned} $$ Equation (7.1) ### Figure 1: One network. Two directions. Activations travel towards the prediction. Gradients travel back from the loss. We also have individual loss terms ℓ i , which return the negative log-likelihood of the ground truth label y i given the model prediction f[x i , ϕ] for training input x i . For example, this might be the least squares loss ℓ i = (f[x i , ϕ] − y i ) 2 . The total loss is the sum of these terms over the training data: i=1 The most commonly used optimization algorithm for training neural networks is stochastic gradient descent (SGD), which updates the parameters as: $$ L[\phi]=\sum_{i=1}^{I}\ell_i $$ Equation (7.2) i∈B t where α is the learning rate, and B t contains the batch indices at iteration t. To compute this update, we need to calculate the derivatives: ∂ℓ i ∂β k and ∂ℓ i , ∂Ω k (7.4) for the parameters {β k , Ω k } at every layer k ∈ {0, 1, . . . , K} and for each index i in the batch. The first part of this chapter describes the backpropagation algorithm, which computes these derivatives efficiently. In the second part of the chapter, we consider how to initialize the network parameters $$ \phi_{t+1}\leftarrow\phi_t-\alpha\sum_{i\in B_t}\frac{\partial\ell_i[\phi_t]}{\partial\phi} $$ Equation (7.3) before we commence training. We describe methods to choose the initial weights Ω k and biases β k so that training is stable. ## 7.2 Computing derivatives The derivatives of the loss tell us how the loss changes when we make a small change to the parameters. Optimization algorithms exploit this information to manipulate the parameters so that the loss becomes smaller. The backpropagation algorithm computes these derivatives. The mathematical details are somewhat involved, so we first make two observations that provide some intuition. Observation 1: Each weight (element of Ω k ) multiplies the activation at a source hidden unit and adds the result to a destination hidden unit in the next layer. It follows that the effect of any small change to the weight is amplified or attenuated by the activation at the source hidden unit. Hence, we run the network for each data example in the batch and store the activations of all the hidden units. This is known as the forward pass (figure 7.1). The stored activations will subsequently be used to compute the gradients. Observation 2: A small change in a bias or weight causes a ripple effect of changes through the subsequent network. The change modifies the value of its destination hidden Figure 7.1 Backpropagation forward pass. The goal is to compute the derivatives of the loss ℓ with respect to each of the weights (arrows) and biases (not shown). In other words, we want to know how a small change to each parameter will affect the loss. Each weight multiplies the hidden unit at its source and contributes the result to the hidden unit at its destination. Consequently, the effects of any small change to the weight will be scaled by the activation of the source hidden unit. For example, the blue weight is applied to the second hidden unit at layer 1; if the activation of this unit doubles, then the effect of a small change to the blue weight will double too. Hence, to compute the derivatives of the weights, we need to calculate and store the activations at the hidden layers. This is known as the forward pass since it involves running the network equations sequentially. unit. This, in turn, changes the values of the hidden units in the subsequent layer, which will change the hidden units in the layer after that, and so on, until a change is made to the model output and, finally, the loss. Hence, to know how changing a parameter modifies the loss, we also need to know how changes to every subsequent hidden layer will, in turn, modify their successor. These same quantities are required when considering other parameters in the same or earlier layers. It follows that we can calculate them once and reuse them. For example, consider computing the effect of a small change in weights that feed into hidden layers h 3 , h 2 , and h 1 , respectively: • To calculate how a small change in a weight or bias feeding into hidden layer h 3 modifies the loss, we need to know (i) how a change in layer h 3 changes the model output f , and (ii) how a change in this output changes the loss ℓ (figure 7.2a). • To calculate how a small change in a weight or bias feeding into hidden layer h 2 modifies the loss, we need to know (i) how a change in layer h 2 affects h 3 , (ii) how h 3 changes the model output, and (iii) how this output changes the loss (figure 7.2b). • To calculate how a small change in a weight or bias feeding into hidden layer h 1 modifies the loss, we need to know (i) how a change in layer h 1 affects layer h 2 , (ii) how a change in layer h 2 affects layer h 3 , (iii) how layer h 3 changes the model output, and (iv) how the model output changes the loss (figure 7.2c). Figure 7.2 Backpropagation backward pass. a) To compute how a change to a weight feeding into layer h 3 (blue arrow) changes the loss, we need to know how the hidden unit in h 3 changes the model output f and how f changes the loss (orange arrows). b) To compute how a small change to a weight feeding into h 2 (blue arrow) changes the loss, we need to know (i) how the hidden unit in h 2 changes h 3 , (ii) how h 3 changes f , and (iii) how f changes the loss (orange arrows). c) Similarly, to compute how a small change to a weight feeding into h 1 (blue arrow) changes the loss, we need to know how h 1 changes h 2 and how these changes propagate through to the loss (orange arrows). The backward pass first computes derivatives at the end of the network and then works backward to exploit the inherent redundancy of these computations. As we move backward through the network, we see that most of the terms we need were already calculated in the previous step, so we do not need to re-compute them. Proceeding backward through the network in this way to compute the derivatives is known as the backward pass. The ideas behind backpropagation are relatively easy to understand. However, the derivation requires matrix calculus because the bias and weight terms are vectors and matrices, respectively. To help grasp the underlying mechanics, the following section derives backpropagation for a simpler toy model with scalar parameters. We then apply the same approach to a deep neural network in section 7.4. ## 7.3 Toy example Consider a model f[x, ϕ] with eight scalar parameters ϕ = {β 0 , ω 0 , β 1 , ω 1 , β 2 , ω 2 , β 3 , ω 3 } that consists of a composition of the functions sin[•], exp[•], and cos[•]: $$ f[x,\phi]=\beta_3+\omega_3\cos\!\left[\beta_2+\omega_2\exp\!\left(\beta_1+\omega_1\sin[\beta_0+\omega_0x]\right)\right] $$ Equation (7.5) P and a least squares loss function L[ϕ] = i ℓ i with individual terms: ℓ i = (f[x i , ϕ] − y i ) 2 , th th where, as usual, x i is the i training input, and y i is the i training output. You can think of this as a simple neural network with one input, one output, one hidden unit at each layer, and different activation functions sin[•], exp[•], and cos[•] between each layer. We aim to compute the derivatives: $$ \ell_i=(f[x_i,\phi]-y_i)^2 $$ Equation (7.6) ∂ℓ i , ∂β 0 ∂ℓ i , ∂ω 0 ∂ℓ i , ∂β 1 ∂ℓ i , ∂ω 1 ∂ℓ i , ∂β 2 ∂ℓ i , ∂ω 2 ∂ℓ i , ∂β 3 and ∂ℓ i . ∂ω 3 Of course, we could find expressions for these derivatives by hand and compute them directly. However, some of these expressions are quite complex. For example: i · sin β 2 + ω 2 · exp β 1 + ω 1 · sin[β 0 + ω 0 · x i ] . (7.7) Such expressions are awkward to derive and code without mistakes and do not exploit the inherent redundancy; notice that the three exponential terms are the same. The backpropagation algorithm is an efficient method for computing all of these derivatives at once. It consists of (i) a forward pass, in which we compute and store a series of intermediate values and the network output, and (ii) a backward pass, in which Figure 7.3 Backpropagation forward pass. We compute and store each of the intermediate variables in turn until we finally calculate the loss. we calculate the derivatives of each parameter, starting at the end of the network, and reusing previous calculations as we move toward the start. Forward pass: We treat the computation of the loss as a series of calculations: We compute and store the values of the intermediate variables f k and h k (figure 7.3). Backward pass #1: We now compute the derivatives of ℓ i with respect to these intermediate variables, but in reverse order: $$ \begin{aligned}f_0&=\beta_0+\omega_0x_i\\h_1&=\sin[f_0]\\f_1&=\beta_1+\omega_1h_1\\h_2&=\exp[f_1]\\f_2&=\beta_2+\omega_2h_2\\h_3&=\cos[f_2]\\f_3&=\beta_3+\omega_3h_3\\\ell_i&=(f_3-y_i)^2\end{aligned} $$ Equation (7.8) ### Figure 2: Follow the gradient. The chapter's sin → exp → cos toy network, with values you can change. The first of these derivatives is straightforward: ∂ℓ i $$ \frac{\partial\ell_i}{\partial f_3},\;\frac{\partial\ell_i}{\partial h_3},\;\frac{\partial\ell_i}{\partial f_2},\;\frac{\partial\ell_i}{\partial h_2},\;\frac{\partial\ell_i}{\partial f_1},\;\frac{\partial\ell_i}{\partial h_1},\;\frac{\partial\ell_i}{\partial f_0} $$ Equation (7.9) The next derivative can be calculated using the chain rule: ∂ℓ i ∂f 3 ∂ℓ i = . ∂h 3 ∂h 3 ∂f 3 (7.11) The left-hand side asks how ℓ i changes when h 3 changes. The right-hand side says we can decompose this into (i) how f 3 changes when h 3 changes and (ii) how ℓ i changes when f 3 changes. In the original equations, h 3 changes f 3 , which changes ℓ i , and the derivatives $$ \frac{\partial\ell_i}{\partial f_3}=2(f_3-y_i) $$ Equation (7.10) $$ \frac{\partial\ell_i}{\partial h_3}=\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3} $$ Equation (7.11) Figure 7.4 Backpropagation backward pass #1. We work backward from the end of the function computing the derivatives ∂ℓ i /∂f • and ∂ℓ i /∂h • of the loss with respect to the intermediate quantities. Each derivative is computed from the previous one by multiplying by terms of the form ∂f k /∂h k or ∂h k /∂f k−1 . represent the effects of this chain. Notice that we already computed the second of these derivatives, and the other is the derivative of β 3 + ω 3 · h 3 with respect to h 3 , which is ω 3 . We continue in this way, computing the derivatives of the output with respect to these intermediate quantities (figure 7.4): $$ \frac{\partial\ell_i}{\partial f_2}=\frac{\partial h_3}{\partial f_2}\left(\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3}\right)\quad\cdots\quad\frac{\partial\ell_i}{\partial f_0}=\frac{\partial h_1}{\partial f_0}\left(\frac{\partial f_1}{\partial h_1}\frac{\partial h_2}{\partial f_1}\frac{\partial f_2}{\partial h_2}\frac{\partial h_3}{\partial f_2}\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3}\right) $$ Equation (7.12) In each case, we have already computed the quantities in the brackets in the previous step, and the last term has a simple expression. These equations embody Observation 2 from the previous section (figure 7.2); we can reuse the previously computed derivatives if we calculate them in reverse order. Backward pass #2: Finally, we consider how the loss ℓ i changes when we change the parameters β • and ω • . Once more, we apply the chain rule (figure 7.5): In each case, the second term on the right-hand side was computed in equation 7.12. When k > 0, we have f k = β k + ω k · h k , so: $$ \frac{\partial\ell_i}{\partial\beta_k}=\frac{\partial f_k}{\partial\beta_k}\frac{\partial\ell_i}{\partial f_k},\qquad\frac{\partial\ell_i}{\partial\omega_k}=\frac{\partial f_k}{\partial\omega_k}\frac{\partial\ell_i}{\partial f_k} $$ Equation (7.13) $$ \frac{\partial f_k}{\partial\beta_k}=1,\qquad\frac{\partial f_k}{\partial\omega_k}=h_k $$ Equation (7.14) Figure 7.5 Backpropagation backward pass #2. Finally, we compute the derivatives ∂ℓ i /∂β • and ∂ℓ i /∂ω • . Each derivative is computed by multiplying the term ∂ℓ i /∂f k by ∂f k /∂β k or ∂f k /∂ω k as appropriate. This is consistent with Observation 1 from the previous section; the effect of a change in the weight ω k is proportional to the value of the source variable h k (which was stored in the forward pass). The final derivatives from the term f 0 = β 0 + ω · x i are: Backpropagation is both simpler and more efficient than computing the derivatives individually, as in equation 7.7. 1 $$ \frac{\partial f_0}{\partial\beta_0}=1,\qquad\frac{\partial f_0}{\partial\omega_0}=x_i $$ Equation (7.15) ## 7.4 Backpropagation algorithm Now we repeat this process for a three-layer network (figure 7.1). The intuition and much of the algebra are identical. The main differences are that intermediate variables f k , h k are vectors, the biases β k are vectors, the weights Ω k are matrices, and we are using ReLU functions rather than simple algebraic functions like cos[•]. Forward pass: We write the network as a series of sequential calculations: 1 Note that we did not actually need the derivatives ∂l /∂h of the loss with respect to the activations. i k In the final backpropagation algorithm, we will not compute these explicitly. $$ \begin{aligned}f_0&=\beta_0+\Omega_0x_i\\h_1&=a[f_0]\\f_1&=\beta_1+\Omega_1h_1\\h_2&=a[f_1]\\f_2&=\beta_2+\Omega_2h_2\\h_3&=a[f_2]\\f_3&=\beta_3+\Omega_3h_3\\\ell_i&=l[f_3,y_i]\end{aligned} $$ Equation (7.16) Figure 7.6 Derivative of rectified linear unit. The rectified linear unit (orange curve) returns zero when the input is less than zero and returns the input otherwise. Its derivative (cyan curve) returns zero when the input is less than zero (since the slope here is zero) and one when the input is greater than zero (since the slope here is one). where f k−1 represents the pre-activations at the k th hidden layer (i.e., the values before the ReLU function a[•]) and h k contains the activations at the k th hidden layer (i.e., after the ReLU function). The term l[f 3 , y i ] represents the loss function (e.g., least squares or binary cross-entropy loss). In the forward pass, we work through these calculations and store all the intermediate quantities. Appendix B.5 Matrix calculus Backward pass #1: Now let’s consider how the loss changes when we modify the preactivations f 0 , f 1 , f 2 . Applying the chain rule, the expression for the derivative of the loss ℓ i with respect to f 2 is: ∂ℓ i ∂h 3 ∂f 3 ∂ℓ i = . ∂f 2 ∂f 2 ∂h 3 ∂f 3 The three terms on the right-hand side have sizes D 3 × D 3 , D 3 × D f , and D f × 1, respectively, where D 3 is the number of hidden units in the third layer, and D f is the $$ \frac{\partial\ell_i}{\partial f_2}=\frac{\partial h_3}{\partial f_2}\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3} $$ Equation (7.17) dimensionality of the model output f 3 . Similarly, we can compute how the loss changes when we change f 1 and f 0 : $$ \frac{\partial\ell_i}{\partial f_1}=\frac{\partial h_2}{\partial f_1}\frac{\partial f_2}{\partial h_2}\left(\frac{\partial h_3}{\partial f_2}\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3}\right) $$ Equation (7.18) Note that in each case, the term in brackets was computed in the previous step. By working backward through the network, we can reuse the previous computations. Moreover, the terms themselves are simple. Working backward through the righthand side of equation 7.17, we have: • The derivative ∂ℓ i /∂f 3 of the loss ℓ i with respect to the network output f 3 will depend on the loss function but usually has a simple form. • The derivative ∂f 3 /∂h 3 of the network output with respect to hidden layer h 3 is: $$ \frac{\partial\ell_i}{\partial f_0}=\frac{\partial h_1}{\partial f_0}\frac{\partial f_1}{\partial h_1}\left(\frac{\partial h_2}{\partial f_1}\frac{\partial f_2}{\partial h_2}\frac{\partial h_3}{\partial f_2}\frac{\partial f_3}{\partial h_3}\frac{\partial\ell_i}{\partial f_3}\right) $$ Equation (7.19) If you are unfamiliar with matrix calculus, this result is not obvious. It is explored in problem 7.6. • The derivative ∂h 3 /∂f 2 of the output h 3 of the activation function with respect to its input f 2 will depend on the activation function. It will be a diagonal matrix since each activation only depends on the corresponding pre-activation. For ReLU functions, the diagonal terms are zero everywhere f 2 is less than zero and one otherwise (figure 7.6). Rather than multiply by this matrix, we extract the diagonal $$ \frac{\partial f_3}{\partial h_3}=\frac{\partial}{\partial h_3}(\beta_3+\Omega_3h_3)=\Omega_3^T $$ Equation (7.20) terms as a vector I[f 2 > 0] and pointwise multiply, which is more efficient. Problem 7.6 Problems 7.7–7.8 The terms on the right-hand side of equations 7.18 and 7.19 have similar forms. As we progress back through the network, we alternately (i) multiply by the transpose of the weight matrices Ω Tk and (ii) threshold based on the inputs f k−1 to the hidden layer. These inputs were stored during the forward pass. Backward pass #2: Now that we know how to compute ∂ℓ i /∂f k , we can focus on calculating the derivatives of the loss with respect to the weights and biases. To calculate the derivatives of the loss with respect to the biases β k , we again use the chain rule: which we already calculated in equations 7.17 and 7.18. Similarly, the derivative for the weights vector Ω k , is given by: $$ \frac{\partial\ell_i}{\partial\beta_k}=\frac{\partial\ell_i}{\partial f_k} $$ Equation (7.21) Again, the progression from line two to line three is not obvious and is explored in problem 7.9. However, the result makes sense. The final line is a matrix of the same size as Ω k . It depends linearly on h k , which was multiplied by Ω k in the original expression. This is also consistent with the initial intuition that the derivative of the weights in Ω k $$ \frac{\partial\ell_i}{\partial\Omega_k}=\frac{\partial\ell_i}{\partial f_k}h_k^T $$ Equation (7.22) will be proportional to the values of the hidden units h k that they multiply. Recall that we already computed these during the forward pass. ## 7.4.1 Backpropagation algorithm summary We now briefly summarize the final backpropagation algorithm. Consider a deep neural network f[x i , ϕ] that takes input x i , has K hidden layers with ReLU activations, and individual loss term ℓ i = l[f[x i , ϕ], y i ]. The goal of backpropagation is to compute the derivatives ∂ℓ i /∂β k and ∂ℓ i /∂Ω k with respect to the biases β k and weights Ω k . Forward pass: We compute and store the following quantities: Backward pass: We start with the derivative ∂ℓ i /∂f K of the loss function ℓ i with respect to the network output f K and work backward through the network: $$ \begin{aligned}f_0&=\beta_0+\Omega_0x_i\\h_k&=a[f_{k-1}]\\f_k&=\beta_k+\Omega_kh_k\end{aligned}\qquad k\in\{1,\ldots,K\} $$ Equation (7.23) where ⊙ denotes pointwise multiplication, and I[f k−1 > 0] is a vector containing ones where f k−1 is greater than zero and zeros elsewhere. Finally, we compute the derivatives with respect to the first set of biases and weights: $$ \begin{aligned}\frac{\partial\ell_i}{\partial\beta_k}&=\frac{\partial\ell_i}{\partial f_k}\\\frac{\partial\ell_i}{\partial\Omega_k}&=\frac{\partial\ell_i}{\partial f_k}h_k^T\\\frac{\partial\ell_i}{\partial f_{k-1}}&=\mathbb{I}[f_{k-1}>0]\odot\left(\Omega_k^T\frac{\partial\ell_i}{\partial f_k}\right)\end{aligned} $$ Equation (7.24) $$ \frac{\partial\ell_i}{\partial\beta_0}=\frac{\partial\ell_i}{\partial f_0},\qquad\frac{\partial\ell_i}{\partial\Omega_0}=\frac{\partial\ell_i}{\partial f_0}x_i^T $$ Equation (7.25) ∂Ω 0 ∂f 0 i We calculate these derivatives for every training example in the batch and sum them together to retrieve the gradient for the SGD update. Note that the backpropagation algorithm is extremely efficient; the most demanding computational step in both the forward and backward pass is matrix multiplication (by Ω and Ω T , respectively) which only requires additions and multiplications. However, it is not memory efficient; the intermediate values in the forward pass must all be stored, and this can limit the size of the model we can train. ## 7.4.2 Algorithmic differentiation Although it’s important to understand the backpropagation algorithm, it’s unlikely that you will need to code it in practice. Modern deep learning frameworks such as PyTorch and TensorFlow calculate the derivatives automatically, given the model specification. This is known as algorithmic differentiation. Each functional component (linear transform, ReLU activation, loss function) in the framework knows how to compute its own derivative. For example, the PyTorch ReLU function z out = relu[z in ] knows how to compute the derivative of its output z out with respect to its input z in . Similarly, a linear function z out = β + Ωz in knows how to compute the derivatives of the output z out with respect to the input z in and with respect to the parameters β and Ω. The algorithmic differentiation framework also knows the sequence of operations in the network and thus has all the information required to perform the forward and backward passes. These frameworks exploit the massive parallelism of modern graphics processing units (GPUs). Computations such as matrix multiplication (which features in both the forward and backward pass) are naturally amenable to parallelization. Moreover, it’s possible to perform the forward and backward passes for the entire batch in parallel if the model and intermediate results in the forward pass do not exceed the available memory. Since the training algorithm now processes the entire batch in parallel, the input becomes a multi-dimensional tensor. In this context, a tensor can be considered the generalization of a matrix to arbitrary dimensions. Hence, a vector is a 1D tensor, a matrix is a 2D tensor, and a 3D tensor is a 3D grid of numbers. Until now, the training data have been 1D, so the input for backpropagation would be a 2D tensor where the first dimension indexes the batch element and the second indexes the data dimension. In subsequent chapters, we will encounter more complex structured input data. For example, in models where the input is an RGB image, the original data examples are 3D (height × width × channel). Here, the input to the learning framework would be a 4D tensor, where the extra dimension indexes the batch element. Problem 7.11 ## 7.4.3 Extension to arbitrary computational graphs We have described backpropagation in a deep neural network that is naturally sequential; we calculate the intermediate quantities f 0 , h 1 , f 1 , h 2 . . . , f k in turn. However, models need not be restricted to sequential computation. Later in this book, we will meet models with branching structures. For example, we might take the values in a hidden layer and process them through two different sub-networks before recombining. Fortunately, the ideas of backpropagation still hold if the computational graph is acyclic. Modern algorithmic differentiation frameworks such as PyTorch and TensorFlow can handle arbitrary acyclic computational graphs.