Lesson 10 · Part II · Autograd on single numbers

The order of blame

In what order must the graph be visited?

~40 min · 1 lab · builds on 09 Many paths, one sum

This lesson builds on lessons 01–09. New here? Start at lesson 01, or carry on and load the finished pieces with one click.

$c = a \cdot a + a$ at a = 3. After backward, what is a.grad?

The product sends 3 to each of its two uses of a, and the sum sends 1: 3 + 3 + 1 = 7.

x is a Value holding 2.0, and you write y = x * 3. What does y record in _prev and _op?

Nothing extra: y holds 6.0, and that is enough to go backward

6.0 alone can't say where it came from: 2 · 3 and 1.5 · 4 both make it.

x and a new Value holding 3.0, and '*'

The plain 3 is wrapped in a Value first, so both parents are Values that a gradient can reach.

The numbers 2.0 and 3.0, and '*'

Numbers can't receive a gradient or lead any further back, so _prev keeps Values.

_prev holds x and the wrapped 3.0, and _op is '*'. Today's question is the order in which backward visits such records.

Who goes first?

Each _backward now adds its share into its inputs' gradients, so a Value used several times collects every share.

So far you called each _backward by hand, in an order you picked. A model has thousands of Values, so a program has to pick the order. Which order is safe?

A small graph:

w = Value(2.0)
x = w * w
e = x * 3
d = e * 2
c = x + d

Walk back from c breadth-first (c, then its parents, then theirs) and run each node's _backward the first time you reach it. What is w.grad at the end? Nudging says the true slope is 28.

28: every node is visited, so every share arrives

Every node is visited, but x too early: its backward runs while x.grad holds only the 1 that came straight from c. The 6 that comes through d arrives after x has passed its gradient on.

4: x passes its gradient on before the share through d and e arrives

x's backward runs with x.grad = 1, sending 2 · 2 · 1 = 4 to w, and never runs again.

32: x is reached by two paths, so its backward runs twice

Running twice would send 4 when x holds 1, then 28 when it holds 7, and 4 + 28 counts the first share twice. The walk marks each node as seen and never queues it again, so x's backward runs once, too early.

4. x is reached first straight from c, and its backward runs before e has sent x its share of 6. x ends up holding 7, but it passed its gradient on to w while it held only 1, so w holds 4. A node may pass gradient on only after every node that uses it has finished. The cell below runs the walk: breadth-first gives w.grad = 4.0 where nudging says 28.0.

Breadth-first backward on the graph above, next to the nudged slope.

from collections import deque
import hx
from ember.scalar import Value


def breadth_first_backward(root):
    """Visit nodes nearest the output first; run each node's _backward the first time it is reached."""
    root.grad = 1.0
    seen, queue = {id(root)}, deque([root])
    while queue:
        node = queue.popleft()
        node._backward()
        for parent in node._prev:
            if id(parent) not in seen:
                seen.add(id(parent))
                queue.append(parent)


w = Value(2.0)
x = w * w
e = x * 3
d = e * 2
c = x + d
for v, name in [(w, "w"), (x, "x"), (e, "e"), (d, "d"), (c, "c")]:
    v.label = name
breadth_first_backward(c)
print(f"breadth-first: w.grad = {w.grad}")
hx.show_graph(c)


def c_of(w):
    """The same graph on plain floats: c as a function of w alone."""
    x = w * w
    return x + (x * 3) * 2


nudged = (c_of(2.001) - c_of(2.0)) / 0.001
print(f"nudging w by 0.001: slope {nudged:.1f}")

breadth-first: w.grad = 4.0
nudging w by 0.001: slope 28.0

The graph after the breadth-first walk, each node with its value and the gradient it collected. The two unnamed nodes are the plain 3 and 2, each wrapped in a Value.

node	op	forward value	gradient
#0	input	2	12
#1	input	3	8
w	input	2	4
x	*	4	7
e	*	12	2
d	*	24	1
c	+	28	1

Users before the used

The rule: run a node's _backward only after every node that uses it has run, so that its gradient is complete before it passes anything on. An order of a graph's nodes in which every node comes after the nodes it was made from is called a topological order. Backward runs one in reverse: users before the used.

