A First Taste of Algorithms

Chapter 9: Building the Learner

✦ ✦ ✦

In which eight chapters return as parts on a workbench, and the machine is assembled, and it speaks

The one missing piece

Chapter 8 left you holding the whole idea of learning and one unpaid bill. A model is a formula with knobs; training steps every knob downhill on the loss; the step direction is the gradient, a slope per knob. On the bowl, one knob, you computed that slope by hand — f′(x) = 2x. But a real model has not one knob but thousands, even billions, wired through layers of multiplication and squashing, and the loss is a single number sitting at the far end of that wiring. The bill: how do you get the slope with respect to every knob at once, when the knobs are buried a dozen operations deep?

Computing each slope separately is hopeless — billions of knobs, each needing its own derivative through the whole tangle. There has to be a way to get them all in one sweep. There is, and it is the most important algorithm in this book that you have not yet met: backpropagation. By the end of this chapter you will not have read about it. You will have built it — sixty lines, from nothing — and then used it to assemble a working learner that generates names of mathematicians who never existed but plausibly could have. The parts are all already on your workbench, made in earlier chapters. This chapter is assembly.

And the first part requires the one Python tool this book has deliberately withheld for nine chapters.

A number that remembers how it was made

Here is the problem that forces the new tool. To push blame backward through the wiring, each number in the computation must remember three things: its value, the other numbers it was built from, and how to pass blame to them. A plain Python number — 3.0 — remembers only its value. It has forgotten its parents and its history. We need a number that doesn’t forget.

A thing that bundles data together with behavior — a value, its parents, and a rule — is an object, and the tool for minting objects is class. This is why classes waited: not because they are advanced, but because nothing earlier needed them, and a tool introduced before its need is a tool half-understood. Backpropagation needs them. Here is the whole tool, learned on the smallest possible example:

class Value:
    def __init__(self, data, parents=()):
        self.data = data          # the number itself
        self.grad = 0.0           # blame, filled in later by backprop
        self._parents = set(parents)
        self._backward = lambda: None   # how to pass blame to parents

    def __add__(self, other):     # teaches Python what  a + b  means for Values
        out = Value(self.data + other.data, (self, other))
        def _backward():
            self.grad += out.grad     # addition passes blame through unchanged
            other.grad += out.grad
        out._backward = _backward
        return out

Read class as a factory. Value(3.0) builds one number-that-remembers; self is the object being built, and self.data, self.grad, self._parents are the three things it carries. The strange-looking __add__ is Python’s hook for the + symbol: define it, and a + b for two Values produces a new Value that remembers its two parents — so the act of computing silently records its own history. (You met this idea of a process recording its history once before: Chapter 3’s call stack, the machine remembering paused work. Here the computation remembers its construction.)

The line that matters most is inside _backward: when addition’s output receives blame (out.grad), it passes that blame to both parents unchanged. Why unchanged? Because if a + b nudges up by a hair, both a and b contributed exactly that hair — Book 2’s derivative of a sum. Every operation knows its own blame-rule, and the rule is just its derivative. Multiplication’s rule:

    def __mul__(self, other):
        out = Value(self.data * other.data, (self, other))
        def _backward():
            self.grad += other.data * out.grad   # blame scaled by the OTHER factor
            other.grad += self.data * out.grad
        out._backward = _backward
        return out

Multiplication passes blame scaled by the other factor — because if a·b and you wiggle a, the output moves by b times the wiggle (Book 2 again: the derivative of a·b with respect to a is b). That is the entire secret of backpropagation, hiding in plain sight: each operation, when built, tucks away a tiny function that knows how to pass blame to its parents, and that function is nothing but the operation’s derivative. Add a few more operations the same way — powers, tanh for squashing, exp and log for probabilities — each three lines, each just its derivative, and the engine is nearly done.

Figure 9.1 — A number that remembers how it was made: the graph of L = (a·b + c)², each node carrying its forward value and, after the backward sweep, its share of the blame. Chapter 5’s graph, now the substrate of calculus.

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