Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture II of IV

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:

x1x_1x2x_2yy
000
011
101
110

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.

python runs in your browser · first run downloads ~240 kb
Plate I The limit of a linear model, by exhaustive search rather than by training. Every line on a 60-cubed grid of coefficients is scored against XOR, and the best manages 3 of 4, which is exactly what you get by guessing one output wrong on purpose. AND and OR, listed underneath, are both solved perfectly by a single line: it is not that Boolean functions are hard, it is that this one is not linearly separable.

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 x∈R2x \in \mathbb{R}^{2}. Send it through an affine map into a hidden layer of HH units, apply a nonlinear function elementwise, then send the result through a second affine map down to one output, and squash that into (0,1)(0, 1) so it can be read as a probability:

z(1)=W(1)x+b(1),a(1)=tanh⁡ ⁣(z(1)),z(2)=W(2)a(1)+b(2),a(2)=σ ⁣(z(2)),\begin{aligned} z^{(1)} &= W^{(1)} x + b^{(1)}, & a^{(1)} &= \tanh\!\big(z^{(1)}\big), \\[3pt] z^{(2)} &= W^{(2)} a^{(1)} + b^{(2)}, & a^{(2)} &= \sigma\!\big(z^{(2)}\big), \end{aligned}

where σ(z)=1/(1+e−z)\sigma(z) = 1/(1 + e^{-z}) is the logistic sigmoid. The parameters are W(1)∈RH×2W^{(1)} \in \mathbb{R}^{H \times 2}, b(1)∈RHb^{(1)} \in \mathbb{R}^{H}, W(2)∈R1×HW^{(2)} \in \mathbb{R}^{1 \times H} and b(2)∈Rb^{(2)} \in \mathbb{R}. Count them: for H=4H = 4 that is 8+4+4+1=178 + 4 + 4 + 1 = 17 numbers. Seventeen numbers is the whole model.

The nonlinearity is not decoration

It is worth being brutal about why tanh⁡\tanh is in there, because it is the single most common misunderstanding about depth. Delete it, and the network becomes

a(2)=W(2)(W(1)x+b(1))+b(2)=(W(2)W(1))x+(W(2)b(1)+b(2)),a^{(2)} = W^{(2)}\big(W^{(1)} x + b^{(1)}\big) + b^{(2)} = \big(W^{(2)} W^{(1)}\big) x + \big(W^{(2)} b^{(1)} + b^{(2)}\big),

which is an affine map, with matrix W(2)W(1)W^{(2)}W^{(1)} and offset W(2)b(1)+b(2)W^{(2)}b^{(1)} + b^{(2)}. 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.

python runs in your browser · first run downloads ~240 kb
Plate II Depth without a nonlinearity, collapsed. A three-unit hidden layer and a one-unit output layer are multiplied out into the single 1×21 \times 2 matrix W(2)W(1)W^{(2)}W^{(1)}, then both are evaluated on the same four inputs. The columns agree to every printed digit, and they agree for every input, not just these: the equality is an identity, not a coincidence. This is the plate to remember whenever someone says a model is powerful because it is deep.

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 (x1,x2)(x_1, x_2) the two 1s are on opposite corners and no line separates them. But the hidden layer maps each point to new coordinates (a1(1),a2(1))(a^{(1)}_1, a^{(1)}_2), 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 a(1)a^{(1)} column: the two inputs that XOR wants labelled 1 both map to hidden activations near (+1,+1)(+1, +1), 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.

python runs in your browser · first run downloads ~240 kb
Plate III XOR solved by hand, with every intermediate shown. The weights are not learned; they are chosen so the hidden units compute recognisable Boolean functions. Hidden unit 1 is an OR, hidden unit 2 is a NAND, and the output is an AND of the two, which is one of the standard constructions of XOR. Read the a(1)a^{(1)} column as a new pair of coordinates for each input point: in those coordinates a single line does what no line could do in the original ones.

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 a(2)a^{(2)} is a probability, so score it with the binary cross-entropy, the negative log-likelihood of the label under that probability:

L=−1n∑i=1n[yilog⁡ai(2)+(1−yi)log⁡(1−ai(2))].L = -\frac{1}{n}\sum_{i=1}^{n}\Big[y_i \log a^{(2)}_i + (1 - y_i)\log\big(1 - a^{(2)}_i\big)\Big].

Read it one example at a time. If y=1y = 1 the term is −log⁡a(2)-\log a^{(2)}, which is 00 when the network says 1 and grows without bound as it approaches 0. If y=0y = 0 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 z(2)z^{(2)}, using σ′(z)=σ(z)(1−σ(z))\sigma'(z) = \sigma(z)\big(1 - \sigma(z)\big):

