The usual explanation of backpropagation (Rumelhart et al., 1986), the algorithm used to train neural networks, is that it is propagating errors for each node backwards. But when I first learned about the algorithm, I had a question that I could not find answered directly: why does it have to go backwards? A neural network is just a composite function, and we know how to compute the derivatives of composite functions using the chain rule. Why don’t we just compute the gradient in a forward pass? I found that answering this question strengthened my understanding of backprop.
I will assume the reader broadly understands neural networks and gradient descent and even has some familiarity with backprop. I’ll first setup backprop with some useful concepts and notation and then explain why a forward propagation algorithm is supoptimal.
Recall that the goal of backprop is to efficiently compute ∂f/∂θipartial f / partial theta_i∂f/∂θi for every weight θitheta_iθi in a neural network fff. To frame the problem, let’s reason about an arbitrary weight θ1theta_1θ1 and node vvv somewhere in fff:
To be clear, the node vvv refers to the output value of the node after passing the weighted sum of its inputs through an activation function σsigmaσ, i.e.:
u=θ1t1+θ2t2+⋯+θntnv=σ(u)
begin{aligned}
u &= theta_1 t_1 + theta_2 t_2 + dots + theta_n t_n \
v &= sigma(u)
end{aligned}
uv=θ1t1+θ2t2+⋯+θntn=σ(u)
Note that in a typical diagram, uuu, σsigmaσ, and vvv would all be a single node, denoted by the dashed line. In my mind, the most important observation needed to understand backprop is this: most of computing ∂f/∂θ1partial f / partial theta_1∂f/∂θ1 can be done locally at every node because of the chain rule:
∂f∂θ1=∂f∂v∂v∂u∂u∂θ1
frac{partial f}{partial theta_1} =
frac{partial f}{partial v}
frac{partial v}{partial u}
frac{partial u}{partial theta_1}
∂θ1∂f=∂v∂f∂u∂v∂θ1∂u
We can compute ∂v/∂upartial v / partial u∂v/∂u analytically; it just depends on the definition of σsigmaσ. And we know that ∂u/∂θ1=t1partial u / partial theta_1 = t_1∂u/∂θ1=t1. So at every node vvv, if we knew ∂f/∂vpartial f / partial v∂f/∂v, we could compute ∂f/∂θ1partial f / partial theta_1∂f/∂θ1.
The challenge with computing ∂f/∂vpartial f / partial v∂f/∂v is that downstream nodes depend on the value of vvv. Thankfully, the multivariable chain rule has the answer. Given a multivariable function g(w1,w2,…,wm)g(w_1, w_2, dots, w_m)g(w1,w2,…,wm) in which each wiw_iwi is a single variable function wi(v)w_i(v)wi(v), the multivariable chain rule says:
∂g∂v=∂∂vg(w1(v),w2(v),…,wm(v))=∑j∂g∂wj∂wj∂v
frac{partial g}{partial v} = frac{partial}{partial v} g(w_1(v), w_2(v), dots, w_m(v)) = sum_{j} frac{partial g}{partial w_j} frac{partial w_j}{partial v}
∂v∂g=∂v∂g(w1(v),w2(v),…,wm(v))=j∑∂wj∂g∂v∂wj
So we can compute ∂f/∂θipartial f / partial theta_i∂f/∂θi for any weight θitheta_iθi, meaning we have the necessary machinery to attempt to implement backprop in a forward rather than backward pass. Let’s see what happens.
We want a forward propagating algorithm that can compute the partial derivative ∂f/∂θipartial f / partial theta_i∂f/∂θi for an arbitrary weight θitheta_iθi. We showed above that at node vvv, this is equivalent to:
∂f∂θi=∂f∂v∂v∂θi
frac{partial f}{partial theta_i} =
frac{partial f}{partial v}
frac{partial v}{partial theta_i}
∂θi∂f=∂v∂f∂θi∂v
Note that I’ve dropped the intermediate variable uuu for ease of notation. To design our forward propagating algorithm, let’s formalize an important fact: in a directed computational graph in which node bbb depends upon node aaa, it is impossible to compute ∂b/∂apartial b / partial a∂b/∂a at any point before node bbb:
This claim should be obvious. If our computational graph represents a function f(a)=bf(a) = bf(a)=b, it is impossible to compute f′(a)f^{prime}(a)f′(a) without access to fff and therefore bbb.
In our setup, for every downstream node wjw_jwj that depends on a node vvv, it is impossible to compute ∂wj/∂vpartial w_j / partial v∂wj/∂v at node vvv. Therefore, in order to compute ∂f/∂vpartial f / partial v∂f/∂v, we must decompose the term using the multivariable chain rule and pass the other terms needed to compute ∂f/∂θipartial f / partial theta_i∂f/∂θi forward to each node wjw_jwj that depends on vvv:
∂f∂θi=(∑j∂f∂wj∂wj∂v⏟Compute on wj)∂v∂θi⏞Pass forward
frac{partial f}{partial theta_i} =
Big(
sum_{j} frac{partial f}{partial w_j}
underbrace{frac{partial w_j}{partial v}}_{text{Compute on $w_j$}}
Big)
overbrace{frac{partial v}{partial theta_i}}^{text{Pass forward}}
∂θi∂f=(j∑∂wj∂fCompute on wj∂v∂wj)∂θi∂vPass forward
We can see that such an algorithm blows up computationally because we’re forward propagating the same message many times over. For example, if we want to compute ∂f/∂θipartial f / partial theta_i∂f/∂θi and ∂f/∂θkpartial f / partial theta_k∂f/∂θk where θitheta_iθi and θktheta_kθk are different weights in the same layer, we need to compute ∂v/∂θipartial v / partial theta_i∂v/∂θi and ∂v/∂θkpartial v / partial theta_k∂v/∂θk separately, but all the other terms are repeated:
∂f∂θi=(∑j(∑k∂f∂zk∂zk∂wj)∂wj∂v)⏞Repeated terms∂v∂θi∂f∂θk=(∑j(∑k∂f∂zk∂zk∂wj)∂wj∂v)∂v∂θk
begin{aligned}
frac{partial f}{partial theta_i} =
overbrace{
Big(
sum_{j}
Big(
sum_{k}
frac{partial f}{partial z_k}
frac{partial z_k}{partial w_j}
Big)
frac{partial w_j}{partial v}
Big)}^{text{Repeated terms}}
color{#11accd}{
frac{partial v}{partial theta_i}
}
\
frac{partial f}{partial theta_k} =
Big(
sum_{j}
Big(
sum_{k}
frac{partial f}{partial z_k}
frac{partial z_k}{partial w_j}
Big)
frac{partial w_j}{partial v}
Big)
color{#bc2612}{
frac{partial v}{partial theta_k}
}
end{aligned}
∂θi∂f=(j∑(k∑∂zk∂f∂wj∂zk)∂v∂wj)Repeated terms∂θi∂v∂θk∂f=(j∑(k∑∂zk∂f∂wj∂zk)∂v∂wj)∂θk∂v
Here is a diagram of message passing the repeated terms:
I think the above diagram is the lynchpin in understanding why backprop goes backwards. This is the key insight: if we already had access to downstream terms, for example ∂wj/∂vpartial w_j / partial v∂wj/∂v, then we could message pass those terms backwards to node vvv in order to compute ∂f/∂vpartial f / partial v∂f/∂v. Since each node is just passing its own local term, the backward pass could be done in linear time with respect to the number of nodes.
I hope this explanation it clarifies how you might get to backprop from first principles trying to compute derivatives in a directed acyclic graph. On a given node bbb that depends on a node aaa, we simply message pass ∂b/∂apartial b / partial a∂b/∂a back to aaa. The multivariable chain rule helps prove the correctness of backprop. For any node vvv with downstream weights wjw_jwj, if vvv simply sums the backwardly propagating messages, it computes its desired derivative:
∂f∂v=∑j∂f∂wj∂wj∂v
frac{partial f}{partial v} = sum_{j} frac{partial f}{partial w_j} frac{partial w_j}{partial v}
∂v∂f=j∑∂wj∂f∂v∂wj
Once you understand the main computational problem backprop solves, I think the standard explanation of backpropagating errors makes much more sense. This process is can be viewed as a solution to a kind of credit assignment problem: each node tells its upstream neighbors what they did wrong. But the reason the algorithm works this way is because a naive, forward propagating solution would have quadratic runtime in the number of nodes.
Source: Hacker News
You must be logged in to post a comment.