"6.5 Back-Propagation and Other Differentiation Algorithms
When we use a feedforward neural network to accept an input x and produce an
output yˆ, information flows forward through the network. The inputs x provide
the initial information that then propagates up to the hidden units at each layer
and finally produces yˆ. This is called forward propagation. During training,
forward propagation can continue onward until it produces a scalar cost J(θ).
The back-propagation algorithm (Rumelhart et al., 1986a), often simply called
backprop, allows the information from the cost to then flow backwards through
the network, in order to compute the gradient.
Computing an analytical expression for the gradient is straightforward, but
numerically evaluating such an expression can be computationally expensive. The
back-propagation algorithm does so using a simple and inexpensive procedure.
The term back-propagation is often misunderstood as meaning the whole
learning algorithm for multi-layer neural networks. Actually, back-propagation
refers only to the method for computing the gradient, while another algorithm,
such as stochastic gradient descent, is used to perform learning using this gradient.
Furthermore, back-propagation is often misunderstood as being specific to multilayer neural networks, but in principle it can compute derivatives of any function
(for some functions, the correct response is to report that the derivative of the
function is undefined). Specifically, we will describe how to compute the gradient
∇xf(x, y) for an arbitrary function f , wherex is a set of variables whose derivatives
are desired, and y is an additional set of variables that are inputs to the function
but whose derivatives are not required. In learning algorithms, the gradient we most
often require is the gradient of the cost function with respect to the parameters,
∇θ J(θ). Many machine learning tasks involve computing other derivatives, either
as part of the learning process, or to analyze the learned model. The backpropagation algorithm can be applied to these tasks as well, and is not restricted
to computing the gradient of the cost function with respect to the parameters. The
idea of computing derivatives by propagating information through a network is
very general, and can be used to compute values such as the Jacobian of a function
f with multiple outputs. We restrict our description here to the most commonly
used case where f has a single output.
204
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
6.5.1 Computational Graphs
So far we have discussed neural networks with a relatively informal graph language.
To describe the back-propagation algorithm more precisely, it is helpful to have a
more precise computational graph language.
Many ways of formalizing computation as graphs are possible.
Here, we use each node in the graph to indicate a variable. The variable may
be a scalar, vector, matrix, tensor, or even a variable of another type.
To formalize our graphs, we also need to introduce the idea of an operation.
An operation is a simple function of one or more variables. Our graph language
is accompanied by a set of allowable operations. Functions more complicated
than the operations in this set may be described by composing many operations
together.
Without loss of generality, we define an operation to return only a single
output variable. This does not lose generality because the output variable can have
multiple entries, such as a vector. Software implementations of back-propagation
usually support operations with multiple outputs, but we avoid this case in our
description because it introduces many extra details that are not important to
conceptual understanding.
If a variable y is computed by applying an operation to a variable x, then
we draw a directed edge from x to y. We sometimes annotate the output node
with the name of the operation applied, and other times omit this label when the
operation is clear from context.
Examples of computational graphs are shown in figure 6.8.
6.5.2 Chain Rule of Calculus
The chain rule of calculus (not to be confused with the chain rule of probability) is
used to compute the derivatives of functions formed by composing other functions
whose derivatives are known. Back-propagation is an algorithm that computes the
chain rule, with a specific order of operations that is highly efficient.
Let x be a real number, and let f and g both be functions mapping from a real
number to a real number. Suppose that y = g(x) and z = f (g(x)) = f (y). Then
the chain rule states that
dz
dx = dz
dy
dy
dx . (6.44)
We can generalize this beyond the scalar case. Suppose that x ∈ Rm, y ∈ Rn,
205
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
z
x y
(a)
×
x w
(b)
u(1)
dot
b
u(2)
+
yˆ
σ
(c)
X W
U (1)
matmul
b
U (2)
+
H
relu
x w
(d)
yˆ
dot
λ
u(1)
sqr
u(2)
sum
u(3)
×
Figure 6.8: Examples of computational graphs. (a)The graph using the× operation to
compute z = xy. (b)The graph for the logistic regression prediction yˆ = σ

