Kangaroos and Training Neural Networks

Somewhere in a machine learning system there are numbers that can be turned, like dials. Nobody sets them by hand. The machine finds them by trying something, seeing how wrong it was, adjusting, and trying again — a few million times.

That process has a name, numerical optimization, and a reputation for being impenetrable. It is not. It is a kangaroo looking for a mountain.

Training a NN is a form of numerical optimization, which can be likened to a kangaroo searching for the top of Mt. Everest. Everest is the global optimum, the highest mountain in the world, but the top of any other really tall mountain such as K2 (a good local optimum) would be satisfactory. On the other hand, the top of a small hill like Chapel Hill, NC, (a bad local optimum) would not be acceptable. Warren S. Sarle, comp.ai.neural-nets, 1993

Here is the mountain he means. This one is not a metaphor and not a drawing — it is twenty kilometres of the Khumbu, sampled every seventy-eight metres from public elevation data, with Everest in the middle.

Worth one aside, because it is the whole article in miniature. Everest is 8,849 metres. The highest point in that data is 8,749 — a hundred metres short, and it stays short however finely you sample it. The surveyed number comes from people standing on the summit with satellite receivers. This comes from radar looking down at a snow-covered pyramid from orbit, onto a grid that has no sample exactly on the peak, and a grid cannot hold a point it never measured.

Nothing in the rest of this piece is stranger than that. Every landscape a machine climbs is a sampled one, and it is always a little lower and a little smoother than the thing it stands for. Hold onto it; we come back to it at the end.

The map

Two things need translating before the kangaroo can start.

The compass is the dials. North–south is one number the machine can turn; east–west is another. Every position on the map is one particular setting of those two dials.

Altitude is how well it is doing. High ground is a good answer, low ground is a bad one. Sarle put it the other way round — machine learning people measure error, so they talk about descending into valleys — but multiply by minus one and it is the same landscape. Uphill is better. That is all you need.

Two dials, of course, is a lie of convenience. A real system has millions, and the landscape has millions of directions rather than four. Nobody can picture that, including the people who work on it every day, and the two-dial version is what they picture instead.

Now the hard part, which is the part everyone skips.

Initial weights are usually chosen randomly, which means that the kangaroo is dropped by parachute somewhere over Asia by a pilot who has lost the map. Sarle

She does not get to pick where she starts. She does not know where Everest is — if anybody knew, there would be no need to search. And she cannot see the landscape you are looking at. She can only feel the ground under her feet.

Everything that follows is a different answer to one question: given that, which way should she jump?

Act one: feeling around

The simplest possible answer. Jump somewhere nearby at random. If the new spot is higher, stay. If it is lower, go back and try a different direction.

That is a hill climber, and it works, in the narrow sense that it always ends up somewhere higher than it started.

Watch the rejected attempts. Most jumps are wasted. She is not being clever; she is being persistent, and near the top she spends most of her effort discovering that everything around her is lower.

What she actually sees

Everything above is a lie of presentation. You have been looking at the whole landscape this entire time. She has not.

Two things are worth sitting with here.

The first is the number in the corner. They work hard — four independent searches, hundreds of evaluations between them — and cover almost none of the world. A search can look energetic and still have touched a few per cent of the map. Nothing about being busy makes it thorough.

The second only shows up on the second toggle. Turn the landscape on and she is standing next to something enormous that she has no way of knowing about. Turn it off again and that mountain simply does not exist, because for her it does not. Every judgement she makes is correct given what she can feel; it is the given that ruins her.

This is the honest version of every other figure in this article. The rest are drawn our way round because a dark screen teaches nothing — but her way round is the true one, and it is worth having seen once.

The same thing works in three dimensions, and it is worth one look because the flat map understates it. From above, unseen ground is merely dark. In relief, it is not there — she is hopping along a thin lit ridge suspended in nothing, and the mountain she is on has no visible shape beyond the few metres she has walked.

There is an obvious improvement available: stop guessing which way is up, and measure it.

The bowling ball

This is the bit that usually gets replaced with a paragraph of calculus. In the same thread, Lutz Prechelt refused to do that, and explained it with sports equipment instead. He starts by naming the gap:

The analogy only explains WHAT the algorithm does, but not HOW it does the most intricate part: chosing the direction of the next jump. Lutz Prechelt, comp.ai.neural-nets, 1993

Then he closes it. The kangaroo digs two trenches at her feet — one running north–south, one running east–west — and lines them with steel, and then teflon, so that they are perfectly smooth and frictionless. She takes a bowling ball out of her pouch, drops it into the north–south trench, and watches which way it rolls, and how far.

Then she does the east–west trench.

Say the ball rolls 8 cm north and 14 cm east. Now she multiplies. A kangaroo using a learning rate of 50 jumps to a point 4 metres north and 7 metres east of where she was standing.