Put the nodes of the graph in an order that runs every _backward correctly: each node only after every node that uses it.

c, d, e, x, w, and here it is the only order: x is used by c and by e, so x waits for both, and e waits for d.

A program finds a topological order by depth-first search. Start at the output. Before you add a node to the list, visit each of its parents, so a node goes in only once all of its parents are in. The list then runs from the leaves to the output, and reversed it is a safe backward order. Written as a function that calls itself, it is only a few lines long. Run it on a long chain.

The recursive depth-first order on a chain of 100 additions, then 5000.

from ember.scalar import Value


def order_recursive(node, seen, order):
    if id(node) in seen:
        return
    seen.add(id(node))
    for parent in node._prev:
        order_recursive(parent, seen, order)
    order.append(node)


for length in [100, 5000]:
    out = Value(1.0)
    for _ in range(length):
        out = out + 1.0
    try:
        order = []
        order_recursive(out, set(), order)
        print(f"chain of {length} additions: ordered {len(order)} nodes")
    except RecursionError:
        print(f"chain of {length} additions: RecursionError (Python ran out of stack)")

chain of 100 additions: ordered 201 nodes
chain of 5000 additions: RecursionError (Python ran out of stack)

A chain of 100 additions is fine, and its order holds every added 1.0 too, each wrapped in a Value of its own. A chain of 5000 raises RecursionError: every nested call is a frame on Python's stack, and Python stops at about 1000, its recursion limit. A recurrent network unrolled over a long text is deeper than that, so the walk keeps its own stack in a list instead.

What: write Value.backward(): build a topological order of every Value this one depends on with an explicit stack (no recursion), set this Value's grad to 1, and run each node's _backward from the output back to the leaves.

Why: without it you call every _backward by hand, in an order you work out yourself. From here on nobody does. Lesson 12's training loop calls loss.backward() once per step, and lesson 14 rebuilds this walk for tensors.

Your ember backpropagates any graph with one call.

Recursive depth-first search appends a node after all its parents are done. How can a list used as a stack, holding (node, parents_done) pairs, do the same without recursion?
Push (self, False). Pop a pair: if its flag is True, append the node to the order; otherwise, if the node is new, mark it seen, push (node, True), then push (parent, False) for each parent. Then set self.grad = 1.0 and call _backward on each node of reversed(order).
Nearly the code: order, seen, stack = [], set(), [(self, False)]; while stack: node, done = stack.pop(); ... then self.grad = 1.0 and for node in reversed(order): node._backward().

L.backward() gives every gradient of L = (z - 3)^2 with z = w*x + b.
After y.backward(), y.grad is 1.0.
x reaches c directly and through d, so x's backward must wait for both shares.
backward() handles a chain of 5,000 additions without a RecursionError.
In a * a * a, a's gradient is 3a^2, counted once per use.
For d = (a + 1) * (3a) the gradient is 6a + 3.

