Lesson 05 · Part I · Why learning works at all

Bending space

Why stack layers, and why must there be a kink?

~35 min · 1 lab · builds on 04 The simplest decision

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

A step neuron's loss is measured at w1 = 0.3 and again at w1 = 0.300001. Neither measurement flips an answer. What slope does numerical_derivative report?

0. The loss did not change, so there is nothing to follow: that is why lesson 04 switched to sigmoid.

A line's errors on three points are 1.5, −0.5 and −1. Is it a perfect fit?

Yes: its errors average 0

They do average 0: (1.5 − 0.5 − 1) / 3 = 0. The misses balance; they are still misses.

No: its mean squared error is (2.25 + 0.25 + 1) / 3, about 1.17

Squaring makes every miss count, so the score can only be 0 when every error is 0.

Nearly: an average error of 0 means the misses are tiny

The average of signed errors says nothing about their size: a miss of 1.5 is not tiny.

It misses every point. The mean squared error, about 1.17, says so; the signed average hides it.

Two cuts

One neuron draws one straight boundary, so it learns AND and OR and fails on XOR.

XOR needs two cuts. So put two neurons side by side, a hidden layer, and feed their two outputs to a third neuron. What does stacking layers buy you?

Stack two straight lines. The first turns x into $2x + 1$ ; the second takes that result, triples it and adds 4. What shape does the output have as x varies?

A line with a bend where the two lines meet

Nothing in either function bends: composing them multiplies the slopes, 3 · 2, and carries the offsets through.

A straight line

3(2x + 1) + 4 = 6x + 7

. A line of a line is a line.

A curve, like

x^{2}

, because x gets multiplied twice

x is multiplied by 2 and then by 3, which is multiplying by 6, not by x.

$6x + 7$ . Stacking straight-line layers gives one straight line, however many you stack.

Try it on XOR anyway. Two hidden units and one output, with no kink anywhere, make nine knobs, and your gradient_descent trains them.

Two stacked linear layers, trained on XOR for 500 steps.

import random
from ember.basics import gradient_descent, mse

XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]


def stacked(x, k):
    """Two linear layers and no kink: two hidden units, then one output."""
    h1 = k[0] * x[0] + k[1] * x[1] + k[2]
    h2 = k[3] * x[0] + k[4] * x[1] + k[5]
    return k[6] * h1 + k[7] * h2 + k[8]


def loss(k):
    return mse([t for _, t in XOR], [stacked(x, k) for x, _ in XOR])


random.seed(0)
k, _ = gradient_descent(loss, [random.uniform(-1, 1) for _ in range(9)], 0.1, 500)
print(f"loss after 500 steps: {loss(k):.4f}")
for x, t in XOR:
    print(f"{x} -> {stacked(x, k):.3f}   (want {t})")

loss after 500 steps: 0.2501
(0, 0) -> 0.500   (want 0)
(0, 1) -> 0.488   (want 1)
(1, 0) -> 0.512   (want 1)
(1, 1) -> 0.500   (want 0)

After 500 steps the loss is 0.2501 and every output sits near 0.5: nine knobs in two layers did no better than one neuron.

Why stacking lines gives a line

Composing two straight lines multiplies their slopes and carries the offsets: $3(2x + 1) + 4 = 6x + 7$ , slope 3 · 2 = 6 and offset 3 · 1 + 4 = 7.

The same holds for any number of inputs and any number of layers. Each straight-line layer hands a straight line to the next, which absorbs it, so the whole stack is one straight-line layer: a linear function of its inputs.

The first line turns x into $-x + 3$ ; the second doubles that result and subtracts 1. The result is a straight line. What is its slope?

$2 \cdot (-x + 3) - 1 = -2x + 5$ , so the slope is 2 · (−1) = −2.

The fix is a kink between the layers: a function that is not a straight line, called a nonlinearity. The simplest kink has one bend.

relu keeps positive numbers and turns negative ones into 0. In code, relu(z) is max(0, z), so relu(−1.5) = 0 and relu(2) = 2.

Two hidden units with a relu each compute XOR. The first computes relu(x1 - x2), the second relu(x2 - x1), and the output adds them. At (1, 0) that is 1 + 0 = 1; at (1, 1) it is 0 + 0 = 0.

Same network: the hidden units compute relu(x1 - x2) and relu(x2 - x1), and the output adds them. What is the output at x1 = 0.5 and x2 = 0.2?

The first hidden unit gives relu(0.3) = 0.3 and the second relu(−0.3) = 0, so the output is 0.3. The network computes the distance between x1 and x2, which on 0s and 1s is XOR.

Enough kinks can follow a curve: $x^{2}$ on [0, 2], rebuilt from 1, 2, 4 and 8 relu ramps.

import hx


def relu(z):
    return max(0.0, z)


def ramps(x, n):
    """x * x on [0, 2], rebuilt from n relu ramps that bend at evenly spaced points."""
    knots = [2 * i / n for i in range(n + 1)]
    slopes = [(knots[i + 1] ** 2 - knots[i] ** 2) / (knots[i + 1] - knots[i]) for i in range(n)]
    y = 0.0
    for i in range(n):
        bend = slopes[i] - (slopes[i - 1] if i else 0.0)
        y += bend * relu(x - knots[i])
    return y


xs = [i / 200 for i in range(401)]
series = [{"name": "x * x", "x": xs, "y": [x * x for x in xs]}]
for n in [1, 2, 4, 8]:
    worst = max(abs(ramps(x, n) - x * x) for x in xs)
    print(f"{n} ramps: worst miss {worst:.4f}")
    series.append({"name": f"{n} ramps", "x": xs, "y": [ramps(x, n) for x in xs]})
hx.plot("line", {"series": series})

