It is two in the morning and you are the night clerk. Letters keep coming. You cannot read a word of any language on Earth. You have two wire baskets, a pencil, and a ledger with one line per word. By dawn you will be better at spotting a lie than anyone in the building — and you still will not know what a single word means.
A hands-on hour inside the Bayesian spam filter — Stanford & Microsoft Research, 1998; a kitchen-table essay, August 2002. Everything on this page is computed live in your browser. Nothing is pre-recorded.
Act one · 3 May 1978
Gary Thuerk sold computers for the Digital Equipment Corporation. On 3 May 1978 he wanted to invite the West Coast to an open house for two new machines, the DECSYSTEM-2020 and the DECSYSTEM-2020T. He had a list of roughly four hundred people on the ARPANET — nearly everybody who was the ARPANET on that coast — and he did not feel like typing four hundred letters.
So he sent one letter to all of them. The mail system could not hold that many addresses in the header, so the overflow spilled down into the body of the message, and the first piece of junk mail in history arrived with a long, ragged list of its own victims printed inside it.
The reaction was immediate and unanimous: don't do that again. A representative of the Defense Communications Agency made Thuerk promise. For about fifteen years, the promise held.
Then it stopped holding. By 2009 — measured across a whole year — about 85 out of every 100 messages moving through the world's mail systems were junk.Kaspersky Security Bulletin, Spam Evolution 2009: average 85.2% for the year; the single worst day, 22 February, hit 93%.
Here is the strange part. The thing that eventually pushed that number back down was not a law, and not a clever trick, and not a list of banned words. It was a piece of eighteenth-century arithmetic that does not understand language at all.
Instrument one
You are the clerk. Below is a stack of mail. For each letter you do exactly one thing: throw it in the keep basket or the junk basket. You are not judging the words. You are only sorting the envelope. The ledger does the rest.
Every time you sort a letter, every word inside it gets one pencil mark in one of two columns. That is the entire act of learning. There is no other step.
The desk, live. Each envelope you sort flies to a basket and leaves its words behind as marks on the open page.
Two tallies per word, and one number computed from them. That number is the whole filter.
| Word | In keep | In junk | Chance it means junk |
|---|
b = junk letters containing the word. g = keep letters containing it. The 2 is not a typo: Paul Graham deliberately doubled the "keep" side so the filter would rather let a spam through than eat a real letter. That single 2 is an ethical decision written as arithmetic.
How far each word leans
Computed live from your own sorting. Left of the line: this word smells like real mail. Right of it: junk.
Instrument two
A new letter lands. The clerk does not read it. The clerk looks up every word in the ledger, throws away the boring ones, keeps the fifteen that lean hardest in either direction, and multiplies. Watch it happen.
Turn them off one at a time and watch the verdict wobble. None of these three is in any textbook. All three exist because a real person was losing real letters and got angry about it.
Act two · the word "naive"
To multiply those fifteen numbers together, the filter has to assume that the words are strangers to each other — that seeing free tells you nothing at all about whether you will also see offer. This is not slightly wrong. It is wildly, embarrassingly wrong. Language is made of words that travel in packs.
Statisticians call the method naive Bayes, and the "naive" is not affectionate. It is a warning label. And yet the thing works. For fifty years that was an open scandal in machine learning: a method built on a false premise kept beating methods built on true ones.
Pedro Domingos and Michael Pazzani finally explained why, in 1997. Their answer is one of the loveliest ideas in the field, and you can feel it with your hands on the next bench.
Here is one word the ledger thinks is junk-ish. Now write that same word into the letter again and again. Each repeat is a new "independent" piece of evidence — as far as the filter knows.
Two bars. The tall one is the filter's confidence. The short one is the truth — because saying the same word ten times is still one fact about the letter, not ten.
The number becomes nonsense. The decision stays right.Domingos & Pazzani, "On the Optimality of the Simple Bayesian Classifier under Zero-One Loss", Machine Learning 29 (1997), 103–130.
That is the whole trick. A spam filter is never asked "how sure are you, to four decimal places?" It is asked one question with two possible answers: basket A or basket B. To get that right you do not need the correct probability. You only need to land on the correct side. Naive Bayes ruins the number and saves the answer, and for sorting letters the answer is all anybody wanted.
Which is also why you should never trust a naive Bayes filter's "99.97% certain". It is not lying to you on purpose. It simply has no idea it has counted the same fact ten times.
Instrument three
A filter that catches every spam is easy: throw away all the mail. The hard part is the other direction. Somewhere in this thousand-letter sack is a note from your grandmother that happens to use the word money. Deleting it is not a 1% error. It is a catastrophe with a face.
The filter you trained above is now run over a thousand fresh letters it has never seen. Every square below is one real letter, scored live.
Notice what the base-rate slider does to the middle number while the guillotine stays still. The filter did not get better or worse. The world changed, and the same filter's answers changed meaning underneath it. This is the single most misread fact in all of applied machine learning.
Moving the guillotine
Measured on the same thousand letters, at every threshold from 0.50 to 0.999. The vertical line is where you have it set.
Train the same filter on 5 letters, then 10, then 20, and so on. Test it twice: on the letters it studied, and on a thousand it has never seen. The gap between the two lines is the oldest ghost in machine learning.
Accuracy against the size of the ledger
Measured in your browser, right now. Each point is a filter trained from scratch.
The orange line is the filter grading its own homework. The blue line is the only one that matters. A filter that has memorised forty letters perfectly and fails on the forty-first has learned nothing; it has just built a very small museum.
Act three · the other side of the desk
Every filter creates the thing that defeats it. The moment enough people ran a word-counting filter, the people sending junk started writing for the filter instead of for you. Swap a letter for a digit. Bury the pitch under a paragraph of a stolen novel. Sprinkle in words your grandmother would use. This is called Bayesian poisoning, and it is the first adversarial attack on a machine learning system that ordinary people ever lived through.
Your message has to score below the guillotine to be delivered. Try to get it there without changing what it is selling.
Press the report button and watch the disguises die. Every invented spelling you used is now a word in the ledger with a mark in exactly one column — and the more inventive you were, the more damning each one becomes. The filter does not need to know that v1agra is a drug. It only needs to have seen it once, in the junk basket.
"If a lot of the brain of the filter is in the individual databases, then merely tuning spams to get through the seed filters won't guarantee anything about how well they'll get through individual users' varying and much more trained filters."Paul Graham, "A Plan for Spam", August 2002.
That is the deep move, and it is not a maths trick. A single global filter is one lock, and one key opens it everywhere. Ten million filters each trained on one person's own friends, jobs, jokes and grandmothers are ten million different locks. The spammer can no longer test their key.
Did poisoning work? Honestly: sometimes. In 2004 John Graham-Cumming showed that just throwing random words at a filter was nearly useless — about 4 messages in 10,000 got through. But Wittel and Wu, the same year, pushed spam past SpamBayes by adding fifty ordinary English words; and Stern, Mason and Shepherd measured a filter's precision falling from 84% to 67% under the same attack. The spammers' better answer, in the end, was to stop using words at all and send pictures instead — which is how the spam war walked straight into computer vision.
The long version
Things this page is not sure about
A lesson that hides its soft spots is a sales pitch. Here are the places where the story above is thinner than it looks.
The exam