朴素贝叶斯分类器 - 时间轨迹

朴素贝叶斯分类器


贝叶斯定理是概率论中非常有名的一个定理,而朴素贝叶斯(Naive Bayes)则是贝叶斯理论下非常有名的一个算法,在ML和NLP领域里面应用非常多。之前做过一些学习笔记,今天把原来的笔记再梳理了一下,发到博客上面来。如有不对之处,欢迎指正。另外,因为过的时间比较久了,当时整理时参考的一些出处已经记不得了,后面就不附出处了,开始正题。

贝叶斯公式

先看一下贝叶斯涉及到的一些概率论的概念:

$$ P(A|B) = \frac{P(AB)}{P(B)} $$

上面的公式是条件概率(conditional probability)的通用定义,介绍以下三个概念:

  • 边缘概率(marginal probability):仅和单个随机变量有关的概率,比如上面的$P(A)$和$P(B)$。
  • 联合概率(joint probability):包含多个条件且所有条件同时成立的概率。
  • 条件概率:在某些条件确定的情况下另外一些条件发生的概率,比如上面公式是$P(A|B)$就是A的条件概率。

下面看著名的贝叶斯公式:

$$ P(X|Y) = \frac{P(Y|X)P(X)}{P(Y)} $$

公式及其推导非常简单,因为$P(XY)=P(Y|X)P(X)$,用该式替换掉条件概率公式的分母即可得到贝叶斯公式。这里我们再介绍几个术语,在上面公式中:

  • $P(X)$称之为(X的)先验概率(prior probability),因为$P(X)$的概率是已知的了。
  • $P(Y|X)$称之为(Y的)条件概率,和之前概念一样。
  • $P(X|Y)$称之为(X的)后验概率(posterior probability)。

贝叶斯公式形式很简单,那有什么重大意义呢?

上面我在写贝叶斯公式的时候用X、Y代替了原来的A、B,是因为我们一般用X表示自变量,Y表示应变量。而贝叶斯公式就是来描述这种因果关系的,这样写更习惯一些。放到现实中,X就是事件发生的原因,Y对应于事件的结果。贝叶斯公式的重大意义在于给出了一个解决逆问题的方法,所谓逆问题是指从结果Y反推原因X,因为有些情况下事情发生的原因往往是无法被直接观察和测量的。举一些例子:

  • 通信:根据含有噪声的接收信号Y推测发送信号X
  • 语音识别:根据麦克风识别的音频波形数据Y推测语音信息X
  • 文字识别:根据扫描仪读取的图像数据Y推测用户书写的文字X
  • 垃圾邮件过滤:根据收到的邮件文本Y推测邮件的类型X(是否是广告等)

这里再提一下先验概率和后验概率(因为我当时对于这二者的含义疑惑了比较久),这二者主要用于表示事件是发生于结果Y取得之前还是之后,比如$P(X)$是Y还没有得到,所以为先验概率;而$P(X|Y)$是结果Y已经得到了,所以为后验概率。

从上面的描述可以看出,X和Y之间存在一定的因果关系,这样我们是不是可以建立一个$X=f(Y)$的公式来由结果Y计算原因X呢?这的确是一种解决方案,但实际效果往往会很差,因为现实中存在噪声和误差,即使即使X相同,Y也可能不同,而贝叶斯公式给出了一个借助概率来处理这些噪声与误差进而解决逆问题的方法,这便是它的伟大之处。

那么问题来了,贝叶斯公式中的$P(Y)$如何求解呢?这时候就用到全概率公式了:

假设{$B_n:n=1,2,3...$}是一个概率空间的有限或者可数无限的分割(即$B_n$为一个完备事件组),且每个集合$B_n$是一个可测集合,则对任意事件$A$有全概率公式:

$$ P(A) = \sum_n P(AB_n) $$

再结合条件概率公式,全概率公式又可写作:

$$ P(A) = \sum_n P(A|B_n)P(B_n) $$

全概率公式的意义在于将一复杂事件A的概率求解问题转化为了在不同情况或不同原因$B_n$下发生的简单事件的概率的求和问题。

所以由全概率公式可知:

$$ P(Y) = \sum_j P(Y|X_j)P(X_j) $$

从而有:

$$ P(X_i|Y) = \frac{P(Y|X_i)P(X_i)}{\sum_j P(Y|X_j)P(X_j)} $$

上面是比较一般化的情况,$X_j$是事件集合里面的部分集合,所有的$X_j$构成一个完备事件组。如果我们将原因划分为$X$和$\lnot X$(非$X$,即$X$的补集),这样上述公式可以简写为:

$$ P(X|Y) = \frac{P(Y|X)P(X)}{P(Y|X)P(X) + P(Y|\lnot X)P(\lnot X)} $$

这也是贝叶斯公式的扩展形式。

朴素贝叶斯

公式推导

朴素贝叶斯(下文简称NB)是监督学习里面的一种分类算法,使用场景为:

