Training a Network

Sixty people have each been measured twice, and thirty of them belong to one group and thirty to the other. Plotted against their two measurements they fall into two rings, a small one near the middle of the picture and a wider one around it, so the inner group is completely surrounded. No straight boundary can separate them, and the box above measures exactly that. Fitted on the same sixty people, a straight boundary calls 0.583 of them correctly, which is barely better than tossing a coin, and the chain trained below reaches 1.000.

Everything the chain is made of has already been built. Two measurements feed six units with hyperbolic tangent activations, those six feed a single unit that does not, a loss scores the answer against the truth, and a backward walk hands every one of the twenty-five numbers in the chain a slope. What is left is the part none of those pages covered, which is what to do with those slopes, how many times, on which rows, and when to stop.

It is worth saying plainly what the loop adds, since none of it is arithmetic. Something has to count the passes, decide which rows each step reads and in what order, keep whatever is worth looking at afterwards, and say when to stop, and every one of those is a decision somebody makes rather than a quantity anything computes. Section 28 sets them out with what each of them costs.

Start from an untrained chain, whose twenty-five numbers were drawn at random, and take exactly one step. The backward walk measures the loss on its way forward and hands back one slope for every number. Each number then moves against its own slope, by the same fraction of it, and that fraction is the step size. Nothing else happens.

every number w:    w  ←  w  −  rate × (slope of the loss at w)

0.345584 − 0.5 × 0.028119   =  0.331525
0.000000 − 0.5 × (−0.038580)  =  0.019290

… taking one step

The table above is that step in full, and the bars underneath belong to section 5. Notice how small the drop is. One step of a loop that will run two hundred times moved the loss by nine thousandths, and it moved it by changing every number in the chain by a few hundredths at most.

The twenty-five numbers are not one undifferentiated pile. Eighteen of them belong to the hidden layer, twelve weights and six biases, and seven to the output unit, six weights and one bias. Their slopes are of visibly different sizes, and the largest single slope anywhere in the chain, 0.084723, sits in the output layer.

That the output layer’s slopes are the larger ones at the start is what the backpropagation page would predict. A slope deep in the chain is the slope above it multiplied by the weights it passed through and by the activation function’s own slope, and every one of those factors is smaller than one here, so a slope shrinks the further down the chain it is carried.

It is tempting to read the step size as how far the chain moves, and it is not. The step size multiplies the slope, and the slope has a length of its own that changes at every point of the walk. What the chain actually covers is the step size times that length, measured across all twenty-five numbers at once.

distance covered  =  rate × ‖slope‖

0.5 × 0.139819  =  0.069910

The same step size therefore moves the chain a different distance on every epoch, and moves it further wherever the loss is steep. That is a useful property rather than an awkward one, since the walk slows down of its own accord as it approaches somewhere flat, and it is also the reason a step size that worked on one problem means nothing on another.

There is a prediction hidden inside every step. The slope says how fast the loss changes right where it was read, so it also says how much the loss ought to fall for a step of a given size, and the two are not the same number. The slope describes the loss only in the immediate neighbourhood of the point it was taken at, and a step carries the chain out of that neighbourhood.

predicted drop  =  rate × ‖slope‖²

0.5 × 0.139819²  =  0.009775
actual drop      =  0.009155

The bars in the widget in section 2 are that comparison at eight step sizes, all taken from the same slope at the same untrained chain. At a rate of 0.001 the step delivers 0.9999 of what the slope promised, at 0.05 it delivers 0.9936, at 0.5 it delivers 0.9366, at 1.0 it delivers 0.8735 and at 5.0 it delivers 0.3940.

That is the usual caution about small steps arriving as a measurement, and the useful part of it is that the falling off is gradual, so there is no particular rate at which the slope stops being informative.

What that argument does not say is that a small step is better. At a rate of 5.0 the step keeps only 39 percent of its promise and still reaches a loss of 0.688570, lower than the 0.717923 the well-behaved rate of 0.5 reached, because 39 percent of a promise ten times as large is still more. Part 2 is about where that stops being true.

