How can a computer learn without being told the rules?

The full story

The episode's narration, word for word. Numbers link to the sources below; timestamps play that moment.

The question 0:00

Last time, we met machine learning: the part of AI that learns from examples instead of following rules people wrote. How can a computer learn something nobody told it? Start with a job that sounds easy to write rules for: spotting junk email.

Writing the rules by hand 0:19

Try it. If an email says "click", call it junk. In 2002 the programmer Paul Graham found that one rule alone caught about eighty per cent of his spam, while wrongly flagging about one good email in a hundred ¹. But the last few per cent were very hard, and every stricter rule flagged more good mail ¹. Researchers at Stanford and Microsoft had already warned, in 1998, that hand-made rule lists must be constantly re-tuned as junk mail changes, and that the work is tedious and error-prone ².

A checkers board at IBM 0:56

Arthur Samuel joined IBM in 1949, and in his spare time he worked on getting a computer to play checkers ^3,4. His first checkers program ran in 1952, on the IBM 701 ³. By 1955 he had a version that learned, and on the twenty-fourth of February 1956 it was shown on television ³.

Too many moves to write down 1:22

Why checkers? The rules are simple, but in the 1950s nobody knew a recipe that guaranteed a win, or even a draw ³. Samuel worked out that following every possible game would mean about ten to the power of forty choices of move ³. Even at three choices every billionth of a second, that would take about ten to the power of twenty-one centuries ³. So his program looked just a few moves ahead, then gave each board a score ³. The score was a weighted sum: count things like how many pieces each side has, multiply each count by how much it matters, and add them up ³.

The machine picks the weights 2:03

Apart from the basics, like counting pieces, Samuel didn't tell the program how much each thing mattered ³. He gave it the rules of the game, a sense of direction, and a long list of features that might matter, with their weights unknown ³. Those weights are just numbers, like dials on a mixing desk, and the program's job was to turn them ³. So nobody wrote the rules for playing well. Somebody wrote the rules for learning.

Alpha and Beta 2:33

How did it turn them? Samuel made two copies of his program, which he called Alpha and Beta ³. Alpha adjusted its weights after every move, while Beta kept its weights fixed for the whole game ³. Whenever Alpha came out ahead, Beta adopted Alpha's new settings ³. It was self-play, in the 1950s ³. An earlier version learned a different way, by rote: it saved more than fifty-three thousand board positions it had seen ³.

Beating its own author 3:05

In July 1959 he published the results, in a paper called "Some Studies in Machine Learning Using the Game of Checkers" ³. It reported that the computer had learned to play better checkers than the person who wrote the program, in eight or ten hours of play ³. IBM credits him with coining the term machine learning ⁴. You'll often see him quoted as saying computers can learn without being explicitly programmed, but that sentence isn't in the 1959 paper ³. What he actually wrote is more careful: learning from experience should eventually remove much of the need for detailed programming ³.

How good was it, really? 3:45

In 1962 the program beat Robert Nealey, a self-described checkers master ⁴. The win is often retold as beating a champion, but Nealey only won his state title four years later ⁵. The next year, in a rematch by post, Nealey won one game and drew five ⁵. In 1966, playing the two finalists of a world championship match, the program lost all eight games ⁵. It was a real milestone, not a superhuman player ⁵.

The smallest learning there is 4:18

So what does learning look like when you can see every step? Here are eight days at a beach kiosk: the top temperature, and how many cold drinks it sold. This data is made up, but the maths is real. Say you guess "two drinks for every degree". That line misses most days by a few drinks, and one day by ten. Learning means finding the line that misses least.

Squaring the misses 4:45

To score a line, take each miss, square it, and add them up ⁶. Squaring stops misses above and below from cancelling out, and makes big misses count far more. The guessed line scores two hundred and thirty-two. The best possible straight line scores about fifty-two. It says about 2.9 extra drinks per degree, adjusted by a bias of minus twenty-three. Those two numbers are the whole model. In the jargon, the slope is a weight, the fixed adjustment is the bias, and finding them from examples is called training ⁷.

An idea from the comets 5:25

The French mathematician Adrien-Marie Legendre published this method of least squares in 1805, in a book about the orbits of comets ^6,8. In 1809, Carl Friedrich Gauss published it too, said he'd been using it since 1795, and a long argument over who came first followed ^6,8. Much of machine learning uses the same basic idea, with far more dials: score the misses, then make the score small.

Training, then using 5:57

Once the two numbers are found, the examples can be put away. Give it a new day, say thirty-eight degrees, and the line predicts about eighty-six drinks. Training happens once, or now and then to update ⁹. Using the trained model, which the field calls inference, happens every time a new question comes in ¹⁰.

A spam filter that counts 6:19

Now back to spam, the learning way. Start with emails that a person has already labelled, spam or good ¹⁰. Here are eight made-up ones. For each word, count what share of the spam contains it, and what share of the good mail does. In our little pile, the word "free" turns up in half the spam but a quarter of the good mail, so it's a bit spammy. The words "cash" and "prize" show up in spam but not in good mail, so they're spammier, while "notes" and "lunch" lean good. Adding one to every count means no word is ever treated as impossible.

Scoring a new email 7:00