xw + b

.
Some of the intermediate expressions do not have names in the algebraic expression
but need names in the graph. We simply name the i-th such variable u(i)
. (c)The
computational graph for the expression H = max{0,XW + b}, which computes a design
matrix of rectified linear unit activations H given a design matrix containing a minibatch
of inputs X . (d)Examples a–c applied at most one operation to each variable, but it
is possible to apply more than one operation. Here we show a computation graph that
applies more than one operation to the weights w of a linear regression model. The
weights are used to make both the prediction yˆ and the weight decay penalty λ

i w2
i .
206
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
g maps from Rm to Rn, and f maps from Rn to R. If y = g(x) and z = f(y), then
∂z
∂xi
= 
j
∂z
∂yj
∂yj
∂xi
. (6.45)
In vector notation, this may be equivalently written as
∇xz =
 ∂y
∂x

∇y z, (6.46)
where ∂y
∂x is the n × m Jacobian matrix of g.
From this we see that the gradient of a variable x can be obtained by multiplying
a Jacobian matrix ∂y
∂x by a gradient ∇yz. The back-propagation algorithm consists
of performing such a Jacobian-gradient product for each operation in the graph.
Usually we do not apply the back-propagation algorithm merely to vectors,
but rather to tensors of arbitrary dimensionality. Conceptually, this is exactly the
same as back-propagation with vectors. The only difference is how the numbers
are arranged in a grid to form a tensor. We could imagine flattening each tensor
into a vector before we run back-propagation, computing a vector-valued gradient,
and then reshaping the gradient back into a tensor. In this rearranged view,
back-propagation is still just multiplying Jacobians by gradients.
To denote the gradient of a value z with respect to a tensor X, we write ∇Xz,
just as if X were a vector. The indices into X now have multiple coordinates—for
example, a 3-D tensor is indexed by three coordinates. We can abstract this away
by using a single variable i to represent the complete tuple of indices. For all
possible index tuples i, (∇Xz)i gives ∂z
∂Xi
. This is exactly the same as how for all
possible integer indices i into a vector, (∇x z)i gives ∂z
∂xi
. Using this notation, we
can write the chain rule as it applies to tensors. If Y = g(X) and z = f(Y), then
∇X z =
j
(∇XYj ) ∂z
∂Yj
. (6.47)
6.5.3 Recursively Applying the Chain Rule to Obtain Backprop
Using the chain rule, it is straightforward to write down an algebraic expression for
the gradient of a scalar with respect to any node in the computational graph that
produced that scalar. However, actually evaluating that expression in a computer
introduces some extra considerations.
Specifically, many subexpressions may be repeated several times within the
overall expression for the gradient. Any procedure that computes the gradient
207
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
will need to choose whether to store these subexpressions or to recompute them
several times. An example of how these repeated subexpressions arise is given in
figure 6.9. In some cases, computing the same subexpression twice would simply
be wasteful. For complicated graphs, there can be exponentially many of these
wasted computations, making a naive implementation of the chain rule infeasible.
In other cases, computing the same subexpression twice could be a valid way to
reduce memory consumption at the cost of higher runtime.
We first begin by a version of the back-propagation algorithm that specifies the
actual gradient computation directly (algorithm 6.2 along with algorithm 6.1 for the
associated forward computation), in the order it will actually be done and according
to the recursive application of chain rule. One could either directly perform these
computations or view the description of the algorithm as a symbolic specification
of the computational graph for computing the back-propagation. However, this
formulation does not make explicit the manipulation and the construction of the
symbolic graph that performs the gradient computation. Such a formulation is
presented below in section 6.5.6, with algorithm 6.5, where we also generalize to
nodes that contain arbitrary tensors.
First consider a computational graph describing how to compute a single scalar
u(n) (say the loss on a training example). This scalar is the quantity whose
gradient we want to obtain, with respect to the ni input nodes u(1) to u(ni). In
other words we wish to compute ∂u(n)
∂u(i) for all i ∈ {1, 2, . . . , ni}. In the application
of back-propagation to computing gradients for gradient descent over parameters,
u(n) will be the cost associated with an example or a minibatch, while u(1) to u(ni)
correspond to the parameters of the model.
We will assume that the nodes of the graph have been ordered in such a way
that we can compute their output one after the other, starting at u(ni+1) and
going up to u(n)
. As defined in algorithm 6.1, each node u(i) is associated with an
operation f(i) and is computed by evaluating the function
u(i) = f(A(i)
) (6.48)
where A(i) is the set of all nodes that are parents of u(i)
.
That algorithm specifies the forward propagation computation, which we could
put in a graph G. In order to perform back-propagation, we can construct a
computational graph that depends onG and adds to it an extra set of nodes. These
form a subgraph B with one node per node of G. Computation in B proceeds in
exactly the reverse of the order of computation in G, and each node of B computes
the derivative ∂u(n)
∂u(i) associated with the forward graph node u(i)
. This is done
208
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Algorithm 6.1 A procedure that performs the computations mapping ni inputs
u(1) to u(ni) to an output u(n)
. This defines a computational graph where each node
computes numerical value u(i) by applying a function f (i) to the set of arguments
A(i) that comprises the values of previous nodes u(j)
, j < i, with j ∈ Pa(u(i)
). The
input to the computational graph is the vector x, and is set into the first ni nodes
u(1) to u(ni ) . The output of the computational graph is read off the last (output)
node u(n)
.
for i = 1, . . . , ni do
u(i) ← xi
end for
for i = ni + 1, . . . , n do
A(i) ← {u(j) | j ∈ Pa(u(i) )}
u(i) ← f (i)
(A(i)
)
end for
return u(n)
using the chain rule with respect to scalar output u(n)
:
∂u(n)
∂u(j) = 
i:j∈Pa(u(i) )
∂u(n)
∂u(i)
∂u(i)
∂u(j) (6.49)
as specified by algorithm 6.2. The subgraph B contains exactly one edge for each
edge from node u(j) to node u(i) of G. The edge from u(j) to u(i) is associated with
the computation of ∂u(i)
∂u(j) . In addition, a dot product is performed for each node,
between the gradient already computed with respect to nodes u(i) that are children
of u(j) and the vector containing the partial derivatives ∂u(i)
∂u(j) for the same children
nodes u(i) . To summarize, the amount of computation required for performing
the back-propagation scales linearly with the number of edges in G, where the
computation for each edge corresponds to computing a partial derivative (of one
node with respect to one of its parents) as well as performing one multiplication
and one addition. Below, we generalize this analysis to tensor-valued nodes, which
is just a way to group multiple scalar values in the same node and enable more
efficient implementations.
The back-propagation algorithm is designed to reduce the number of common
subexpressions without regard to memory. Specifically, it performs on the order
of one Jacobian product per node in the graph. This can be seen from the fact
that backprop (algorithm 6.2) visits each edge from node u(j) to node u(i) of
the graph exactly once in order to obtain the associated partial derivative ∂u(i)
∂u(j) .
209
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Algorithm 6.2 Simplified version of the back-propagation algorithm for computing
the derivatives of u(n) with respect to the variables in the graph. This example is
intended to further understanding by showing a simplified case where all variables
are scalars, and we wish to compute the derivatives with respect to u(1), . . . , u(ni )
.
This simplified version computes the derivatives of all nodes in the graph. The
computational cost of this algorithm is proportional to the number of edges in
the graph, assuming that the partial derivative associated with each edge requires
a constant time. This is of the same order as the number of computations for
the forward propagation. Each ∂u(i)
∂u(j) is a function of the parents u(j) of u(i)
, thus
linking the nodes of the forward graph to those added for the back-propagation
graph.
Run forward propagation (algorithm 6.1 for this example) to obtain the activations of the network
Initialize grad_table, a data structure that will store the derivatives that have
been computed. The entry grad_table[u(i)
] will store the computed value of
∂u(n)
∂u(i) .
grad_table[u(n)
] ← 1
for j = n − 1 down to 1 do
The next line computes ∂u(n)
∂u(j) = 
i:j∈Pa(u(i) )
∂u(n)
∂u(i)
∂u (i)
∂u(j) using stored values:
grad_table[u(j) ] ← 
i:j∈Pa(u(i)) grad_table[u(i) ] ∂u(i)
∂u(j)
end for
return {grad_table[u(i)
] | i = 1, . . . , ni}
Back-propagation thus avoids the exponential explosion in repeated subexpressions.
However, other algorithms may be able to avoid more subexpressions by performing
simplifications on the computational graph, or may be able to conserve memory by
recomputing rather than storing some subexpressions. We will revisit these ideas
after describing the back-propagation algorithm itself.
6.5.4 Back-Propagation Computation in Fully-Connected MLP
To clarify the above definition of the back-propagation computation, let us consider
the specific graph associated with a fully-connected multi-layer MLP.
Algorithm 6.3 first shows the forward propagation, which maps parameters to
the supervised loss L(yˆ, y) associated with a single (input,target) training example
(x, y), with ˆy the output of the neural network when x is provided in input.
Algorithm 6.4 then shows the corresponding computation to be done for
210
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
z
x
y
w
f
f
f
Figure 6.9: A computational graph that results in repeated subexpressions when computing
the gradient. Let w ∈ R be the input to the graph. We use the same function f : R → R
as the operation that we apply at every step of a chain: x = f(w), y = f(x), z = f( y).
To compute ∂z
∂w , we apply equation 6.44 and obtain:
∂z
∂w (6.50)
= ∂z
∂y
∂y
∂x
∂x
∂w (6.51)
=f
(y)f
(x)f
(w) (6.52)
=f
(f(f(w)))f 
(f(w))f
(w) (6.53)
Equation 6.52 suggests an implementation in which we compute the value off (w) only
once and store it in the variable x. This is the approach taken by the back-propagation
algorithm. An alternative approach is suggested by equation 6.53, where the subexpression
f(w) appears more than once. In the alternative approach, f(w) is recomputed each time
it is needed. When the memory required to store the value of these expressions is low, the
back-propagation approach of equation 6.52 is clearly preferable because of its reduced
runtime. However, equation 6.53 is also a valid implementation of the chain rule, and is
useful when memory is limited.
211
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
applying the back-propagation algorithm to this graph.
Algorithms 6.3 and 6.4 are demonstrations that are chosen to be simple and
straightforward to understand. However, they are specialized to one specific
problem.
Modern software implementations are based on the generalized form of backpropagation described in section 6.5.6 below, which can accommodate any computational graph by explicitly manipulating a data structure for representing symbolic
computation.
Algorithm 6.3 Forward propagation through a typical deep neural network and
the computation of the cost function. The loss L(yˆ, y) depends on the output
yˆ and on the target y (see section 6.2.1.1 for examples of loss functions). To
obtain the total cost J, the loss may be added to a regularizer Ω(θ), where θ
contains all the parameters (weights and biases). Algorithm 6.4 shows how to
compute gradients of J with respect to parameters W and b. For simplicity, this
demonstration uses only a single input example x. Practical applications should
use a minibatch. See section 6.5.7 for a more realistic demonstration.
Require: Network depth, l
Require: W(i)
,i ∈ {1, . . . , l}, the weight matrices of the model
Require: b(i) ,i ∈ {1, . . . , l}, the bias parameters of the model
Require: x, the input to process
Require: y, the target output
h(0) = x
for k = 1, . . . , l do
a(k) = b(k) + W(k)h(k−1)
h(k) = f(a(k)
)
end for
yˆ = h(l)
J = L(yˆ, y) + λΩ(θ)
6.5.5 Symbol-to-Symbol Derivatives
Algebraic expressions and computational graphs both operate on symbols, or
variables that do not have specific values. These algebraic and graph-based
representations are called symbolic representations. When we actually use or
train a neural network, we must assign specific values to these symbols. We
replace a symbolic input to the network x with a specific numeric value, such as
[1.2, 3.765, −1.8].
212
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Algorithm 6.4 Backward computation for the deep neural network of algorithm 6.3, which uses in addition to the input x a target y. This computation
yields the gradients on the activations a(k) for each layer k, starting from the
output layer and going backwards to the first hidden layer. From these gradients,
which can be interpreted as an indication of how each layer’s output should change
to reduce error, one can obtain the gradient on the parameters of each layer. The
gradients on weights and biases can be immediately used as part of a stochastic gradient update (performing the update right after the gradients have been
computed) or used with other gradient-based optimization methods.
After the forward computation, compute the gradient on the output layer:
g ← ∇yˆJ = ∇yˆL(yˆ, y)
for k = l, l − 1, . . . , 1 do
Convert the gradient on the layer’s output into a gradient into the prenonlinearity activation (element-wise multiplication if f is element-wise):
g ← ∇a(k)J = g  f
(a(k)
)
Compute gradients on weights and biases (including the regularization term,
where needed):
∇b(k)J = g + λ∇b(k)Ω(θ)
∇W (k)J = g h(k−1) + λ∇W (k)Ω(θ)
Propagate the gradients w.r.t. the next lower-level hidden layer’s activations:
g ← ∇h(k−1) J = W(k) g
end for
213
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
z
x
y
w
f
f
f
z
x
y
w
f
f
f
dz
dy
f 
dy
dx
f 
dz
dx
×
dx
dw
f 
dz
dw
×
Figure 6.10: An example of the symbol-to-symbol approach to computing derivatives. In
this approach, the back-propagation algorithm does not need to ever access any actual
specific numeric values. Instead, it adds nodes to a computational graph describing how
to compute these derivatives. A generic graph evaluation engine can later compute the
derivatives for any specific numeric values. (Left)In this example, we begin with a graph
representing z = f (f(f (w))). (Right)We run the back-propagation algorithm, instructing
it to construct the graph for the expression corresponding to dz
dw . In this example, we do
not explain how the back-propagation algorithm works. The purpose is only to illustrate
what the desired result is: a computational graph with a symbolic description of the
derivative.
Some approaches to back-propagation take a computational graph and a set
of numerical values for the inputs to the graph, then return a set of numerical
values describing the gradient at those input values. We call this approach “symbolto-number” differentiation. This is the approach used by libraries such as Torch
(Collobert et al., 2011b) and Caffe (Jia, 2013).
Another approach is to take a computational graph and add additional nodes
to the graph that provide a symbolic description of the desired derivatives. This
is the approach taken by Theano (Bergstra et al., 2010; Bastien et al., 2012)
and TensorFlow (Abadi et al., 2015). An example of how this approach works
is illustrated in figure 6.10. The primary advantage of this approach is that
the derivatives are described in the same language as the original expression.
Because the derivatives are just another computational graph, it is possible to run
back-propagation again, differentiating the derivatives in order to obtain higher
derivatives. Computation of higher-order derivatives is described in section 6.5.10.
We will use the latter approach and describe the back-propagation algorithm in
214
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
terms of constructing a computational graph for the derivatives. Any subset of the
graph may then be evaluated using specific numerical values at a later time. This
allows us to avoid specifying exactly when each operation should be computed.
Instead, a generic graph evaluation engine can evaluate every node as soon as its
parents’ values are available.
The description of the symbol-to-symbol based approach subsumes the symbolto-number approach. The symbol-to-number approach can be understood as
performing exactly the same computations as are done in the graph built by the
symbol-to-symbol approach. The key difference is that the symbol-to-number
approach does not expose the graph.
6.5.6 General Back-Propagation
The back-propagation algorithm is very simple. To compute the gradient of some
scalar z with respect to one of its ancestors x in the graph, we begin by observing
that the gradient with respect to z is given by dz
dz = 1. We can then compute
the gradient with respect to each parent of z in the graph by multiplying the
current gradient by the Jacobian of the operation that produced z. We continue
multiplying by Jacobians traveling backwards through the graph in this way until
we reach x. For any node that may be reached by going backwards from z through
two or more paths, we simply sum the gradients arriving from different paths at
that node.
More formally, each node in the graph G corresponds to a variable. To achieve
maximum generality, we describe this variable as being a tensor V. Tensor can
in general have any number of dimensions. They subsume scalars, vectors, and
matrices.
We assume that each variable V is associated with the following subroutines:
• get_operation(V): This returns the operation that computes V, represented by the edges coming into V in the computational graph. For example,
there may be a Python or C++ class representing the matrix multiplication
operation, and the get_operation function. Suppose we have a variable that
is created by matrix multiplication, C = AB. Then get_operation(V)
returns a pointer to an instance of the corresponding C++ class.
• get_consumers(V, G): This returns the list of variables that are children of
V in the computational graph G.
• get_inputs(V, G): This returns the list of variables that are parents of V
in the computational graph G.
215
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Each operation op is also associated with a bprop operation. This bprop
operation can compute a Jacobian-vector product as described by equation 6.47.
This is how the back-propagation algorithm is able to achieve great generality.
Each operation is responsible for knowing how to back-propagate through the
edges in the graph that it participates in. For example, we might use a matrix
multiplication operation to create a variable C = AB. Suppose that the gradient
of a scalar z with respect to C is given by G. The matrix multiplication operation
is responsible for defining two back-propagation rules, one for each of its input
arguments. If we call the bprop method to request the gradient with respect to
A given that the gradient on the output is G, then the bprop method of the
matrix multiplication operation must state that the gradient with respect to A
is given by GB. Likewise, if we call the bprop method to request the gradient
with respect to B, then the matrix operation is responsible for implementing the
bprop method and specifying that the desired gradient is given by AG. The
back-propagation algorithm itself does not need to know any differentiation rules. It
only needs to call each operation’s bprop rules with the right arguments. Formally,
op.bprop(inputs, X, G) must return

