Back-Propagation and Other Differentiation Algorithms

Computational graphs

Back-propagation is a way to compute gradients. It does not learn by itself. A learning algorithm such as stochastic gradient descent uses the gradient that back-propagation returns. In principle it computes derivatives of any function, and this chapter describes the common case of a single output. To describe it exactly, this chapter uses a computational graph. Each node holds one variable, which may be a number, a vector, a matrix or a tensor. A directed edge from one node to another means that the second variable is computed from the first by an operation. An operation is a simple function of one or more variables that returns one output. A complicated function is built by composing many operations.

The book's Figure 6.8 shows graphs for small expressions, such as and the logistic regression prediction. Panel (c) builds a rectifier layer on a minibatch of inputs, and every panel follows the same rule: one node for each operation and a name for each intermediate value. The logistic regression graph is a good example to work through, because it has intermediate variables that need names.

The graph below computes the output from the input , the weight and the bias . It names two intermediate values, and , and applies the logistic sigmoid at the end. The list of steps is written here for this page and is not printed in the book.

The chain rule

The chain rule of calculus differentiates a function built by composing functions whose derivatives are known. Back-propagation is an algorithm that applies the chain rule in one specific order, which is efficient for graphs with many nodes.

For a single variable, let and . The chain rule says that

When the variables are vectors, the derivative becomes a Jacobian: the matrix of all partial derivatives of the outputs with respect to the inputs. The gradient of with respect to is the Jacobian transposed times the gradient with respect to .

From this we see that the gradient of a variable can be obtained by multiplying a Jacobian by a gradient. Back-propagation performs one such product for each operation in the graph. The book writes the same idea for tensors in equation 6.47.

The example has , and . The demo multiplies the transposed Jacobian by the gradient on the output, as equation 6.46 says. It then checks the answer with a finite difference: the change in for a very small change in one input, divided by that change. The finite difference is added as a check and is not a step of the algorithm.

Shared work in a chain

Each node of a graph is computed from its parents. Equation 6.48 writes this for node i, where is the set of parents. Algorithm 6.1 computes the graph node by node, from the inputs to the output.

Back-propagation builds a second graph with one node for each node of the first, and runs it in the reverse order. The derivative of the output with respect to node is the sum, over the children of , of the derivative of the output with respect to times the derivative of with respect to .

Each edge is visited once, so the cost scales with the number of edges. The saving comes from sharing: a value that is needed twice is computed once and reused. Algorithm 6.2 keeps a table, grad_table, with one entry per node, and fills it from the output backwards.

A chain makes the sharing concrete. Figure 6.9 draws the graph of , which applies the same function three times. The chain rule gives the derivative as a product of three factors, and each factor is the derivative of at one of the intermediate values.

Equation 6.52 suggests computing each intermediate value once, storing it, and reusing it. The other expansion, equation 6.53, recomputes the inner calls each time. The demo below counts the calls to for the two choices. Only calls to are counted, and the derivative of f is treated as a separate cost. This count is added for this page and is not in the book.

Without reuse, the recursion unfolds into a sum over paths in the graph, equation 6.55. Each path contributes a product of local derivatives. Because the number of paths can grow exponentially with depth, the expanded sum can be far more expensive than the recursion.

The ladder below is a simple graph in which the number of paths grows exponentially. It has an input, K stages of two nodes each, and an output. Every node in one stage connects to both nodes in the next stage. The ladder is added here and is not in the book.

Back-propagation in a network

A multilayer perceptron is a chain of layers. Algorithm 6.3 is the forward pass. It takes the input, computes each layer's pre-activation from the layer below, and applies the activation function to get that layer's output. It repeats this until it reaches the output and the cost.

Algorithm 6.4 is the backward pass. It starts from the gradient of the cost with respect to the output. At each layer it multiplies by the derivative of the activation function, records the gradients for that layer's bias and weights, and then passes the gradient to the layer below by multiplying with the transpose of the weight matrix. Each backward step uses values stored during the forward pass, which is why those values must be kept.

The demo below runs the backward pass on a tiny network: two inputs, two hidden sigmoid units and one linear output. The numbers are chosen for this page. Each press reveals one step, and the last step compares the result with finite differences.

Symbol-to-symbol derivatives