∂L∂z(2)=(−ya(2)+1−y1−a(2))⏟∂L/∂a(2)⋅a(2)(1−a(2))⏟∂a(2)/∂z(2)=a(2)−y.\frac{\partial L}{\partial z^{(2)}} = \underbrace{\left(\frac{-y}{a^{(2)}} + \frac{1-y}{1-a^{(2)}}\right)}_{\partial L / \partial a^{(2)}} \cdot \underbrace{a^{(2)}\big(1 - a^{(2)}\big)}_{\partial a^{(2)} / \partial z^{(2)}} = a^{(2)} - y .

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 δ(ℓ)=∂L/∂z(ℓ)\delta^{(\ell)} = \partial L / \partial z^{(\ell)}, 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,

δ(2)=a(2)−y.\delta^{(2)} = a^{(2)} - y .

Parameters of the output layer. Since z(2)=∑jWj(2)aj(1)+b(2)z^{(2)} = \sum_j W^{(2)}_j a^{(1)}_j + b^{(2)}, the derivative of z(2)z^{(2)} with respect to Wj(2)W^{(2)}_j is just aj(1)a^{(1)}_j, so by the chain rule

∂L∂Wj(2)=δ(2)aj(1),∂L∂b(2)=δ(2).\frac{\partial L}{\partial W^{(2)}_j} = \delta^{(2)} a^{(1)}_j, \qquad \frac{\partial L}{\partial b^{(2)}} = \delta^{(2)} .

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 aj(1)a^{(1)}_j influences the loss only through z(2)z^{(2)}, and z(2)z^{(2)} depends on it with coefficient Wj(2)W^{(2)}_j. So ∂L/∂aj(1)=Wj(2)δ(2)\partial L / \partial a^{(1)}_j = W^{(2)}_j \delta^{(2)}. To get from there to zj(1)z^{(1)}_j we pass through tanh⁡\tanh, whose derivative is 1−tanh⁡21 - \tanh^2, and we already have tanh⁡(zj(1))\tanh(z^{(1)}_j) sitting in aj(1)a^{(1)}_j:

