2.2 Naive Bayes

Recall the “ground truth” regressor from the regression module: \[ f^*(x) := \mathbb{E}[Y \mid X = x]. \] You can show that it achieves the smallest possible expected prediction error. This chapter asks the same question for classification: what is the optimal classifier \(f^* : \mathbb{R}^d \to \mathcal{Y}\), where \(\mathcal{Y}\) is a finite set? We then derive Naive Bayes, a classifier motivated by the answer.

This chapter has a fair amount of notation, but the ideas are not complicated. Take it one symbol at a time.

The optimal classifier

Examples of classifiers

Accuracy

To say which classifier is best, we need a way to measure how good a classifier is.

Definition. Assume \(X, Y \sim D(X, Y)\). The accuracy of a classifier \(f : \mathbb{R}^d \to \mathcal{Y}\) is \[ \text{acc}(f) := \mathbb{P}\big(f(X) = Y\big) = \int_x p_{XY}\big(x, f(x)\big)\, dx = \int_x p_{Y|X}\big(f(x) \mid x\big)\, p_X(x)\, dx. \]

Here \(\mathbb{P}\) is the probability of an event (the classifier’s prediction matches the label), while the lowercase \(p\)’s are density functions. Read \(p_{XY}(x, f(x))\) as “the probability that \(X = x\) and \(Y = f(x)\).” Integrating over all inputs gives the overall probability of a correct prediction. The last equality just rewrites the joint density as a conditional times a marginal.

We want a classifier that maximizes accuracy.

Theorem (optimality of the Bayes classifier)

Consider the Bayes classifier \[ f^*(x) := \operatorname*{argmax}_{y} p_{Y|X}(y \mid x). \] Then for any classifier \(g : \mathbb{R}^d \to \mathcal{Y}\), \[ \text{acc}(g) \leq \text{acc}(f^*). \]

The result is intuitive: at every input, the Bayes classifier predicts the most likely label. Here is how to prove it formally.

Proof. Pick any classifier \(g : \mathbb{R}^d \to \mathcal{Y}\).

Fix \(x \in \mathbb{R}^d\). Looking at one input at a time is easier; we will integrate over all inputs at the end. Conditioning on \(X = x\), \[ \mathbb{P}\big(g(x) = Y \mid X = x\big) = p_{Y|X}\big(g(x) \mid x\big). \] By definition, \(f^*(x) = \operatorname*{argmax}_y p_{Y|X}(y \mid x)\) is the label with the largest conditional density at \(x\). Thus \[ p_{Y|X}\big(g(x) \mid x\big) \leq p_{Y|X}\big(f^*(x) \mid x\big). \] This holds at every \(x\), so it still holds after taking the expectation over \(X\), that is, integrating both sides against \(p_X(x)\): \[ \int_x p_{Y|X}\big(g(x) \mid x\big)\, p_X(x)\, dx \;\leq\; \int_x p_{Y|X}\big(f^*(x) \mid x\big)\, p_X(x)\, dx \quad\Longrightarrow\quad \text{acc}(g) \leq \text{acc}(f^*). \qquad \blacksquare \]

Remark. So the Bayes classifier is the best we can ever do, and we would like to approximate it. The naive approach is to estimate \(p_{Y|X}(y \mid x)\) directly, but for continuous \(x \in \mathbb{R}^d\) this requires a lot of data for large \(d\). There is a separate conditional distribution for every possible input, infinitely many of them, and each one is hard to estimate.

Naive Bayes

From the Bayes classifier to Naive Bayes

The hard part is conditioning on the continuous input \(X\). Bayes’ rule lets us flip the condition so that we condition on the label \(Y\) instead, which is discrete: \[ \begin{aligned} f^*(x) &= \operatorname*{argmax}_{y \in \mathcal{Y}} p_{Y|X}(y \mid x) \\ &= \operatorname*{argmax}_{y \in \mathcal{Y}} \frac{p_{XY}(x, y)}{p_X(x)} \\ &= \operatorname*{argmax}_{y \in \mathcal{Y}} \frac{p_{X|Y}(x \mid y)\, p_Y(y)}{p_X(x)} \\ &= \operatorname*{argmax}_{y \in \mathcal{Y}} \underbrace{p_Y(y)}_{\text{class prior}} \cdot \underbrace{p_{X|Y}(x \mid y)}_{\text{class conditional}}. \end{aligned} \] The last step drops the denominator. Since \(x\) is given, \(p_X(x)\) is the same no matter which label we consider, so it does not change the argmax. This is the same “constants don’t matter” trick from Chapter 1.2.

So the task becomes estimating two simpler things:

The Naive Bayes classifier

The class conditional is still hard to estimate when \(x\) is high-dimensional. Naive Bayes makes it easier with one extra assumption, and that assumption is why it is called naive. (The derivation above is exactly the Bayes classifier. Naive Bayes is not.)

Setup (Naive Bayes)

Independence means we only ever estimate one-dimensional distributions, one per feature and class, instead of a \(d\)-dimensional distribution where correlations between features make estimation hard.

Choosing distributions. Each feature can get the distribution that fits it: a Bernoulli for a true/false feature, a Gaussian for a continuous one. So Naive Bayes handles datasets with mixed feature types naturally.

Speed. Because the parameter estimates usually have closed forms, Naive Bayes trains very fast: you just plug into formulas. Compare this with logistic regression, which needs an iterative algorithm like gradient descent.

Intuition. Think of each factor as evidence. The class prior is what we believe before seeing the input. Each \(p_{X^{(j)}|Y}(x^{(j)} \mid y)\) is the evidence feature \(j\) provides for label \(y\). Multiplying them combines all the evidence into an overall score for each label.

Example: detecting email spam

Assume we have estimated the following distributions (in practice, with MLE):

Check yourself

How does Naive Bayes classify “win a free gift!!!”?

Answer

The email contains both words, so \(x = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\). Compare the two labels, dropping the shared denominator \(\mathbb{P}(X = x)\) and using the independence of the features: \[ \begin{aligned} \mathbb{P}\big(Y = 1 \mid X = [1, 1]\big) &\propto \mathbb{P}(Y = 1)\, \mathbb{P}\big(X = [1, 1] \mid Y = 1\big) = 0.4 \times (0.8 \times 0.7) = 0.224, \\ \mathbb{P}\big(Y = 0 \mid X = [1, 1]\big) &\propto 0.6 \times (0.4 \times 0.1) = 0.024. \end{aligned} \] Since \(0.224 > 0.024\), label the email as \(1\) (spam).

Example: MLE for a Bernoulli distribution

Where do estimates like “\(\text{Bernoulli}(0.4)\)” come from? Every distribution in the example above is a Bernoulli, whether it describes labels (the class prior) or binary features (the class conditionals). So we only need the MLE for a Bernoulli parameter.

The MLE is just the proportion of ones in the data. That is what intuition says; now it is rigorously derived.