That is the whole of it. The two trenches are the two dials, tested one at a time. How far the ball rolls is how steeply the ground falls away in that direction. And the learning rate is a multiplier — 8 cm becomes 4 m because 8 × 50 = 400.

It is not important for the algorithm whether the kangaroo uses the same bowling ball over and over again, or throws it away after each measurement and picks a new one from its pouch next time. This is because in the backpropagation world, bowling balls bio-degrade in zero time. Prechelt

Two trenches, two numbers, one multiplication. That is a gradient, and it is the entire mechanism the phrase “the network learns” is standing in front of.

Here is that, with everything she cannot see taken away.

That single arrow is the entire content of a backpropagation step. Not a plan, not a route, not a view of the mountain — one direction, measured where she is standing, thrown away as soon as she lands.

Act two: how far to jump

The learning rate looked like a footnote. It is not. It is the single number most likely to be wrong, and Sarle spends more of the thread on its failures than on any other topic.

The trouble is what the multiplier is applied to. Roll distance depends on steepness, so the jump does too:

A major problem with standard backprop is that the distance the kangaroo hops is related to the steepness of the terrain. If the kangaroo starts on a gently sloping plain instead of a mountain side, she will take very small hops and make very slow progress. When she finally starts to ascend a mountain, her hops get longer and more dangerous, and she may hop off the mountain altogether. Sarle

Three failures in one paragraph, and they pull in opposite directions.

Too small and she is correct and useless. Too large and the first jump from steep ground throws her clean across the map — she has not made a mistake about direction, only about how much to trust it.

And there is a third failure that only shows up at the end:

If the kangaroo ever gets near the peak, she may jump back and forth across the peak without ever landing on it. If you use a decaying step size, the kangaroo gets tired and makes smaller and smaller hops, so if she ever gets near the peak she has a better chance of actually landing on it before the Himalayas erode away. Sarle

A jump sized for crossing a plain is far too big for a summit. The fix is to get tired on purpose: shrink the jump as you go. Modern systems all do some version of this, and call it a learning rate schedule.

Act three: getting unstuck

Everything so far shares one flaw, and it is fatal.

Every method above only ever goes uphill. Which means every one of them stops at the top of whatever hill it happened to land on. Not Everest — the nearest hill. If the parachute dropped her on Chapel Hill, she climbs Chapel Hill, plants a flag, and reports success.

This is not a rare edge case. It is the normal outcome.

Four runs, four answers. Nobody made a mistake and nobody can tell they are not alone — each kangaroo did the correct thing given what she could feel under her feet, and where she ended up was decided by the parachute rather than by the climbing.

Run it across thirty starts on a landscape that does have one true summit and the same thing shows up as a number.

So the rest of the thread is about kangaroos willing to do something that looks, locally, like a mistake.

Get drunk

In simulated annealing, the kangaroo is drunk and hops around randomly for a long time. However, she gradually sobers up and the more sober she is, the more likely she is to hop up hill. Sarle

Early on she will go downhill happily, which means she can leave a hill she has already climbed and find a better one. As she sobers, downhill jumps get rarer, until eventually she only goes up and settles wherever she is.

The name comes from metalworking — heat a metal and cool it slowly and the atoms settle into a better arrangement than if you had quenched it. The kangaroo version is more memorable and means the same thing.

Send more kangaroos

If one kangaroo lands somewhere unpromising, land a hundred.

A genetic algorithm begins like random multistart. However, these kangaroos do not know that they are supposed to be looking for the top of a mountain. Every few years, you shoot the kangaroos at low altitudes and hope the ones that are left will be fruitful, multiply, and ascend. Sarle

Which is, allowing for the phrasing, an accurate description of a genetic algorithm. Scatter a population, cull the low ones, breed the survivors, repeat.

Nothing in that figure climbs. Each generation is a scatter of individuals standing where they were born, and the only thing that happens is that the scatter gets denser in the good places and empties out of the bad ones. That is the whole mechanism — no kangaroo ever improved, the population did.

A third is not a good number. It is an enormous improvement on zero.

Sarle then undercuts his own animal:

Current research suggests that fleas may be more effective than kangaroos in genetic algorithms, since their faster rate of reproduction more than compensates for their shorter hops. Sarle

Put her on the actual Earth

Every landscape so far has been invented. They are good landscapes — they were designed by people who wanted to know whether a search method works, and they are hard in the specific ways real problems are hard — but nobody has ever stood on one.

So here is the planet. The same elevation data as the Everest close-up at the top of this page, all of it, at seventy-eight kilometres to the sample. Sarle’s Everest and his K2 are both on it. So is Chapel Hill.

Drop sixty kangaroos at random, give each one two thousand two hundred hops, and let them work.

Fourteen of the sixty hill climbers drown.

