How Back-Propagation Works · MLP Forward & Backward · Symbol-to-Symbol

§6.5.3 Recursively applying the chain rule

Writing down the gradient with the chain rule is easy; evaluating it efficiently is the whole game. The trap is repeated subexpressions. Take the book’s fig 6.9 — a chain $z = f(f(f(w)))$ — and expand the chain rule fully: $\frac{dz}{dw} = f'(f(f(w)))\, f'(f(w))\, f'(w)$ . Written this way, $f(w)$ is recomputed again and again; for a general graph the number of such repeats grows exponentially with depth. Back-propagation instead stores each intermediate gradient in a grad_table and reuses it — a table-filling dynamic-programming strategy that makes the cost proportional to the number of edges.

Watch it happen: a forward pass fills each node’s value, then the backward pass fills the gradients top-to-bottom, each step one Jacobian-gradient product:

Fig 6.9 (interactive) — back-propagation on z = f(f(f(w))), f(v) = v²: forward values, then the grad_table filling backward

w1.5

phase: ready · step 0/7

grad_table

∂z/∂w = ?

∂z/∂x = ?

∂z/∂y = ?

∂z/∂z = ?

Each backward step is one Jacobian-gradient product: the local derivative f′ times the gradient already stored downstream. Storing them (not recomputing) is what makes backprop O(edges) instead of exponential.

The two halves as algorithms — forward (algorithm 6.1) computes and stores every node; backward (algorithm 6.2) fills the gradient table in reverse:

Algorithms 6.1 + 6.2 — forward computation, then back-propagation (click lines)

1FORWARD: for i = 1…nᵢ: $u^{(i)} \leftarrow x_i$ (set the inputs)ⓘ
2for i = nᵢ+1…n: $u^{(i)} \leftarrow f^{(i)}(\mathbb{A}^{(i)})$ ⓘ
3BACKWARD: grad_table[ $u^{(n)}$ ] $\leftarrow 1$ ⓘ
4for j = n−1 down to 1:ⓘ
5grad_table[ $u^{(j)}$ ] $\leftarrow \sum_{i:\, j \in Pa(u^{(i)})}$ grad_table[ $u^{(i)}$ ] $\frac{\partial u^{(i)}}{\partial u^{(j)}}$ ⓘ
6return grad_table restricted to the inputsⓘ

§6.5.4 Back-propagation in a fully-connected MLP

For an actual network, the forward and backward passes take a particularly clean form. Forward (algorithm 6.3): march up the layers. Backward (algorithm 6.4): the gradient $\boldsymbol{g}$ flows down, and at each layer you read off the weight/bias gradients on the way:

Algorithm 6.3 — forward pass of a depth-l MLP

1 $\boldsymbol{h}^{(0)} = \boldsymbol{x}$ ⓘ
2for k = 1…l:ⓘ
3 $\boldsymbol{a}^{(k)} = \boldsymbol{b}^{(k)} + \boldsymbol{W}^{(k)}\boldsymbol{h}^{(k-1)}$ ⓘ
4 $\boldsymbol{h}^{(k)} = f(\boldsymbol{a}^{(k)})$ ⓘ
5 $\hat{\boldsymbol{y}} = \boldsymbol{h}^{(l)}, \quad J = L(\hat{\boldsymbol{y}}, \boldsymbol{y}) + \lambda\,\Omega(\boldsymbol{\theta})$ ⓘ

Algorithm 6.4 — backward pass (click lines)

1 $\boldsymbol{g} \leftarrow \nabla_{\hat{\boldsymbol{y}}} J = \nabla_{\hat{\boldsymbol{y}}} L(\hat{\boldsymbol{y}}, \boldsymbol{y})$ ⓘ
2for k = l, l−1, …, 1:ⓘ
3 $\boldsymbol{g} \leftarrow \nabla_{\boldsymbol{a}^{(k)}} J = \boldsymbol{g} \odot f'(\boldsymbol{a}^{(k)})$ ⓘ
4 $\nabla_{\boldsymbol{b}^{(k)}} J = \boldsymbol{g} + \lambda\nabla_{\boldsymbol{b}^{(k)}}\Omega,\quad \nabla_{\boldsymbol{W}^{(k)}} J = \boldsymbol{g}\,\boldsymbol{h}^{(k-1)\top} + \lambda\nabla_{\boldsymbol{W}^{(k)}}\Omega$ ⓘ
5 $\boldsymbol{g} \leftarrow \nabla_{\boldsymbol{h}^{(k-1)}} J = \boldsymbol{W}^{(k)\top}\boldsymbol{g}$ ⓘ

The rhythm of the backward pass

Each layer does three things in order: push the gradient through the nonlinearity ( $\odot f'$ ), harvest the weight/bias gradients (outer product with the stored activation), and propagate the gradient down one layer ( $\boldsymbol{W}^\top$ ). Its cost mirrors the forward pass — multiply by each $\boldsymbol{W}$ going up, by each $\boldsymbol{W}^\top$ going down: $O(w)$ compute; memory $O(m\, n_h)$ to hold the stored pre-activations.

§6.5.5 Symbol-to-symbol differentiation

Two ways to implement all this:

Term by term

\text{symbol-to-number} \quad\text{vs}\quad \text{symbol-to-symbol}

$\text{symbol-to-number}$	take the graph + numeric inputs, return numeric gradients (Torch, Caffe)	numbers out
$\text{symbol-to-symbol}$	add NEW NODES to the graph that symbolically describe the derivatives (Theano, TensorFlow, fig 6.10) — a generic engine evaluates them later for any numeric input	graph out
$\Rightarrow \text{higher-order}$	because the derivatives are themselves a graph, you can run back-propagation AGAIN on them — differentiating the derivatives to get Hessians etc. (§6.5.10)	the payoff

The symbol-to-symbol view subsumes symbol-to-number (it does the same computations, just without exposing the derivative graph). The next section formalizes the general algorithm — every operation supplying its own local bprop rule — and its cost: general back-propagation.

Check yourself — how back-propagation works

1.For z = f(f(f(w))), the naive chain-rule expansion recomputes f(w) many times. How does back-propagation avoid the exponential blowup?

2.In BackpropLab with w = 1.5, step through to the end. What is ∂z/∂w, and does it match the closed form?

3.In the MLP backward pass (algorithm 6.4), what three things does each layer do, in order?

4.Why does the forward pass STORE the pre-activation a⁽ᵏ⁾?

5.What does the symbol-to-symbol approach (Theano/TensorFlow) enable that symbol-to-number (Torch/Caffe) does not?

5 questions