526
CHAPTER 13. NEURAL NETS AND DEEP LEARNING
parameters, it is possible to ﬁnd parameters that yield low training loss but
nevertheless perform poorly in the real world. This phenomenon is called over-
ﬁtting, a problem we have mentioned several times, starting in Section 9.4.4.
For the moment, we assume that our goal is to ﬁnd parameters that minimize
the expected loss on the training set. This goal is achieved by gradient descent.
There is an elegant algorithm called backpropagation that allows us to compute
these gradients eﬃciently. Before we describe backpropagation, we need a few
preliminaries.
13.3.1
Compute Graphs
A compute graph captures the data ﬂow of a deep network. Formally, a compute
graph is a directed, acyclic graph (DAG). Each node in the compute graph has
an operand and, optionally, an operator. The operand can be a scalar, a vector,
or a matrix. The operator is a linear-algebra operator (such as + or ×), an
activation function (such as σ) or a loss function (such as MSE). When a node
has both an operand and an operator, the operator is written above the operand.
When a node has only an operand, its output is the value associated with
the operand. The output of a node with an operator is the result of applying
its operator to its immediate predecessors in the graph and then assigning the
result to the operand. In general, the operator can be an arbitrary expression
that uses its inputs to produce an output.3
Example 13.2 : Figure 13.8 shows the compute graph for a single-layer dense
network described by y = σ(Wx + b) where x is the input and y is the output.
We then compute an MSE loss against the training-set output ˆy. That is, we
have a single layer of n nodes. The vector y is of length n and represents the
outputs of each of these nodes. There are k inputs, and (x, ˆy) represents one
training example. Matrix W represents the weights on the inputs of the nodes;
that is, Wij is the weight for input j at the ith node. Finally, b represents the
n biases, so its ith element is the negative of the threshold of the ith node.
u
v
y
y
x
W
b
L
MSE
σ
Figure 13.8: Compute graph for a single-layer dense network
For the graph in Fig. 13.8, we have:
3Sometimes the order of operands to the operator matters. We shall ignore that detail
here and assume it is understood from the context.
