A First Taste of Algorithms

Lab 9: The Engine

✦ ✦ ✦

The capstone. You build backpropagation from nothing — sixty lines — verify it against the calculus by hand and against finite differences by machine, then train a tiny model end to end with your own engine to prove it is real. Then numpy arrives as the scale instrument, the name model trains until it speaks, and the parrot exam from Chapter 8 returns with teeth: you watch the training loss fall while the held-out loss begins to climb, and you name the moment they part. Everything in nine chapters has been parts on a workbench. This is the build.

1. The number that remembers

A plain number forgets its history. Build one that doesn’t — the Value, learned in pieces. Start with the skeleton and the two core operations:

import math, random

class Value:
    def __init__(self, data, parents=()):
        self.data = data
        self.grad = 0.0
        self._parents = set(parents)
        self._backward = lambda: None

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data + other.data, (self, other))
        def _backward():
            self.grad += out.grad
            other.grad += out.grad
        out._backward = _backward
        return out

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data * other.data, (self, other))
        def _backward():
            self.grad += other.data * out.grad
            other.grad += self.data * out.grad
        out._backward = _backward
        return out

a = Value(2.0)
b = Value(-3.0)
c = a * b
print(c.data, c._parents)

Value(2.0) builds a number-that-remembers; c = a * b builds a new one that remembers a and b as parents. The isinstance guard lets you write a + 1 (it wraps the bare 1 into a Value). Each operation’s _backward is a tiny function holding that operation’s derivative — addition passes blame whole, multiplication scales it by the other factor. Confirm c knows its parents before moving on.

2. The backward sweep

History recorded forward; now price it backward. The sweep is Chapter 5’s depth-first traversal, walked in reverse:

    def backward(self):
        order = []
        visited = set()
        def build(v):
            if v not in visited:
                visited.add(v)
                for parent in v._parents:
                    build(parent)
                order.append(v)
        build(self)
        self.grad = 1.0
        for v in reversed(order):
            v._backward()

Add this method inside the Value class (same indentation as __add__). Then the moment of truth — build a small expression, sweep, and check against calculus you can do by hand:

a = Value(2.0)
b = Value(-3.0)
c = Value(7.0)
L = (a * b + c) * (a * b + c)        # L = (ab + c)^2
L.backward()
print("L    =", L.data, "  (expect 1)")
print("a.grad =", a.grad, "  (expect -6)")
print("b.grad =", b.grad, "  (expect  4)")
print("c.grad =", c.grad, "  (expect  2)")

By hand: ab + c = 1, so L = 1; the outer square contributes 2·(ab+c) = 2; then ∂L/∂a = 2·b = −6, ∂L/∂b = 2·a = 4, ∂L/∂c = 2. The engine should agree exactly. It does — and you have just watched blame flow from one number out to three, through a graph the computation recorded itself.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses