Lesson 03 · Part I · Why learning works at all

Downhill in the dark

You can only feel the slope underfoot. Now what?

~40 min · 2 labs · builds on 02 How wrong is wrong?

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

A line's errors on four points are 2, −2, 0 and 0. What is its mean squared error?

The squares are 4, 4, 0 and 0, which sum to 8, and 8 / 4 = 2. The signed errors would have averaged 0.

You raise b by 1 and leave w alone. By how much does every prediction of the line $w \cdot x + b$ change?

By exactly 1, whatever x is: b is added once to every prediction. Keep that in mind; it is the slope of a prediction with respect to b.

A hillside in the dark

A loss turns a line's misses into one number, and grid search finds the best line by trying every knob setting on a grid: 441 tries for two knobs.

Ten knobs with 21 values each would need $21^{10}$ tries, more than sixteen million million. So picture the loss as the height of a hillside, and the knobs as the spot where you stand. It is dark, and you can't see the valley. All you can do is feel the ground under your feet.

You stand at w = 1.0 on the loss of the taxi line, with b held at 3. You know no loss value yet. You may measure the loss at any w you like, one w at a time. What is the fewest measurements that tell you which direction of w lowers the loss?

Two: the loss where you stand, and the loss a tiny step away. If the step lowered the loss, that way is downhill; if it raised it, the other way is.

Downhill by hand: change w, run, read the two losses, and try to reach the bottom.

from ember.basics import predict_line, mse

km = [1, 2, 3, 5, 8]
fare = [5.6, 7.9, 10.4, 15.6, 22.9]


def loss_at(w, b=3.0):
    return mse(fare, [predict_line(x, w, b) for x in km])


w = 1.0                  # change this and run again: can you find the bottom?
nudge = 0.001
print(f"loss at w = {w}: {loss_at(w):.4f}")
print(f"loss at w = {w + nudge}: {loss_at(w + nudge):.4f}")

loss at w = 1.0: 45.9400
loss at w = 1.001: 45.8785

At w = 1.0 the loss is 45.9400, and a nudge to the right gives 45.8785: downhill is to the right, but the two numbers don't say how far to go.

By hand this is slow even for one knob. With two knobs you would also have to choose which one to move, and by how much.

The slope underfoot

The slope underfoot is how much the loss changes per unit of nudge: nudge a knob by a small amount h, and divide the change in the loss by h. With two knobs, nudge one and hold the other still. That is a partial slope, and a new sign, $\partial$ , writes it: $\frac{\partial L}{\partial w}$ reads "the partial slope of L with respect to w".

On the four points (1, 3), (2, 5), (3, 7) and (4, 9), with h = 0.01: $\frac{\partial L}{\partial w} \approx \frac{L(w + h, b) - L(w, b)}{h}$ At w = 1 and b = 1, L(1, 1) = 7.5 and L(1.01, 1) = 7.35075, so the slope is (7.35075 − 7.5) / 0.01 = −14.925.

Same points, same place (w = 1, b = 1). Now hold w still and nudge b: L(1, 1.01) = 7.4501. What is $\frac{\partial L}{\partial b}$ ?

(7.4501 − 7.5) / 0.01 = −4.99. Both slopes are negative, so raising either knob lowers the loss, and w's slope is three times steeper.

Now the step. Move each knob against its slope, by a small multiple of the slope. That multiple is the learning rate, written lr. A negative slope means the loss falls as the knob grows, so the knob moves up. Both knobs move in the same step, each by its own partial slope.

One step: $w_{\text{new}} = w - \text{lr} \cdot \frac{\partial L}{\partial w}$ With lr = 0.01 at w = 1: 1 − 0.01 · (−14.925) = 1.14925.

Take the same kind of step for b, at another spot: from b = 2, with $\frac{\partial L}{\partial b}$ = −3 and lr = 0.01. Where does b land?

2 − 0.01 · (−3) = 2.03. Against the slope, so up.

What: write numerical_derivative(f, x, h): the slope of a one-input function f at x, measured by nudging x by h.

Why: without it there is no slope to follow. gradient_descent in the next lab calls it once per knob, and lesson 11 uses it again to check derivative formulas.

Your ember can feel a slope.

Measure f where you stand and a tiny step h to the right. How do two heights and the distance between them make a slope?
Slope is rise over run: how much f changed between your two points, divided by how far apart they are.
Nearly the code: return (f(x + h) - f(x)) / ...

The measured slope of x * x at x = 3 is about 6.
A straight line has the same slope everywhere.
The measured slope of sin at 0 is about 1.
numerical_derivative compares f(x + h) with f(x), using the h it is given.

