朴素贝叶斯法（Naive Bayes）

在高斯判别分析（GDA）方法中，特征向量 $x$ 是连续的，值为实数的向量。下面我们要讲的是当 $x_i$ 是离散值的时候来使用的另外一种学习算法。

下面就来继续看一个之前见过的样例，来尝试建立一个邮件筛选器，使用机器学习的方法。这回咱们要来对邮件信息进行分类，来判断是否为商业广告邮件（就是垃圾邮件），还是非垃圾邮件。在学会了怎么实现之后，我们就可以让邮件阅读器能够自动对垃圾信息进行过滤，或者单独把这些垃圾邮件放进一个单独的文件夹中。对邮件进行分类是一个案例，属于文本分类这一更广泛问题集合。

假设我们有了一个训练集（也就是一堆已经标好了是否为垃圾邮件的邮件）。要构建垃圾邮件分选器，咱们先要开始确定用来描述一封邮件的特征$x_i$有哪些。

我们将用一个特征向量来表示一封邮件，这个向量的长度等于字典中单词的个数。如果邮件中包含了字典中的第 $i$ 个单词，那么就令 $x_i = 1$；反之则$x_i = 0$。例如下面这个向量：

$$x=\begin{bmatrix}1\\0\\0\\\vdots \\1\\ \vdots \\0\end{bmatrix} \begin{matrix}\text{a}\\ \text{aardvark}\\ \text{aardwolf}\\ \vdots\\ \text{buy}\\ \vdots\\ \text{zygmurgy}\\ \end{matrix}$$

就用来表示一个邮件，其中包含了两个单词 “a” 和 “buy”，但没有单词 “aardvark”， “aardwolf” 或者 “zymurgy” 。这个单词集合编码整理成的特征向量也成为词汇表（vocabulary,）， 所以特征向量 $x$ 的维度就等于词汇表的长度。

注：实际应用中并不需要遍历整个英语词典来组成所有英语单词的列表，实践中更常用的方法是遍历一下训练集，然后把出现过一次以上的单词才编码成特征向量。这样做除了能够降低模型中单词表的长度之外，还能够降低运算量和空间占用，此外还有一个好处就是能够包含一些你的邮件中出现了而词典中没有的单词，比如本课程的缩写CS229。有时候（比如在作业里面），还要排除一些特别高频率的词汇，比如像冠词the，介词of 和and 等等；这些高频率但是没有具体意义的虚词也叫做stop words，因为很多文档中都要有这些词，用它们也基本不能用来判定一个邮件是否为垃圾邮件。

选好了特征向量了，接下来就是建立一个生成模型（generative model）。所以我们必须对$p(x|y)$进行建模。但是，假如我们的单词有五万个词，则特征向量$x \in {0, 1}^{50000}$ （即 $x$是一个 $50000$ 维的向量，其值是$0$或者$1$），如果我们要对这样的 $x$进行多项式分布的建模，那么就可能有$2^{50000}$ 种可能的输出，然后就要用一个 $(2^{50000}-1)$维的参数向量。这样参数明显太多了。

要给$p(x|y)$建模，先来做一个非常强的假设。我们假设特征向量$x_i$ 对于给定的 $y$ 是独立的。 这个假设也叫做朴素贝叶斯假设（Naive Bayes ，NB assumption）， 基于此假设衍生的算法也就叫做朴素贝叶斯分类器（Naive Bayes classifier）。 例如，如果 $y = 1$ 意味着一个邮件是垃圾邮件；然后其中”buy” 是第$2087$个单词，而 “price”是第$39831$个单词；那么接下来我们就假设，如果我告诉你 $y = 1$，也就是说某一个特定的邮件是垃圾邮件，那么对于$x{2087}$ （也就是单词 buy 是否出现在邮件里）的了解并不会影响你对$x{39831}$ （单词price出现的位置）的采信值。更正规一点，可以写成 $p(x{2087}|y) = p(x{2087}|y, x{39831})$。（要注意这个并不是说$x{2087}$ 和 $x{39831}$这两个特征是独立的，那样就变成了$p(x{2087}) = p(x{2087}|x{39831})$，我们这里是说在给定了 $y$ 的这样一个条件下，二者才是有条件的独立。）

然后我们就得到了等式：

$$\begin{aligned} p(x_1, ..., x_{50000}|y) & = p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2) ... p(x_{50000}|y,x_1,x_2,...,x_{49999})\\ & = p(x_1|y)p(x_2|y)p(x_3|y) ... p(x_{50000}|y)\\ & = \prod^n_{i=1}p(x_i|y)\\ \end{aligned}$$