A step size too small does not fail loudly. The loop runs, every epoch lowers the loss, nothing comes apart and no number misbehaves, and at the end almost nothing has happened. That is the failure worth being able to recognise, because it looks like a working loop that simply needs more time, and sometimes it is and sometimes it is not.

Multiplying the rate by ten makes the difference visible but not sufficient. At 0.01 the loss reaches 0.701984 and the accuracy 0.500, and at 0.1 it reaches 0.623762 and 0.733. The useful range on this problem starts somewhere between 0.1 and 0.5, and the run at 0.1 is the interesting one to look at, since it is plainly learning and two hundred epochs cannot say whether it would arrive.

Between the rate that does nothing and the rate that comes apart there is a range where the loop simply works, and on this chain it covers at least everything from a half to five, a factor of ten. Every curve in the chart below starts from the identical twenty-five numbers and runs for the same two hundred epochs, so the only thing separating them is the step size.

… walking eight runs of two hundred epochs

At 0.5 the loss reaches 0.135431 and every person is called correctly, at 2.0 it reaches 0.024188, and at 5.0 it reaches 0.008412. All three end at an accuracy of 1.000. The rate of 5.0 is fifty times the rate of 0.1 and ten times the default the box at the top of the page uses, and it reaches the lowest loss of the eight, though it is also the only one of the three whose loss ever rises, on 3 of its 199 readings.

The picture usually drawn of a step size that is too large has the loss shooting off to infinity, and that is one of two things that can happen. The other, which happened here, is that the walk keeps producing perfectly ordinary numbers and simply stops making progress, overshooting the bottom on every step and landing somewhere no better than where it came from.

A rate of one hundred behaves the same way, rising on 77 of the 199 readings, reaching 0.550848 at epoch 193 and finishing at 12.186892. I expected at least one of these to produce a value that is not a number, and on this chain under this loss none of them does, however large the rate. The reason is worth knowing and is in the next section.

Switch the objective in the chart above from log-loss to squared error and the same chain, from the same starting numbers, at the same rates, does run away. The reason is that log-loss squashes the chain’s raw output into a chance before scoring it, so however large the output grows the slope it produces is bounded, while squared error compares the raw output with the target directly and its slope grows with the output without limit.

The gap between those two columns is worth a sentence. The loss overflows first, while the twenty-five numbers are still finite enough for another step to be built out of them, and it takes one or two more epochs before a step produces a number that is not a number. So the measurement stops saying anything an epoch or two before the chain does, and once the weights have gone there is nothing left to walk from, since every later slope is computed out of them.

The measurements above suggest a recipe rather than a formula, and it is the one the practice collections give. Start too large deliberately and come down. A rate that thrashes announces itself within a few tens of epochs, since the loss rises about half the time; a rate that is too small looks fine for as long as you care to run it and tells you nothing. Divide by three or ten until the loss falls on nearly every epoch, then take one more division as a margin.

Every step so far read all sixty people, measured the loss over all of them, and moved once. Nothing forces that. The loss is an average over rows and so is every slope in it, so an average over some of the rows is also a number, and a step can be taken against it. The rows a single step is taken from are its batch, and the batch size is the one setting that decides how many steps an epoch contains.

steps in one epoch  =  ⌈ rows ÷ batch size ⌉

60 ÷ 60  =  1 step        60 ÷ 15  =  4 steps
60 ÷ 30  =  2 steps       60 ÷ 1   =  60 steps

Reading every row before moving is the whole-batch case, and it is what Cauchy described. Reading one row before moving is the other extreme, and it is what the perceptron did and what Robbins and Monro justified. Everything between them is a choice, and the usual arrangement is to shuffle the rows at the start of each epoch and then walk through them in consecutive slices, so no row is used twice in an epoch and no batch is the same batch twice.

A batch of five people points in a direction, and that direction is not the direction all sixty point in. It is an estimate of it, correct on average over all the batches that might have been drawn, and any particular draw can be a long way off. That difference can be measured directly by asking for the angle between the two directions.

