机器学习笔记5: 朴素贝叶斯算法

朴素贝叶斯模型

在上节介绍的GDA方法中，输入特征x是连续型随机变量。现在我们介绍一个算法用于处理x是离散值的情况。

我们以邮件分类为例来介绍这个算法，邮件分类问题是文本分类(text classification)问题的一个子集。这里我们只考虑把邮件分为两类：垃圾邮件(spam email)和非垃圾邮件(non-spam email)。

我们把邮件中所有出现的单词的集合称为词汇表(vocabulary)。首先我们构造特征向量x_i，x_i的长度等于词汇表里单词的个数。如果词汇表中第i个单词出现在某封邮件中，那么x_i=1，否则x_i=0，比如：

上图表明这封邮件里包含a和buy这两个单词，但不包含aardvark，aardwolf，zygmurgy这三个单词。

构建完特征向量后，我们需要对p(x|y)进行建模。假设词汇表里有50000个单词，那么x是50000维的向量且每个元素在0和1内取值，这样可能的结果就有2⁵⁰⁰⁰⁰种，如果用多项式分布建模的话，就会有2⁵⁰⁰⁰⁰ - 1个参数，这显然是个天文数字。

为了简化问题，我们就需要做一些假设。我们假设给定y的情况下，x_i之间是条件独立的，这个假设称为朴素贝叶斯假设(Naive Bayes assumption)。举例来说，如果y=1表示垃圾邮件，buy是第2087个单词，price是第39831个单词，那么在已知该邮件是垃圾邮件的情况下，“buy出现在该邮件中”和“price出现在该邮件中”这两件事是互不相关的。用形式化的方法表述就是，p(x₂₀₈₇|y)=p(x₂₀₈₇|y, x₃₉₈₃₁)。注意，我们不是说x₂₀₈₇和x₃₉₈₃₁是互相独立的，而是说在给定y的情况下x₂₀₈₇和x₃₉₈₃₁是条件独立的。

因此我们可以作如下推导：

其中第一个等号基于条件概率链式法则，第二个等号基于朴素贝叶斯假设。需要说明的是，尽管朴素贝叶斯假设是个比较强的假设，但在实际问题中表现的效果很好。

我们的模型由φ_i|y=1 = p(x_i=1|y=1)，φ_i|y=0 = p(x_i=1|y=0)和φ_y = p(y=1)这三个参数决定，其似然函数为

通过最大化似然函数，可以求得：

上式中的∧表示逻辑上的与(and)。这个公式可以从直观上进行解释，比如φ_i|y=1就是第j个单词出现在垃圾邮件中的次数除以垃圾邮件的总个数。

所有参数确定后，对一个新特征x作预测，我们可以计算出：

根据p(y=1|x)是否大于0.5来判断新邮件是否是垃圾邮件。

最后，尽管上面我们的x取值只是0或1，但实际上可以把它扩展到多个离散值的情况。另外即使x是连续取值的，我们可以通过离散化(discretize)，即按一定的区间将连续值映射到离散值，然后应用朴素贝叶斯算法。

比如对于房价预测问题，我们可以按照上表把住房面积按一定区间离散化，如果住房面积是890，那么对应的特征值x_i就是3。一般来说，如果连续型随机变量不能用多元正态分布建模(不能使用GDA)，那么将其离散化并采用朴素贝叶斯建模是一个更好的算法。

拉普拉斯平滑处理

朴素贝叶斯算法对大多数问题都有很好的表现，但是我们还需要对其作一些修正使得它在文本分类问题中表现地更出色。

假设NIPS是词汇表里的第35000个单词，但是这个单词从未在训练数据中出现过，因此：

所以预测一个包含单词NIPS的邮件是否为垃圾邮件，我们计算得到：

这是由于每一项乘积里都有p(x₃₅₀₀₀|y) = 0，因此分子分母都为0，这使得我们无法进行计算。

这个问题从广义上来讲就是，仅仅因为一个事件没有在训练集中出现就预测它的概率为0不是一个好主意。对于φ_i = p(z=i)，之前根据最大似然估计的结果为：

为了避免某些φ_j等于0，我们可以使用拉普拉斯平滑处理(Laplace smoothing)，修正参数如下：

我们在原参数基础上，分子上加了1，分母上加了k。注意修正之后，所有
φ_j之和仍然为1(j从1到k取值)。并且所有的φ_j都不为0，解决了之前的问题。

将拉普拉斯平滑处理代入到朴素贝叶斯算法，我们得到修正后的参数：

文本分类的事件模型

朴素贝叶斯算法在很多文本分类问题中都表现地不错，但还有个与之相关的算法表现地更出色。

在文本分类的特定领域，朴素贝叶斯算法使用的是多元伯努利事件模型(multi-variate Bernoulli event model)。在该模型中，我们假设下一封邮件的发送方是随机的发送者(可能是垃圾邮件制造者或者是正常发件人)，然后发送方遍历整个字典，然后决定是否将单词i写到邮件中，每个单词i写入的概率p(x_i=1|y) = φ_i|y互相独立。因此，这封邮件出现的概率为：

我们再介绍另一个模型，称之为多项式事件模型(multinomial event model)。这个模型引入了一套不同的符号和特征，x_i表示邮件里第i个单词的在字典中的位置，x_i在1到|V|中取值，|V|是词汇表(字典)的大小。一封由n个单词组成的邮件由长度为n的向量表示(x₁, x₂, ..., x_n)。比如，某封邮件的开头为"A NIPS ..."，那么x₁=1(a是字典里第1个单词)，x₂=35000(NIPS是字典里第35000个单词)。

在多项式事件模型中，我们仍随机选择发送者(和多元伯努利事件模型一样，概率是p(y))，然后发送者根据多项式分布决定第一个单词x₁出来(概率是p(x₁|y))，再以同样的方式决定后续的单词x₂, ..., x_n，直到选出n个单词构成这封邮件。因此，在该模型下邮件出现的概率为：