D2.1 · LESSON 1 OF 6

Computation graphs

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

THE IDEA

Break the formula into small steps

Training a network means finding how the loss changes when each weight changes. Writing that out for a whole network at once is messy. Backpropagation avoids the mess by first splitting the computation into tiny operations (add, multiply, square, tanh) and recording how they connect. That record is a computation graph.

Each node stores its forward value and its immediate inputs, the nodes with an arrow straight into it. Inputs such as a and b are leaves: they have no inputs of their own.

Blue outlines are ready to compute. Click one.

order so far: none

The graph for L = (a·b + c)². Click nodes to compute them. A node can only be computed after its inputs, so the blue outlines show what is ready.

Predict first. For z = a*b + c, what are z's immediate inputs?

Sharing and counting

A value can feed more than one node: when a appears twice in a formula it has two arrows leaving it. The graph never loops back on itself, so there is always an order in which every node comes after its inputs. That order is what the forward pass follows and the next lessons reverse.

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

The graph is L = (a·b + a)². Compute it node by node, then answer questions about its structure.

Blue outlines are ready to compute. Click one.

order so far: none

Node that feeds two different nodes:

Edges in the graph:

To do: Compute every node of the graph, one click at a time, in an order the graph allows
To do: Tick the immediate inputs of the node q
To do: Which node feeds two different nodes?
To do: How many edges (arrows) does the whole graph have?

Part 2. Do it in code

A graph is a list of (name, op, inputs) tuples. The leaves are not in the list: they come in a dict of values. Write evaluate(graph, leaves) that returns a dict with the value of every leaf and every node. It must raise ValueError if a node uses a name that has no value yet (a graph listed in the wrong order).
Write inputs_of(graph, name): the immediate inputs of a node as a list (an empty list for a leaf).
Write users_of(graph, name): the names of the nodes that use `name` as an input, in graph order, each listed once even when it uses the value twice.

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,
}

# graph: list of (name, op, [input names]) in the order they can be computed
def evaluate(graph, leaves):
    pass

def inputs_of(graph, name):
    pass

def users_of(graph, name):
    pass

g = [("p", "mul", ["a", "b"]), ("z", "add", ["p", "c"])]
print(evaluate(g, {"a": 2, "b": 3, "c": 1}))   # z should be 7

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

For z=a*b+c, what are z's immediate inputs?

AThe two leaves a and b, because z depends on them.BOnly the product node a·b, because c is a constant.CThe product node a·b and the input c, because z = (a·b) + c is an add of those two.

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.