朴素贝叶斯模型（naive bayes）
注：本博客为周志华老师《机器学习》的读书笔记，但同时也参考了李航老师的《统计学习》方法，以及其他资料（见参考文献），虽有自己的理解，但博客里的例子是基于《机器学习》的。
在讲具体的原理之前，先说说朴素贝叶斯的几个特点：1、朴素贝叶斯是一种典型的生成式模型，有监督学习可以分为两类：判别模型和生成模型，我们所熟悉的神经网络，支持向量机和logistic regression，决策树等都是判别模型。而朴素贝叶斯和隐马尔可夫模型则属于生成式模型。关于判别式模型和生成式模型的区别这里写一下：
判别式模型由数据直接学习 P(y∣x)P(y|x)P(y∣x)来预测yyy，而生成式模型则是学习每个类别对应的分布P(x∣y)P(x|y)P(x∣y)和P(y)P(y)P(y)（也就是联合概率P(x,y)P(x,y)P(x,y)，P(x,y)=P(x∣y)P(y)P(x,y)=P(x|y)P(y)P(x,y)=P(x∣y)P(y)）。用个通俗易懂的例子来解释下（摘自ng：Generative Learning algorithms），假如我们的任务是个二分类任务，要算法根据训练数据判断出是大象（label=0）还是狗（label=1），判别式模式直接对P(y∣x)P(y|x)P(y∣x)建模，学习的是大象和狗之间的区别（Machine Learning: Generative and Discriminative Models，p10）。而生成式模型则分别对大象建模 P(x∣y=0)P(x|y=0)P(x∣y=0)和对狗建模P(x∣y=1）P(x|y=1）P(x∣y=1），也就是用一个模型来刻画大象，再用另一个模型来刻画狗。来了一个新样本后，它去分别和大象和狗的模型进行匹配，看看更像哪一个，则把新样本分为哪一类。也就是说，生成式模型实际上是建立一个多模型（有多少类就建多少个模型），而判别式模型只有一个模型。
这两种方法各有优缺点，判别模型可以简化学习问题，由于直接面对预测，往往学习的准确率更高（判别式模型性能通常较好，这一点在Ng和Jordan的论文的论文中也说明了，论文：On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes ）这一篇文章是一篇很经典的阐述判别式模型和生成式模型的论文），而生成式模型的学习收敛速度更快，当样本数量增加的时候，学到的模型可以更快的收敛于真实模型。而且可以学习有因变量的任务，比如隐马尔科夫模型。
Note：国内的书李航老师的《统计学习方法》和周志华老师的《机器学习》对生成模型的定义，皆为：先对联合概率P(x,y)P(x,y)P(x,y)建模，然后由此求得P(y∣x)P(y|x)P(y∣x)。虽然本质上和Ng讲的是一样的，但感觉ng的note更好理解，强烈建议大家看一下，note：Generative Learning algorithms，毕竟关于判别模型和生成模型，ng和他的导师Jordan在02年发表了一篇经典论文。
再回到朴素贝叶斯模型的话题上，我们先来看看贝叶斯决策理论，来一点点引出朴素贝叶斯模型，根据贝叶斯公式有：
(1)P(y∣x)=p(x∣y)⋅p(y)p(x)P(y|x)=\frac{p(x|y)\cdot p(y)}{p(x)} \tag{1} P(y∣x)=p(x)p(x∣y)⋅p(y)(1)
其实贝叶斯公式用更加朴素的语言就是：
(2)后验=似然×先验证据后验 = \frac{似然\times先验}{证据}\tag{2} 后验=证据似然×先验(2)
其中，P(y)P(y)P(y)是先验概率，P(x∣y)P(x|y)P(x∣y) 是样本xxx相对于类别yyy的条件概率（也称似然），P(x)P(x)P(x)是一个与yyy无关的归一化因子，因此它对所有类别来说都是相同的，其实就是个常数，因此：
(3)P(y∣x)∝p(x∣y)⋅p(y)P(y|x) \propto p(x|y)\cdot p(y)\tag{3} P(y∣x)∝p(x∣y)⋅p(y)(3)
设样本xxx有nnn个特征为：x1,x2,x3,...,xnx_1,x_2,x_3,...,x_nx1,x2,x3,...,xn，则上式3为：
(4)P(y∣x1,…,xn)∝P(y)P(x1,…xn∣y)P(y \mid x_1, \dots, x_n) \propto P(y) P(x_1, \dots x_n \mid y)\tag{4} P(y∣x1,…,xn)∝P(y)P(x1,…xn∣y)(4)
而根据条件概率的乘法公式，又有：
(5)P(x1,…xn∣y)=P(x1∣y)⋅P(x2∣x1,y)⋅P(x3∣x1,x2,y)⋅⋅⋅P(xn∣x1,x2,....,xn−1,y)P(x_1, \dots x_n \mid y) = P(x_1|y)\cdot P(x_2|x_1,y)\cdot P(x_3|x_1,x_2,y)\cdot \cdot \cdot P(x_n|x_1,x_2,....,x_{n-1},y)\tag{5} P(x1,…xn∣y)=P(x1∣y)⋅P(x2∣x1,y)⋅P(x3∣x1,x2,y)⋅⋅⋅P(xn∣x1,x2,....,xn−1,y)(5)
到这一步，发现没法做了，因为复杂度太高了，后面的多元联合概率没法算。即使对于二元分类，我们的特征xix_ixi是二值的，那么复杂度也有2n2^n2n这种指数级的。因此朴素贝叶斯给出了一个神假设：假设特征之间是独立的。所谓“朴素”二字就体现在这个地方，但是根据我们的常识也知道，样本的特征之间几乎不太可能是相互独立的，因此朴素贝叶斯效果肯定不好，但结果却恰恰相反，无数的实验证明朴素贝叶斯对于文本分类任务效果都很好。
有了特征之间是相互独立的这个假设后，则上面的公式变为：
(6)P(y∣x1,x2,...,xn)=P(y)p(x1,x2,...,xn∣y)P(x1,x2,...,xn)∝P(y)⋅P(x1,x2,...,xn∣y)=P(y)⋅P(x1∣y)⋅P(x2∣x1,y)⋅P(x3∣x1,x2,y)⋅⋅⋅P(xn∣x1,x2,....,xn−1,y)=P(y)⋅P(x1∣y)⋅P(x2∣y)⋅P(x3∣y)⋅⋅⋅P(xn∣y)=P(y)⋅∏i=1nP(xi∣y)\begin{array}{lcl} P(y|x_1,x_2,...,x_n)&=&\frac{P(y)p(x_1,x_2,...,x_n|y)}{P(x_1,x_2,...,x_n)}\\\\ &\propto& P(y)\cdot P(x_1,x_2,...,x_n|y)\\\\ &=&P(y)\cdot P(x_1|y)\cdot P(x_2|x_1,y)\cdot P(x_3|x_1,x_2,y)\cdot \cdot \cdot P(x_n|x_1,x_2,....,x_{n-1},y)\\\\ &=&P(y)\cdot P(x_1|y)\cdot P(x_2|y)\cdot P(x_3|y)\cdot \cdot \cdot P(x_n|y)\\\\ &=&P(y)\cdot \prod_{i=1}^{n}P(x_i|y) \end{array}\tag{6} P(y∣x1,x2,...,xn)=∝===P(x1,x2,...,xn)P(y)p(x1,x2,...,xn∣y)P(y)⋅P(x1,x2,...,xn∣y)P(y)⋅P(x1∣y)⋅P(x2∣x1,y)⋅P(x3∣x1,x2,y)⋅⋅⋅P(xn∣x1,x2,....,xn−1,y)P(y)⋅P(x1∣y)⋅P(x2∣y)⋅P(x3∣y)⋅⋅⋅P(xn∣y)P(y)⋅∏i=1nP(xi∣y)(6)
我们只需最大化后验概率，即：
(7)y^=argmaxyP(y)∏i=1nP(xi∣y)\hat{y} = \arg\max_y P(y) \prod_{i=1}^{n} P(x_i \mid y) \tag{7} y^=argymaxP(y)i=1∏nP(xi∣y)(7)
再回想下上面说的，生成式模型会给每个类别都建立一个模型（分布），然后新样本过来后计算与哪个分布更匹配，就划归到哪一类中，而朴素贝叶斯算法用一句话简短直白的说就是：算出新样本在每个类别的后验概率，然后看哪个最大，就把新样本分到哪个类中。还有一点需要注意的是，朴素贝叶斯并不需要像神经网络，logistic 回归和线性回归这样先根据训练数据去学习参数，然后预测新样本。朴素贝叶斯是直接那新样本去数据集（训练集）去算后验概率，然后分类，这一点与knn很相似，都是不需要训练的。
我们接下来看看公式（7）中，P(y)P(y)P(y)和P(xi∣y)P(x_i|y)P(xi∣y)怎么求，根据大数定律，若样本量充足，则有：
(8)P(yc)=∣Dc∣∣D∣P(y_c) = \frac{|D_c|}{|D|}\tag{8} P(yc)=∣D∣∣Dc∣(8)
(9)P(xi∣y)=∣Dc,xi∣∣Dc∣P(x_i|y) = \frac{|D_{c,x_i}|}{|D_c|}\tag{9} P(xi∣y)=∣Dc∣∣Dc,xi∣(9)
其中，DcD_cDc表示训练集DDD中第ccc类样本的数量，∣Dc,xi∣|D_{c,x_i}|∣Dc,xi∣表示DcD_cDc中第iii个属性上取值为xix_ixi的样本个数。
那么问题来了，对于分类任务而言，类别肯定是离散的，那么特征取值可不一定啊，有可能是离散的也有可能是连续的。上面的公式（9）只适用于特征值为离散的情况，那么对于特征值是连续的，该怎么做呢？这也是生成式模型的特点，需要假设分布，在朴素贝叶斯中，对于连续值，假设其符合高斯分布，即:P(xi∣y)∼N(μc,i,σc,i2)P(x_i|y) \sim N(\mu_{c,i},\sigma^2_{c,i})P(xi∣y)∼N(μc,i,σc,i2)
(10)P(xi∣y)=12πσc,iexp(−(xi−μc,i)22σc,i2)P(x_i|y) = \frac{1}{\sqrt{2 \pi}\sigma_{c,i}}exp(-\frac{(x_i - \mu_{c,i})^2}{2\sigma^2_{c,i}}) \tag{10} P(xi∣y)=2πσc,i1exp(−2σc,i2(xi−μc,i)2)(10)
其中，μc,i,σc,i2\mu_{c,i},\sigma_{c,i}^2μc,i,σc,i2为分别第ccc类样本在第iii个属性上的均值和方差。
这其实就是朴素贝叶斯的原理了，基本就是这些内容，是不是真的很简单直白。在实际使用中（实现），往往还需要做个平滑，防止概率出现0的情况，这个我们下面会讲，这里先提一下。我们先来举个例子，看看在朴素贝叶斯到底是怎么实现分类的。这里的例子以及数据集，均来自周志华老师的《机器学习》书，数据集：
我们取第一条样本当做测试样本，即：
下面是计算过程：
目前看似一切很完美，但是其实暗藏一个bug，上面计算每个类别的概率是个连乘，连乘就会有问题，如果其中一项为0，则结果直接为0。比如，我们有个测试样本的特征为：敲声=清脆，基于上面的数据集，能够发现
P(清脆∣是)=P(敲声=清脆∣好瓜=是)=0/8=0P(清脆|是) = P(敲声=清脆|好瓜=是) = 0/8 = 0 P(清脆∣是)=P(敲声=清脆∣好瓜=是)=0/8=0
因此，**即使其它所有特征都很符合好瓜，但是也会被判定为坏瓜。这显然是不合理的。**因此，就要用到上面提到的平滑技术，对这个概率值进行平滑，这里用拉普拉斯平滑，贝叶斯里的拉普拉斯推导就不写了，有兴趣的可以看下李航老师的《统计学习方法》或者ng的那个note，有个简短的推导。这里直接给出计算公式：
(11)P^(c)=∣Dc∣+1∣D∣+N\widehat{P}(c) = \frac{|D_c| + 1}{|D| + N} \tag{11} P(c)=∣D∣+N∣Dc∣+1(11)
(12)P^(xi∣c)=∣Dc,xi∣+1∣Dc∣+Ni\widehat{P}(x_i|c) = \frac{|D_{c,x_i}| + 1}{|D_c| + N_i} \tag{12} P(xi∣c)=∣Dc∣+Ni∣Dc,xi∣+1(12)
其中，NNN表示训练集中可能的类别数，于二分类而言，N=2N=2N=2。NiN_iNi表示第iii个属性可能的取值数。
因此，在上面的例子中，加入拉普拉斯平滑后，可修正为：
(13)P^(好瓜=是)=8+117+2=0.474，P^(好瓜=否)=9+117+2=0.526\widehat{P}(好瓜=是) = \frac{8+1}{17+2}=0.474，\widehat{P}(好瓜=否) = \frac{9+1}{17+2}=0.526 \tag{13} P(好瓜=是)=17+28+1=0.474，P(好瓜=否)=17+29+1=0.526(13)
同样，
P^(青绿∣是)=P^(色泽=青绿∣好瓜=是)3+18+3=0.364P^(青绿∣否)=P^(色泽=青绿∣好瓜=否)3+19+3=0.333\widehat{P}(青绿|是) = \widehat{P}(色泽=青绿|好瓜=是) \frac{3+1}{8+3}=0.364 \\ \widehat{P}(青绿|否) = \widehat{P}(色泽=青绿|好瓜=否) \frac{3+1}{9+3}=0.333 P(青绿∣是)=P(色泽=青绿∣好瓜=是)8+33+1=0.364P(青绿∣否)=P(色泽=青绿∣好瓜=否)9+33+1=0.333
后面的这里就不算了，感兴趣的可自行算下。显然拉普拉斯平滑解决了上文中提到的概率为0问题，而且当数据集足够大时，样本数足够多时，拉普拉斯平滑也不会对概率产生影响，几乎可以忽略不计。
参考文献
[1]: 周志华 著. 机器学习, 北京: 清华大学出版社
[2]: 李航 著. 统计学习方法, 北京: 清华大学出版社
[3]: Andrew ng. CS229 Lecture notes 《Generative Learning algorithms》
[4]: Sargur N. Srihari. Machine Learning: Generative and Discriminative Models