给定训练集$(X, Y)$,其中每个样本$x$都包含$n$维特征,即$x=(x_1,x_2,...,x_n)$,标签集合含有$k$种类别,即$y=(y_1,y_2,...,y_k)$。如果现在来了一个新的样本$x$,我们如何判断它属于哪个类别?

NB的解决思路是:从概率的角度看,这个问题就是给定x,它属于哪个类别的概率最大。那么问题就转化为求解$P(y_1|x),P(y_2|x),...,P(y_k|x)$中最大的那个,即求后验概率最大的那个:

$$ \mathop{argmax}_{y} P(y|x) $$

所以朴素贝叶斯分类器就是求上式的最大值,根据贝叶斯公式将上面式子展开后如下:

$$ P(y|x_1,...,x_n) = \frac{P(y)P(x_1,...,x_n|y)}{P(x_1,...,x_n)} $$

可以看到,上面的式子中:

  • $P(y)$是先验概率,可以直接根据数据集计算出来。
  • $P(x_1,...,x_n)$如何计算?
  • $P(x_1,...,x_n|y)$如何计算?

首先来看$P(x_1,...,x_n|y)$的计算。这里需要用到条件联合概率分解公式:

  • $P(XY|Z) = P(X|YZ)P(Y|Z)$
  • $P(UVWX|YZ) = P(U|VWXYZ)P(V|WXYZ)P(W|XYZ)P(X|YZ)P(Y|Z)$

利用条件联合概率分解公式:

$$ P(x_1,...,x_n|y) = P(x_1|x_2,...,x_n,y)P(x_2|x_3,...,x_n,y)...P(x_n|y) $$

上面式子很难计算,所以NB理论对条件概率分布做了独立性假设,就是在我们的场景下各个维度特征$x_1,...,x_n$相互独立(这就是朴素贝叶斯中“朴素”二字的含义),即:

$$ P(x_i|y,x_1,...,x_{i-1},x_{i+1},...,x_n) = P(x_i|y) $$

有了上面的假设,之前那个难计算的公式就好计算了:

$$ \begin{align} P(x_1,...,x_n|y) &= P(x_1|x_2,...,x_n,y)P(x_2|x_3,...,x_n,y)...P(x_n|y)\\ &=P(x_1|y)P(x_2|y)...P(x_n|y)\\ &= \frac{P(y)\prod_{i=1}^n P(x_i|y)}{P(x_1,...,x_n)} \end{align} $$

这样,最初的式子就变为:

$$ P(x_1,...,x_n|y) = \frac{P(y)\prod_{i=1}^n P(x_i|y)}{P(x_1,...,x_n)} $$

对于确定的输入,不论$y$取哪个值,${P(x_1,...,x_n)}$都是一样的,所以

$$ P(x_1,...,x_n|y) \propto P(y)\prod_{i=1}^n P(x_i|y) $$

所以新样例$x=(x_1,...,x_n)$所属的类别$y$的计算公式为:

$$ \hat y= \mathop{argmax}_{y} P(y|x)\prod_{i=1}^n P(x_i|y) $$

所以,NB分类器最后就是求先验概率$P(y)$和$x_i$的条件概率$P(x_i|y)$,这两个概率都是可以计算的。

NB共有三个模型:

  • 多项式模型
  • 高斯模型
  • 伯努利模型

多项式和伯努利模型是处理离散型数据的,高斯模型是处理连续型数据的。

多项式模型

当特征是离散的时候,使用多项式模型。多项式模型在计算先验概率$P(y)$和条件概率$P(x_i|y)$的时候会做一些平滑处理:

$$ P(y) = \frac{N_y+\alpha}{N+k\alpha} $$

其中,$N$是样本总数,$k$是类别总数,$N_y$是类别为y的样本个数,$\alpha$是平滑值。

$$ P(x_i|y) = \frac{N_{y,x_i}+\alpha}{N_y+n\alpha} $$

其中,$N_{y,x_i}$是类别为$y$的样本中,第$i$维特征的值是$x_i$的个数,$n$是第$i$维特征的个数,其它同上。

  • $\alpha=1$时,称作Laplace平滑(常用);
  • $0<\alpha<1$时,称作Lidstone平滑;
  • $\alpha=0$时不做平滑。

如果不做平滑,当某一维特征的值$x_i$没在训练样本中出现过时,会导致$P(x_i|y)=0$,从而导致后验概率为0,加上平滑可以克服这个问题。一般比较常用的是Laplace平滑。

下面看一个例子:

有如下训练数据,15个样本,2维特征$X^{(1)}和X^{(2)}$,2种类别-1和1.给定测试样本$x=(2,S)^T$,运用多项式模型(取$\alpha=1$),判断其类别。

序号$X^{(1)}$$X^{(1)}$$Y$
11S-1
21M-1
31M1
41S1
51S-1
62S-1
72M-1
82M1
92L1
102L1
113L1
123M1
133M1
143L1
153L-1

根据公式,我们需要计算先验概率和各种条件概率(注意做了Laplace平滑):

先验概率:

$P(Y=1)=\frac{10}{17}, P(Y=-1)=\frac{7}{17}$