"""Part II: Value, a number that remembers how it was made (the scalar autograd engine).""" from collections.abc import Callable # A type hint that names Value is written in quotes, "Value": this def runs before class Value # exists, and inside the class the name is not ready until the class body ends. Python keeps a # quoted hint as text instead of looking the name up. Value | float means a Value or a plain # number, and tuple["Value", ...] is a tuple of Values of any length. def _as_value(x: "Value | float") -> "Value": """A Value for x: x itself when it already is one, else a new leaf Value holding the number. Args: x: A Value, or a plain number such as 2 or 0.5. Returns: x itself when it is a Value, else a new leaf Value whose data is x as a float. """ if isinstance(x, Value): return x return Value(x) class Value: """A number that remembers the Values it was made from (_prev) and the operation (_op). Attributes: data: The number, as a float. grad: How much the final result (such as a loss) changes for each unit that data grows; 0.0 until a backward pass fills it in. _prev: The Values this one was made from, its parents, as a tuple; () for a leaf. _op: The symbol of the operation that made this Value, such as "+"; "" for a leaf. _backward: Passes this Value's grad back to its parents. It does nothing for a leaf, or for a Value whose operation has no backward yet. """ def __init__(self, data: float, _children: tuple["Value", ...] = (), _op: str = "") -> None: """Make a Value holding data. Args: data: The number, such as 2 or 0.5; it is kept as a float. _children: The Values this one was made from, its parents; () for a leaf. _op: The symbol of the operation that made it, such as "+"; "" for a leaf. """ # --- gap L07.init --- self.data = float(data) self.grad = 0.0 self._prev = tuple(_children) self._op = _op # --- end --- self._backward: Callable[[], None] = lambda: None def __repr__(self) -> str: """How print shows a Value: its data and its grad. Returns: Text such as Value(2.0, grad=0.0). """ # --- gap L07.repr --- return f"Value({self.data!r}, grad={self.grad!r})" # --- end --- def __add__(self, other: "Value | float") -> "Value": """self + other, as a new Value. Args: other: A Value, or a plain number such as 2. Returns: A new Value holding the sum, with self and other (as a Value) as its parents and "+" as its operation. From lesson 08 on, a backward pass sends the result's grad back to each parent, times that parent's local slope; from lesson 09 on, an input used twice, as in a + a, ends up with both shares. """ # --- gap L07.add --- other = _as_value(other) out = Value(self.data + other.data, (self, other), "+") # --- end --- # --- gap L09.add_backward --- def _backward(): self.grad += out.grad other.grad += out.grad out._backward = _backward # --- end --- return out def __mul__(self, other: "Value | float") -> "Value": """self * other, as a new Value. Args: other: A Value, or a plain number such as 2. Returns: A new Value holding the product, with self and other (as a Value) as its parents and "*" as its operation. From lesson 08 on, a backward pass sends the result's grad back to each parent, times that parent's local slope; from lesson 09 on, an input used twice, as in a * a, ends up with both shares. """ # --- gap L07.mul --- other = _as_value(other) out = Value(self.data * other.data, (self, other), "*") # --- end --- # --- gap L09.mul_backward --- def _backward(): self.grad += other.data * out.grad other.grad += self.data * out.grad out._backward = _backward # --- end --- return out # Lesson 07 gives these five forward only; lesson 09 rebuilds them from + and *. def __neg__(self) -> "Value": """-self, as a new Value. Returns: A new Value holding minus this Value's data. From lesson 09 on, a backward pass also reaches this Value through it: its grad gets -1 per unit of the result's grad. """ # --- gap L09.neg --- return self * -1 # --- end --- def __sub__(self, other: "Value | float") -> "Value": """self - other, as a new Value. Args: other: A Value, or a plain number such as 2. Returns: A new Value holding the difference. From lesson 09 on, a backward pass also reaches both sides through it: per unit of the result's grad, self gets 1 and other, when it is a Value, gets -1. """ # --- gap L09.sub --- return self + (-other) # --- end --- def __rsub__(self, other: "Value | float") -> "Value": """other - self, when the left side is a plain number, as in 2 - a. Args: other: The left side of the minus, a plain number such as 2. Returns: A new Value holding the difference. From lesson 09 on, a backward pass also reaches this Value through it: its grad gets -1 per unit of the result's grad. """ # --- gap L09.rsub --- return other + (-self) # --- end --- def __radd__(self, other: "Value | float") -> "Value": """other + self, when the left side is a plain number, as in 2 + a. Args: other: The left side of the plus, a plain number such as 2. Returns: A new Value holding the sum. From lesson 09 on, a backward pass also reaches this Value through it: its grad gets 1 per unit of the result's grad. """ # --- gap L09.radd --- return self + other # --- end --- def __rmul__(self, other: "Value | float") -> "Value": """other * self, when the left side is a plain number, as in 2 * a. Args: other: The left side of the times, a plain number such as 2. Returns: A new Value holding the product. From lesson 09 on, a backward pass also reaches this Value through it: its grad gets other per unit of the result's grad. """ # --- gap L09.rmul --- return self * other # --- end --- # Lesson 07 gives division forward only; lesson 11 rebuilds it from * and **. def __truediv__(self, other: "Value | float") -> "Value": """self / other, as a new Value. Args: other: A Value, or a plain number such as 2; not 0. Returns: A new Value holding the quotient. Raises: ZeroDivisionError: If other is 0. """ other = _as_value(other) return Value(self.data / other.data, (self, other), "/") def __rtruediv__(self, other: "Value | float") -> "Value": """other / self, when the left side is a plain number, as in 2 / a. Args: other: The left side of the division, a plain number such as 2. Returns: A new Value holding the quotient. Raises: ZeroDivisionError: If this Value's data is 0. """ other = _as_value(other) return Value(other.data / self.data, (other, self), "/") def __pow__(self, exponent: float) -> "Value": """self ** exponent, as a new Value. The exponent is a plain number, never a Value. Args: exponent: An int or a float, such as 2 or -1. Returns: A new Value holding this Value's data to the power exponent, with this Value as its parent and "**" followed by the exponent, such as "**2", as its operation. Raises: TypeError: If exponent is not an int or a float (for example a Value), or if data is negative and exponent is not a whole number. ZeroDivisionError: If this Value's data is 0 and exponent is negative. OverflowError: If the result is too large for a float. """ if not isinstance(exponent, (int, float)): raise TypeError("Value ** needs an int or float exponent, not a Value") # Forward only until lesson 11 gives ** its backward. return Value(self.data ** exponent, (self,), f"**{exponent}") def backward(self) -> None: """Fill in .grad on every Value this one depends on: order the graph so that every node comes after its inputs (with an explicit stack, never recursion), seed this Value's grad with 1.0, then run each node's _backward from this Value back to the leaves.""" # --- gap L10.backward --- raise NotImplementedError("Order the graph with an explicit stack, seed self.grad = 1.0, then run each _backward from the output back.") # --- end ---Running code needs JavaScript. Above is ember/scalar.py as this lab starts.