1 ramps: worst miss 1.0000
2 ramps: worst miss 0.2500
4 ramps: worst miss 0.0625
8 ramps: worst miss 0.0156

$x^{2}$ and its copies made of 1, 2, 4 and 8 relu ramps.

series	points	last	highest
x * x	401	4	4
1 ramps	401	4	4
2 ramps	401	4	4
4 ramps	401	4	4
8 ramps	401	4	4

What: write relu(z), and two_layer(xs, W1, b1, w2, b2): hidden unit j adds b1[j] to the weighted sum of the inputs with row j of W1, then applies relu; the output is the weighted sum of the hidden units with w2, plus b2.

Why: without a kink, any stack of layers collapses into one straight line and XOR stays out of reach. This is the first network in your ember that can compute XOR. Lesson 06 counts what training its nine knobs by nudging costs, and lesson 12 rebuilds it from Values as Layer and MLP.

Your ember has a hidden layer, and it can bend.

relu keeps positive numbers and makes negative ones 0: which built-in returns the larger of two numbers? For two_layer: how many hidden units are there, and where does each find its weights and its bias?
relu is max(0.0, z). In two_layer, first build the list of hidden values: for each row of W1, with its bias from b1, take the weighted sum of xs, add the bias and apply relu. The output is the weighted sum of the hidden values with w2, plus b2.
Nearly the code: hidden = [relu(sum(w * x for w, x in zip(row, xs)) + b) for row, b in zip(W1, b1)], then return sum(w * h for w, h in zip(w2, hidden)) + b2.

relu(3) is 3; relu(-2) and relu(0) are 0.
With hidden units relu(x1 + x2) and relu(x1 + x2 - 1), two_layer computes XOR.
Hidden units 3, 0.5 and 0 give 1 * 3 - 2 * 0.5 + 3 * 0 + 0.5 = 2.5.
The output layer has no relu: it can be large and negative.

"""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 --- raise NotImplementedError("Return z when it is positive, else 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 --- raise NotImplementedError("Compute each hidden unit with relu, then the weighted sum of the hidden units plus b2.") # --- end ---Running code needs JavaScript. Above is ember/basics.py as this lab starts.

Train your two_layer on XOR from a random start and draw its boundary.

import random
import hx
from ember.basics import two_layer, gradient_descent, mse

XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]


def unpack(k):
    return [[k[0], k[1]], [k[2], k[3]]], [k[4], k[5]], [k[6], k[7]], k[8]


def loss(k):
    W1, b1, w2, b2 = unpack(k)
    return mse([t for _, t in XOR], [two_layer(x, W1, b1, w2, b2) for x, _ in XOR])


random.seed(0)
w = [random.uniform(-1, 1) for _ in range(6)]
start = [w[0], w[1], w[2], w[3], 0.0, 0.0, w[4], w[5], 0.0]
k, _ = gradient_descent(loss, start, 0.1, 500)
W1, b1, w2, b2 = unpack(k)
print(f"loss after 500 steps: {loss(k):.4f}")
for x, t in XOR:
    print(f"{x} -> {round(two_layer(x, W1, b1, w2, b2), 2) + 0.0:.2f}   (want {t})")
grid = {"x0": -0.5, "x1": 1.5, "y0": -0.5, "y1": 1.5, "nx": 21, "ny": 21}
values = [[two_layer((-0.5 + 0.1 * i, -0.5 + 0.1 * j), W1, b1, w2, b2) for i in range(21)] for j in range(21)]
hx.plot("boundary", {"grid": grid, "values": values, "points": [{"x": a, "y": c, "c": t} for (a, c), t in XOR], "threshold": 0.5})

loss after 500 steps: 0.0000
(0, 0) -> 0.00   (want 0)
(0, 1) -> 1.00   (want 1)
(1, 0) -> 1.00   (want 1)
(1, 1) -> 0.00   (want 0)

The trained two-layer network's output over the plane: two cuts, with (0, 1) and (1, 0) on the yes side.

class	points
0	2
1	2
21×21 grid, 49% of it on the class 1 side

The run ends with a loss of 0.0000 and the outputs 0.00, 1.00, 1.00 and 0.00: two cuts, where one neuron could make only one. Not every random start gets there. From some starts a hidden unit outputs 0 for all four inputs, its slope is 0, and it stops learning; lesson 23 comes back to that.

Ramps copying $x^{2}$ on [0, 2] miss by at most 1 with one ramp, 0.25 with two and 0.0625 with four. What is the worst miss with 16 ramps?

Each doubling quarters the worst miss: 0.0156 at 8 and 0.0039 at 16, exactly 1 / 256. Enough kinks can follow a smooth curve as closely as you like.

A friend builds a 20-layer network with no relu or sigmoid anywhere, hoping for more power than two layers. What can it compute?

More than a two-layer network: every layer adds power

Each extra straight-line layer is absorbed into the one before it, so depth adds nothing.

Nothing: a network with no kinks can't be trained at all

It trains fine, to the best straight line; it can't be anything else.

Only a straight-line function of its inputs, like a single layer

Twenty straight-line layers compose into one: multiply the slopes, carry the offsets.

One straight-line function, however deep. The power comes from the kinks between the layers.

Where this goes

two_layer has nine knobs, and gradient_descent nudged each one separately at every step. Lesson 06 adds up that bill for a network with 10,000 knobs.

When you finish this lesson

Your ember can now: compute XOR with two layers and a kink

It already could:

train a neuron that decides AND and OR
fit a line by walking downhill on its loss
score any line with one number, and search a grid for the best one

Next The bill for nudging · 10,000 knobs: how many forward passes for one gradient? · ~30 min

Continue

Previous 04 The simplest decision Next 06 The bill for nudging 10,000 knobs: how many forward passes for one gradient?

Report a problem with this lesson