Lecture II · Machine Learning
A neural network from scratch
In Lecture I the model was a line, the loss was a bowl, and the answer had a closed form that gradient descent was merely a slow way of reaching. This lecture keeps gradient descent and takes away everything else. The model stops being linear, the loss stops being a bowl, the optimum stops being unique, and there is no algebraic expression for the answer at all.
What survives is the method. Differentiate the loss, step against the gradient, repeat. The only new work is the differentiating, and doing it efficiently on a composed function is the algorithm called backpropagation. It has a reputation for difficulty that it does not deserve. It is the chain rule, run right to left, with the intermediate results kept instead of recomputed.
Where the line runs out
Here is the smallest problem in the world that a line cannot solve. Four points, two inputs, one output:
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
That is XOR, exclusive or: the output is 1 when exactly one input is 1. Try to separate the two classes with a straight cut through the unit square and you will fail, because the two 1s sit on opposite corners. Any line putting both of them on one side drags at least one 0 across with them.
The plate below does not train anything. It searches every line on a coarse grid, which is a stronger claim than training: no line found by any method could beat the best line found by exhaustive search.
The classical response to this in 1969 was that neural networks were a dead end. The actual response is that one layer is a dead end, and that the fix is to put a layer in front of it that changes the coordinates first.
The model: two layers, and something in between
Take the input . Send it through an affine map into a hidden layer of units, apply a nonlinear function elementwise, then send the result through a second affine map down to one output, and squash that into so it can be read as a probability:
where is the logistic sigmoid. The parameters are , , and . Count them: for that is numbers. Seventeen numbers is the whole model.
The nonlinearity is not decoration
It is worth being brutal about why is in there, because it is the single most common misunderstanding about depth. Delete it, and the network becomes
which is an affine map, with matrix and offset . Two layers, one line. A hundred layers, one line. The composition of linear maps is linear, so without a nonlinearity between them, depth buys precisely nothing: you have a more expensive parameterisation of exactly the model from Lecture I.
Bending the space
Here is what the hidden layer actually does, and it is worth stating in plain words because the algebra hides it: the hidden layer does not find a cleverer line. It moves the points.
In the original coordinates the two 1s are on opposite corners and no line separates them. But the hidden layer maps each point to new coordinates , and in those coordinates the two 1s can land next to each other. Once they do, a single line finishes the job, and the output layer is that single line. The network is a change of coordinates followed by logistic regression.
The plate below runs a hand-built network with weights chosen to make this legible. Read the column: the two inputs that XOR wants labelled 1 both map to hidden activations near , and the two it wants labelled 0 map somewhere else. In the new coordinates the problem is linearly separable, and the output layer is just the line that separates them.
Hand-choosing weights is fine for four points. For anything real we need the network to find them, which means we need the gradient of the loss with respect to all seventeen numbers.
The loss, and the one simplification worth memorising
The output is a probability, so score it with the binary cross-entropy, the negative log-likelihood of the label under that probability:
Read it one example at a time. If the term is , which is when the network says 1 and grows without bound as it approaches 0. If it is the mirror image. Confident and wrong is punished arbitrarily hard, which is the behaviour you want from a probabilistic model and is not what squared error gives you.
Now the piece of algebra that makes everything below tidy. Differentiate the loss for a single example with respect to the output pre-activation , using :
Multiply it out and watch everything cancel. The whole ugly expression collapses to prediction minus target. This is not luck: the sigmoid is the inverse of the log-odds and cross-entropy is the log-likelihood, so pairing them is designed to produce it. Notice too that this is the identical form we got in Lecture I from a linear output with squared error. That correspondence is worth holding on to: for a well-matched output activation and loss, the error signal entering the network is always just how wrong you were.
The chain rule, run backwards
Now the derivation. Write , the gradient with respect to a layer’s pre-activations. Everything follows from computing those.
At the output. By the calculation above, for one example,
Parameters of the output layer. Since , the derivative of with respect to is just , so by the chain rule
In words, and this is the sentence to keep: the gradient of a weight is the error at its output end times the activation at its input end. Every weight gradient in every network, of any depth, has that form.
Back through the nonlinearity. The hidden activation influences the loss only through , and depends on it with coefficient . So . To get from there to we pass through , whose derivative is , and we already have sitting in :
Parameters of the first layer. Same rule as before, error at the output end times activation at the input end, where the input end is now itself:
That is the entire algorithm. In matrix form, for a general layer :
with the elementwise product. Two lines, any depth. Deep learning libraries are, at their mathematical core, an efficient implementation of those two lines plus a graph to run them over.
Why “back”, and why it is not just the chain rule
Students often ask why this needs a name if it is only the chain rule. Here is the honest answer.
The chain rule tells you what the derivative is. It does not tell you what order to evaluate it in, and the order is where all the cost lives. Suppose you computed each parameter’s derivative independently, expanding the chain rule from the input forward each time. Every one of those expansions would recompute the same partial products through the upper layers. With parameters you would do forward-sized passes, and the whole thing costs .
Backpropagation computes once per layer and reuses it for every parameter feeding into that layer. Total cost: one forward pass and one backward pass, so , the same order as simply evaluating the network.
If that sounds familiar it should. Storing a shared subresult rather than recomputing it down every branch is exactly memoization, and backpropagation is dynamic programming over the computation graph, in the same sense as the DSA course’s dynamic programming lecture. The recursion has overlapping subproblems, the s are the table, and the backward sweep is the order that fills the table before it is read. That is the whole content of the word “back”.
The backward pass, one example, every number printed
Derivations are easy to nod along to and hard to believe. So here is one example pushed forward through a small network, then pulled back, with every intermediate value printed, and then the whole gradient audited against central finite differences exactly as Lecture I insisted.
Change a weight in that plate and rerun it. The analytic and numeric columns move together, which is the only evidence that matters: the derivation and the code agree with an independent estimate that knows nothing about either.
Training it
Wrap the backward pass in the same loop as Lecture I. Nothing about the outer algorithm changes at all: differentiate, step against the gradient, repeat.
Notice what the loss curve does not do: descend smoothly and monotonically to a unique global minimum. This surface is not a bowl. It has flat regions where has saturated and gradients nearly vanish, it has many distinct minima related by permuting the hidden units, and which one you reach depends on where you started. That is the price of leaving Lecture I’s quadratic behind, and it is permanent: every result in modern deep learning lives on a loss surface like this one.
Why you cannot initialise to zero
One consequence of the surface’s structure deserves its own figure, because it is the first bug most people write.
Set every weight to the same value. Then every hidden unit computes the same thing, so every hidden unit receives the same , so every hidden unit takes the same update, so they remain identical after the step. By induction they are identical forever. A network of hidden units initialised identically has exactly one unit’s worth of capacity, permanently, and no amount of training recovers it.
The standard fix is to draw the initial weights randomly, at a scale that depends on the number of inputs to the unit. The training code above uses , which keeps the pre-activations from starting deep in the flat tails of , where the derivative is near zero and nothing learns.
The plate: a boundary you can watch form
Everything so far has been XOR, four points, because four points can be printed in full. The plate below is the same network on real two-dimensional data, with the two things worth seeing drawn side by side: the decision surface over the plane, and the network itself with the pass stepped through layer by layer.
Push on it in this order. Start on the rings dataset with one hidden unit and run it: watch it fail, and watch how it fails, with a single straight boundary sliding around trying to cut a ring in half. Then raise the hidden units to four and run again. Then step the Pass control one stage at a time and read the network diagram: forward through layer 1, forward through layer 2, then appearing at the output and propagating back into the hidden layer. That right-to-left sweep is the algorithm, and it is the thing this lecture exists to make visible.
| width | steps | loss | accuracy |
|---|---|---|---|
| h = 4 | 4000 | 0.0007 | 100.0% |
| h = 1 | 4000 | 0.4787 | 75.0% |
The surface above is the top row, run at build time on XOR: h = 4 hidden tanh units, learning rate 0.5, 4000 full-batch gradient steps, from 50.0% accuracy at the random start to 100.0%. The bottom row is the same code with the hidden layer cut to a single unit, which can only ever draw a straight line and so stalls at 75.0% on a problem that has four quadrants. With JavaScript enabled the dataset, the width, the learning rate and the seed are all live, and the backward pass can be stepped one layer at a time.
class 1 class 0 the 0.5 contour, where the network is undecided ◎the traced example edge width is magnitude, colour is sign: green positive, ochre negative
The oldest counterexample in the subject: four corners, class 1 where the two coordinates disagree in sign. No straight line separates them, so a network with no hidden layer, or with a hidden layer and no nonlinearity, cannot get above 75% no matter how long it trains. Two hidden tanh units are enough; one is not.
The diagram traces the one marked example, so the values in the nodes are its activations and its deltas; the update the Step applies is the mean of those gradients over all n points, because the loss is a mean. The node marked 1 at the head of each column is the bias input, drawn rather than hidden so that db = d reads as what it is: the gradient of a weight whose input is always 1. And d2 = a2 − y is that short only because the sigmoid's derivative and the cross-entropy's cancel; pair the sigmoid with squared error instead and a factor of a2(1 − a2) survives, goes to zero exactly where the network is most confidently wrong, and the gradient dies.
What it costs
Let be the number of parameters and the number of training examples.
| Cost | |
|---|---|
| Forward pass, one example | |
| Backward pass, one example | , about twice the forward pass in practice |
| One full-batch gradient step | |
| Memory | for parameters and gradients, plus the stored activations |
| Naive per-parameter differentiation | , which is why nobody does it |
| Finite-difference gradient | , a debugging tool only |
The last two rows are the same order for the same reason, and both are the reason backpropagation is a named algorithm rather than an exercise. The memory row is the one that bites in practice: the backward pass needs the activations the forward pass computed, so training a deep network costs memory proportional to its depth in a way that merely running it does not.
What comes next
The pieces are now all in place and all of them generalise. Add more hidden layers and the two boxed matrix equations run unchanged, one layer at a time. Swap for ReLU and only changes. Swap the single sigmoid output for a softmax over classes and survives verbatim with one-hot. Stop using every example on every step and you have minibatch stochastic gradient descent, which a later lecture takes up along with the optimizers Lecture I’s plate let you race.
None of that is a new idea. It is this lecture’s two lines, applied more times.
Lecture III goes the other way instead, and drops the gradient altogether: a decision tree has no loss to differentiate, no learning rate and no small steps, and asking what it does instead is the fastest way to see that “learning” and “descending” are not the same word.
Problems
Work these in order. The last one runs its own checks; make every row green.
On paper, the collapse. Prove that a network with affine layers and no nonlinearity between them computes an affine function of its input, by induction on . Then answer the follow-up that matters: a network with nonlinearities does have more expressive power, but the proof above does not tell you how much more. State what changes in the induction step when is inserted, and be precise about which step fails.
On paper, the cancellation. Derive in full for a single example, starting from and , using . Do not skip the algebra; the point is to watch every term cancel. Then repeat the exercise for squared error with the same sigmoid output, and say what extra factor survives. That surviving factor is the whole reason squared error trains a saturated sigmoid so badly: say in one sentence what happens to it when the network is confidently wrong.
On paper, the count. A network has layers of sizes . Write the parameter count as a function of . Now suppose you computed the gradient by finite differences instead of backpropagation, at two loss evaluations per parameter. How many forward passes per gradient step, as a function of ? Evaluate both at and at , and then say which row of the cost table above you have just re-derived.
On paper, the permutation. Take a trained network with and swap hidden units 2 and 3, meaning swap rows 2 and 3 of , entries 2 and 3 of , and entries 2 and 3 of . Show that the function computed is unchanged. Conclude that the loss surface has at least distinct global minima. Then explain why this makes “did the two runs find the same solution?” a harder question than comparing weight vectors, and suggest what you would compare instead.
Write the backward pass. Implement
backward(W1, b1, W2, b2, data), returning the gradient of the mean loss as(gW1, gb1, gW2, gb2), shaped exactly like the parameters.forwardandlossare provided. The checks verify every single entry against a central finite difference, confirm you returned the mean rather than the sum, and confirm you did not mutate the parameters you were handed. This is the exercise the whole lecture is for.The checks · run against your code
# a fixed net and dataset, so the checks are deterministic W1 = [[0.30, -0.70], [0.90, 0.20], [-0.50, 0.60]] b1 = [0.10, -0.40, 0.25] W2 = [0.60, -1.10, 0.35] b2 = 0.15 DATA = [([1.0, 0.5], 1.0), ([0.0, 1.0], 0.0), ([-0.4, 0.2], 1.0), ([0.8, -0.9], 0.0)] def numeric(f, x, eps=1e-5): return (f(x + eps) - f(x - eps)) / (2.0 * eps) gW1, gb1, gW2, gb2 = backward(W1, b1, W2, b2, DATA) # the gradient has exactly the shape of the parameters assert len(gW1) == 3 and all(len(r) == 2 for r in gW1) assert len(gb1) == 3 and len(gW2) == 3 # every W1 entry matches a central finite difference worst = 0.0 for j in range(3): for k in range(2): def f(v, j=j, k=k): M = [r[:] for r in W1] M[j][k] = v return loss(M, b1, W2, b2, DATA) worst = max(worst, abs(numeric(f, W1[j][k]) - gW1[j][k])) assert worst < 1e-6 # every W2 entry matches too worst2 = 0.0 for j in range(3): def g(v, j=j): V = W2[:] V[j] = v return loss(W1, b1, V, b2, DATA) worst2 = max(worst2, abs(numeric(g, W2[j]) - gW2[j])) assert worst2 < 1e-6 # and both biases def h(v): return loss(W1, b1, W2, v, DATA) assert abs(numeric(h, b2) - gb2) < 1e-6 worst3 = 0.0 for j in range(3): def q(v, j=j): B = b1[:] B[j] = v return loss(W1, B, W2, b2, DATA) worst3 = max(worst3, abs(numeric(q, b1[j]) - gb1[j])) assert worst3 < 1e-6 # it is the MEAN gradient, not the sum: doubling the data leaves it unchanged gA = backward(W1, b1, W2, b2, DATA) gB = backward(W1, b1, W2, b2, DATA + DATA) assert abs(gA[3] - gB[3]) < 1e-12 assert max(abs(a - b) for a, b in zip(gA[2], gB[2])) < 1e-12 # backward does not mutate the parameters it is handed assert W1 == [[0.30, -0.70], [0.90, 0.20], [-0.50, 0.60]] assert W2 == [0.60, -1.10, 0.35] and b2 == 0.15python runs in your browser · first run downloads ~240 kbPlate VIII Backpropagation, graded entry by entry. A fixed three-unit network and four examples; the checks nudge each of the six entries, three entries, three entries and the output bias, and require agreement to . Two structural checks follow: duplicating the dataset must leave the gradient unchanged (proving it is a mean and not a sum), and the parameter lists must come back untouched. A gradient that passes all of these is one you can trust to train. Hint one
Accumulate into zero-filled structures the same shape as the parameters, one example at a time, then divide every entry by
len(data)at the very end. Build them with a comprehension, not with[[0.0] * 2] * H, which makesHreferences to one list and will silently give you nonsense.Hint two
Per example: call
forwardto geta1, a2; setd2 = a2 - y; addd2 * a1[j]intogW2[j]andd2intogb2; then for eachjcomputed1 = W2[j] * d2 * (1 - a1[j]**2)and addd1 * x[k]intogW1[j][k]andd1intogb1[j]. Note thatd1needsW2[j]at its pre-update value, which is automatic here because nothing is updated insidebackward.The solution
One pass forward, one pass back, accumulated and then averaged:
def backward(W1, b1, W2, b2, data): H = len(W1) n = len(data) gW1 = [[0.0, 0.0] for _ in range(H)] gb1 = [0.0] * H gW2 = [0.0] * H gb2 = 0.0 for x, y in data: a1, a2 = forward(W1, b1, W2, b2, x) d2 = a2 - y for j in range(H): gW2[j] += d2 * a1[j] gb2 += d2 for j in range(H): d1 = W2[j] * d2 * (1.0 - a1[j] * a1[j]) gW1[j][0] += d1 * x[0] gW1[j][1] += d1 * x[1] gb1[j] += d1 for j in range(H): gW1[j][0] /= n gW1[j][1] /= n gb1[j] /= n gW2[j] /= n return gW1, gb1, gW2, gb2 / nFourteen lines, and eleven of them are bookkeeping. The actual calculus is
d2 = a2 - yandd1 = W2[j] * d2 * (1 - a1[j]**2): the error at the output, and the error carried back through one weight and one derivative. Everything else is adding things up. Worth noticing thata1is used on the way back, which is why the forward pass has to keep it: that single fact is where the memory cost of training a deep network comes from.