Your backward() on the breadth-first graph and on the 5000-step chain.

import hx
from ember.scalar import Value

w = Value(2.0)
x = w * w
e = x * 3
d = e * 2
c = x + d
for v, name in [(w, "w"), (x, "x"), (e, "e"), (d, "d"), (c, "c")]:
    v.label = name
c.backward()
print(f"backward(): w.grad = {w.grad}")
hx.show_graph(c)

v = Value(1.0)
out = v
for _ in range(5000):
    out = out + 1.0
out.backward()
print(f"chain of 5000 additions: v.grad = {v.grad}")

backward(): w.grad = 28.0
chain of 5000 additions: v.grad = 1.0

Your backward() gives w.grad = 28.0, the nudged slope, and v.grad = 1.0 at the start of the 5000-step chain, with no recursion to run out of.

The same graph after your backward(). x collects 1 from c and 6 through e before it passes anything on, and w, used twice by x, receives 2 · 7 = 14 from each use: 28.

node	op	forward value	gradient
#0	input	2	12
#1	input	3	8
w	input	2	28
x	*	4	7
e	*	12	2
d	*	24	1
c	+	28	1

Suppose you had kept a list of every Value of this graph in the order it was made. Would running each one's _backward from the end of that list, newest first, also work? Why?

No: the order Values were created in has nothing to do with the graph

It has everything to do with it: a Value can only be made from Values that already exist.

Only if no Value is used twice

Shared Values are exactly why order matters, and newest-first still visits every user of x before x.

Yes: every Value is created after its inputs, so newest-first visits every user of a Value before the Value itself

A Value can only be made from Values that already exist, so each parent is older than every Value made from it.

Yes: creation order is already a topological order. backward() sorts because all it is handed is the output, not the history of when each Value was made.

Where this goes

Your engine backpropagates any graph built from + and *. Lesson 11 adds powers, exp, log, tanh and relu, and a way to prove each backward right.

When you finish this lesson

Your ember can now: backpropagate through any graph with one call to backward()

It already could:

get the right gradient for a value used in many places
send a gradient backward through + and *
record how every number was made, and draw it as a graph

Next Trust, but verify · How do you know your derivative is right? · ~45 min

Continue

Previous 09 Many paths, one sum Next 11 Trust, but verify How do you know your derivative is right?

Report a problem with this lesson