That is not a figure of speech and it is not a tuning problem. Two thirds of this planet is ocean, so a quarter of the random drops land in one — and on an abyssal plain there is no uphill to find. She feels around, everything nearby is the same depth or deeper, and she stops. No step size fixes that. Nothing from act two fixes that. The method’s entire strategy is go up from here, and there is no up.

The annealed kangaroo, from the identical sixty starting points and the same number of hops, averages five thousand three hundred metres and every single one of them ends on high ground. The difference between the two panels is one rule: be willing to go downhill at first. She can leave the ocean because she is drunk enough not to care that leaving makes things worse.

The sobering-up schedule is the whole game

Annealing has a dial, and until now it has been set for you. It governs how fast she sobers up. Here is what it does.

Read it as a collapse. Sober up fast and the sixty runs finish on twenty-one separate highlands — Greenland, the Rockies, the Andes, the Ethiopian highlands, the Alps, a scatter across Antarctica. Every one of them is a perfectly real mountain. None of them is the highest.

Sober up slowly and they finish on three, and fifty-odd of the sixty are on the same one.

This is the clearest thing in the article, and it is worth saying plainly: the schedule does not decide how well she does. It decides which mountain she ends up on. A kangaroo who freezes early is not searching badly — she is searching a smaller world, one that happens to contain whatever she was standing near when she stopped being willing to leave.

Notice what she settles for at 0.9 and 0.99, too. The single most common outcome is the Antarctic plateau: a vast, easy, high place that is nowhere near the highest. Broad and easy beats narrow and tall, every time, for a searcher who has stopped wandering.

How far, not just how willing

There is a second dial, and this is the one the metaphor keeps eliding. Temperature governs how willing she is to go downhill. It says nothing about how far she jumps. Those are different things and they fail differently.

Over two hundred runs of three thousand hops on this planet:

Big hops find the right continent and can never resolve a summit. Small hops resolve a summit and can never cross an ocean. Neither is wrong; they are answers to different questions, and the run only asks one of them at a time.

Which is Sarle’s tired kangaroo, arriving where it was needed all along:

If the kangaroo gets tired and makes smaller and smaller hops, she will eventually make it to the top of the nearest mountain. Sarle

Start with the hops of a kangaroo who has no idea where she is, and end with the hops of one who thinks she is nearly there. That beats every fixed setting at actually standing on the summit.

And it can be overdone, in exactly the way act two warned. Shrink too fast and she is crawling before she has finished looking — thirty per cent decaying to nothing scores worse than not decaying at all. Getting tired is a strategy. Getting tired too early is just stopping.

Act three and a half: the kangaroo who draws her own map

This one is not in the email. Sarle was writing in 1993 and the method arrived properly in 1998, so nobody in the thread could have mentioned it. It is here because it is the only idea in this article that is different in kind from everything above, rather than different in degree.

Every kangaroo so far has been cheap and blind. Hundreds of hops, each decided from what she can feel under her feet at that instant, and nothing remembered except the best spot so far.

This one is expensive and thoughtful. She hops about twenty times in total. Between hops she sits down and reconstructs the entire landscape from the handful of places she has actually stood — and, crucially, marks how sure she is about each part of the reconstruction.

Then she goes wherever the answer to one question is highest: where might I find ground better than the best I have found so far? Which is not the same as “where do I think it is high”. A place she is confident is merely average scores nothing. A place she knows nothing about scores well, because it might be anything.

And here is what was actually there the whole time. Same camera, same vertical scale, same twenty-two hops drawn on top — the only difference is that this one is the real landscape rather than her reconstruction of it.

Watch her walk away from a summit. She will climb something, confirm it is good, and then leave — because a blank grey region on the other side of the map might be better, and she will never know unless she goes and stands there. None of the other kangaroos can do that, because none of them knows what it does not know.

The same map, from her side

Act one ended with a hill climber that took two hundred hops and sensed four per cent of the world. Here is this kangaroo doing the same thing, with the same controls.

The pools of light are the whole difference. The hill climber’s coverage is one smear, because each hop had to start where the last one ended. These are scattered across the map, because she was never obliged to walk — between hops she thinks, and thinking is free. She still cannot see the landscape. She has simply stopped needing to.

How eager should she be to wander?

That question has a number attached, and it is the most interesting dial in the whole article, because it is the only one where both extremes are bad.

Everywhere else, a setting is either right or it is too much of something. Too small a learning rate is slow; too large and she flies off the mountain — but “slow” and “broken” are not the same kind of failure. Here the two failures are symmetric, and each is the other’s cure.

The number is how much credit she gives to not knowing. Call it her optimism: when she scores a place, she takes what she expects to find there and adds a few multiples of how uncertain she is. Nothing else changes.