"""Part I: learning with plain Python numbers and lists (no NumPy, no framework yet).""" 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 --- raise NotImplementedError("Nudge x by h and divide the change in f by 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 --- raise NotImplementedError("Measure every knob's slope, then move every knob against it, steps times.") # --- end ---Running code needs JavaScript. Above is ember/basics.py as this lab starts.

What: write gradient_descent(f, params, lr, steps). Each step, measure every knob's partial slope with numerical_derivative, then move each knob against its slope by lr times the slope. Return the final knobs and the losses: one before the first step and one after each.

Why: without it the only way to fit a line is the grid, whose cost multiplies with every knob. It fits the taxi line without a grid, lesson 04 uses it to train a neuron, and lesson 06 counts what its nudging costs.

Your ember can walk downhill.

A partial slope nudges one knob and holds the rest still. numerical_derivative wants a function of one number: can you build one that puts a number into position i of params and calls f on the result?
For each i, define along(v) that returns f(params[:i] + [v] + params[i + 1:]); the slope is numerical_derivative(along, params[i], h). Bind i with a default argument, def along(v, i=i), or every along sees the loop's last i. Measure all the slopes first, then move all the knobs, and record f(params) before the loop and after every step.
Nearly the code: losses = [f(params)]; each step builds slopes, then params = [p - lr * s for p, s in zip(params, slopes)] and losses.append(f(params)); at the end, return params, losses.

One step moves every knob by minus lr times its partial slope.
Knobs move together: every slope is measured at the same point.
100 steps on a bowl centred at (3, -1) end near (3, -1).
Descending the mse of predict_line recovers the line y = 2x + 1.
losses holds f at the start and after each step: steps + 1 numbers.
gradient_descent returns new knobs and does not change the list it was given.
With lr = 1.1 on k^2 every step overshoots, so the loss grows.

Fitting the taxi line from w = 0, b = 0 with lr = 0.01 takes about 330 steps to get the loss under 0.05. You make the learning rate ten times bigger: lr = 0.1. How many steps now?

About 33: ten times the step, a tenth of the steps

That holds only while each step still lands closer to the bottom. Past a certain size, a step overshoots the valley by more than it started away.

It never gets there: the loss grows at every step

Each step jumps past the bottom to a point higher up the other side, where the slope is steeper, so the next jump is bigger still.

About 330 again: the learning rate changes how precise the answer is, not how fast you get there

The rate multiplies every step, so it sets the speed directly, and past a limit it decides whether you arrive at all.

Bigger is faster only up to a limit. Past it, the walk climbs out of the valley.

The cell below runs four rates side by side. At lr 0.01 the loss is under 0.05 after 328 steps, and at lr 0.04 after 82. At lr 0.1 it passes a million after 4 steps, so its line in the plot stops there.

Your gradient_descent, one step at a time, at four learning rates.

import math
import hx
from ember.basics import predict_line, mse, gradient_descent

km = [1, 2, 3, 5, 8]
fare = [5.6, 7.9, 10.4, 15.6, 22.9]


def loss(knobs):
    w, b = knobs
    return mse(fare, [predict_line(x, w, b) for x in km])


series = []
for lr in [0.001, 0.01, 0.04, 0.1]:
    knobs, losses, reached = [0.0, 0.0], [loss([0.0, 0.0])], None
    for step in range(1, 401):
        knobs, _ = gradient_descent(loss, knobs, lr, 1)
        losses.append(loss(knobs))
        if reached is None and losses[-1] < 0.05:
            reached = step
        if losses[-1] > 1e6:
            break
    if reached:
        print(f"lr {lr}: loss under 0.05 after {reached} steps")
    elif losses[-1] > 1e6:
        print(f"lr {lr}: loss above a million after {len(losses) - 1} steps")
    else:
        print(f"lr {lr}: loss still {losses[-1]:.3f} after 400 steps")
    series.append({"name": f"lr {lr}", "x": list(range(len(losses))), "y": [math.log10(v) for v in losses]})
hx.plot("line", {"series": series})

lr 0.001: loss still 1.156 after 400 steps
lr 0.01: loss under 0.05 after 328 steps
lr 0.04: loss under 0.05 after 82 steps
lr 0.1: loss above a million after 4 steps

Base-10 log of the loss at each step, for four learning rates.

series	points	first	last	lowest	highest
lr 0.001	401	2.288	0.06283	0.06283	2.288
lr 0.01	401	2.288	-1.576	-1.576	2.288
lr 0.04	401	2.288	-2.049	-2.049	2.288
lr 0.1	5	2.288	6.392	2.288	6.392

Where you stand, a loss has partial slopes $\frac{\partial L}{\partial w}$ = 8 and $\frac{\partial L}{\partial b}$ = −2. With lr = 0.1, how does each knob move?

Both go down: gradient descent makes the knobs smaller

It makes the loss smaller. A negative slope means raising the knob lowers the loss, so b goes up.

Only w moves: you step along the steepest knob first

Every knob moves at every step, each by lr times its own slope; b's move is smaller because its slope is.

w goes down by 0.8 and b goes up by 0.2

Each knob moves against its own slope:

w - 0.1 \cdot 8

and

b - 0.1 \cdot (-2)

w drops by 0.8 and b rises by 0.2. Each knob follows its own slope, in the same step.

Where this goes

gradient_descent tunes the knobs of any function whose loss you can measure. Lesson 04 hands it a function that makes yes-or-no decisions, and meets a function with no slope to feel.

When you finish this lesson

Your ember can now: fit a line by walking downhill on its loss

It already could:

score any line with one number, and search a grid for the best one
turn two knobs, w and b, into a prediction

Next The simplest decision · What is the simplest thing that makes a decision? · ~40 min

Continue

Previous 02 How wrong is wrong?Next 04 The simplest decision What is the simplest thing that makes a decision?

Report a problem with this lesson