So far the derivatives were evaluated for specific numbers. The symbol-to-symbol approach instead adds nodes to the graph that compute the derivative as a new expression. Figure 6.10 of the book shows this for . The derivative graph can then be evaluated for any numerical input, and the same machinery can differentiate it again. Some libraries take a graph together with numbers and return numbers (symbol-to-number, as in Torch and Caffe). Others, such as Theano and TensorFlow, add nodes that describe the derivative (symbol-to-symbol). The book takes the second approach.

With equal to the sine, equation 6.52 gives a concrete expression. Here = sin(w) and = sin(x), and the derivative is the product below. The expression is added for this example.

General back-propagation

The algorithm needs only a local rule for each operation. To compute the gradient of a scalar with respect to an ancestor , start with the gradient of with respect to itself, which is 1. Multiply by the Jacobian of each operation while moving backwards through the graph. Where gradients arrive at a node along two or more paths, add them.

Each operation supplies a bprop method that returns the gradient for its inputs. For an operation with inputs and a gradient on its output, the method must return the sum below, which is the chain rule of equation 6.47 written for one operation.

The bprop method should treat all of its inputs as distinct, even when they are the same variable. For , the rule returns for each input, and the algorithm adds the two to get .

Algorithm 6.5 is the outer skeleton, which does setup and cleanup. Most of the work happens in build_grad, Algorithm 6.6, which adds the contribution of each consumer node to the table.

Weight decay in training

The book's example trains a multilayer perceptron with one hidden layer and no biases. The hidden layer is the rectifier applied to the input times the first weight matrix. The predictions are the hidden layer times the second weight matrix. The cross-entropy cost from the data is minimized. To keep the weights small, a weight decay penalty is added, which gives the total cost in equation 6.56.

Figure 6.11 draws the graph for this example. The cost has two branches, the cross-entropy and the weight decay term, and the gradient with respect to a weight adds the contributions of both.

The gradient of the penalty with respect to a weight is twice the coefficient times the weight. Back-propagation handles the penalty like any other path: the penalty node sends its gradient to each weight it reads.

The main memory cost of the algorithm is that the input to each hidden nonlinearity must be stored from the forward pass until the backward pass returns to that point. The memory cost is , where is the number of examples in the minibatch and is the number of hidden units.

Complications and other ways to differentiate

The book notes that real implementations are more involved than the description here. An operation may return more than one tensor. Many tensors must be added together, and doing so can use too much memory if each one is stored first. Data types need care, and some operations have no gradient at certain inputs, and the code must track those cases. None of these changes the central idea.

Back-propagation is also one approach to automatic differentiation. It is a special case of reverse mode accumulation. Other approaches evaluate the parts of the chain rule in other orders. Finding the order with the lowest cost is NP-complete, and it can require simplifying the algebra first.

Take the softmax of unnormalized log probabilities , followed by a cross-entropy cost. Equation 6.57 defines the softmax, where is the predicted probability of each class.

A human can see that the derivative of the cost with respect to each is minus . Back-propagation does not find this shortcut and propagates through every logarithm and exponential. The demo below shows the shortcut is correct. Choose a target class and move the scores.

The matrix product in equation 6.58 shows another choice. The matrices can be thought of as Jacobians, and the product can be taken from the right or from the left. The order from the right, which is backward mode, needs only matrix-vector products when the last factor is a column vector. The order from the left, which is forward mode, needs matrix-matrix products. The cheaper order depends on the shapes. The demo below uses a chain in which has rows and columns, and are square with rows, and is a column vector. When a graph has more outputs than inputs, forward mode is sometimes the better choice, because it does not store the values and gradients for the whole graph.

Higher-order derivatives

Derivatives can be differentiated again. Some frameworks support higher-order derivatives, and they use the same kind of graph for the derivative as for the original function. In deep learning the quantity that matters is often the Hessian, the matrix of second partial derivatives. For parameters the Hessian has by entries, and can easily be in the billions, so the full Hessian cannot be stored.

Krylov methods are iterative techniques that use only products of the Hessian with a vector. Equation 6.59 gives such a product by differentiating the gradient along the vector . The outer gradient is taken of a function of the inner gradient. If is itself produced by a graph, the differentiation must not pass through that graph. The full Hessian can still be built, one column at a time, by multiplying by each one-hot vector .

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 6.5 (pages 204–224), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.