Email SPAM Classifier

naive bayes is the classifier you get by taking bayes’ rule seriously and probability theory not seriously at all. 𐃏 it assumes every feature is independent of every other feature given the class — an assumption that is false for essentially all real data — and yet it filters spam, routes support tickets and triages documents well enough that it has survived five decades of fancier competition. this page derives it, counts why the “naive” part is the whole point, builds a spam filter from scratch, and is honest about where it breaks (its probabilities, not its decisions).

bayes’ rule as a classifier#

we want the most probable class for a feature vector \(x = (x_1, \dots, x_d)\). bayes’ rule rewrites the posterior in terms of things we can estimate (Wasserman, Larry, 2010):

\begin{equation} p(y = c \mid x) = \frac{p(x \mid y = c)\, \pi_c}{\sum_{c’} p(x \mid y = c’)\, \pi_{c’}}, \end{equation}

where \(\pi_c = p(y = c)\) is the class prior. the denominator is the same for every class, so the map decision rule (maximum a posteriori) drops it:

\begin{equation} \hat{y} = \operatorname*{arg\,max}_{c}\; \pi_c \, p(x \mid y = c) = \operatorname*{arg\,max}_{c}\; \Big[ \log \pi_c + \log p(x \mid y = c) \Big]. \end{equation}

nothing naive so far — this is the bayes classifier, and with the true distributions it is optimal for 0–1 loss (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009). the problem is the likelihood: \(p(x \mid y = c)\) is a joint distribution over all \(d\) features, and estimating a joint is exactly the thing small datasets cannot do.

the naive assumption#

naive bayes assumes the features are conditionally independent given the class:

\begin{equation} p(x_1, \dots, x_d \mid y = c) = \prod_{j=1}^{d} p(x_j \mid y = c). \end{equation}

graphically: the class is the lone parent of every feature, and there are no edges between features. knowing the class screens off everything one feature could tell you about another.

what the assumption buys: the parameter count collapses#

count parameters for \(d\) binary features and \(K\) classes:

• full joint likelihood. \(p(x \mid y = c)\) is a distribution over \(2^d\) configurations, so each class needs \(2^d - 1\) free parameters: \(K(2^d - 1)\) in total (plus \(K-1\) for the prior).
• naive likelihood. each feature needs one bernoulli parameter per class: \(Kd\) in total (plus the same \(K-1\)).

for a modest spam filter with \(d = 30\) binary word-presence features and \(K = 2\):

\begin{equation} \underbrace{2\,(2^{30} - 1) \approx 2.1 \times 10^{9}}_{\text{full joint}} \qquad \text{vs} \qquad \underbrace{2 \times 30 = 60}_{\text{naive}}. \end{equation}

exponential to linear in \(d\). the full joint would need more training emails than have ever been sent; the naive model is estimable from a few hundred. that is the trade: naive bayes accepts (possibly large) bias in exchange for variance low enough to learn anything at all in high dimensions — the extreme low-variance end of the bias–variance dial. 𐃏

the variants#

the factorisation says nothing about what each per-feature likelihood \(p(x_j \mid y)\) is. pick it to match the feature type (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009):

\begin{align*} \textbf{bernoulli:} \quad & p(x \mid y = c) = \prod_{j=1}^{d} \theta_{cj}^{\,x_j} (1 - \theta_{cj})^{1 - x_j}, && x_j \in \{0, 1\} \\[4pt] \textbf{multinomial:} \quad & p(x \mid y = c) = \frac{\big(\sum_j x_j\big)!}{\prod_j x_j!} \prod_{j=1}^{d} \theta_{cj}^{\,x_j}, && x_j \in \{0, 1, 2, \dots\}, \;\; \textstyle\sum_j \theta_{cj} = 1 \\[4pt] \textbf{gaussian:} \quad & p(x \mid y = c) = \prod_{j=1}^{d} \frac{1}{\sqrt{2\pi\sigma_{cj}^2}} \exp\!\left( -\frac{(x_j - \mu_{cj})^2}{2\sigma_{cj}^2} \right), && x_j \in \mathbb{R} \end{align*}

• bernoulli nb: features are word presence. explicitly penalises the absence of class-typical words (the \((1-x_j)\) factor), which helps on short documents.
• multinomial nb: features are word counts; the document is a bag of tokens drawn from a class-specific die. 𐃏 the workhorse for text.
• gaussian nb: continuous features get a per-class, per-feature normal. maximum likelihood fits \(\mu_{cj}, \sigma_{cj}^2\) by the class-conditional sample mean and variance — training is one pass of bookkeeping.

mixing types is fine: the log-likelihood is a sum over features, so each feature can bring its own distribution.

smoothing: why zero counts are fatal#

maximum likelihood for the multinomial model is just relative frequency:

\begin{equation} \hat{\theta}_{cj} = \frac{N_{cj}}{\sum_{j’} N_{cj’}}, \end{equation}

where \(N_{cj}\) counts occurrences of word \(j\) in class-\(c\) training documents. now let one test email contain a vocabulary word never seen in spam. then \(\hat\theta_{\text{spam},j} = 0\), and because the likelihood is a product, the entire spam posterior is annihilated by a single factor — one unseen word outvotes fifty incriminating ones, with infinite confidence. in log space it is a \(-\infty\) no other term can repair.

lidstone smoothing adds a pseudo-count \(\alpha > 0\) to every word–class pair:

\begin{equation} \hat{\theta}_{cj} = \frac{N_{cj} + \alpha}{\sum_{j’} N_{cj’} + \alpha V}, \qquad V = |\text{vocabulary}|, \end{equation}

with \(\alpha = 1\) the classic laplace smoothing. this is not a hack: it is exactly the map estimate under a symmetric dirichlet prior \(\mathrm{Dir}(\alpha + 1)\) on \(\theta_c\) — pretend you saw every word \(\alpha\) times before looking at the data (Deisenroth, Marc Peter and Faisal, A. Aldo and Ong, Cheng Soon, 2020). small \(\alpha\) trusts counts; large \(\alpha\) flattens towards uniform. tune it on held-out data like any other regulariser.

log-space implementation#

a 2,000-word email multiplies 2,000 numbers of magnitude \(10^{-3}\) to \(10^{-5}\); the product underflows double precision long before word 300. nobody computes the product — everyone computes the sum of logs:

\begin{equation} \text{score}_c(x) = \log \pi_c + \sum_{j} x_j \log \hat{\theta}_{cj}, \end{equation}

• decide: \(\hat y = \operatorname{arg\,max}_c \text{score}_c(x)\) — no normalisation needed.
• calibrate: if you want actual posteriors, normalise with log-sum-exp, subtracting the max score first so the exponentials cannot overflow: \(\log Z = m + \log \sum_c e^{\text{score}_c - m}\), \(m = \max_c \text{score}_c\).
• train: everything is counting, one pass over the data, trivially parallel and trivially online — new labelled email arrives, increment counters, done.

a spam filter from scratch#

seven emails, honest arithmetic, no libraries. spam contributes 10 tokens, ham 12, and the joint vocabulary has \(V = 15\) words, so e.g. the smoothed estimate for “cash” (twice in spam, absent from ham) is \(\hat\theta_{\text{spam,cash}} = \tfrac{2+1}{10+15} = 0.12\) and \(\hat\theta_{\text{ham,cash}} = \tfrac{0+1}{12+15} \approx 0.037\) — smoothing keeps ham merely sceptical of “cash”, not infinitely so.

import math
from collections import Counter

train = [("win cash now",           "spam"),
         ("limited offer win prize","spam"),
         ("cash prize inside",      "spam"),
         ("meeting notes attached", "ham"),
         ("lunch meeting tomorrow", "ham"),
         ("offsite notes attached", "ham"),
         ("agenda for tomorrow",    "ham")]

# --- train: count everything once ------------------------------------
docs = Counter(c for _, c in train)                      # class counts
words = {c: Counter() for c in docs}                     # word counts per class
for text, c in train:
    words[c].update(text.split())
vocab = sorted(set(w for c in words for w in words[c]))
V = len(vocab)

def log_likelihood(w, c, alpha=1.0):                     # laplace-smoothed
    return math.log((words[c][w] + alpha) /
                    (sum(words[c].values()) + alpha * V))

def classify(text):
    x = [w for w in text.split() if w in vocab]          # drop out-of-vocab words
    scores = {c: math.log(docs[c] / len(train)) +
                 sum(log_likelihood(w, c) for w in x) for c in docs}
    z = max(scores.values())                             # log-sum-exp, stably
    logZ = z + math.log(sum(math.exp(s - z) for s in scores.values()))
    return scores, {c: math.exp(s - logZ) for c, s in scores.items()}

print(f"vocab size V = {V}, priors: spam {docs['spam']}/7, ham {docs['ham']}/7")
print(f"theta('cash'|spam) = (2+1)/(10+{V}) = {math.exp(log_likelihood('cash','spam')):.4f}")
print(f"theta('cash'|ham)  = (0+1)/(12+{V}) = {math.exp(log_likelihood('cash','ham')):.4f}")
for msg in ["win cash prize", "meeting agenda tomorrow", "win cash tomorrow"]:
    scores, post = classify(msg)
    print(f"'{msg}': log p(spam,x) = {scores['spam']:.3f}, "
          f"log p(ham,x) = {scores['ham']:.3f}, p(spam|x) = {post['spam']:.4f}")

vocab size V = 15, priors: spam 3/7, ham 4/7
theta('cash'|spam) = (2+1)/(10+15) = 0.1200
theta('cash'|ham)  = (0+1)/(12+15) = 0.0370
'win cash prize': log p(spam,x) = -7.208, log p(ham,x) = -10.447, p(spam|x) = 0.9623
'meeting agenda tomorrow': log p(spam,x) = -10.504, log p(ham,x) = -7.557, p(spam|x) = 0.0499
'win cash tomorrow': log p(spam,x) = -8.307, log p(ham,x) = -9.349, p(spam|x) = 0.7392

sanity-check the first message by hand: all three words have \(\hat\theta_{\text{spam},j} = 0.12\), so \(\log p(\text{spam}, x) = \log\tfrac{3}{7} + 3\log 0.12 = -0.847 - 6.361 = -7.208\). matches. note the third message: “tomorrow” is ham evidence, so the posterior retreats from 0.96 to 0.74 — the votes are additive in log space, exactly as the next section formalises.

the same pipeline at real scale — sklearn’s MultinomialNB on an actual email corpus, with vectorisers and evaluation — lives in this notebook:

naive bayes is a linear classifier#

for the binary bernoulli model, expand the log posterior odds:

\begin{align*} \log \frac{p(y = 1 \mid x)}{p(y = 0 \mid x)} &= \log \frac{\pi_1}{\pi_0} + \sum_{j=1}^{d} \Big[ x_j \log \frac{\theta_{1j}}{\theta_{0j}} + (1 - x_j) \log \frac{1 - \theta_{1j}}{1 - \theta_{0j}} \Big] \\ &= \underbrace{\log \frac{\pi_1}{\pi_0} + \sum_{j} \log \frac{1 - \theta_{1j}}{1 - \theta_{0j}}}_{b} \; + \; \sum_{j} \underbrace{\log \frac{\theta_{1j}(1 - \theta_{0j})}{\theta_{0j}(1 - \theta_{1j})}}_{w_j}\, x_j \; = \; w^{\top} x + b. \end{align*}

the multinomial case is even quicker: \(\log p(x \mid c)\) is \(\sum_j x_j \log \theta_{cj}\) plus a class-independent term, so \(w_j = \log(\theta_{1j}/\theta_{0j})\). either way the decision boundary \(w^\top x + b = 0\) is a hyperplane — the same hypothesis class as logistic regression. 𐃏

the difference is purely in how the weights are fit: naive bayes estimates \(w\) generatively (model \(p(x \mid y)\), read the weights off the counts), logistic regression discriminatively (optimise the conditional likelihood of \(y \mid x\) directly). the generative route needs far less data to reach its (higher) asymptotic error; the discriminative route wins when data is plentiful.¹

the calibration caveat#

naive bayes is routinely a good classifier and a bad probability estimator. correlated features are the culprit: if thirty features all restate the same evidence, the model counts that evidence thirty times, and the posterior gets driven towards 0 or 1 exponentially fast. the argmax is often unharmed — double-counting frequently pushes scores away from the boundary on the correct side, and 0–1 loss only asks for the right ordering (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009) — but the reported \(p(\text{spam} \mid x) = 0.9999997\) is fiction.

practical consequences:

• never threshold raw nb posteriors against costs (“only delete if 99% sure”) without recalibrating — platt scaling or isotonic regression on a held-out set fixes most of it.
• ranking by posterior (triage queues, top-k retrieval) is usually fine: miscalibration is closer to a monotone distortion than a reshuffle.
• see performance metrics for measuring this (reliability diagrams, brier score) rather than assuming it.

when naive bayes wins#

despite — really, because of — its bias, naive bayes is the right first model surprisingly often (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome, 2009):

• small \(n\), large \(d\). with thousands of features and hundreds of examples, most flexible models drown in variance; nb’s per-feature estimates stay stable. text is the canonical case: bag-of-words puts \(d\) in the tens of thousands.
• speed and simplicity. training is one counting pass (\(O(nd)\) time, \(O(Kd)\) memory), prediction is a dot product, and online updates are increments. as a production baseline it is nearly free.
• streaming and drifting data. counts can be decayed or windowed; the model retrains continuously without an optimiser.
• a floor for fancier models. if your svm or fine-tuned transformer cannot beat smoothed naive bayes on your corpus, your pipeline has a bug. (on the imdb sentiment benchmark, an nb-flavoured linear model held its own against neural methods for years.)²

its losses are just as predictable: plentiful data with strong feature interactions (vision, tabular data with cross-effects) hands the win to discriminative and nonparametric models that can spend their variance budget.

see also#

• logistic regression — the discriminative twin: same hyperplane, opposite estimation philosophy
• support vector machines — what to try when the linear boundary is right but the probabilistic story is not
• decision trees — the opposite bias: interactions first, independence never
• ensembles — where the variance-hungry models claw back the large-data regime
• k-nearest neighbours — the other famously simple baseline, with the mirror-image failure mode in high dimensions