… running five thousand steps, which takes a second or two

The bars are the cosine of that angle at the untrained chain, averaged over two hundred draws. A batch of every row agrees with the whole crowd exactly, at 1.000, since it is the same calculation. A batch of thirty averages 0.780, a batch of fifteen 0.546, a batch of five 0.332 and a batch of one only 0.073, which is very nearly a right angle.

And the worst single draw of one person points at −0.785, which is about a hundred and forty-two degrees away from where the crowd wanted to go, so the step taken from that one person made the loss worse on the fifty-nine it did not read.

Even a batch of thirty, half the crowd, produced one draw at −0.0009. Half the data pointing at right angles to what all of it wanted is not a rare pathology, it is what an average over a small sample does, and the loop tolerates it because the next step reads a different half.

Given how badly a small batch points, the result of actually running it is the surprising part. The curves in the chart above are the same chain from the same starting numbers at the same step size, run for the same sixty epochs, differing only in how many rows each step read. They are not close together.

The run that read one person at a time finished at a loss a hundred and seventy times lower than the run that read all sixty, and it got there by taking sixty times as many steps. So what the table shows is that an epoch is a much bigger unit of work once it is cut into pieces, which is a different claim from a small batch being better, and section 16 sets out the three ways of making the comparison.

The batch of one is also the only one of the five whose loss ever rises. It goes up between consecutive epochs on 5 of the 59 occasions, while every other batch size falls on every single one. That is the noise from section 12 arriving as something visible, and it is the thing a small batch is usually credited with, since a step that sometimes goes the wrong way can leave a resting place that a step always going downhill would settle into.

I could not measure that benefit here and I am not going to claim it. This chain reaches an accuracy of 1.000 from every batch size that gets enough steps, so there is no bad resting place for the noise to rescue anything from. What is measurable on this crowd is the cost side, which is that the loss curve of the smallest batch is the only one you cannot read as a straightforward record of progress.

If a step on one row cost a sixtieth of a step on sixty rows, the batch size would be nearly free and the smallest would always win. It costs considerably more than that. The arithmetic inside a step is proportional to the rows, but the work around it, building the blocks, walking the chain, rebuilding every layer, is the same whatever the batch holds, and at this size that surrounding work is most of the cost.

So sixty times the steps cost thirty-seven times the time rather than sixty, which is a saving and a small one. The same measurement on a large network on a graphics card comes out very differently, because there the surrounding work is a smaller share and the arithmetic runs on hardware that is idle unless the batch is large, and it is the reason batch sizes in the hundreds are ordinary there and a batch of one is not.

There are three ways to hold something fixed while varying the batch size, and they answer three different questions. Fixing the epochs asks which run learns most from one pass over the data. Fixing the steps asks which run learns most per update. Fixing the wall-clock time asks which run learns most per second, which is the only one a person waiting for a result actually cares about.

An epoch is a complete pass through the training rows, however many steps that takes. It is a bookkeeping unit rather than a mathematical one, and it exists because it is the natural place to shuffle, to measure, and to decide whether to carry on. When the batch is every row, an epoch and a step are the same thing, which is why the distinction only becomes visible once Part 3 has been read.

The loss reported after an epoch is worth being careful about, because the backward walk measures on its way forward. The number an epoch reports therefore belongs to the chain as it stood before that epoch’s step, not after it. That is why the first reading of a run is the untrained loss, and why a run of two hundred epochs reports 0.135431 as its last reading while the chain it finishes with actually stands at 0.134309.

A loop can watch three things without any extra data. The loss it measured, the share of the training rows it then calls correctly, and the largest single slope anywhere in the chain. They tell you different things and they do not rise and fall together.

… walking two hundred epochs

The loss falls smoothly across the whole run. The accuracy does not, sitting flat for long stretches and then stepping up, because it only counts which side of a half each answer landed on while the loss cares how far from the truth each answer is. A chain can spend fifty epochs becoming more confident about people it was already calling correctly, which lowers the loss and moves the accuracy not at all.