• No optimism at all. She goes wherever her map already says is highest. Her map says it is highest because she has been there. So she goes there again. And again.
• Enormous optimism. She goes wherever she knows least, which is always the place she has been furthest from. She conducts a beautiful survey of a continent and summits nothing.

The second and fourth panels are the argument. κ = 0.5 visits eighteen places and finishes at −0.8. κ = 8 visits all twenty-five and finishes at −15.7. The thorough one loses, by a factor of twenty. It maps the terrain beautifully and never converts any of it into altitude, because every time it gets near something good it notices somewhere it has not been.

And the greedy panel is worse still, in a way that is easy to miss: it looks like it has taken four or five samples. It has taken twenty-five. They are stacked on top of each other, because with no credit for uncertainty the best-looking spot on the map stays the best-looking spot on the map forever. Its line on the chart below is flat from the fifth evaluation onward — twenty wasted hops.

There is no universally right setting. The best value depends on the landscape, which she cannot see, which is the whole problem she was built to solve. This is where the honest answer becomes uncomfortable, and it is the same uncomfortable answer as the learning rate in act two: you tune it, by trying values and seeing what happens.

And this closes a loop. The expensive-to-evaluate thing this method was built for is, in practice, training a machine learning model — you cannot afford thousands of attempts when each one takes a day. So the honest answer to “how do you pick the learning rate from Act two?” is that you optimize that too, with this. The kangaroo ends up searching for a kangaroo.

Act four: where the mountains came from

Everything so far has assumed the landscape is simply there — a fixed thing the kangaroo is exploring badly. Prechelt points out, most of the way down the thread, that this is completely false, and it is the most important sentence in it:

Why does the Himalaya look just like it does? The answer is: it doesn’t. The mountains in which the kangaroo jumps around are `induced’ by your training data. Each example suggests certain hills or mountains at certain points on the surface of the (otherwise absolutely flat) earth. Prechelt

The ground is not scenery. It is built out of the examples you showed the machine. Start with a flat plain; every training example raises a hill where it falls; the landscape is what you get when they all pile up.

Ten examples give you ten lumps. A thousand overlap into something that looks like real terrain.

Here is the part that should worry you.

Draw a different twelve examples — same machine, same process, just a different handful of data — and rebuild. The big mountains stay roughly where they were. The small hills move somewhere else entirely.

Which tells you something the kangaroo cannot know: the big mountains are real and the small hills are an accident of which examples you happened to get. Under her feet they feel identical. Both are solid ground, both slope upward, and she has no way at all to tell them apart.

So when she summits a small hill and plants her flag, she has climbed something that exists only because of the particular examples she was trained on. Show the machine different data and the mountain is not there. She is standing on a plain, at no particular height, having climbed nothing.

That is what overfitting is. Not a subtle statistical failure — a kangaroo triumphant on top of a hill that was never there.

And it is why anyone serious keeps some data back. A landscape built from examples the machine never trained on is the only way to ask whether the mountain was real.

More data, fewer imaginary mountains. Which is the entire reason the industry is so hungry for it.

Standing on ground that keeps moving

One more consequence, and it explains something that otherwise looks insane.

Real systems do not build the whole landscape before setting off. They show the machine a handful of examples, take one step on the landscape those examples build, then throw it away and draw a fresh handful.

Sarle saw it coming:

With on-line training, there are frequent earthquakes, and mountains constantly appear and disappear. This makes it difficult for the blind kangaroo to tell whether she has ever reached the top of a mountain, and she has to take small hops to avoid falling into the gaping chasms that can open up at any moment. Sarle

It sounds like a disaster and it is how essentially everything is trained. No single handful is right, but the errors point in different directions and mostly cancel; the pull toward the real mountains is the one thing every handful agrees on. It is also why very large steps and very small batches are a bad combination — you are taking a confident stride on ground that is about to be demolished.

What actually works

Prechelt ends with a ranking. After a full page of algorithms, he lists the best ways to find Mount Everest:

1. to know where it is
2. to have a map on which you can find it
3. to know someone who knows where it is or who has a map
4. to send a kangaroo to search for it

Prechelt

Every method in this article is number four. Dead last, behind asking a friend.

It is a joke, and it is also the practical summary of the last decade of the field. Nobody starts from a random parachute drop any more if they can avoid it. They start from a model somebody else already trained — someone else’s map, which is number two, or number three if you count downloading it.

Searching is what you do when you have nothing better. It works. It is just not the first thing to reach for.

Have a go

Every figure above is fixed: one landscape, one algorithm, one seed, chosen to make one point. The tool is the same code with nothing fixed — all six searches, every landscape including the real ones, and every knob that was quietly set for you here, with a chart underneath saying whether it worked.

The most instructive thing you can do with it takes about thirty seconds: put a hill climber on Himmelblau and step the seed. Same algorithm, same landscape, same everything, and watch which summit she ends up on.