Naive Bayes

A filter that counts words

In 2002 Paul Graham published an essay arguing that the way to beat spam was not more hand-written rules but counting: how often each word appears in spam versus in real mail. Email clients and servers soon shipped filters built on that idea. Microsoft Research had shown the same approach four years earlier. The method underneath is naive Bayes, and it is still the first thing to try for many text problems.

What is it?

Naive Bayes is a classifier that picks the class whose probability, given the evidence, is highest, using Bayes’ rule and one bold simplification: every feature, for example every word, is treated as independent of the others once you know the class.

How does it work?

Training is counting. For each class, count how many training messages it has and how often each word appears in it. To classify a new message, each word nudges the score towards the class that uses it more. Add up the nudges, add the starting bias of how common each class is, and pick the winner.

Why does it matter?

It trains in one pass over the data, handles tens of thousands of features, needs little data, and every decision can be explained word by word. That makes it a standard baseline for spam, topic and sentiment classification, and a clean introduction to probabilistic, or generative, models.

Key takeaways

• Naive Bayes classifies by choosing the class with the highest probability given the features.
• Training is just counting how often each feature appears with each class.
• It is fast, needs little data and explains its decisions, which makes it a strong first baseline for text.

Bayes’ rule

Everything rests on one line of probability, which is easiest to understand by counting emails.

What is it?

Bayes’ rule turns “how likely is this evidence, if the email is spam?” into “how likely is spam, given this evidence?” The first is easy to estimate from training data. The second is what we want.

Bayes’ rule. P(spam) is the prior, P(word | spam) the likelihood, P(spam | word) the posterior. The denominator is the same for every class, so to compare classes you only need the top line.

How does it work?

In the figure, P(prize | spam) = 12/30, P(spam) = 30/100 and P(prize) = 14/100. Plug them in: (0.4 × 0.3) / 0.14 ≈ 0.86, the same answer as counting. To classify, compute the top line for each class and pick the larger. It is often easier to compare the two classes as odds: posterior odds = prior odds × likelihood ratio, here (30 : 70) × (0.4 / 0.029) ≈ 6 : 1.

Why does it matter?

The prior matters. The same evidence means much more for a common class than a rare one, which is why a test that is 99% accurate can still be wrong most of the time about a rare disease. A classifier that ignores how common each class is will flag far too many rare-class cases.

Key takeaways

• Bayes’ rule: posterior is proportional to likelihood times prior.
• In odds form, the prior odds are multiplied by a likelihood ratio for each piece of evidence.
• The prior matters: the same clue means less when the class it points to is rare.

The naive assumption

One word is easy. A message has dozens, and estimating how every combination of words behaves would need impossibly many examples.

What is it?

The naive assumption is that features are conditionally independent given the class: once you know an email is spam, seeing “free” tells you nothing extra about whether you will see “prize”. It is plainly false for language, and it is what makes the model practical.

How does it work?

Independence turns one impossible probability into a product of easy ones, each estimated by counting. In the multinomial model used for text, P(w | spam) is the share of all word occurrences in spam training messages that are the word w.

Naive Bayes. The class score is the prior times one factor per word in the message, repeated words included.

Taking logs and subtracting the ham score from the spam score gives a sum you can read: the log prior odds plus one term per word, ln P(w | spam) − ln P(w | ham). Positive terms push towards spam, negative towards ham.

Why does it matter?

The number of things to estimate grows with the vocabulary, not with the number of word combinations. A few hundred labelled messages are enough to get started, and the per-word terms are an honest explanation of every decision.

Key takeaways

• Naive Bayes assumes the features are independent once the class is known.
• The class score becomes a product of per-word probabilities, each estimated by counting.
• In log-odds form every word adds a readable vote, which makes decisions easy to explain.

Smoothing and logs

Two small engineering details decide whether naive Bayes works at all: what to do about zero counts, and how to multiply hundreds of tiny numbers.

What is it?

Laplace (add-one) smoothing pretends every word was seen α more times in every class than it really was. Log probabilities replace the product of probabilities with a sum of their logarithms.

How does it work?

Smoothed word probability. count(w, c) is how often w appears in class c, N_c the total word count of class c, |V| the vocabulary size. α = 1 is Laplace smoothing.

Without smoothing, one unseen word gives a zero likelihood that no amount of other evidence can overturn; if one word is unseen in each class, both scores are zero and the answer is 0 / 0. With smoothing, unseen words get a small, equal-ish probability in both classes. Words never seen in any training message are usually skipped.

Multiplying a hundred probabilities of about 0.01 gives 10⁻²⁰⁰; a few more and the result is smaller than the smallest positive 64-bit float (about 10⁻³⁰⁸), so it becomes exactly 0. Since log(a·b) = log a + log b and log is increasing, summing logs picks the same class and neverunderflows.

Key takeaways

• Without smoothing, one word unseen in a class forces that class’s probability to zero.
• Laplace smoothing adds α to every count: P(w | c) = (count + α) / (N_c + α|V|).
• Summing log probabilities gives the same decision as multiplying, without underflow.

When it fails

Naive Bayes is wrong about the world in a specific way, and knowing the way tells you when to trust it.

What goes wrong?

Correlated features are double-counted. “Hong” and “Kong” almost always appear together, but naive Bayes treats them as two independent clues and multiplies both in. The more redundant the features, the more extreme, and overconfident, its probabilities.

Why does it often still work?

Classification only needs the right class to come out on top, not the right probability. Domingos and Pazzani showed that naive Bayes can be the optimal classifier under zero-one loss even when independence is violated by a wide margin. In practice its accuracy is often good while its probabilities are poorly calibrated, pushed towards 0 and 1. Rennie and colleagues catalogue other problems on text, such as bias towards classes with more training data, and simple fixes.

With continuous features, Gaussian naive Bayes models each feature with a normal distribution per class. It fails when the class distributions are far from normal or when interactions between features matter, for example when only a combination of two values signals the class.

Ng and Jordan showed this trade-off formally and on real datasets: naive Bayes approaches its best error with far fewer examples, and logistic regression overtakes it as the training set grows.

Key takeaways

• Correlated features are counted several times, making naive Bayes overconfident.
• It can still classify well, because only the ranking of classes needs to be right.
• With little data it is a strong baseline; with lots of data discriminative models usually win.

Check your understanding

Six situations that test whether you can apply Bayes’ rule and naive Bayes, not just recite them.

A disease affects 1 in 1,000 people. A test catches 99% of cases and wrongly flags 2% of healthy people. Someone tests positive. Roughly how likely are they to have the disease?

Next, meet a classifier built on geometry instead of probability in Support Vector Machines, or see how modern language models handle text in Natural Language Processing.

References

The papers, essays and textbooks behind this lesson.

References

1. [1]

   A Plan for Spam(opens in a new tab)

   Paul Graham, 2002

   The essay that popularised statistical, word-probability spam filtering in email clients.

2. [2]

   A Bayesian Approach to Filtering Junk E-Mail(opens in a new tab)

   Mehran Sahami, Susan Dumais, David Heckerman & Eric Horvitz, 1998

   AAAI Workshop on Learning for Text Categorization. An early naive Bayes spam filter, from Microsoft Research.

3. [3]

   Introduction to Information Retrieval, chapter 13: Text classification and naive Bayes(opens in a new tab)

   Christopher Manning, Prabhakar Raghavan & Hinrich Schütze, 2008

   Cambridge University Press. The multinomial model, add-one smoothing and log probabilities, as used in this lesson. Free online.

4. [4]

   On the Optimality of the Simple Bayesian Classifier under Zero-One Loss(opens in a new tab)

   Pedro Domingos & Michael Pazzani, 1997

   Machine Learning 29, 103–130. Why naive Bayes classifies well even when its independence assumption, and its probabilities, are badly wrong.

5. [5]

   Tackling the Poor Assumptions of Naive Bayes Text Classifiers(opens in a new tab)

   Jason Rennie, Lawrence Shih, Jaime Teevan & David Karger, 2003

   ICML 2003. Documents systematic problems with naive Bayes on text and simple fixes such as complement naive Bayes.

6. [6]

   On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes(opens in a new tab)

   Andrew Y. Ng & Michael I. Jordan, 2001

   NeurIPS 2001. Naive Bayes approaches its best error with far fewer examples; logistic regression overtakes it as data grows.