And the largest slope rises before it falls, peaking at 0.084723 in the very first epoch, dropping to 0.024 by epoch 25, rising again to 0.052 by epoch 75 as the chain learns the nonlinear relationship it needs, and settling to 0.028 by the end.

On this run it does not stop. The loss falls by 0.3667 over the first hundred epochs and by a further 0.2249 over the second hundred, so it is still falling at a healthy rate when the run ends, and only from epoch 193 onward is it within a hundredth of where it finishes. Every person is called correctly from epoch 180. A loop stopped at 180 and a loop stopped at 200 would be indistinguishable by accuracy and clearly different by loss.

loss at epoch 1     0.7271        accuracy 0.483
loss at epoch 50    0.5893        accuracy 0.750
loss at epoch 100   0.3604        accuracy 0.917
loss at epoch 200   0.1354        accuracy 1.000

So the loss has not stopped falling here, and it would not stop if the run were three times as long, since a chain that can separate its training rows can always separate them more confidently. Something else has to say when to stop, and the three candidates are a fixed budget of epochs, a threshold on the largest slope, and a second set of people the steps were not taken from. Part 5 is about why the third is the only one of the three that answers the question anybody actually has.

Take fourteen of the sixty people, seven from each group, and train on those alone. Hold the other forty-six back and score them after every epoch too, without ever taking a step from them. Now there are two numbers per epoch. The first is what a loop watching its own progress would see and the second is what it cannot see, and the whole of this part is that the first says almost nothing about the second.

The chain here is given eight hidden tangent units rather than six, thirty-three numbers over fourteen people, which is more than enough capacity to describe those fourteen exactly. Three of their labels are then flipped, so that there is something in the training rows the rest of the crowd genuinely does not share.

… running six hundred epochs and scoring both sets at each

The two lines separate almost immediately and never come back together. The training loss falls from 0.7210 to 0.0757 over six hundred epochs, and it falls on every one of those six hundred without a single exception. The held-out loss reaches its lowest point of 0.5354 at epoch 73 and then rises on every one of the epochs after it, all the way to 1.6472.

Epoch 73 is where the walk should have stopped, and it is invisible from inside. At that epoch the training loss stands at 0.3070 and is still falling, and nothing about it announces anything. Every one of the remaining five hundred and twenty-seven epochs lowered the training loss and raised the held-out one.

This is what early stopping is, and it is why it needs a second set of people rather than a cleverer reading of the first. Keep the numbers from the epoch at which the held-out loss was lowest, and throw away everything the walk did afterwards. It costs one extra measurement per epoch and a copy of the chain, and Prechelt’s 1998 chapter is about the awkward practical question of how long to keep going after a new low before believing it was the last one.

Having a held-out set does not settle the question by itself, because there is more than one way to score it. The held-out loss is lowest at epoch 73, and the held-out accuracy is highest at epoch 51, where it reaches 0.7609. Those are twenty-two epochs apart on a six-hundred-epoch run, and they are two defensible answers to the question of when this walk was at its best.

The disagreement has the same source as the one in section 18. Accuracy only counts sides and loss counts distances, so a chain can become more confident about people it is calling wrongly, which raises its loss without changing its accuracy at all. Whichever of the two you stop on, say which, since reporting a stopping epoch without saying what it was chosen by is not reporting anything.

The rising held-out curve above is the textbook picture, and it needed three flipped labels to produce. Press the other button on the chart and the same fourteen people with the labels as they were drawn give a curve that flattens instead. The held-out loss reaches 0.2469 at epoch 256, and it does rise on every one of the three hundred and forty-four epochs after that, by 0.0113 in total. The held-out accuracy reaches 0.9130 at epoch 131 and is still exactly 0.9130 at epoch 600.

So the shape of the second curve depends on what there is in the training rows to memorise. With clean labels a chain with spare capacity mostly stops learning anything new, and with three rows contradicting the pattern it spends five hundred epochs learning those three and gets steadily worse at everybody else. The training loss cannot tell the two cases apart at all, finishing under 0.1 in both.