δj(1)=Wj(2)δ(2)⏟error arriving from above⋅(1−(aj(1))2)⏟tanh⁡′ ⁣(zj(1)).\delta^{(1)}_j = \underbrace{W^{(2)}_j \delta^{(2)}}_{\text{error arriving from above}} \cdot \underbrace{\big(1 - (a^{(1)}_j)^2\big)}_{\tanh'\!\big(z^{(1)}_j\big)} .

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 xx itself:

∂L∂Wjk(1)=δj(1)xk,∂L∂bj(1)=δj(1).\frac{\partial L}{\partial W^{(1)}_{jk}} = \delta^{(1)}_j x_k, \qquad \frac{\partial L}{\partial b^{(1)}_j} = \delta^{(1)}_j .

That is the entire algorithm. In matrix form, for a general layer ℓ\ell:

δ(ℓ)=((W(ℓ+1))Tδ(ℓ+1))⊙f′(z(ℓ)),∇W(ℓ)L=δ(ℓ)(a(ℓ−1))T,\delta^{(\ell)} = \Big(\big(W^{(\ell+1)}\big)^{\mathsf T} \delta^{(\ell+1)}\Big) \odot f'\big(z^{(\ell)}\big), \qquad \nabla_{W^{(\ell)}} L = \delta^{(\ell)} \big(a^{(\ell-1)}\big)^{\mathsf T},

with ⊙\odot 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 PP parameters you would do O(P)O(P) forward-sized passes, and the whole thing costs O(P2)O(P^2).

Backpropagation computes δ(ℓ)\delta^{(\ell)} once per layer and reuses it for every parameter feeding into that layer. Total cost: one forward pass and one backward pass, so O(P)O(P), 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 δ\deltas 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.

python runs in your browser · first run downloads ~240 kb
Plate IV Forward, backward, and the audit. One input, one target, a 2 to 2 to 1 network with fixed weights. The forward block prints z(1),a(1),z(2),a(2)z^{(1)}, a^{(1)}, z^{(2)}, a^{(2)} and the loss; the backward block prints δ(2)\delta^{(2)}, then every parameter gradient, then δ(1)\delta^{(1)}, in the order the algorithm actually computes them, right to left. The last block re-derives six of those gradients from scratch by nudging each weight and re-running the forward pass, and reports the worst disagreement. The gaps come out around 10−1210^{-12}, which is finite-difference noise and not error.

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.

python runs in your browser · first run downloads ~240 kb
Plate V XOR learned rather than hand-built, at three network sizes. One hidden unit cannot do it and does not pretend to: the loss stalls and accuracy sits at 0.75, the same 3-of-4 the exhaustive line search reached in Plate I, because one hidden unit plus one output unit is still only bending the space along a single direction. Two units suffice, which is the minimum construction you derived by hand. Four converge faster and further, because more units mean more ways for the random initialisation to land somewhere useful. All three runs use the same seed, learning rate 2.5, and full-batch descent, so the only variable is width.

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 tanh⁡\tanh 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 δ\delta, so every hidden unit takes the same update, so they remain identical after the step. By induction they are identical forever. A network of HH hidden units initialised identically has exactly one unit’s worth of capacity, permanently, and no amount of training recovers it.

python runs in your browser · first run downloads ~240 kb
Plate VI Symmetry, unbroken. Four hidden units all initialised to the same weights, trained for two thousand epochs, with the four rows of W(1)W^{(1)} printed as they evolve. They move, so it is not that learning has stopped; they move together, and remain four copies of one row. The gradient cannot distinguish units that are indistinguishable. Random initialisation is not superstition, it is what makes the units different problems.

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 1/fan-in1/\sqrt{\text{fan-in}}, which keeps the pre-activations from starting deep in the flat tails of tanh⁡\tanh, where the derivative 1−tanh⁡21 - \tanh^2 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 δ(2)\delta^{(2)} appearing at the output and δ(1)\delta^{(1)} 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.

The same network trained on XOR with four hidden units and with one, showing final loss and training accuracy.
widthsteps lossaccuracy
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.

Data
Hidden units
Learning rate
Seed
7
Train
Pass
Decision surface

Network

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.

Plate VII A network learning a boundary no line can draw. Left, the decision surface over the plane, shaded from one class to the other with the training points on top; right, the network itself, with edge thickness showing the magnitude of each weight and edge colour its sign. Choose a dataset, a width, and a learning rate, then Step for one full-batch gradient step or Run to train. The Pass control walks a single training step through its four stages, forward layer 1, forward layer 2, backward layer 2, backward layer 1, so the backward sweep can be read one layer at a time instead of taken on faith. One hidden unit fails on rings and on XOR, visibly and for the reason Plate V measured. Reduced motion jumps to the trained state.

What it costs

Let PP be the number of parameters and nn the number of training examples.

Cost
Forward pass, one exampleO(P)O(P)
Backward pass, one exampleO(P)O(P), about twice the forward pass in practice
One full-batch gradient stepO(nP)O(nP)
MemoryO(P)O(P) for parameters and gradients, plus the stored activations
Naive per-parameter differentiationO(nP2)O(nP^2), which is why nobody does it
Finite-difference gradientO(nP2)O(nP^2), 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 tanh⁡\tanh for ReLU and only f′f' changes. Swap the single sigmoid output for a softmax over kk classes and δ(2)=a(2)−y\delta^{(2)} = a^{(2)} - y survives verbatim with yy 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.

  1. On paper, the collapse. Prove that a network with LL affine layers and no nonlinearity between them computes an affine function of its input, by induction on LL. 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 ff is inserted, and be precise about which step fails.

  2. On paper, the cancellation. Derive ∂L/∂z(2)=a(2)−y\partial L / \partial z^{(2)} = a^{(2)} - y in full for a single example, starting from L=−[ylog⁡a+(1−y)log⁡(1−a)]L = -[y \log a + (1-y)\log(1-a)] and a=σ(z)a = \sigma(z), using σ′=σ(1−σ)\sigma' = \sigma(1 - \sigma). Do not skip the algebra; the point is to watch every term cancel. Then repeat the exercise for squared error L=12(a−y)2L = \tfrac12 (a - y)^2 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.

  3. On paper, the count. A network has layers of sizes 2→H→12 \to H \to 1. Write the parameter count as a function of HH. 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 HH? Evaluate both at H=4H = 4 and at H=1000H = 1000, and then say which row of the cost table above you have just re-derived.

  4. On paper, the permutation. Take a trained network with H=4H = 4 and swap hidden units 2 and 3, meaning swap rows 2 and 3 of W(1)W^{(1)}, entries 2 and 3 of b(1)b^{(1)}, and entries 2 and 3 of W(2)W^{(2)}. Show that the function computed is unchanged. Conclude that the loss surface has at least H!H! 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.

  5. 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. forward and loss are 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.15
    python runs in your browser · first run downloads ~240 kb
    Plate VIII Backpropagation, graded entry by entry. A fixed three-unit network and four examples; the checks nudge each of the six W(1)W^{(1)} entries, three W(2)W^{(2)} entries, three b(1)b^{(1)} entries and the output bias, and require agreement to 10−610^{-6}. 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 makes H references to one list and will silently give you nonsense.

    Hint two

    Per example: call forward to get a1, a2; set d2 = a2 - y; add d2 * a1[j] into gW2[j] and d2 into gb2; then for each j compute d1 = W2[j] * d2 * (1 - a1[j]**2) and add d1 * x[k] into gW1[j][k] and d1 into gb1[j]. Note that d1 needs W2[j] at its pre-update value, which is automatic here because nothing is updated inside backward.

    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 / n

    Fourteen lines, and eleven of them are bookkeeping. The actual calculus is d2 = a2 - y and d1 = 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 that a1 is 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.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.