Naive Bayes Classifier

Bayes' rule plus conditional independence for a fast generative classifier.

The idea

The naive Bayes classifier is generative: it models how each class produces its data, then turns that model around with Bayes' rule to classify. For a class $C$ and an observed feature vector $x$, $\mathbb{P}(C \mid x) = \frac{\mathbb{P}(C)\,\mathbb{P}(x \mid C)}{\mathbb{P}(x)}.$ The model needs two ingredients. The prior $\mathbb{P}(C)$ is the class's overall rate, before any features are seen; the likelihood $\mathbb{P}(x \mid C)$ says how that class distributes its features. The denominator $\mathbb{P}(x)$ carries no $C$, so it is identical for every class and cannot change which class ranks first. The figure shows the rule for a single binary test: the population square splits into a column for a class $D$ and a column for its complement $\neg D$, with widths equal to the priors; the shaded band in each column is that class's likelihood of a positive result $+$; and the posterior $\mathbb{P}(D \mid +)$ is the share of the total shaded area lying in the $D$ column.

The likelihood is hard to estimate directly. Over $d$ features, $\mathbb{P}(x \mid C)$ is a distribution on $d$-tuples, and the number of distinct tuples grows exponentially with $d$, so no sample of realistic size pins it down. The naive assumption is that, within a class, the features are independent of one another. It collapses the joint likelihood into a product of $d$ one-feature distributions, each of which we can estimate by counting. The assumption is usually false — the words in an email are not independent — which distorts the probabilities the method reports while often leaving the class it ranks first correct.

Algorithm.

Algorithm: Naive Bayes Classification Input: class priors P(C), per-feature likelihoods P(xj | C) estimated by counting, an observed x = (x1, ..., xd) Output: a predicted class and, when wanted, its posterior probability 1. score each class C: P(C) × P(x1 | C) × ... × P(xd | C) // Bayes' numerator, collapsed by the naive assumption 2. to classify, return the class of largest score // the shared denominator P(x) cannot change the winner 3. for a probability, return the winning score divided by the sum of all scores // that sum is P(x); the quotient is the posterior

Ways to work on it

• Walkthrough. Score classes by combining a prior with independent per-feature likelihoods.
• Practice. Score one class from its prior and per-feature likelihoods.
• Hardest. Score both classes and normalize to a posterior probability.

Not sure where to start? Take the ten-question placement test.