Build a spam detector

Formulas here are written in plain text, since the site renders no maths typesetting library.

The model#

Multinomial naive Bayes models a document as a sequence of draws from a per-class word distribution. For a document d with word counts x = (x_1, ..., x_V) over a vocabulary of size V, and class c:

                                    V
log p(c | d)  =  log p(c)  +   sum     x_t * log p(t | c)   +  const
                                  t=1

• p(c) is the class prior, estimated as the fraction of training documents in class c.
• p(t | c) is the probability of term t under class c.
• x_t is the count of term t in the document.
• const is log p(d), identical across classes, so it drops out of the argmax.

Parameters are estimated by smoothed maximum likelihood:

p(t | c)  =  ( N_tc + alpha ) / ( sum_s N_sc  +  alpha * V )

N_tc is the total count of term t across all training documents of class c. alpha is the additive smoothing constant, defaulting to 1.0 in scikit-learn (Laplace smoothing). Smoothing is not optional: an unsmoothed zero count sends the whole log-probability to negative infinity, so one unseen word would veto a class outright.

Why "naive"#

The model assumes term occurrences are conditionally independent given the class. This is plainly false for natural language — "New" and "York" are strongly dependent — and it means the resulting probability estimates are badly calibrated, typically pushed toward 0 or 1.

The ranking, however, survives. Domingos and Pazzani (1997), On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, show that the argmax can be correct over a much wider region than the region where the independence assumption holds. Naive Bayes is a good classifier and a poor probability estimator, and the distinction matters when you threshold on predict_proba.

Event models#

McCallum and Nigam (1998), A Comparison of Event Models for Naive Bayes Text Classification, distinguish two formulations that are routinely conflated:

• Multinomial: features are term counts. Repeated terms contribute repeatedly. Better on larger vocabularies; this is MultinomialNB.
• Bernoulli: features are binary presence indicators, and crucially the model includes an explicit factor for terms that are absent. This is BernoulliNB, and it can win on very short documents where non-occurrence is informative.

ComplementNB (Rennie et al., 2003, Tackling the Poor Assumptions of Naive Bayes Text Classifiers) estimates parameters from the complement of each class and is measurably more robust under class imbalance. On skewed spam corpora it is often the better default.

Complexity#

Let N be the number of documents, L the mean document length, V the vocabulary size and C the number of classes.

• Training: O(N * L) to accumulate counts, plus O(C * V) to normalise. It is a single pass, it parallelises across documents, and it streams — no document need be held in memory twice.
• Prediction: O(L_d * C) per document, touching only terms present in that document.
• Memory: O(C * V) for the parameter table.

This is why naive Bayes survived as a production spam filter through the 2000s at volumes where anything iterative was infeasible.

Practical adjustments that matter#

TF-IDF and length normalisation. Rennie et al. document that raw counts overweight repeated terms, and recommend a log transform log(1 + x_t), IDF weighting, and L2 normalisation per document. Applying these to naive Bayes is theoretically inconsistent with the generative story and empirically improves it substantially.

NBSVM. Wang and Manning (2012), Baselines and Bigrams: Simple, Good Sentiment and Topic Classification, use naive Bayes log-count ratios as feature values inside a linear SVM. It remains a stubbornly strong baseline on short-text classification, and it is worth beating before reaching for a transformer.

The hashing trick. HashingVectorizer maps terms into a fixed 2^b space with a signed hash, removing the vocabulary dictionary entirely. This gives constant memory and permits online updating, at the cost of hash collisions and no inverse mapping back to words.

What a production filter actually looks like#

Content classification is a minority of the system. A modern mail provider layers:

1. Connection-level reputation — IP and domain history, which rejects the bulk of volume before the body is ever parsed.
2. Authentication — SPF, DKIM and DMARC, verifying the sender is who the envelope claims.
3. Behavioural signals — how recipients across the fleet interact with similar messages, aggregated within minutes.
4. Content models — gradient-boosted trees or transformer encoders over text, URLs, attachments and rendered HTML.
5. Near-duplicate detection — locality-sensitive hashing to catch a campaign after its first few thousand deliveries.

Two properties dominate the engineering. First, the adversary adapts: this is adversarial classification, formalised by Dalvi et al. (2004), where the data-generating distribution responds to your classifier. Retraining cadence is a first-class design parameter, not an afterthought.

Second, the loss is asymmetric by orders of magnitude. Filters are tuned to false-positive rates around one in ten thousand or better, accepting substantially more false negatives in exchange. Optimising accuracy, or even F1, targets the wrong quantity entirely.

Attacks to be aware of. Good-word attacks append innocuous high-ham-weight tokens to shift the score (Lowd and Meek, 2005). Poisoning attacks inject crafted training examples through the "report spam" channel itself. Both are why no serious filter trains on unfiltered user feedback without robust aggregation.

Papers#

• Sahami, Dumais, Heckerman and Horvitz, A Bayesian Approach to Filtering Junk E-Mail, AAAI Workshop 1998 — the paper that started this application.
• McCallum and Nigam, A Comparison of Event Models for Naive Bayes Text Classification, AAAI Workshop 1998.
• Domingos and Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning 29, 1997.
• Rennie, Shih, Teevan and Karger, Tackling the Poor Assumptions of Naive Bayes Text Classifiers, ICML 2003.
• Dalvi, Domingos, Mausam, Sanghai and Verma, Adversarial Classification, KDD 2004.
• Lowd and Meek, Good Word Attacks on Statistical Spam Filters, CEAS 2005.
• Metsis, Androutsopoulos and Paliouras, Spam Filtering with Naive Bayes — Which Naive Bayes?, CEAS 2006.
• Wang and Manning, Baselines and Bigrams, ACL 2012.

What to learn next#

• Text classification — the general problem this project is one instance of.
• Model evaluation — precision, recall and why accuracy misleads.
• Sentiment analysis — the same pipeline, a harder label to predict.