Lesson 06 · Part I · Why learning works at all

The bill for nudging

10,000 knobs: how many forward passes for one gradient?

~30 min · 1 lab · builds on 05 Bending space

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

$2(3x - 1) + 5$ is a straight line. What is its slope?

$2(3x - 1) + 5 = 6x + 3$ , so the slope is 2 · 3 = 6: the slopes multiply.

Gradient descent on some loss prints 4, 9, 20 and 45 over four steps. What is the most likely fix?

A bigger learning rate, to get over the hump faster

A bigger step overshoots further, so the loss would grow faster still.

A smaller learning rate: each step overshoots the valley by more than the last

A loss that grows faster at every step is the signature of steps that jump past the bottom.

More steps: it hasn't settled yet

Each step makes the next one bigger, so more steps only take it further away.

Shrink the learning rate. A loss that grows at every step is overshooting, and it will not settle by itself.

Nine knobs, then a million

Your two_layer network solves XOR once gradient_descent has tuned its nine knobs. It found each knob's slope by nudging that knob and measuring the loss again.

Nine knobs is nothing. A small image classifier has about a million, and a language model has billions. How much does one set of slopes cost?

To measure every partial slope by nudging, you measure the loss once where you stand, then once more with each knob nudged in turn. A model has 10,000 knobs. How many forward passes (evaluations of the loss) is that?

10,001: one where you stand, and one per knob. The bill grows in step with the number of knobs.

One forward pass of a model with 1,000,000 knobs takes 1 millisecond. How long does one nudged gradient take?

About a second: computers do a million of anything quickly

A million simple additions, yes. This is a million forward passes of the whole model, 1 ms each.

About 17 minutes: a million and one passes of 1 ms each

1,000,001 · 1 ms is about 1,000 seconds, and that buys one step; training takes thousands of steps.

About 2 ms: one pass where you stand, one with every knob nudged

Nudge all the knobs together and the loss changes once: you learn how their combined effect moved, not which knob did what.

About 17 minutes for a single step of training. Nudging is exact enough and far too slow.

Count it. numerical_derivative measures the loss twice for each knob, once where you stand and once nudged. Wrap the loss in a counter and ask for every slope, one knob at a time.

Count the loss calls that one set of slopes costs, for 1, 10, 100 and 1,000 knobs.

from ember.basics import numerical_derivative

for n in [1, 10, 100, 1000]:
    calls = 0

    def loss(knobs):
        global calls
        calls += 1
        return sum((k - 1.0) ** 2 for k in knobs)

    knobs = [0.0] * n
    for i in range(n):
        numerical_derivative(lambda v: loss(knobs[:i] + [v] + knobs[i + 1:]), knobs[i])
    print(f"{n:>5} knobs: {calls:>5} loss calls for one set of slopes")

    1 knobs:     2 loss calls for one set of slopes
   10 knobs:    20 loss calls for one set of slopes
  100 knobs:   200 loss calls for one set of slopes
 1000 knobs:  2000 loss calls for one set of slopes

For 1,000 knobs that is 2,000 loss calls for one set of slopes: two per knob, because each nudge also re-measures where you stand.

Every slope at once

The list of every partial slope of the loss has a name, the gradient, and a new symbol, $\nabla L$ , read "grad L". Measured by nudging, a method called finite differences, the slopes can share one measurement, the loss where you stand, which brings the bill for n knobs to $n + 1$ passes. The gradient points uphill, the way the loss grows fastest, so gradient descent steps against it.

The gradient is the list of all the partial slopes: $\nabla L = [\,\frac{\partial L}{\partial w_1},\ \frac{\partial L}{\partial w_2},\ \ldots\,]$ For $L = 3 w_1 - 2 w_2 + 5$ , nudging $w_1$ from 1 to 1.01 at $w_2$ = 1 moves L from 6 to 6.03, a slope of 3. Nudging $w_2$ from 1 to 1.01 at $w_1$ = 1 moves L from 6 to 5.98, a slope of −2. So $\nabla L = [3, -2]$ everywhere.

$L = 4 w_1 - w_2 + 2 w_3 + 7$ . What is $\frac{\partial L}{\partial w_3}$ ?

2: raising $w_3$ by 1 raises L by 2, whatever the other knobs are. The whole gradient is [4, −1, 2].

