A First Taste of Algorithms · Learning as an Algorithm

A number called wrong

Classification copies labels; the other half of learning predicts numbers — tomorrow’s temperature, a house’s price, a test score from hours studied. Here the examples are pairs (x, y), and the learner is a formula with adjustable knobs. Take the simplest: predict y as w·x, one knob, the slope w. Which w is best?

The move that unlocks everything: define wrongness as a number. For a candidate w, measure each example’s miss — prediction minus truth — square it, and average over all examples:

L(w) = average of (w·xᵢ − yᵢ)²

This is a loss function, and pause on what just happened, because it is the hinge of the whole subject: the fuzzy demand “fit the data well” became a single number L(w) attached to every candidate knob-setting, and learning became minimization — find the w making one number small. Everything after this is optimization. (Why squared misses, rather than absolute ones or fourth powers? Three honest reasons: squaring punishes large misses more than proportionally, which is usually what you want; it treats high and low misses symmetrically; and — decisive for the next section — the squared loss is smooth, a polished bowl Book 2’s calculus can get its hands on. There is also a fourth reason, which is that the choice has a track record older than electricity.)

A human moment

The loss function found a planet. On the first night of 1801, the astronomer Giuseppe Piazzi spotted a faint new object — Ceres, the first asteroid — and tracked it for six weeks before it slid behind the sun’s glare, carrying only a thin arc of noisy observations with it. The astronomers of Europe could not agree where it would re-emerge; the discovery was about to be lost. A 24-year-old named Carl Friedrich Gauss — yes, the schoolboy of Lab 0, third appearance, last one — attacked the problem with a then-private method: choose the orbit whose predictions make the sum of squared misses against the observations as small as possible, and trust the noisy data collectively though no single observation deserved trust alone. His predicted position was nowhere near anyone else’s. In December 1801, almost a year after its loss, Ceres was found again — essentially where Gauss’s minimization said to look — and an obscure young man became the most famous mathematician in Europe overnight. (Honesty about the credit: Legendre published the method of least squares first, in 1805, and the priority quarrel between them was real and bitter. The idea, as usual, was ready before either man.) Every loss function minimized in every training run today is the direct descendant of that orbit: wrongness made into one number, and the number made small.

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