第一行的等式就是简单地来自概率的基本性质，第二个等式则使用了朴素贝叶斯假设。这里要注意，朴素贝叶斯假设也是一个很强的假设，产生的这个算法可以适用于很多种问题。

我们这个模型的参数为 $\phi{i|y=1} = p (x_i = 1|y = 1), \phi{i|y=0} = p (x_i = 1|y = 0)$, 而 $\phi_y = p (y = 1)$。和以往一样，给定一个训练集${(x^{(i)},y^{(i)}); i = 1, …, m}$，就可以写出下面的联合似然函数：

$$\mathcal{L}(\phi_y,\phi_{j|y=0},\phi_{j|y=1})=\prod^m_{i=1}p(x^{(i)},y^{(i)})$$

找到使联合似然函数取得最大值的对应参数组合 $\phiy , \phi{i|y=0} 和 \phi_{i|y=1}$ 就给出了最大似然估计：

$$\begin{aligned} \phi_{j|y=1} &=\frac{\sum^m_{i=1}1\{x_j^{(i)} =1 \wedge y^{(i)} =1\} }{\sum^m_{i=1}1\{y^{(i)} =1\}} \\ \phi_{j|y=0} &= \frac{\sum^m_{i=1}1\{x_j^{(i)} =1 \wedge y^{(i)} =0\} }{\sum^m_{i=1}1\{y^{(i)} =0\}} \\ \phi_{y} &= \frac{\sum^m_{i=1}1\{y^{(i)} =1\}}{m}\\ \end{aligned}$$

在上面的等式中，”$\wedge$(and)”这个符号的意思是逻辑”和”。这些参数有一个非常自然的解释。例如 $\phi_{j|y=1}$ 正是单词 $j$ 出现的邮件中垃圾邮件所占 $(y = 1)$ 的比例。

拟合好了全部这些参数之后，要对一个新样本的特征向量 $x$ 进行预测，只要进行如下的简单地计算：

$$\begin{aligned} p(y=1|x)&= \frac{p(x|y=1)p(y=1)}{p(x)}\\ &= \frac{(\prod^n_{i=1}p(x_i|y=1))p(y=1)}{(\prod^n_{i=1}p(x_i|y=1))p(y=1)+ (\prod^n_{i=1}p(x_i|y=0))p(y=0)} \\ \end{aligned}$$

然后选择有最高后验概率的概率。

最后我们要注意，刚刚我们对朴素贝叶斯算法的使用中，特征向量 $x_i$ 都是二值化的，其实特征向量也可以是多个离散值，比如${1, 2, …, k_i}$这样也都是可以的。这时候只需要把对$p(x_i|y)$ 的建模从伯努利分布改成多项式分布。实际上，即便一些原始的输入值是连续值（比如我们第一个案例中的房屋面积），也可以转换成一个小规模的离散值的集合，然后再使用朴素贝叶斯方法。例如，如果我们用特征向量 $x_i$ 来表示住房面积，那么就可以按照下面所示的方法来对这一变量进行离散化：

居住面积	$<400$	$400-800$	$800-1200$	$1200-1600$	$>1600$
离散值 $x_i$	$1$	$2$	$3$	$4$	$5$

这样，对于一个面积为 $890$ 平方英尺的房屋，就可以根据上面这个集合中对应的值来把特征向量的这一项的$x_i$值设置为$3$。然后就可以用朴素贝叶斯算法，并且将$p(x_i|y)$作为多项式分布来进行建模，就都跟前面讲过的内容一样了。当原生的连续值的属性不太容易用一个多元正态分布来进行建模的时候，将其特征向量离散化然后使用朴素贝叶斯法（NB）来替代高斯判别分析法（GDA），通常能形成一个更好的分类器。

1 拉普拉斯平滑（Laplace smoothing）

刚刚讲过的朴素贝叶斯算法能够解决很多问题了，但还能对这种方法进行一点小调整来进一步提高效果，尤其是应对文本分类的情况。我们来简要讨论一下一个算法当前状态的一个问题，然后在讲一下如何解决这个问题。

还是考虑垃圾邮件分类的过程，设想你学完了CS229的课程，然后做了很棒的研究项目，之后你决定在$2003$年$6$月把自己的作品投稿到NIPS会议，这个NIPS是机器学习领域的一个顶级会议，递交论文的截止日期一般是六月末到七月初。你通过邮件来对这个会议进行了讨论，然后你也开始收到带有 nips 四个字母的信息。但这个是你第一个NIPS论文，而在此之前，你从来没有接到过任何带有 nips 这个单词的邮件；尤其重要的是，nips 这个单词就从来都没有出现在你的垃圾/正常邮件训练集里面。加入这个 nips 是你字典中的第$35000$个单词那么你的朴素贝叶斯垃圾邮件筛选器就要对参数$\phi_{35000|y}$ 进行最大似然估计，如下所示：