各种条件概率:

$P(X^{(1)}=1|Y=1)=\frac{3}{12}, P(X^{(1)}=2|Y=1)=\frac{4}{12}, P(X^{(1)}=3|Y=1)=\frac{5}{12}$

$P(X^{(2)}=S|Y=1)=\frac{2}{12}, P(X^{(2)}=M|Y=1)=\frac{5}{12}, P(X^{(2)}=L|Y=1)=\frac{5}{12}$

$P(X^{(1)}=1|Y=-1)=\frac{4}{9}, P(X^{(1)}=2|Y=-1)=\frac{3}{9}, P(X^{(1)}=3|Y=-1)=\frac{2}{9}$

$P(X^{(2)}=S|Y=-1)=\frac{4}{9}, P(X^{(2)}=M|Y=-1)=\frac{3}{9}, P(X^{(2)}=L|Y=-1)=\frac{2}{9}$

对于给定的$x=(2,S)^T$,根据NB公式计算:

属于1类别的概率:

$P(Y=1)P(X^{(1)}=2|Y=1)P(X^{(2)}=S|Y=1)=\frac{10}{17}\frac{4}{12}\frac{2}{12}=\frac{5}{153}\approx0.0327$

属于-1类别的概率:

$P(Y=-1)P(X^{(1)}=2|Y=-1)P(X^{(2)}=S|Y=-1)=\frac{7}{17}\frac{3}{9}\frac{4}{9}=\frac{28}{459}\approx0.0610$

所以,显然对于特征$x=(2,S)^T$,应该属于-1类别。

高斯模型

当特征是连续变量的时候,运用多项式模型就会导致很多$P(x_i|y_k)=0$(不做平滑的情况下),此时即使做平滑,所得到的条件概率也难以描述真实情况。所以处理连续型特征变量,一般采用高斯模型:

$$ P(x_i|y) = \frac{1}{\sqrt {2\pi\sigma^2_y}}exp(-\frac{(x_i-\mu_y)^2}{2\sigma^2_y}) $$

其中,$\mu_y$和$\sigma^2_y$分别标识类别为$y$的样本中,第$i$维特征的均值和方差。

看一个例子:

已知如下一些样本数据:

性别身高(英尺)体重(磅)脚掌(英寸)
618012
5.9219011
5.5817012
5.9216510
51006
5.51508
5.421307
5.751509

现在问题来了:已知某人身高6英尺,体重130磅,脚掌8英寸,请问该人是男是女?

这里$P(男)=P(女)=0.5$,依据NB分类器,我们还需计算:

$$ P(身高|性别)P(体重|性别)P(脚掌|性别)P(性别) $$

但可以看到,由于身高、体重、脚掌都是连续变量,不能采用离散变量的方法计算概率。而且由于样本太少,也无法分成区间计算。怎么办?

可以假设男性和女性的身高、体重、脚掌都服从正太分布,通过样本计算出均值和方差,也就是的到正态分布的概率密度函数。有了概率密度函数,就可以把值带入,算出某一点密度函数的值。比如男性的身高是均值为5.855,方差为0.035的正太分布。所以,男性的身高为6英尺的概率的相对值等于1.5789(大于1并没有关系,因为这里是密度函数的值,只用来反映各个值的相对可能性)。

$$ P(身高|性别)=\frac{1}{\sqrt {2\pi\sigma^2_y}}exp(-\frac{(6-\mu_y)^2}{2\sigma^2_y}) \approx 1.5789 $$

对于脚掌和体重同样可以计算均值和方差(计算过程省略)。有了这些数据以后,就可以计算性别的分类了:

是男性的概率:

$P(身高=6|男)P(体重=130|男)P(脚掌=8|男)P(男) \approx 6.1984 \times 10^{-9}$

是女性的概率:

$P(身高=6|女)P(体重=130|女)P(脚掌=8|女)P(女) \approx 5.3778 \times 10^{-4}$

可以看到,女性的概率比男性要高出将近10000倍,所以判断该人为女性。

伯努利模型

与多项式模型一样,伯努利模型适用于离散特征的情况,所不同的是,伯努利模型中每个特征的取值只能是1或0(以文本分类为例,某个单词在文档中出现过,则其特征值为,否则为0)。

伯努利模型中,条件概率$P(x_i|y)$的计算方式时:

  • 当特征值$x_i=1$时,$P(x_i|y)=P(x_i=1|y)$
  • 当特征值$x_i=0$时,$P(x_i|y)=1-P(x_i=1|y)$

总结

总结一下重点:

  • 贝叶斯公式的重大意义在于提供了一种使用概率解决逆问题的方法。
  • 朴素贝叶斯的朴素指的是假定各个特征之间是相互独立的,从而简化了计算过程。

PS:打公式好累,真是痛并快乐着...


本文由时间轨迹创作,转载请注明出处及链接。
赞赏


微信赞赏

支付宝赞赏

添加新评论

选择表情

友情提醒:填写邮箱是当别人回复你的评论时,会给邮箱发邮件提醒。

|