Image: Joe Mabel (CC BY-SA 3.0)How a spam filter decides
The spam filters that cleaned up email in the early 2000s did not know what spam was. They counted words. Paul Graham's essay "A Plan for Spam" of 2002 described a filter that scored every word by how often it appeared in spam against legitimate mail, combined the scores, and caught more than 99 per cent of spam with almost no false alarms; the hand-written rules it replaced had managed far less. The method is naive Bayes, it fits on one page, and you can do it with a pencil.
Counting words in twenty emails
Suppose a vocabulary of six words: free, offer, win, meeting, report, project. For each email we note only whether each word appears, not how often. Twenty training emails, 8 of them spam and 12 legitimate (call them ham), give these counts of emails containing each word:
- Spam (8 emails): free 6, offer 5, win 4, meeting 1, report 0, project 1.
- Ham (12 emails): free 1, offer 1, win 0, meeting 8, report 7, project 6.
The filter needs the probability that each word appears in an email of each class. The obvious estimate is the fraction: "free" appears in 6 of 8 spam emails, so \(P(\text{free} \mid \text{spam}) = 0.75\). But "report" appears in 0 of 8, and a probability of exactly 0 would make any email containing "report" impossible as spam, however many other spam words it carried. One unseen word would override all the evidence.
Add one to everything
The fix is Laplace smoothing, named after Pierre-Simon Laplace, who proposed it in the 1770s for the probability that the Sun rises tomorrow: add 1 to the count of emails that contain the word and 2 to the total (one for each outcome, present and absent). Then
\[ P(\text{report} \mid \text{spam}) = \frac{0 + 1}{8 + 2} = 0.1, \qquad P(\text{free} \mid \text{spam}) = \frac{6 + 1}{8 + 2} = 0.7. \]With smoothing, the six spam probabilities are 0.7, 0.6, 0.5, 0.2, 0.1, 0.2, and the six ham probabilities are 0.143, 0.143, 0.071, 0.643, 0.571, 0.5 (the ham fractions have 14 in the denominator). The prior probabilities of the classes are \(P(\text{spam}) = 8/20 = 0.4\) and \(P(\text{ham}) = 0.6\).
The assumption in the name
A new email arrives containing "free", "offer", and "meeting", and not the other three words. Bayes' rule says the probability that it is spam is proportional to the prior times the likelihood of the email given spam. The likelihood of a particular combination of six present-or-absent words would need a table with 64 entries per class, and we have 8 spam emails to fill it from. So the filter assumes the words are independent given the class: the probability of the combination is the product of the six individual probabilities, present words contributing \(P(\text{word} \mid \text{class})\) and absent words \(1 - P(\text{word} \mid \text{class})\).
The assumption is false. "Free" and "offer" plainly travel together. It is also the reason the method works at all with so little data: six numbers per class instead of 64, each estimated from the whole set. The name "naive" is the field's own joke about it, and the joke has lasted because the classifier keeps winning on problems where its assumption is nonsense. The probabilities it outputs are badly calibrated (too close to 0 or 1), but the decision, which class has the higher score, is usually right.
Working in logarithms
Multiplying six probabilities is already awkward by hand; a real filter with 50,000 words would multiply thousands of numbers below 1 and the product would underflow to zero in a computer's arithmetic. So the filter adds logarithms instead. The score for spam is
\[ \log 0.4 + \log 0.7 + \log 0.6 + \log(1 - 0.5) + \log 0.2 + \log(1 - 0.1) + \log(1 - 0.2), \]one term per word in order (free present, offer present, win absent, meeting present, report absent, project absent). The natural logarithms are \(-0.916 - 0.357 - 0.511 - 0.693 - 1.609 - 0.105 - 0.223 = -4.415\). The score for ham is
\[ \log 0.6 + \log 0.143 + \log 0.143 + \log(1 - 0.071) + \log 0.643 + \log(1 - 0.571) + \log(1 - 0.5), \]which is \(-0.511 - 1.946 - 1.946 - 0.074 - 0.442 - 0.847 - 0.693 = -6.459\). The spam score is larger by 2.04, so the filter says spam. Turning the difference back into a probability gives \(e^{-4.415} / (e^{-4.415} + e^{-6.459})\), about 0.885: an 88 per cent spam verdict, driven by "free" and "offer" and held back by "meeting".
Notice what the log form makes visible. Each word contributes a fixed amount of evidence, its log probability under spam minus its log probability under ham, and the verdict is the sum of the evidence plus the prior. "Free" contributes \(\log 0.7 - \log 0.143 = 1.59\) in favour of spam; "meeting" contributes \(\log 0.2 - \log 0.643 = -1.17\) against. A word's weight of evidence is a number you could print next to it, and in the early filters people did.
What the real filters added
Graham's filter used word frequencies within the email rather than presence alone, and considered only the fifteen most decisive words of each message, which blunted the independence assumption's worst effects. Later filters added tokens from the headers, pairs of words, and the sender's history, and learned from each user's own corrections, so that the counts above were updated every time someone clicked "this is spam". The spammers responded with the letter salad and the lists of innocent words at the bottom of their messages, which were attempts to drag the sum of evidence back towards ham, and the filters responded by weighting words by how surprising they were. The arms race is still on; the arithmetic is the same.
Naive Bayes is also where the two halves of the field meet. The filter is a probabilistic model that reasons with Bayes' rule, and it is a classifier learned from labelled examples, the same job that logistic regression and a neural network do with a different model of the words. A reader who has done this example by hand has done, in miniature, what a language model does when it assigns a probability to the next word: it combines a prior with evidence from the context, and it works in logarithms because the products are too small to hold.
Unit 3 of the AI Masterclass builds this filter after Bayesian networks and the medical test, and Unit 5 returns to it as the probabilistic cousin of logistic regression.