$$\begin{aligned} \phi_{35000|y=1} &= \frac{\sum^m_{i=1}1\{x^{(i)}_{35000}=1 \wedge y^{(i)}=1 \}}{\sum^m_{i=1}1\{y^{(i)}=0\}} &=0 \\ \phi_{35000|y=0} &= \frac{\sum^m_{i=1}1\{x^{(i)}_{35000}=1 \wedge y^{(i)}=0 \}}{\sum^m_{i=1}1\{y^{(i)}=0\}} &=0 \\ \end{aligned}$$

也就是说，因为之前程序从来没有在别的垃圾邮件或者正常邮件的训练样本中看到过 nips 这个词，所以它就认为看到这个词出现在这两种邮件中的概率都是$0$。因此当要决定一个包含 nips 这个单词的邮件是否为垃圾邮件的时候，他就检验这个类的后验概率，然后得到了：

$$\begin{aligned} p(y=1|x) &= \frac{ \prod^n_{i=1} p(x_i|y=1)p(y=1) } {\prod^n_{i=1} p(x_i|y=1)p(y=1) +\prod^n_{i=1} p(x_i|y=1)p(y=0) }\\ &= \frac00\\ \end{aligned}$$

这是因为对于” $\prod^n{i=1} p(x_i|y)$”中包含了$p(x{35000}|y) = 0$的都加了起来，也就还是$0$。所以我们的算法得到的就是 $\frac00$，也就是不知道该做出怎么样的预测了。

然后进一步拓展一下这个问题，统计学上来说，只因为你在自己以前的有限的训练数据集中没见到过一件事，就估计这个事件的概率为零，这明显不是个好主意。假设问题是估计一个多项式随机变量 $z$ ，其取值范围在${1,…, k}$之内。接下来就可以用$\phi_i = p (z = i)$ 来作为多项式参数。给定一个 $m$ 个独立观测${z^{(1)}, …, z^{(m)}}$ 组成的集合，然后最大似然估计的形式如下：

$$\phi_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}}m$$

正如咱们之前见到的，如果我们用这些最大似然估计，那么一些$\phi_j$可能最终就是零了，这就是个问题了。要避免这个情况，咱们就可以引入拉普拉斯平滑（Laplace smoothing）， 这种方法把上面的估计替换成：

$$\phi_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}+1}{m+k}$$

这里首先是对分子加$1$，然后对分母加$k$，要注意$\sum^k_{j=1} \phi_j = 1$依然成立（自己检验一下），这是一个必须有的性质，因为$\phi_j$ 是对概率的估计，然后所有的概率加到一起必然等于$1$。另外对于所有的 $j$ 值，都有$\phi_j \neq 0$，这就解决了刚刚的概率估计为零的问题了。在某些特定的条件下（相当强的假设条件下，arguably quite strong），可以发现拉普拉斯平滑还真能给出对参数$\phi_j$ 的最佳估计（optimal estimator）。

回到我们的朴素贝叶斯分选器问题上，使用了拉普拉斯平滑之后，对参数的估计就写成了下面的形式：

$$\begin{aligned} \phi_{j|y=1} & =\frac{\sum^m_{i=1}1\{x_j^{(i)}=1\wedge y ^{(i)}=1\}+1}{\sum^m_{i=1}1{\{y^{(i)}=1\}}+2}\\ \phi_{j|y=0} & =\frac{\sum^m_{i=1}1\{x_j^{(i)}=1\wedge y ^{(i)}=10\}+1}{\sum^m_{i=1}1{\{y^{(i)}=0\}}+2}\\ \end{aligned}$$

（在实际应用中，通常是否对$\phi_y$ 使用拉普拉斯并没有太大影响，因为通常我们会对每个垃圾邮件和非垃圾邮件都有一个合适的划分比例，所以$\phi_y$ 会是对$p(y = 1)$ 的一个合理估计，无论如何都会与零点有一定距离。）

2 针对文本分类的事件模型（Event models for text classification）

到这里就要给咱们关于生成学习算法的讨论进行一下收尾了，所以就接着讲一点关于文本分类方面的另一个模型。我们刚已经演示过的朴素贝叶斯方法能够解决很多分类问题了，不过还有另一个相关的算法，在针对文本的分类效果还要更好。

