Naive Bayes

Two Ways to Classify

Logistic regression, from last note, is discriminative. It learns the boundary between classes and nothing else. “Hand me the features, I’ll tell you which side of the line you’re on.” It never learns what spam or normal email actually look like. It just draws the divide.

A generative model does the opposite. It learns what each class looks like, separately, and then asks of a new example: “which one does this resemble more?”

Think of two ways to spot a counterfeit bill:

• Discriminative: learn the single telltale difference between real and fake.
• Generative: study real bills thoroughly and fake bills thoroughly; for a new bill, see which pile it resembles.

Naive Bayes is the classic generative classifier, and its home turf is text: spam filtering.

Bayes’ Theorem: the Engine

We want the probability an email is spam given its words:

$P(\text{spam} \mid \text{words})$

Reading the notation: $P(\text{spam} \mid \text{words})$ means “the chance it’s spam, given the words we can see.” That vertical bar $\mid$ is just shorthand for the word “given.”

But that probability is hard to measure directly. Bayes’ theorem lets us flip it into two things we can count from data:

$P(\text{spam} \mid \text{words}) \;\propto\; P(\text{words} \mid \text{spam}) \times P(\text{spam})$

What is $\propto$? It just means “proportional to,” as in “rises and falls in step with.” We never need the exact probability here, only which class scores higher, so proportional is all we need.

• $P(\text{words} \mid \text{spam})$ = how likely these words are if it’s spam, learned by reading lots of spam.
• $P(\text{spam})$ = how common spam is in general, the prior.

The slogan version is worth memorizing:

posterior $\propto$ likelihood $\times$ prior.

What’s “ham”? It’s just the spam-world nickname for normal, non-spam email. Every message gets sorted into one of two piles: spam or ham.

Do the same calculation for ham, and whichever score comes out bigger wins.

The “Naive” Part

There’s a catch. Computing $P(\text{words} \mid \text{spam})$ for a whole email at once is hopeless, there are endless possible word combinations. So Naive Bayes makes one bold, lazy assumption:

Pretend every word is independent of the others.

Then the probability of the whole email is just each word’s probability multiplied together:

$P(w_1, w_2, \ldots \mid \text{spam}) = P(w_1 \mid \text{spam}) \times P(w_2 \mid \text{spam}) \times \ldots$

It’s called naive because it is plainly false. “New” and “York” are not independent, and word order clearly matters. It throws all of that away and treats the email as an unordered bag of words.

And yet it works shockingly well, especially for spam. Being a little wrong about independence rarely changes which class ends up with the bigger score.

Step 1: Training Is Just Counting

Before it can judge anything, the model reads a big pile of emails a human already labelled spam or ham, and simply counts.

To learn $P(\text{free} \mid \text{spam})$, it asks one plain question: of all the spam emails, what fraction contained the word “free”? If 8 of 10 did, then $P(\text{free} \mid \text{spam}) = 0.80$. Repeat in the ham pile, maybe only 1 in 20, so $P(\text{free} \mid \text{ham}) = 0.05$.

That counting is the training. No equations to solve, no gradient descent, no boundary to fit. Just tally every word in each pile. (It also counts how many emails are spam overall, which gives the prior $P(\text{spam})$.)

Step 2: Scoring a New Email

Now a fresh email arrives, “free money now”. We look up each word’s already-counted probabilities and multiply them:

• Spam score $= P(\text{free}\mid\text{spam}) \times P(\text{money}\mid\text{spam}) \times P(\text{now}\mid\text{spam}) \times P(\text{spam})$
• Ham score $= P(\text{free}\mid\text{ham}) \times P(\text{money}\mid\text{ham}) \times P(\text{now}\mid\text{ham}) \times P(\text{ham})$

The spam score comes out about $100\times$ larger. Flagged. No boundary line was ever drawn, we just counted words during training and multiplied them at test time.

When to Reach for Which

Discriminative and generative are two tools, not a right-and-wrong:

Naive Bayes powered the first practical spam filters, and it is still the go-to baseline for text classification. When someone builds a new text classifier, this is the number they have to beat.

Next we leave probability behind for a while and classify by geometry: nearest neighbors and support vector machines.