Sanjeev Arora and Tengyu Ma • Dec 20, 2016 • 20 minute read
Backpropagation gives a fast way to compute the sensitivity of the output of a neural network to all of its parameters while keeping the inputs of the network fixed: specifically it computes all partial derivatives ∂f/∂wi where f is the output and wi is the ith parameter. (Here parameters can be edge weights or biases associated with nodes or edges of the network, and the precise details of the node computations —e.g., the precise form of nonlinearity like Sigmoid or RELU— are unimportant.) Doing so gives the gradient ∇f of f with respect to its network parameters, which allows a gradient descent step in the training: change all parameters simultaneously to move the vector of parameters a small amount in the direction −∇f.
Note that backpropagation computes the gradient exactly, but properly training neural nets needs many more tricks than just backpropagation. Understanding backpropagation is useful for understanding the advanced tricks.
The importance of backpropagation derives from its efficiency. Assuming node operations take unit time, the running time is linear, specifically, O(Network Size)=O(V+E), where V is the number of nodes in the network and E is the number of edges. The only technical ingredient is chain rule from calculus, but applying it naively would have resulted in quadratic running time—which would be hugely inefficient for networks with millions or even thousands of parameters.
Side Note: Expert readers will recognize that in the standard accounts of neural net training, the actual quantity of interest is the gradient of the training loss, which happens to be a simple function of the network output. But the above phrasing is fully general since one can simply add a new output node to the network that computes the training loss from the old output. Then the quantity of interest is indeed the gradient of this new output with respect to network parameters.
Backpropagation applies only to acyclic networks with directed edges. (Later we briefly sketch its use on networks with cycles.)
Without loss of generality, acyclic networks can be visualized as being structured in numbered layers, with nodes in the t+1th layer getting all their inputs from the outputs of nodes in layers t and earlier. We use f∈R to denote the output of the network. In all our figures, the input of the network is at the bottom and the output on the top.
We start with a simple claim that reduces the problem of computing the gradient to the problem of computing partial derivatives with respect to the nodes:
Claim 1: To compute the desired gradient with respect to the parameters, it suffices to compute ∂f/∂u for every node u.
Let’s be clear what ∂f/∂u means. Suppose we cut off all the incoming edges of the node u, and fix/clamp the current values of all network parameters. Now imagine changing u from its current value. This change may affect values of nodes at higher levels that are connected to u, and the final output f is one such node. Then ∂f/∂u denotes the rate at which f will change as we vary u. (Aside: Readers familiar with the usual exposition of back-propagation should note that there f is the training error and this ∂f/∂u turns out to be exactly the “error” propagated back to on the node u.)
Claim 1 is a direct application of chain rule, and let’s illustrate it for a simple neural nets (we address more general networks later). Suppose node u is a weighted sum of the nodes z1,…,zm (which will be passed through a non-linear activation σ afterwards). That is, we have u=w1z1+⋯+wnzn. By Chain rule, we have
∂f∂w1=∂f∂u⋅∂u∂w1=∂f∂u⋅z1.
Hence, we see that having computed ∂f/∂u we can compute ∂f/∂w1, and moreover this can be done locally by the endpoints of the edge where w1 resides.
Towards computing the derivatives with respect to the nodes, we first recall the multivariate Chain rule, which handily describes the relationships between these partial derivatives (depending on the graph structure).
Suppose a variable f is a function of variables u1,…,un, which in turn depend on the variable z. Then, multivariate Chain rule says that
∂f∂z=∑j=1n∂f∂uj⋅∂uj∂z .
This formula is perfectly suitable for our cases. Below is the same example as we used before but with a different focus and numbering of the nodes.
We see that given we’ve computed the derivatives with respect to all the nodes that is above the node z, we can compute the derivative with respect to the node z via a weighted sum, where the weights involve the local derivative ∂uj/∂z that is often easy to compute. This brings us to the question of how we measure running time. For book-keeping, we assume that
Basic assumption: If u is a node at level t+1 and z is any node at level ≤twhose output is an input to u, then computing ∂u∂z takes unit time on our computer.
It is useful to first point out the naive quadratic time algorithm implied by the chain rule. Most authors skip this trivial version, which we think is analogous to teaching sorting using only quicksort, and skipping over the less efficient bubblesort.
The naive algorithm is to compute ∂ui/∂uj for every pair of nodes where ui is at a higher level than uj. Of course, among these V2 values (where V is the number of nodes) are also the desired ∂f/∂ui for all i since f is itself the value of the output node.
This computation can be done in feedforward fashion. If such value has been obtained for every uj on the level up to and including level t, then one can express (by inspecting the multivariate chain rule) the value ∂uℓ/∂uj for some uℓ at level t+1 as a weighted combination of values ∂ui/∂uj for each ui that is a direct input to uℓ. This description shows that the amount of computation for a fixed j is proportional to the number of edges E. This amount of work happens for all V values of j, letting us conclude that the total work in the algorithm is O(VE).
The more efficient backpropagation, as the name suggests, computes the partial derivatives in the reverse direction. Messages are passed in one wave backwards from higher number layers to lower number layers. (Some presentations of the algorithm describe it as dynamic programming.)
Messaging protocol: The node u receives a message along each outgoing edge from the node at the other end of that edge. It sums these messages to get a number S (if u is the output of the entire net, then define S=1) and then it sends the following message to any node z adjacent to it at a lower level: S⋅∂u∂z
Clearly, the amount of work done by each node is proportional to its degree, and thus overall work is the sum of the node degrees. Summing all node degrees counts each edge twice, and thus the overall work is O(Network Size).
To prove correctness, we prove the following:
Main Claim: At each node z, the value S is exactly ∂f/∂z.
Base Case: At the output layer this is true, since ∂f/∂f=1.
Inductive case: Suppose the claim was true for layers t+1 and higher and u is at layer t, with outgoing edges go to some nodes u1,u2,…,um at levels t+1 or higher. By inductive hypothesis, node z indeed receives ∂f∂uj×∂uj∂z from each of uj. Thus by Chain rule,S=∑mi=1∂f∂ui∂ui∂z=∂f∂z. This completes the induction and proves the Main Claim.
We first observe that Claim 1 continues to hold in this very general setting. This is without loss of generality because we can view the parameters associated to the edges as also sitting on the nodes (actually, leaf nodes). This can be done via a simple transformation to the network; for a single node it is shown in the picture below; and one would need to continue to do this transformation in the rest of the networks feeding into u1,u2,.. etc from below.
Then, we can use the messaging protocol to compute the derivatives with respect to the nodes, as long as the local partial derivative can be computed efficiently. We note that the algorithm can be implemented in a fairly modular manner: For every node u, it suffices to specify (a) how it depends on the incoming nodes, say, z1,…,zn and (b) how to compute the partial derivative times S, that is, S⋅∂u∂zj.
Extension to vector messages: In fact (b) can be done efficiently in more general settings where we allow the output of each node in the network to be a vector (or even matrix/tensor) instead of only a real number. For example, as illustrated below, suppose the node U∈Rd1×d3 is a product of two matrices W∈Rd1×d2 and Z∈Rd2×d3. Then we have that ∂U/∂Z is a linear operator that maps Rd2×d3 to Rd1×d3, which naively require a matrix representation of dimension d2d3×d2d3. However, the computation (b) can be done efficiently becauseS⋅∂U∂Z=SW.
Such vector operations can also be implemented efficiently using today’s GPUs.
For simplicity, suppose two parameters a and b are supposed to share the same value. This is equivalent to adding a new node u and connecting u to both a and b with the operation a=uand b=u. Thus, by chain rule, ∂f∂u=∂f∂a⋅∂a∂u+∂f∂b⋅∂b∂u=∂f∂a+∂f∂b. Hence, equivalently, the gradient with respect to a shared parameter is the sum of the gradients with respect to individual occurrences.
2) Backpropagation on networks with loops. The above exposition assumed the network is acyclic. Many cutting-edge applications such as machine translation and language understanding use networks with directed loops (e.g., recurrent neural networks). These architectures —all examples of the “differentiable computing” paradigm below—can get complicated and may involve operations on a separate memory as well as mechanisms to shift attention to different parts of data and memory.
Claim (informal): Suppose an acyclic network with V nodes and E edges has output f and leaves z1,…,zm. Then there exists a network of size O(V+E) that has z1,…,zm as input nodes and ∂f∂z1,…,∂f∂zm as output nodes.
The proof of the Claim follows in straightforward fashion from implementing the message passing protocol as an acyclic circuit.
Next we show how to compute ∇2f(z)⋅v where v is a given fixed vector. Let g(z)=⟨∇f(z),v⟩ be a function from Rd→R. Then by the Claim above, g(z) can be computed by a network of size O(V+E). Now apply the Claim again on g(z), we obtain that ∇g(z) can also be computed by a network of size O(V+E).
Note that by construction, ∇g(z)=∇2f(z)⋅v. Hence we have computed the Hessian vector product in network size time.
##That’s all!
Please write your comments on this exposition and whether it can be improved.
Spread the word: