A First Taste of Algorithms

Chapter 8: Learning as an Algorithm

✦ ✦ ✦

In which the two questions soften without surrendering, and an old wound reopens on a landscape

A different kind of problem

Every problem in this book so far came with a definition. “Sorted” has a definition; “shortest path” has a definition; an algorithm could be proved correct because correct meant something exact. Now consider the problems your devices answer all day: is this email spam? Is this photo of a cat? Given the words so far, what word comes next? Try to write the definition of “cat photo” precise enough to check a procedure against. There isn’t one. Nobody has one. And yet the problems get solved, billions of times a day, to a standard everyone lives with.

The escape is a different deal with the problem. Instead of a definition, you are handed examples — ten thousand photos labeled cat/not-cat, a million emails labeled spam/not-spam — and the task becomes: produce a procedure whose answers agree with the examples, and keep agreeing on examples you haven’t seen. An algorithm fitted to examples rather than derived from a definition is called learning, and this chapter’s claim is that it is not a new subject. It is this book’s same two questions, in their final form:

Does it work? softens to: is it approximately correct, on average, over the examples the world will actually send? — and Chapter 7 spent itself making “on average” a phrase you can compute, concentrate, and trust. That promotion is cashed here, immediately and forever.
What does it cost? doesn’t soften at all. We still count.

The simplest learner

Here is a complete learning algorithm, four lines long, with no training step whatsoever. The examples are points — say, each point is (hours of sleep, hours of practice) for a student, labeled by whether they passed the audition. To predict a new student’s fate: find the example nearest to them, and copy its label.

That’s the whole algorithm — nearest neighbor — and “learning” here is just storage: the learner memorizes the examples and does nothing else until asked. All the cost lands at answer time, and the cost is an old friend wearing new clothes: finding the nearest point in a pile of n examples is search — Chapter 1’s linear scan, distance instead of equality, n steps per question. (And Chapter 1’s sequel question returns with it: could structure make the search cheap, the way sortedness did? For points in space the answer is yes, with lovely data structures this book only waves at — but the instinct to ask is the chapter’s point.)

Figure 8.1 — The nearest-neighbor map: twelve memorized examples and the territory each one governs. Note the island around the lone deep point — memory, faithfully serving one example, possibly an error.

Simple as it is, nearest neighbor already contains the field’s central tension, visible in its map. Each memorized example governs the territory nearer to it than to anything else — and one example deep in foreign territory (a mislabeled point, an odd duck) carves out a little island of its influence. The learner serves that island as faithfully as everything else, because the learner cannot tell data from noise: it memorizes both. Whether faithful memory is wisdom or gullibility is the question the chapter ends on. File the island; we return to it.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses