Naive Bayes

Bayes' rule plus a deliberately naive independence assumption: start from each class's prior, multiply in each clue's likelihood, pick the highest posterior.

9 min read Watch it move Build it

Naive Bayes is a fast probabilistic classifier — the classic spam filter — built on Bayes' rule. It starts from how common each class is, multiplies in how telltale each clue (each word) is for that class, and picks the class with the highest result. The 'naive' part is assuming the clues are independent, which is rarely true but works surprisingly well.

Bayes' rule, applied to classification

We want the posterior P(class | clues) — the probability of a class given the evidence. Bayes' rule rewrites it using things we can count from training data: the prior P(class) (how common the class is) and the likelihood P(clue | class) (how telltale each clue is).

P(class | clues) ∝ P(class) · P(clue1|class) · P(clue2|class) · ...
                   [ prior ]  [ ------ likelihoods ------ ]

The 'naive' assumption

Multiplying the per-clue likelihoods assumes conditional independence: within a class, each clue is unrelated to the others. For text that's plainly false — 'new' and 'york' co-occur — yet the errors tend to wash out, and the *ranking* of classes usually stays correct even when the probabilities themselves are off.

Worked example: spam filter

Suppose 40% of mail is spam: prior P(spam) = 0.4, P(ham) = 0.6. From training, the word 'free' appears in 30% of spam but only 2% of ham. An email containing 'free':

spam score = P(spam)*P('free'|spam) = 0.4 * 0.30 = 0.120
ham  score = P(ham )*P('free'|ham ) = 0.6 * 0.02 = 0.012

0.120 > 0.012  =>  classify as SPAM
(normalized: P(spam|'free') = 0.120 / 0.132 = 0.91)

The zero-frequency trap

If a word never appeared in spam during training, its likelihood is 0 — and one zero multiplied into the chain zeroes out the *entire* score, no matter how damning the other words are. The fix is Laplace (add-one) smoothing: add a small count to every word so nothing is ever exactly zero.

Work in log-space

Multiplying hundreds of tiny probabilities underflows to zero in floating point. In practice you add logarithms instead: log P(class) + sum of log P(clue|class). Sums are numerically stable, and the class with the largest log-score is still the winner.

OperationTimeSpace

Train · count clue frequencies per classO(n·d)O(c·d)

Predict · c classes, d features per itemO(c·d)O(c·d)

Check yourself

Why does Naive Bayes need Laplace (add-one) smoothing?