i
(∇ Xop.f(inputs)i) Gi, (6.54)
which is just an implementation of the chain rule as expressed in equation 6.47.
Here, inputs is a list of inputs that are supplied to the operation, op.f is the
mathematical function that the operation implements,X is the input whose gradient
we wish to compute, and G is the gradient on the output of the operation.
The op.bprop method should always pretend that all of its inputs are distinct
from each other, even if they are not. For example, if the mul operator is passed
two copies of x to compute x2, the op.bprop method should still return x as the
derivative with respect to both inputs. The back-propagation algorithm will later
add both of these arguments together to obtain 2x, which is the correct total
derivative on x.
Software implementations of back-propagation usually provide both the operations and their bprop methods, so that users of deep learning software libraries are
able to back-propagate through graphs built using common operations like matrix
multiplication, exponents, logarithms, and so on. Software engineers who build a
new implementation of back-propagation or advanced users who need to add their
own operation to an existing library must usually derive the op.bprop method for
any new operations manually.
The back-propagation algorithm is formally described in algorithm 6.5.
216
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Algorithm 6.5 The outermost skeleton of the back-propagation algorithm. This
portion does simple setup and cleanup work. Most of the important work happens
in the build_grad subroutine of algorithm 6.6 .
Require: T, the target set of variables whose gradients must be computed.
Require: G, the computational graph
Require: z, the variable to be differentiated
Let G be G pruned to contain only nodes that are ancestors of z and descendents
of nodes in T.
Initialize grad_table, a data structure associating tensors to their gradients
grad_table[z] ← 1
for V in T do
build_grad(V, G, G , grad_table)
end for
Return grad_table restricted to T
In section 6.5.2, we explained that back-propagation was developed in order to
avoid computing the same subexpression in the chain rule multiple times. The naive
algorithm could have exponential runtime due to these repeated subexpressions.
Now that we have specified the back-propagation algorithm, we can understand its
computational cost. If we assume that each operation evaluation has roughly the
same cost, then we may analyze the computational cost in terms of the number
of operations executed. Keep in mind here that we refer to an operation as the
fundamental unit of our computational graph, which might actually consist of very
many arithmetic operations (for example, we might have a graph that treats matrix
multiplication as a single operation). Computing a gradient in a graph with n nodes
will never execute more than O(n2) operations or store the output of more than
O(n2) operations. Here we are counting operations in the computational graph, not
individual operations executed by the underlying hardware, so it is important to
remember that the runtime of each operation may be highly variable. For example,
multiplying two matrices that each contain millions of entries might correspond to
a single operation in the graph. We can see that computing the gradient requires as
most O(n2) operations because the forward propagation stage will at worst execute
all n nodes in the original graph (depending on which values we want to compute,
we may not need to execute the entire graph). The back-propagation algorithm
adds one Jacobian-vector product, which should be expressed with O(1) nodes, per
edge in the original graph. Because the computational graph is a directed acyclic
graph it has at most O(n2 ) edges. For the kinds of graphs that are commonly used
in practice, the situation is even better. Most neural network cost functions are
217
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
Algorithm 6.6 The inner loop subroutine build_grad(V, G, G
, grad_table) of
the back-propagation algorithm, called by the back-propagation algorithm defined
in algorithm 6.5.
Require: V, the variable whose gradient should be added to G and grad_table.
Require: G, the graph to modify.
Require: G
, the restriction of G to nodes that participate in the gradient.
Require: grad_table, a data structure mapping nodes to their gradients
if V is in grad_table then
Return grad_table[V]
end if
i ← 1
for C in get_consumers(V, G
) do
op ← get_operation(C)
D ← build_grad(C, G,G
, grad_table)
G(i) ← op.bprop(get_inputs(C, G
), V, D)
i ← i + 1
end for
G ←
i G(i)
grad_table[V] = G
Insert G and the operations creating it into G
Return G
roughly chain-structured, causing back-propagation to have O(n) cost. This is far
better than the naive approach, which might need to execute exponentially many
nodes. This potentially exponential cost can be seen by expanding and rewriting
the recursive chain rule (equation 6.49) non-recursively:
∂u(n)
∂u(j) = 
path (u(π1),u(π2) ,...,u(πt) ),
from π1=j to πt=n

t
k=2
∂u(πk)
∂u(πk−1 )
. (6.55)
Since the number of paths from node j to node n can grow exponentially in the
length of these paths, the number of terms in the above sum, which is the number
of such paths, can grow exponentially with the depth of the forward propagation
graph. This large cost would be incurred because the same computation for
∂u(i)
∂u(j) would be redone many times. To avoid such recomputation, we can think
of back-propagation as a table-filling algorithm that takes advantage of storing
intermediate results ∂u(n)
∂u(i) . Each node in the graph has a corresponding slot in a
table to store the gradient for that node. By filling in these table entries in order,
218
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
back-propagation avoids repeating many common subexpressions. This table-filling
strategy is sometimes called dynamic programming.
6.5.7 Example: Back-Propagation for MLP Training
As an example, we walk through the back-propagation algorithm as it is used to
train a multilayer perceptron.
Here we develop a very simple multilayer perception with a single hidden
layer. To train this model, we will use minibatch stochastic gradient descent.
The back-propagation algorithm is used to compute the gradient of the cost on a
single minibatch. Specifically, we use a minibatch of examples from the training
set formatted as a design matrix X and a vector of associated class labels y.
The network computes a layer of hidden features H = max{0, XW(1)}. To
simplify the presentation we do not use biases in this model. We assume that our
graph language includes a relu operation that can compute max{0, Z} elementwise. The predictions of the unnormalized log probabilities over classes are then
given by HW (2). We assume that our graph language includes a cross_entropy
operation that computes the cross-entropy between the targets y and the probability
distribution defined by these unnormalized log probabilities. The resulting crossentropy defines the cost JMLE. Minimizing this cross-entropy performs maximum
likelihood estimation of the classifier. However, to make this example more realistic,
we also include a regularization term. The total cost
J = JMLE + λ