What: write numerical_gradient(f, params, h): measure f once at params, then once per parameter with only that one nudged by h; return the list of slopes and the number of calls to f.

Why: without it you can't see what a gradient costs, or check a faster one. It is the honest, slow way to get a gradient. Lessons 07 to 10 build backpropagation to replace it, and lesson 11 turns it into the checker that proves backpropagation right.

Your ember can measure a whole gradient, and it knows the bill.

Measure the loss where you stand once, and keep it. For each parameter, what changes between that measurement and the nudged one?
base = f(params). For each i, copy params, add h to position i, measure, and the slope is (nudged - base) / h. The count is one call for base plus one per parameter.
Nearly the code: base = f(params); a loop that appends (f(moved) - base) / h; then return grads, len(params) + 1.

The gradient of p0^2 + p1^2 + p2^2 at [1, -2, 3] is about [2, -4, 6].
Three knobs cost four calls to f: one at params, one per nudged knob.
The reported count equals the number of times f really ran.
Nudging happens on copies: the list passed in is unchanged afterwards.
With h = 0.5, f = p0^2 at [1] gives (2.25 - 1) / 0.5 = 2.5 in two calls.
For sin(p0) at 0.3 the gradient is about cos(0.3).

"""Part I: learning with plain Python numbers and lists (no NumPy, no framework yet).""" import math from collections.abc import Callable, Sequence # The type hints after a parameter (x: float) and after -> say what a function takes and # returns. Python does not check them. # Sequence[float] is a list or a tuple of numbers, and Callable[[float], float] is a function # that takes one number and returns one. def predict_line(x: float, w: float, b: float) -> float: """The line's prediction at x: the slope w times x, plus the intercept b. Args: x: The input, such as a ride's distance in km. w: The slope: how much the prediction grows for each unit of x. b: The intercept: the prediction at x = 0. Returns: The prediction for x, a number in the units of the targets. """ # --- gap L01.predict_line --- return w * x + b # --- end --- def mse(ys: Sequence[float], preds: Sequence[float]) -> float: """Mean squared error: the average of (y - pred) squared over the pairs. Args: ys: The targets; at least one. preds: The predictions, one per target (same length as ys): preds[i] goes with ys[i]. Returns: The loss: 0.0 when every prediction equals its target, and never negative. Raises: ZeroDivisionError: If ys is empty. """ # --- gap L02.mse --- return sum((y - p) ** 2 for y, p in zip(ys, preds)) / len(ys) # --- end --- def mae(ys: Sequence[float], preds: Sequence[float]) -> float: """Mean absolute error: the average of |y - pred| over the pairs. Args: ys: The targets; at least one. preds: The predictions, one per target (same length as ys): preds[i] goes with ys[i]. Returns: The loss: 0.0 when every prediction equals its target, and never negative. Raises: ZeroDivisionError: If ys is empty. """ # --- gap L02.mae --- return sum(abs(y - p) for y, p in zip(ys, preds)) / len(ys) # --- end --- def grid_search( xs: Sequence[float], ys: Sequence[float], ws: Sequence[float], bs: Sequence[float], loss: Callable[[Sequence[float], Sequence[float]], float], ) -> tuple[float, float]: """Try the line of every pair (w, b) from ws and bs and return the pair (w, b) whose predictions get the lowest loss(ys, preds). On a tie the pair tried first wins (ws is the outer loop). Args: xs: The inputs. ys: The targets, one per input (same length as xs). ws: The slopes to try; at least one. bs: The intercepts to try; at least one. loss: A score for one line, such as mse or mae: loss(ys, preds) takes the targets and that line's predictions for xs, in order, and returns a number; lower is better. Returns: The best pair (w, b), with w taken from ws and b from bs. """ # --- gap L02.grid_search --- best, best_loss = None, None for w in ws: for b in bs: value = loss(ys, [predict_line(x, w, b) for x in xs]) if best_loss is None or value < best_loss: best, best_loss = (w, b), value return best # --- end --- def numerical_derivative(f: Callable[[float], float], x: float, h: float = 1e-6) -> float: """The slope of f at x, measured by nudging x forward by h: (f(x + h) - f(x)) / h. Args: f: A function that takes one number and returns one number. x: Where to measure the slope. h: The size of the nudge: small, and not 0. Returns: The measured slope: about how much f changes for each unit that x grows, near x. Raises: ZeroDivisionError: If h is 0. """ # --- gap L03.numerical_derivative --- return (f(x + h) - f(x)) / h # --- end --- def gradient_descent( f: Callable[[list[float]], float], params: list[float], lr: float, steps: int, h: float = 1e-6, ) -> tuple[list[float], list[float]]: """Walk downhill on f, a function of a list of knobs. Each step measures every knob's partial slope with numerical_derivative (nudge that knob, hold the others still), and only then moves every knob by -lr times its slope. Returns (the final knobs as a new list, the losses), where losses holds f before the first step and after every step (steps + 1 numbers). Args: f: The loss: takes a list of knobs, as many as params holds, and returns a number. params: The knobs to start from. The caller's list is not changed. lr: The learning rate, usually small and positive, such as 0.01. steps: How many steps to take; 0 or more. h: The nudge numerical_derivative uses to measure each slope. Returns: (knobs, losses): knobs is a new list with one number per knob of params, and losses holds steps + 1 numbers, the first being f(params). """ # --- gap L03.gradient_descent --- params = list(params) losses = [f(params)] for _ in range(steps): slopes = [] for i in range(len(params)): def along(v, i=i): return f(params[:i] + [v] + params[i + 1:]) slopes.append(numerical_derivative(along, params[i], h)) params = [p - lr * s for p, s in zip(params, slopes)] losses.append(f(params)) return params, losses # --- end --- def sigmoid(z: float) -> float: """The smooth step 1 / (1 + e^-z): near 0 for very negative z, 0.5 at 0, near 1 for large z. Args: z: Any number, such as a neuron's weighted sum plus its bias. Returns: A number between 0 and 1, rising as z rises. Above 0.5 reads as yes. Raises: OverflowError: If z is below about -709, where e^-z is too large for a float. """ # --- gap L04.sigmoid --- return 1.0 / (1.0 + math.exp(-z)) # --- end --- def neuron(xs: Sequence[float], ws: Sequence[float], b: float) -> float: """One neuron: the sigmoid of the weighted sum of the inputs plus the bias. Args: xs: The inputs. ws: The weights, one per input (same length as xs): ws[i] goes with xs[i]. b: The bias. Returns: The neuron's output, between 0 and 1. Above 0.5 reads as yes. """ # --- gap L04.neuron --- return sigmoid(sum(w * x for w, x in zip(ws, xs)) + b) # --- end --- def train_neuron( data: Sequence[tuple[Sequence[float], float]], lr: float = 1.0, steps: int = 1000, ) -> tuple[list[float], float]: """Fit one neuron to data, a list of (inputs, target) pairs with targets 0 or 1: run gradient_descent on the mse of the neuron's outputs, over the knobs [weights..., bias], starting from all zeros. Returns (weights as a list, bias). Args: data: The examples; at least one. Every example has the same number of inputs. lr: The learning rate handed to gradient_descent. steps: How many gradient_descent steps to take; 0 or more. Returns: (ws, b): ws holds one weight per input of an example, and b is the bias. With steps = 0 every one of them is 0.0. """ # --- gap L04.train_neuron --- n = len(data[0][0]) targets = [t for _, t in data] def loss(knobs): return mse(targets, [neuron(xs, knobs[:n], knobs[n]) for xs, _ in data]) knobs, _ = gradient_descent(loss, [0.0] * (n + 1), lr, steps) return knobs[:n], knobs[n] # --- end --- def relu(z: float) -> float: """The kink: z when z is positive, else 0. Args: z: Any number, such as a hidden unit's weighted sum plus its bias. Returns: A number that is never negative. """ # --- gap L05.relu --- return z if z > 0 else 0.0 # --- end --- def two_layer( xs: Sequence[float], W1: Sequence[Sequence[float]], b1: Sequence[float], w2: Sequence[float], b2: float, ) -> float: """A two-layer network on one input list xs. Hidden unit k is relu(W1[k] . xs + b1[k]); the output is w2 . hidden + b2, with no squashing on the output. Args: xs: The inputs. W1: The hidden layer's weights: one row per hidden unit, and each row holds one weight per input (same length as xs). b1: The hidden layer's biases, one per hidden unit (same length as W1). w2: The output's weights, one per hidden unit (same length as W1). b2: The output's bias. Returns: The network's output: any number, since nothing squashes it. """ # --- gap L05.two_layer --- hidden = [relu(sum(w * x for w, x in zip(row, xs)) + b) for row, b in zip(W1, b1)] return sum(w * h for w, h in zip(w2, hidden)) + b2 # --- end --- def numerical_gradient( f: Callable[[list[float]], float], params: list[float], h: float = 1e-6, ) -> tuple[list[float], int]: """Every partial slope of f (a function of a list of knobs) at params, by forward differences: one call at params itself, then one call per knob with only that knob nudged by h. Returns (grads, calls): the list of slopes and the number of times f was called. Args: f: The loss: takes a list of knobs, as many as params holds, and returns a number. params: The knobs to measure at. The caller's list is not changed. h: The size of the nudge: small, and not 0. Returns: (grads, calls): grads is a new list with one slope per knob, in the order of params, and calls is len(params) + 1. Raises: ZeroDivisionError: If h is 0. """ # --- gap L06.numerical_gradient --- raise NotImplementedError("Call f once at params, then once per nudged knob; return (grads, calls).") # --- end ---Running code needs JavaScript. Above is ember/basics.py as this lab starts.