A new email arrives: "free cash prize". Combine its word scores the way Graham's filter did, and it comes out at about ninety-three per cent spammy ¹. "Notes for lunch" scores about five per cent ¹. This is called a naive Bayes filter ¹¹. It's naive because it treats every word as independent of the others, which isn't true, yet it famously works well for spam ¹¹. But its scores are better for sorting than as true probabilities ¹¹.

What the counting found 7:32

Nobody wrote "free means spam". The numbers came from the labelled mail, so each person's filter can learn from their own ^2,1. Graham, training on about four thousand emails of each kind, reported missing fewer than five spams in a thousand, with no good mail flagged ¹. And it found clues he'd never have written down ¹. The code for bright red text, f f zero zero zero zero, turned out to be as strong a sign of spam as any rude word ¹.

Testing on emails it hasn't seen 8:06

How do you know it learned, rather than just remembered? You test it on examples it never trained on ¹². The 1998 Stanford and Microsoft team trained their filter on 1,538 real emails, then tested it on 251 that arrived later ². Google's machine learning course gives a warning example: a spam model that looks ninety-nine per cent precise, but only because many test emails are copies of training ones ¹².

It learns whatever is in the data 8:37

A model learns whatever pattern is in its examples, including accidents. In 2019, researchers tested a skin-cancer image classifier on harmless moles, photographed with and without the pen marks surgeons draw on skin ¹³. With the marks, it correctly cleared only about forty-six per cent of them, down from eighty-four ¹³. With the marks cropped out, it cleared ninety-seven per cent ¹³. It seems to have learned that pen marks go with worrying moles ¹³.

Wrong answers in the answer key 9:09

Labels can be wrong too. A 2021 study estimated that at least three per cent of the labels in ten widely used test datasets were wrong, on average ¹⁴. And if the answer key is wrong, even the marks can't be trusted: models get graded against the mistakes ¹⁴. Wrong labels in the examples a model learns from are a problem too.

Memorising the practice exam 9:33

Give a model enough dials and it can fit every example exactly. Here, a curve with eight dials passes through all eight practice days with zero error. But on seven new days, its average squared miss is about one hundred and thirty-four, around twenty times worse than the plain line's. That's overfitting: matching the training examples so closely that it fails on new ones ¹⁵. It's like memorising last year's exam answers. You ace the practice paper and fail the real one.

Where the analogy breaks 10:09

Where that analogy breaks: a student can memorise and understand, but an overfit model has simply fitted the noise, the random wobble in its data ¹⁶. Keep some examples back for testing only ¹². If a simpler model does as well, prefer it ¹⁷. And get more examples, and more varied ones ¹⁰.

The road Samuel didn't take 10:31

So a computer learns without being told the rules because someone writes the rules for learning, and the examples do the rest. In that 1959 paper, Samuel described a second road he didn't take: a randomly connected network of simple switches that learns by reward and punishment, inspired by nerve cells ³. He thought practical machines like that were a long way off, and his footnotes cite a new idea called the perceptron ³. That's the road today's AI took. So what is a neural network, and how is it not like a brain?

Sources

Every factual claim in the episode is tied to one of these. Spotted an error? Tell us.

1. P. Graham, "A Plan for Spam" (August 2002) — paulgraham.com
2. M. Sahami, S. Dumais, D. Heckerman, E. Horvitz, "A Bayesian Approach to Filtering Junk… — cdn.aaai.org
3. A. L. Samuel, "Some Studies in Machine Learning Using the Game of Checkers", IBM… — people.csail.mit.edu
4. IBM, "The games that helped AI evolve" (IBM history) — ibm.com
5. J. Schaeffer, Chinook project, University of Alberta: "Arthur Samuel's Legacy"… — webdocs.cs.ualberta.ca
6. Wikipedia: "Least squares" (history: Legendre 1805, Gauss 1809 and the 1795 claim, Ceres) — en.wikipedia.org
7. Google for Developers, Machine Learning Crash Course: "Linear regression" (y′ = b +… — developers.google.com
8. MacTutor History of Mathematics (University of St Andrews): "Adrien-Marie Legendre" — mathshistory.st-andrews.ac.uk
9. Google for Developers, Machine Learning Crash Course: "Static vs. dynamic training"… — developers.google.com
10. Google for Developers, Introduction to Machine Learning: "Supervised learning"… — developers.google.com
11. scikit-learn User Guide: "Naive Bayes" — scikit-learn.org
12. Google for Developers, Machine Learning Crash Course: "Dividing the original dataset"… — developers.google.com
13. J. K. Winkler et al., "Association Between Surgical Skin Markings in Dermoscopic… — jamanetwork.com
14. C. G. Northcutt, A. Athalye, J. Mueller, "Pervasive Label Errors in Test Sets… — arxiv.org
15. Google for Developers, Machine Learning Crash Course: "Overfitting" — developers.google.com
16. scikit-learn examples: "Underfitting vs. Overfitting" — scikit-learn.org
17. Google for Developers, Machine Learning Crash Course: "Model complexity" ("Simpler… — developers.google.com

Researched and scripted with AI assistance, fact-checked claim by claim, with synthetic narration and diagrams drawn in code. How we make episodes.