在针对文本进行分类的特定背景下，咱们上面讲的朴素贝叶斯方法使用的是一种叫做多元伯努利事件模型（Multi-Variate Bernoulli event model）。 在这个模型里面，我们假设邮件发送的方式，是随机确定的（根据先验类class priors， $p(y)$），无论是不是垃圾邮件发送者，他是否给你发下一封邮件都是随机决定的。那么发件人就会遍历词典，决定在邮件中是否包含某个单词 $i$，各个单词之间互相独立，并且服从概率分布$p(xi=1|y)=\phi{i|y}$。因此，一条消息的概率为：$p(y)\prod^n_{i-1}p(x_i|y)$

然后还有另外一个模型，叫做多项式事件模型（Multinomial event model）。 要描述这个模型，我们需要使用一个不同的记号和特征集来表征各种邮件。设 $x_i$ 表示单词中的第$i$个单词。因此，$x_i$现在就是一个整数，取值范围为${1,…,|V|}$，这里的$|V|$是词汇列表（即字典）的长度。这样一个有 $n$ 个单词的邮件就可以表征为一个长度为 $n$ 的向量$(x_1,x_2,…,x_n)$；这里要注意，不同的邮件内容，$n$ 的取值可以是不同的。例如，如果一个邮件的开头是”A NIPS . . .” ，那么$x_1 = 1$ (“a” 是词典中的第一个)，而$x_2 = 35000$ (这是假设 “nips”是词典中的第35000个)。

在多项式事件模型中，我们假设邮件的生成是通过一个随机过程的，而是否为垃圾邮件是首先决定的（根据$p(y)$），这个和之前的模型假设一样。然后邮件的发送者写邮件首先是要生成 从对单词$(p(x1|y))$ 的某种多项式分布中生成 $x_1$。然后第二步是独立于 $x_1$ 来生成 $x_2$，但也是从相同的多项式分布中来选取，然后是 $x_3$,$x_4$ 等等，以此类推，直到生成了整个邮件中的所有的词。因此，一个邮件的总体概率就是$p(y)\prod^n{i=1}p(x_i|y)$。要注意这个方程看着和我们之前那个多元伯努利事件模型里面的邮件概率很相似，但实际上这里面的意义完全不同了。尤其是这里的$x_i|y$现在是一个多项式分布了，而不是伯努利分布了。

我们新模型的参数还是$\phiy = p(y)$，这个跟以前一样，然后还有$\phi{k|y=1} = p(xj =k|y=1)$ (对任何 $j$)以及 $\phi{i|y=0} =p(x_j =k|y=0)$。要注意这里我们已经假设了对于任何$j$ 的值，$p(x_j|y)$这个概率都是相等的，也就是意味着在这个哪个词汇生成的这个分布不依赖这个词在邮件中的位置$j$。

如果给定一个训练集${(x^{(i)},y^{(i)}); i = 1, …, m}$，其中 $x^{(i)} = ( x^{(i)}{1} , x^{(i)}{2} ,…, x^{(i)}_{n_i})$（这里的$n$是在第$i$个训练样本中的单词数目），那么这个数据的似然函数如下所示：

$$\begin{aligned} \mathcal{L}(\phi,\phi_{k|y=0},\phi_{k|y=1})& = \prod^m_{i=1}p( x^{(i)},y^{(i)})\\ & = \prod^m_{i=1}(\prod^{n_i}_{j=1}p(x_j^{(i)}|y;\phi_{k|y=0},\phi_{k|y=1}))p( y^{(i)};\phi_y)\\ \end{aligned}$$

让上面的这个函数最大化就可以产生对参数的最大似然估计：

$$\begin{aligned} \phi_{k|y=1}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}}{\sum^m_{i=1}1\{y^{(i)}=1\}n_i} \\ \phi_{k|y=0}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}}{\sum^m_{i=1}1\{y^{(i)}=0\}n_i} \\ \phi_y&= \frac{\sum^m_{i=1}1\{y^{(i)}=1\}}{m}\\ \end{aligned}$$

如果使用拉普拉斯平滑（实践中会用这个方法来提高性能）来估计$\phi{k|y=0}$ 和 $\phi{k|y=1}$，就在分子上加1，然后分母上加$|V|$，就得到了下面的等式：

$$\begin{aligned} \phi_{k|y=1}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}+1}{\sum^m_{i=1}1\{y^{(i)}=1\}n_i+|V|} \\ \phi_{k|y=0}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}+1}{\sum^m_{i=1}1\{y^{(i)}=0\}n_i+|V|} \\ \end{aligned}$$

当然了，这个并不见得就是一个最好的分类算法，不过朴素贝叶斯分选器通常用起来还都出乎意料地那么好。所以这个方法就是一个很好的”首发选择”，因为它很简单又很好实现。