i,j

W (1)
i,j 2
+ 
i,j

W(2)
i,j 2

 (6.56)
consists of the cross-entropy and a weight decay term with coefficient λ. The
computational graph is illustrated in figure 6.11.
The computational graph for the gradient of this example is large enough that
it would be tedious to draw or to read. This demonstrates one of the benefits
of the back-propagation algorithm, which is that it can automatically generate
gradients that would be straightforward but tedious for a software engineer to
derive manually.
We can roughly trace out the behavior of the back-propagation algorithm
by looking at the forward propagation graph in figure 6.11. To train, we wish
to compute both ∇W (1)J and ∇W (2)J. There are two different paths leading
backward from J to the weights: one through the cross-entropy cost, and one
through the weight decay cost. The weight decay cost is relatively simple; it will
always contribute 2λW(i) to the gradient on W(i) .
219
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
X W (1)
U (1)
matmul
H
relu
U (3)
sqr u(4)
sum
W (2) u(7) λ
U (2)
matmul
y
JMLE
cross_entropy
U (5)
sqr u(6)
sum
u(8)
J
+
×
+
Figure 6.11: The computational graph used to compute the cost used to train our example
of a single-layer MLP using the cross-entropy loss and weight decay.
The other path through the cross-entropy cost is slightly more complicated.
Let G be the gradient on the unnormalized log probabilities U(2) provided by
the cross_entropy operation. The back-propagation algorithm now needs to
explore two different branches. On the shorter branch, it adds H G to the
gradient on W(2) , using the back-propagation rule for the second argument to
the matrix multiplication operation. The other branch corresponds to the longer
chain descending further along the network. First, the back-propagation algorithm
computes ∇HJ = GW(2) using the back-propagation rule for the first argument
to the matrix multiplication operation. Next, the relu operation uses its backpropagation rule to zero out components of the gradient corresponding to entries
of U(1) that were less than 0. Let the result be called G . The last step of the
back-propagation algorithm is to use the back-propagation rule for the second
argument of the matmul operation to add XG to the gradient on W(1).
After these gradients have been computed, it is the responsibility of the gradient
descent algorithm, or another optimization algorithm, to use these gradients to
update the parameters.
For the MLP, the computational cost is dominated by the cost of matrix
multiplication. During the forward propagation stage, we multiply by each weight
220
CHAPTER 6. DEEP FEEDFORWARD NETWORKS
matrix, resulting in O(w) multiply-adds, where w is the number of weights. During
the backward propagation stage, we multiply by the transpose of each weight
matrix, which has the same computational cost. The main memory cost of the
algorithm is that we need to store the input to the nonlinearity of the hidden layer.
This value is stored from the time it is computed until the backward pass has
returned to the same point. The memory cost is thus O(mnh), where m is the
number of examples in the minibatch and nh is the number of hidden units.
"
Summarize the above basic principle of back-propagation for neural network training, try to use your own words, do not directly copy the sentence from the above paper.