D2.3 · LESSON 3 OF 6

Reverse accumulation

Apply the chain rule through a graph and implement the core of a scalar reverse-mode autodiff engine.

THE IDEA

Start at the output and walk backwards

The loss changes one-for-one with itself, so the backward pass starts with ∂L/∂L = 1. Going backwards, each node multiplies the gradient it received by its local derivatives and passes the results on. Multiplying along a path is the chain rule.

A value that affects the loss along more than one path receives a contribution from each path, and the contributions are added. This is the most common source of mistakes when doing backpropagation by hand.

x feeds the add node twice. Each edge carries local derivative 1 × upstream 1 = 1. The gradient of x is the SUM of both: 1 + 1 = 2. (Check: x + x = 2x, whose slope is 2.)

Same idea, two graphs. In x + x the single input is used twice, so its gradient is 1 + 1. In a·b + a·c the input a collects a share from each product.

Predict first. If x is used twice in x + x, what is the derivative of the output with respect to x?

Reading the numbers

A gradient of zero does not mean the input is unimportant in general. It means that at this point a small change does nothing, for instance because a multiplying weight is zero or because the upstream gradient is zero.

Chapter context

Backpropagation organizes repeated applications of the chain rule. The graph stores how values depend on earlier values. Reverse traversal accumulates how the final loss changes with each intermediate quantity.

TRY IT YOURSELF

Part 1. Do it hands-on

Move the inputs and watch the gradients (orange) change. Set them so the gradients take the values the tasks describe.

Graph 1: L = (w·x + b − y)²

w2x3b1y5

Graph 2: L = (a·b + a)²

a2b3

To do: Make the loss exactly 0. What happens to all four gradients?
To do: Set the inputs so that ∂L/∂b is exactly −6
To do: Make ∂L/∂x equal to 0 while ∂L/∂w is not 0
To do: Make ∂L/∂w equal to −2 times ∂L/∂b, with ∂L/∂b not 0
To do: On the second graph, L = (a·b + a)², make ∂L/∂a equal to 8
To do: Make ∂L/∂a equal to 0 although a is not 0

Part 2. Do it in code

evaluate and local_grads are given. Write backward(graph, values, out): return a dict with the gradient d(out)/d(name) for EVERY name in values (leaves and nodes). The gradient of out is 1.
Walk the graph from the last node to the first. For each node send upstream * local to each input and ADD it to what the input already holds (an input can be used more than once).
A leaf that is not used by the output must get 0.0. Calling backward twice must give the same answer twice (build a fresh dict each time).

import math

OPS = {
    "add": lambda a, b: a + b,
    "sub": lambda a, b: a - b,
    "mul": lambda a, b: a * b,
    "div": lambda a, b: a / b,
    "sq": lambda a: a * a,
    "tanh": lambda a: math.tanh(a),
    "relu": lambda a: a if a > 0 else 0.0,
    "neg": lambda a: -a,
}

def local_grads(op, args):
    if op == "add":
        return (1.0, 1.0)
    if op == "sub":
        return (1.0, -1.0)
    if op == "mul":
        a, b = args
        return (b, a)
    if op == "div":
        a, b = args
        return (1.0 / b, -a / (b * b))
    if op == "sq":
        return (2.0 * args[0],)
    if op == "tanh":
        t = math.tanh(args[0])
        return (1.0 - t * t,)
    if op == "relu":
        return (1.0 if args[0] > 0 else 0.0,)
    if op == "neg":
        return (-1.0,)

def evaluate(graph, leaves):
    vals = dict(leaves)
    for name, op, ins in graph:
        vals[name] = OPS[op](*[vals[i] for i in ins])
    return vals

def backward(graph, values, out):
    # graph is in forward order. Return {name: d(out)/d(name)}
    pass

g = [("p", "mul", ["a", "b"]), ("u", "add", ["p", "c"]), ("L", "sq", ["u"])]
vals = evaluate(g, {"a": 2.0, "b": 3.0, "c": 1.0})
print(backward(g, vals, "L"))   # a: 42, b: 28, c: 14

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

If x is used twice in x+x, what is the total derivative?

AOne, because x + x has a single path to the output.BZero, because the two uses cancel each other.CTwo, because both paths contribute: 1 from each use of x, added together.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

If $u=ab+c$ and $L=u^2$ , then

\frac{\partial L}{\partial a}=2ub,\quad \frac{\partial L}{\partial b}=2ua,\quad \frac{\partial L}{\partial c}=2u.

At a shared node x, add all downstream contributions: $\partial L/\partial x=\sum_j(\partial L/\partial u_j)(\partial u_j/\partial x)$ .

Worked example

Take a=2,b=3,c=1. Then u=7 and L=49. The upstream gradient into u is 14, giving dL/da=14×3=42, dL/db=14×2=28 and dL/dc=14. These are sensitivities, not new parameter values; an optimizer still needs a step size.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
a,b,c = 2.,3.,1.
u = a*b+c
assert u*u == 49
assert (2*u*b,2*u*a,2*u) == (42,28,14)
h = 1e-5
f = lambda x: (x*b+c)**2
assert isclose((f(a+h)-f(a-h))/(2*h), 42, rel_tol=1e-7)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Forward values and gradients are different objects. Shared branches require addition of gradient contributions. Backpropagation computes derivatives; the optimizer changes parameters.