Naive Bayes Classifier

The Problem

The Naive Bayes classifier is a famous classification technique that takes a probabilistic approach.

Consider a dataset where, for any input feature $x$, the output $y$ is either $1$ or $-1$. This is binary classification, where we have two categories. Naive Bayes can be extended to multiclass classification, but we'll start with the binary case.

For example, suppose we are given a person's glucose level, and each person is labeled as normal or high risk. Risk increases with glucose level. We'll treat normal as $1$ and high risk as $-1$.

Consider any input $x$ and output $y$ as coming from two random variables, $X$ and $Y$. For new data, we need to calculate the probability of the output given the input:

For simplicity, we'll write this as $P(y \mid x)$.

We can't read this directly from the training data, but we can calculate two related probabilities:

• $P(x \mid y)$, the probability of the input given the output class
• $P(y)$, the probability of the output class

For any output class, we know the inputs that belong to it, so we can calculate both of these from the dataset. What we need is a way to get from them to $P(y \mid x)$.

Bayes' Theorem

Think of a Venn diagram with two overlapping circles, $X$ and $Y$. The overlap is $X \cap Y$.

• $P(y \mid x)$ asks: given that we are in $X$, what is the probability of $Y$?
• $P(x \mid y)$ asks: given that we are in $Y$, what is the probability of $X$?

We can write the probability of the overlap in two ways:

Both are equal to the same thing, so they are equal to each other:

Dividing both sides by $P(x)$ gives us what we want. This equation is called Bayes' theorem, and the Naive Bayes classifier is based on it:

Each term has a name:

• $P(y)$ is the prior, the probability of the output class from the training data.
• $P(x \mid y)$ is the likelihood, the probability of the input given the output class.
• $P(y \mid x)$ is the posterior, the probability of the output class given a new input. This is what we calculate.

Expanding the Denominator

The denominator $P(x)$ is the same for every class, because it doesn't depend on $y$. So the posterior is proportional to the numerator:

To see $P(x)$ more clearly, let's expand it. $Y$ and its complement $Y^c$ together make up the whole universal set, and the intersection of $X$ with the universal set is just $X$:

Expanding this gives two separate pieces:

Using the result from earlier, we can rewrite each piece:

So $P(x)$ adds up the probability of the input across the two output classes.

Making a Prediction

For a new input $x$, we calculate the probability of each output class. Whichever probability is higher becomes our output class:

The denominators are the same, and they are both just the expanded $P(x)$. So we only need to compare the numerators. The predicted class $\hat{y}$ is the one that gives the higher value:

For multiclass classification, we have classes such as $0, 1, 2, 3, 4$ instead of $1$ and $-1$. We calculate this value for each class and take the highest.

Multiple Input Features

Now suppose we have multiple input features, such as glucose level, age, and BMI. The output is still normal ($1$) or high risk ($-1$).

Each input now has $d$ features, $x_1, x_2, \dots, x_d$. Using Bayes' theorem as before:

The Naive Assumption

Naive Bayes assumes that the features are independent of each other, given the output class. For our example, this says glucose, age, and BMI are unrelated within each class.

That isn't always true, since age, BMI, and glucose may well be related. This assumption is what makes the method "naive".

With this assumption, we can expand the likelihood into a product:

As before, the denominator is the same for every class, so the posterior is proportional to the numerator:

We calculate this for each output class and take the class with the maximum value:

Example: Will Someone Play?

Consider a dataset that records the weather (sunny, cloudy, rainy), the temperature (hot, mild, cool), and whether someone played that day. The output class is yes ($1$) or no ($-1$).

We want the probability of playing, given that the weather is sunny and the temperature is mild. Using Bayes' theorem:

Now we work out the parts:

• $P(\text{play})$ comes from counting how often the person played in the dataset.
• $P(\text{sunny}, \text{mild} \mid \text{play})$ can be expanded because Naive Bayes treats the features as independent given the class:

We can count both of these from the dataset as well. The denominator is the same for playing and not playing, so we can skip it when comparing the two classes.

We then do the same for the other class, not playing. If the value for playing is higher, the output is playing. Otherwise, the output is not playing.

Summary

The key ideas are:

• Naive Bayes is a probabilistic classifier based on Bayes' theorem.
• It combines the prior $P(y)$ and the likelihood $P(x \mid y)$ to get the posterior $P(y \mid x)$.
• The denominator is the same for every class, so we only compare the numerators.
• It assumes the features are independent given the class, which lets us multiply one probability per feature.
• The predicted class is the one with the highest value of $P(y) \prod_{i=1}^{d} P(x_i \mid y)$.
• It also has many other applications, such as spam classification and text classification.