Naive Bayes

From Lecture: Bayes Classifier and Naive Bayes

Generative vs. Discriminative Algorithm¶

• When we estimate $P(X,Y)$, we call it generative learning. We try to model the distribution behind the scene - the distribution we draw all our samples from. (Remember how we described this omnipotent distribution when talking about the Bayes Optimal Classifier) We achieve this often by modelling $P(X,Y)=P(X|Y)P(Y)$.
• When we only estimate $P(Y|X)$ directly, then we call it discriminative learning. We try to model the probability of a label given features. This is more aligned with our common definition of “predicting” things.

Introduction - Estimating Probability Directly From Data¶

Something Generative¶

Our training consists of the set $D=\{(\mathbf{x}_1,y_1),\dots,(\mathbf{x}_n,y_n)\}$ drawn from some unknown distribution $P(X,Y)$. Because all pairs are sampled i.i.d., we obtain

If we do have enough data, we could estimate $P(X,Y)$ simply through counting:

where $I(\mathbf{x}_i=\mathbf{x} \wedge {y}_i=y)=1$ if $\mathbf{x}_i=\mathbf{x}$ and ${y}_i=y$ and 0 otherwise.

Something Discriminative¶

We are also interested in using similar technique to estimate $P(Y|X)$. Because we know if we have $P(Y|X)$, we can then use the Bayes Optimal Classifier to make predictions. We now want to make some prediction $\hat{P}(y|\mathbf{x})$ based on dataset, and pretend our estimate $\hat{P}(y|\mathbf{x})$ to well describe our real distribution $P(Y|X)$, so we use $\hat{P}(y|\mathbf{x})$ in place of ${P}(y|\mathbf{x})$ in BOC.

So how can we estimate $\hat{P}(y | \mathbf{x})$? Previously we have derived that $\hat P(y)=\frac{\sum_{i=1}^n I(y_i=y)}{n}$. Similarly, $\hat P(\mathbf{x})=\frac{\sum_{i=1}^n I(\mathbf{x}_i=\mathbf{x})}{n}$ and $\hat P(y,\mathbf{x})=\frac{\sum_{i=1}^{n} I(\mathbf{x}_i = \mathbf{x} \wedge {y}_i = y)}{n}$. We can put these two together

The Venn diagram illustrates that the MLE method estimates $\hat{P}(y|\mathbf{x})$ as

Problem: The estimate is only good if there are many training data with the exact same features as $\mathbf{x}$! In high dimensional spaces (or with continuous $\mathbf{x}$), this never happens! So $|B| \rightarrow 0$ and $|C| \rightarrow 0$.

Naive Bayes¶

Naive Bayes will give a solution. It is a kind of generative learning.

So we change gears a bit and turn to estimate $P(\mathbf{x} | y) \text{ and } P(y)$ in the Bayes formula:

Estimating $P(y)$ is easy (assume there are not many classes in this classification problem). We simply need to count how many times we observe each class. Define the fraction of time we see label $c$ as $\hat\pi_c$.

Estimating $P(\mathbf{x}|y)$, however, is not easy! Here we have to make a very bold additional assumption: the Naive Bayes assumption

Naive Bayes Assumption: Each feature values are mutually independent given the label.

Naive Bayes Assumption helps us decompose a single d-dimension problem into d 1-dimension problems.

这是大胆的是因为假设我们用各种词出现的次数来判断一封邮件是否是垃圾邮件，那么明显各个词出现的概率是相关的，他们不可能 independent。

Illustration behind the Naive Bayes algorithm: 假设 $dim(x)=2$, 竖轴是 $[x]_1$, 横轴是 $[x]_2$. 我们实际上有 $[x]_1, [x]_2, y, P$ 四个量需要表示。$y$ 用颜色来表示，所以应该是个三维图来着，那么高度轴就应该是 probability $P$，但是这里就画了二维，碍于图画我们只能想象一下了画的这些曲线其实都在高度轴上

• fig1: $P(x|y)$
• fig2: $P([x]_1|y)$
• fig3: $P([x]_2|y)$
• fig4: $\prod_\alpha P(x_\alpha|y)$ 这幅图所表示的实际上是三维空间向二维空间的一个投影

We then define our Bayes Classifier as:

Estimating $\log(P(x_\alpha | y))$ is easy as we only need to consider one dimension each time.

Take a log or not, this formula defines Naive Bayes.

Estimating $P([\mathbf{x}]_\alpha | y)$ - 3 Notable Cases¶

We will talk about 3 cases where we use Naive Bayes to make predictions. In each case, we make explicit assumptions (refer back to our first chapter to learn about what “assumption” means) about distribution of our samples.

Case #1: Categorical features¶

For $d$ dimensional data, think of it as having $d$ independent dices. Each dice corresponds to a feature in our data point. Each dice has some different values. We roll each dice exactly once, record the result in a corresponding entry in our feature vector.

Features¶

Each feature $\alpha$ falls into one of $K_\alpha$ categories. (So if we have binary features at entry $\alpha$, we would have $K_\alpha = 2$.)

Model $P(x_\alpha \mid y)$:¶

对于 $x$ 的每一维度 $\alpha$, 我们都有一个 $K_\alpha \times |C|$ 的矩阵来表示给定 label $y=c$, $x_{\alpha}$ 取值 $j$ 的概率。