A training loop has at least two sources of randomness, the draw of the starting numbers and the order the rows are visited in, and both are usually controlled by a seed. It is worth knowing precisely what fixing them buys, so the measurement below runs the same configuration twice and then changes one seed at a time.

… running nine loops and four sequences of draws

Two identical requests land on 0.05945412 and 0.05945412, the same to the last bit, which is what makes any of the numbers on this page quotable. Changing only the order the rows are visited in, with the starting numbers untouched, gives 0.05903582 instead, so the order is doing real work. And changing that same order seed on a run that takes the whole crowd in one batch changes nothing whatever, both landing on 0.53659416.

What a seed does not fix is which resting place the walk finds. The loss over twenty-five numbers is not a bowl with one bottom, so where the walk ends depends on where it began, and four draws of the starting numbers under the identical loop end up somewhere different each time.

… running nine loops and four sequences of draws

Three of the four call every person correctly and the fourth reaches 0.9667, one person short, and its loss of 0.155376 is about half as much again as the 0.107094 the best of them reached. Note that the fourth also started highest, at 0.821393 against 0.698006, though four draws is nowhere near enough to say the two are connected.

One kind of layer holds a source of randomness of its own, the one that silences a random share of its units on every training pass. Every other layer here can be rebuilt from its numbers at any moment without consequence, and that one cannot, because rebuilding it rebuilds its generator at the same position and the next pass draws exactly what the last one drew.

… running nine loops and four sequences of draws

On the left, one layer is carried across four passes, and no two passes keep the same units. On the right the same layer is rebuilt from the same seed before each pass, and all four passes are identical, which over a whole run would silence the same units every time and leave a permanently narrower layer instead of one that breaks a different partnership on every pass.

So a layer holding a generator has to be carried through the step rather than rebuilt from its settings, which is the one place in a walk where a step cannot hand back something newly made.

Everything above is a setting somebody has to choose, and a loop that leaves any of them unstated cannot be reproduced by anybody else. The list is short enough to write out in full.

Section 27 is the list of things a report has to state. This one is the list of things a loop has to decide before it can run at all, which is nearly the same list read from the other end, and each of the five has more than one defensible answer with a price attached.

Written out at its smallest the loop is two lines inside a counter, and none of the five choices is visible in either line. They are all decisions about the counter, about which rows the two lines read, and about when the counter stops.

repeat, once per epoch:

    measurement  ←  score the chain and walk the blame down
    chain        ←  move every number against its own slope

A loop can be handed settings that are not wrong so much as empty, and it is worth going through them once, because several of them run all the way to the end and hand back a perfectly ordinary number. The table gathers the cases, with what the mathematics says in each.

The cases above are not all found at the same moment, and the moment is worth knowing, since a walk that only comes apart on its hundred and fifty-fifth pass has spent a hundred and fifty-four passes looking perfectly healthy. Sorted by how early each of them can be known, they fall into four kinds.

The first line is the one worth dwelling on, because it is the only failure here that can be settled by looking at the chain and nothing else. A layer reading eight numbers cannot follow a layer answering with five, and no data changes that, so the question can be asked while the chain is being put together rather than hours into a run, which is the argument the shapes page makes at length.

The plain step of section 2 is the beginning of a long list. Momentum carries part of the previous step into the next one, which helps where the slope points across a narrow valley rather than along it. Per-number step sizes give every one of the twenty-five its own rate, adapted from how large its slopes have been, which is what makes the single global rate of Part 2 less critical.

Neither is on this page, and both need the step to widen from taking a rate to taking something carrying state of its own, which is the same problem the layer holding a draw already posed in section 26.

What does not change is the shape of the loop. It measures, it moves, it does that again on some rows, and some rule eventually says to stop. Momentum and the rest change what moving means, early stopping changes what stopping means, and the arrangement of the four is the same arrangement Cauchy described in 1847.