Your numerical_gradient: forward passes against knobs, and the bill for bigger models.

import hx
from ember.basics import numerical_gradient

sizes, passes = [], []
for n in [1, 10, 100, 250, 500, 1000]:
    grads, calls = numerical_gradient(lambda p: sum((v - 1.0) ** 2 for v in p), [0.0] * n)
    sizes.append(n)
    passes.append(calls)
    print(f"{n:>5} knobs: {calls:>5} forward passes")
hx.plot("line", {"series": [{"name": "forward passes for one gradient", "x": sizes, "y": passes}]})

for n, unit, per in [(10_000, "seconds", 1), (1_000_000, "minutes", 60), (7_000_000_000, "days", 86_400)]:
    print(f"{n:>13,} knobs at 1 ms a pass: about {(n + 1) / 1000 / per:,.0f} {unit} per step")

    1 knobs:     2 forward passes
   10 knobs:    11 forward passes
  100 knobs:   101 forward passes
  250 knobs:   251 forward passes
  500 knobs:   501 forward passes
 1000 knobs:  1001 forward passes
       10,000 knobs at 1 ms a pass: about 10 seconds per step
    1,000,000 knobs at 1 ms a pass: about 17 minutes per step
7,000,000,000 knobs at 1 ms a pass: about 81 days per step