where $[\theta_{jc}]_{\alpha}$ is the probability of feature $\alpha$ having the value $j$, given that the label is $c$. And the constraint indicates that $x_{\alpha}$ must have one of the categories ${1, \dots, K_\alpha}$.

Parameter estimation:¶

where $l$ is a smoothing parameter. By setting $l=0$ we get an MLE estimator, $l>0$ leads to MAP. If we set $l= +1$ we get Laplace smoothing. (Here we made an implicit assumption that each category has the same possibility of happening, so we will have $lK_\alpha$ imaginary draws and we get $[\mathbf{x}_i]_\alpha = j$ happens $l$ times)

Prediction:¶

• $P(y) = \hat\pi_c$ was defined previously
• $P(\mathbf{x}) = \prod_{\alpha = 1}^{d} [\hat\theta_{jc}]_\alpha$ is derived from the Naive Bayes Assumption
• $P(\mathbf{x})$ is a constant

这个预测共需要 $dim \times K_\alpha \times |C|$ 个值，对比如果我们直接采用 $P(x,y)$ 进行预测，我们需要 $K_\alpha^{dim} \times |C|$ 个值是一个巨大的改进。

Case #2: Multinomial features¶

We have one die of $d$ values. Roll it multiple times and jot down the number of times each value appeared. Record that number in the entry corresponding to that value. Therefore, the value of the $i^{th}$ feature shows how many times a particular value appeared.

接着以根据词频判别垃圾邮件作为例子，在 multinomial features 中，$[x]_\alpha=j$ 就是某个词 $\alpha$ 出现了 $j$ 次。

Features:¶

$m$ is the length of this letter and $d$ is the size of the vocabulary

Model $P(\mathbf{x} \mid y)$:¶

虽然本情境中每个词的出现是互相独立的，但是由于信件的长度已经确定，我们只能按照总体来估计，不能像原来一样估计一个$P(x_\alpha \mid y)$. This situation can be modeled by this multinomial distribution

where $\theta_{\alpha c}$ is the probability of selecting word $x_\alpha$ and $\sum_{\alpha = 1}^d \theta_{\alpha c} =1$ (you have to select one of the $d$ words). This equation describes the probability of having such an email (of some number of appearance times of each vocabulary) given it is a spam (or not).

So, we can use this to generate a spam email, i.e., a document $\mathbf{x}$ of class $y = \text{spam}$ by picking $m$ words independently at random from the vocabulary of $d$ words using $P(\mathbf{x} \mid y = \text{spam})$.

Parameter estimation:¶

where $m_i=\sum_{\beta = 1}^{d} x_{i\beta}$ denotes the number of words in document $i$ and $l$ is the smoothing parameter.

Prediction:¶

If you look back at our Bayesian Classifier definition: $\operatorname*{argmax}_y \; \frac{P(\mathbf{x} | y)P(y)}{P(\mathbf{x})}$

The factorial terms are present both at the factor $P(\mathbf{x} | y)$ and the denominator $P(\mathbf{x})$ so they cancel out. And all we need to care about is just the $\theta$ and $\pi$

Case #3: Continuous Normal Features (Gaussian Naive Bayes)¶

In this situation, we assume each class conditional feature distribution $P(x_\alpha|y)$ originates from a Gaussian distribution with its own mean $\mu_{\alpha,y}$ and variance $\sigma_{\alpha,y}^2$. So $P(x_\alpha \mid y=c) = \mathcal{N}\left(\mu_{\alpha c}, \sigma^{2}_{\alpha c}\right)$. Since we have the Naive Bayes Assumption, each class conditional feature distribution is actually independent from each other.

Features:¶

Model $P(x_\alpha \mid y)$:¶

Since it is a Gaussian distribution,

To computer $\mu_{\alpha c}, \sigma^{2}_{\alpha c}$: The mean $\mu_{\alpha,y}$ of $dim \; \alpha$ given label $c$ is just the average feature value of dimension $\alpha$ from all samples with label $y$. The (squared) standard deviation is simply the variance of this estimate.

The full distribution is $P(\mathbf{x}|y)\sim \mathcal{N}(\mathbf{\mu}_y,\Sigma_y)$, where $\Sigma_y$ is a diagonal covariance matrix with $[\Sigma_y]_{\alpha,\alpha}=\sigma^2_{\alpha,y}$. Diagonal because we have our Naive Bayes Assumption of each dimension being independent from each other.

Parameter estimation:¶

According to

We only have to multiply each $P(x_\alpha | y)$ together.

Naive Bayes is a linear classifier¶

A linear classifier has the form $\hat y = \mathbf{w}^\top \mathbf{x} + b$

Naive Bayes leads to a linear decision boundary in many common cases (including multinomial and continuous normal).

Multinomial Case¶

Suppose that $y_i \in \{-1, +1\}$ and features are multinomial

We can show that $\exists \mathbf{w}, b$ such that

That is, our naive bayes classifier always gives the same classification as our linear classifier.

As we showed before, $P(x_\alpha|y=+1)\propto\theta_{\alpha+}^{x_\alpha}$ and $P(Y=+1)=\pi_+$. We continue to define

Let’s start a linear classification with this $\textbf{w}$ and $b$, we will arrive at our Naive Bayes classifier $h(x)$ as go through the steps below.

$$

$$

Continuous Features Case¶

we can show that

. This model is also known as logistic regression. Naive Bayes and Logistic Regression produce asymptotically the same model if the Naive Bayes assumption holds.