Forward passes for one gradient, against the number of knobs: a straight line, one more pass per knob.

series	points	first	last	lowest	highest
forward passes for one gradient	6	2	1001	2	1001

1,001 forward passes for 1,000 knobs. At 1 ms a pass, a million knobs cost about 17 minutes per step, and seven billion about 81 days.

You double the number of knobs in a model. What happens to the number of forward passes one nudged gradient costs?

It stays the same: one set of nudges covers any size

Each knob needs its own nudge, so the passes grow with the knobs.

It quadruples: every knob has to be nudged together with every other knob

Each partial slope nudges one knob and holds the rest still, so pairs never come into it.

It roughly doubles:

n + 1

becomes

2n + 1

One pass where you stand, plus one per knob.

It roughly doubles, and every pass also gets slower as the model grows.

A model has 500 knobs and one forward pass takes 2 ms. How many seconds does one nudged gradient take?

501 passes · 2 ms = 1,002 ms = 1.002 seconds, for one step.

Where this goes

Backpropagation, in lessons 07 to 10, gets every partial slope from one forward pass and one backward pass, whatever the number of knobs. It starts with a number that remembers where it came from.

When you finish this lesson

Your ember can now: measure every slope of a loss at once, and count the cost

Part I gave your ember all of this:

turn two knobs, w and b, into a prediction
score any line with one number, and search a grid for the best one
fit a line by walking downhill on its loss
train a neuron that decides AND and OR
compute XOR with two layers and a kink
measure every slope of a loss at once, and count the cost

Back up your ember (one small zip).

Next A number that remembers · What must a number record so we can ask where it came from? · ~35 min

Continue

Previous 05 Bending space Next 07 A number that remembers What must a number record so we can ask where it came from?

Report a problem with this lesson