贝叶斯决策及朴素贝叶斯分类器的思考

1、贝叶斯决策

贝叶斯决策的出发点是利用概率的不同分类决策与相应的决策代价之间的定折中。基于以下假设：决策问题可以用概率的形式描述，并且假设所有相关的概率结构均已知。（可以回顾推导LR分类器）同时也会出现概率结构不完全知道的情况。

问题：设计一个能分开两类鱼（鲈鱼和鲑鱼）的分类器。

当每条鱼出现时其类别 处于两种可能的状态，用$w$表示类别状态，那么当$w=w_{1}$时是鲈鱼，$w=w_{2}$时是鲑鱼。由于类别状态不确定，可以假设$w$是一个由概率描述其特性的随机变量。假设实际捕到的鲈鱼和鲑鱼的数目相等，那么可以说下一次出现鲈鱼和出现鲑鱼的可能性相等，即可以假定：下一条鱼是鲈鱼的“先验概率”为$P(w_{1})$，下一条鱼是鲑鱼的“先验概率”为$P(w_{2})$，$P(w_{1})+P(w_{2})=1$。先验知识可能取决于季节的不同或捕鱼地点的不同。假定任何方式的错误判决都会付出同样的代价或产生同样的后果

• 判决规则1：如果$P(w_{1})>P(w_{2})$，则判为类$w_{1}$，否则$w_{2}$。缺陷在于判决结果的好坏完全取决于先验概率值，如果$P(w_{1})>>P(w_{2})$，那么判决$w_{1}$将在多数情况下是对的；如果$P(w_{1})=P(w_{2})$，那么我们将只有50%的正确率。
• 判决规则2：可以利用观察到的鱼的光泽度指标$x$来提高分类器性能。不同的鱼将产生不同的光泽度，假定$x$是一个连续随机变量，其分布取决于类别状态，表示为$p(x|w)$的形式（类条件概率密度函数），即类别为w时、x的概率密度函数。$p(x|w_{1})$与$p(x|w_{2})$间的区别表示了鲈鱼和鲑鱼光泽度的区别。

假设已知先验概率$P(w_{j})$，也知道类条件概率密度$p(x|w_{j}),j=1,2$，通过观测和测量，发现鱼的光泽度为$x$，如何获取鱼的类别状态。处于类别$w_{j}$并且具有特征值$x$的模式的联合概率密度可写成

$p(w_{j},x)=P(w_{j}|x)p(x)=p(x|w_{j})P(w_{j})$

可得贝叶斯公式：$P(w_{j}|x)=\frac{p(x|w_{j})P(w_{j})}{p(x)}$  （1）

在二分类情况下：

                              $p(x)=\sum_{j=1}^{2}p(x|w_{j})P(w_{j})$              （2）

$posterior=\frac{likelihood\times prior}{evidence}$

其中$p(x|w_{j})$为$w_{j}$关于$x$的似然函数(likelihood)，表明在其他条件都相等的情况下，使得$p(x|w_{j})$较大的$w_{j}$更有可能是真实的类别。后验概率主要是先验概率和似然函数的乘积决定，evidence因子可以看做是一个标量因子，以保证各类别的后验概率总和为1从而满足概率条件。

如果某个观测值$x$使得$P(w_{1}|x)$比$P(w_{2}|x)$大，作出真实类别是$w_{1}$的判决。计算做出某次判决时的误差概率，观测某一特定的$x$，

对于某一给定的$x$，可以在最小化误差概率的情况下判决，如果$P(w_{1}|x)$比$P(w_{2}|x)$大则为$w_{1}$。很少可能两次观测到严格相同的$x$，因而将规则修改为平均误差概率最小化：

最小化误差概率条件下的贝叶斯决策规则：

如果$P(w_{1}|x)>P(w_{2}|x)$，判别为 $w_{1}$；否则，判别为$w_{2}$。

所以$P(error|x)=min[P(w_{1}|x),P(w_{2}|x)]$。强调后验概率的重要性。

注意到式(1)中evidence因子$p(x)$对于做出某种判决没有其作用，它是一个标量因子，为保证$P(w_{1}|x)+P(w_{2}|x)=1$。Logistic Regression的思想就是：通过x的线性函数对K个类的后验概率建模，而同时确保它们的和为1，并且都在[0,1]中。

因此可以得到完全等价的判决规则：

如果$p(x|w_{1})P(w_{1})>p(x|w_{2})P(w_{2})$，判别为$w_{1}$；否则判别为$w_{2}$。

观察上式，如果对于某个$x$，有$p(x|w_{1})=p(x|w_{2})$，那么说明在某次特定的观测后没有获得新信息。这种情况下判决完全取决于先验概率。另一方面，如果$P(w_{1})=P(w_{2})$，那么类别状态等可能出现，这种情况下判决取决于似然概率$p(x|w_{j})$。贝叶斯决策规则将它们结合以获得最小的误差概率。

 2、贝叶斯决策论的推广

•  允许使用多于一个的特征，将特征标量x换位特征向量x，x处于d维欧式空间
• 允许多于两种类别状态的情形
• 允许有其他行为而不是仅仅是判定类别
• 通过引入一个更一般的损失函数来替代误差概率（精确阐述每种行为付出的代价大小）

令$\{w_{1},...,w_{c}\}$表示有限的$c$个类别集，$\{\alpha_{1},...,\alpha_{a}\}$表示有限的$a$钟可能采取的行为集，风险函数$\lambda(\alpha_{i}|w_{j})$来描述类别状态为$w_{j}$时采取行动$\alpha_{i}$的风险。特征向量x表示一个d维随机变量，令$p(\textbf{x})$表示x的状态条件概率密度函数——在真实类别为$w_{j}$的条件下x的概率密度函数。后验概率$P(w_{j}|\textbf{x})$可得：

 $P(w_{j}|\textbf{x})=\frac{p(\textbf{x}|w_{j})P(w_{j})}{p(\textbf{x})}$

  $p(\textbf{x})=\sum_{j=1}^{c}p(\textbf{x}|w_{j})P(w_{j})$

假定观测某个特定模式x并将采取行动$\alpha_{i}$，如果真实的类别状态为$w_{j}$，那么将有损失$\lambda(\alpha_{i}|w_{j})$。d定义与行为$\alpha_{i}$相关联的损失函数为

$R(\alpha_{i}|\textbf{x})=\sum_{j=1}^{c}\lambda(\alpha_{i}|w_{j})P(w_{j}|\textbf{x})$

$R(\alpha_{i}|\textbf{x})$称为条件风险，无论何时遇到某种特定的观测模式x,通过选择最小化条件风险的行为来使预期的损失最小化。

更为一般的判决规则为找到一个函数$\alpha(\textbf{x})$，可以得到每种可能的观测应该采取哪种行为。即对于每个x，判决函数$\alpha(\textbf{x})$确定了$\alpha$的值$\alpha_{1}$,...,$\alpha_{a}$。总分险R是与某一给定的判决规则相关的预期损失。$R(\alpha_{i}|\textbf{x})$是和行为$\alpha_{i}$有关的条件风险，并且决策规则指定了其行为，所以总风险定义如下：

$R=\int R(\alpha(\textbf{x})|\textbf{x})p(\textbf{x})d\textbf{x}$

整个积分是在整个特征空间进行的。选择$\alpha(\textbf{x})$，使 $R(\alpha_{i}|\textbf{x})$对每个$\textbf{x}$尽可能小，那么总风险将被最小化。

引出如下贝叶斯决策规则：为了最小化总风险，对于所有$i=1,2,...,a$计算条件风险

$R(\alpha_{i}|\textbf{x})=\sum_{j=1}^{c}\lambda(\alpha_{i}|w_{j})P(w_{j}|\textbf{x})$

并且选择行为$\alpha_{i}$使$R(\alpha_{i}|\textbf{x})$最小化。（如果有一种以上的行为都可以使$R(\alpha_{i}|\textbf{x})$最小化，那么该选择哪种行为不重要）。最小化后的总风险值称为贝叶斯风险，记为$R^{*}$

2.1、应用于二分类问题

行为$\alpha_{1}$对应于类别判决$w_{1}$，行为$\alpha_{2}$对应于类别判决$w_{2}$。$\lambda_{ij}=\lambda(\alpha_{i}|w_{j})$表示实际类别$w_{j}$时误判为$w_{i}$所引起的损失。

最小风险决策规则：如果$R(\alpha_{1}|\textbf{x})<R(\alpha_{2}|\textbf{x})$，则判别为$w_{1}$。用后验概率的形式表述为

观察上式，$\lambda_{21}-\lambda_{11}$和$\lambda_{12}-\lambda_{22}$都是正数，因为通常一次错误判决所造成的损失比正确判决要大。

利用贝叶斯公式，用先验概率和条件密度来表示后验概率，决策规则等价于

那么判决为$w_{1}$。

另一种表达方法，合理假设$\lambda_{21}>\lambda_{11}$，如果下式成立 那么判决为$w_{1}$。注意观察，这种判决规则的形式主要依赖于x的概率密度。考虑$p(\textbf{x}|w_{j})$作为$w_{j}$的函数（似然函数），构成似然比$p(\textbf{x}|w_{1})/p(\textbf{x}|w_{2})$。

重要结论：

因此贝叶斯规则可以解释为如果似然比不超过某个不依赖观测值x的阈值，那么可判决为$w_{1}$。

2.2、最小误差率分类（从贝叶斯角度看损失函数）

在分类问题中，通常每种类别状态都与c类中的一种有关，且行为$\alpha_{i}$对应于类别判决$w_{i}$。如果采取行为$\alpha_{i}$而实际类别为$w_{j}$，那么在$i=j$的情况下是正确的，而$i!=j$则会产生误判。

“0-1”损失函数

这个损失函数将0损失赋给一个正确的判决，而将一个单位损失判决给任何一种错误判决，显然这里所有误判都是等代价的。

注意：对于回归任务，如二次型或线性查分损失函数更有用。因为在其中，各个自然值有一个自然的“序”关系，因此可以明确的惩罚某些比其他预测值“更加错误”的预测值。

与这个损失函数对应的风险准确说就是平均误差概率，条件风险为

$P(w_{i}|\textbf{x})$是行为$\alpha_{i}$正确的条件概率。这个最小化风险的贝叶斯决策规则要求选择一种能使条件风险最小化的行为，即需要选择$i$使$P(w_{i}|\textbf{x})$最大，也就说，基于最小化误差概率，有

与最小化误差概率条件下的贝叶斯决策规则的规则相同。

图2-3显示相同条件下的似然比$p(\textbf{x}|w_{1})/p(\textbf{x}|w_{2})$，阈值$\theta_{a}$来自同样的先验概率。如果我们对模式属于$w_{2}$却误判为$w_{1}$的惩罚大于模式$w_{1}$却误判为$w_{2}$的情况（即$\lambda_{21}>\lambda_{12}$)，那么可得阈值$theta_{b}$。注意到将模式判决为$w_{1}$的x的取值范围变小了。$R_{i}$表示在其中决定$w_{i}$的输入空间的区域。

 

3、朴素贝叶斯的学习与分类

设输入空间$\chi\subseteq R^{n}$为$n$维向量，输出空间为类标记集合$Y=(c_{1},c_{2},...,c_{K})$。输入向量$x\in \chi$，输出向量$y \in Y$。X是定义在输入空间$\chi$上的随机向量，Y是定义在输出空间$Y$的随机变量。P(X,Y)是X和Y的联合概率分布。训练数据集$T=\{(x_{1},y_{1}),...,(x_{N},y_{N})\}$由P(X,Y)独立同分布产生。

朴素贝叶斯法通过训练数据集学习联合概率分布P(X,Y)。具体的，学习先验概率分布和条件概率分布，分别为下述形式：

$P(Y=c_{k},k=1,2,...,K$

$P(X=x|Y=c_{k})=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_{k}),k=1,2,...,K$

条件概率分布$P(X=x|Y=c_{k})$有指数级数量的参数，其估计不可行。假设$x^{(j)}$可取值有$S_{j}$个，$j=1,2,...,n$，Y取值有K个，那么参数个数为$K \prod_{j=1}^{n}S_{j}$。

朴素贝叶斯法对条件概率分布做出条件独立型的假设，即

$P(X=x|Y=c_{k})=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_{k})=\prod_{j=1}^{n}P(X^{(j)}=x^{(j)}|Y=c_{k}),k=1,2,...,K$

朴素贝叶斯发实际上学习到生成数据的机制，所以属于生成模型。生成学习方法由训练数据学习联合概率分布P(X,Y)，P(X,Y)=P(X|Y)P(Y)，然后求得后验概率分布P(Y|X)。

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

朴素贝叶斯分类器是一种应用基于独立假设的贝叶斯定理的简单概率分类器。线性分类器通过特征的线性组合来做出分类决定的分类器。本质上，朴素贝叶斯分类器是一种线性分类器（注意，只有特定的某些朴素贝叶斯分类器本质上是线性分类器。）。条件独立性假设等于说是适用于分类的特征在类确定的条件下都是条件独立的。

如果假设输入变量之间存在概率依存关系，模型就变成了贝叶斯网络。

对于给定的 输入x，通过学习到的模型计算后验概率分布

$P(Y=c_{k}|X=x)=\frac{P(X=x|Y=c_{k})P(Y=c_{k})}{\sum_{k}P(X=x|Y=c_{k})P(Y=c_{k})}$

朴素贝叶斯分类器可以表示为：

上式中分母对于所有$c_{k}$是相同的，所以

3.1、后验概率最大化(MAP)

朴素贝叶斯法将实例分到后验概率最大的类中。等价于期望风险最小化。

假设选择0-1损失函数（其实前文已有描述）

这个损失函数将0损失赋给一个正确的判决，而将一个单位损失判决给任何一种错误判决，显然这里所有误判都是等代价的。$f(X)$是分类决策函数。期望风险函数为，期望是对联合分布P(X,Y)取的。

$R_{exp}(f)=E[L(Y,f(X))]$

$R_{exp}(f)=E_{X}\sum_{k=1}^{K}[L(c_{k},f(X))]P(c_{k}|X)$

为使期望风险最小化，只需对$X=x$逐个极小化。由此得到

那么，后验概率最大化等价于0-1损失函数时的期望风险最小化。

 3.2 线性分类器的思考(Brilliant!!!)

线性分类器就是通过在高维样本空间中寻找到一组超平面，将样本空间划分为两个（二分类）或者多个区域（多分类）。线性分类器可以参看SVM学习一文。

$y(x)=w^{T}\phi{(x)}+w_{0}$

找到权重向量$w$，使得输入向量$x$和该权值向量$w$的点积成为分类器的准则。如果输出$y>0$，则属于正类。否则，认为是负类。

给定判别函数$g_{i}(x),i=1,2,...,k$的形式，对于所有的$j!=i$，有$g_{i}(x)>g_{j}(x)$，则此分类器将这个特征向量判为类$c_{i}$。此分类器可以视为一个计算k个判别函数并选取与最大判别值对应的类别的网络或机器。

在具有一般风向的情况下，让$g_{i}(\textbf{x})=-R(\alpha_{i}|\textbf{x})$，这是由于最大的判别函数是与最小的条件风险相对应的。在最小误差概率情况下，令$g_{i}(x)=P(y=c_{i}|X=x)$，此时最大判别函数余最大后验概率相对应。

显然，判别函数的选择并不唯一。一般化，将每一个$g_{i}(x)$替换为$f(g_{i}(x))$，其中$f(\cdot)$是一个单调递增函数，分类结果不变。

$g_{i}(x)=P(y=c_{i}|X=x)=\frac{P(X=x|Y=c_{k})P(Y=c_{k})}{\sum_{k}^{c}P(X=x|Y=c_{k})P(Y=c_{k})}$

$g_{i}(x)=P(y=c_{i}|X=x)=P(X=x|Y=c_{k})P(Y=c_{k})$

$g_{i}(x)=lnP(X=x|Y=c_{k})+lnP(Y=c_{k})$

将特征空间分成c个判决区域，$R_{1},R_{2},...R_{c}$。对于所有$j!=i$，有$g_{i}(x)>g_{j}(x)$，则$x\in R_{i}$。此区域由判决边界来分割，其判决边界即判决空间中使判别函数值最大的曲面。

3.2.1、二分类问题

定义一个判别函数$g(x)=g_{1}(x)-g_{2}(x)$，如果$g(x)>0$，则判别为类$c_{1}$；否则，类$c_{2}$。

朴素贝叶斯分类器是建立在属性变量相互独立的基础上，以后验概率为判定准则的分类器。判别输入向量$x=(x_{1},x_{2},...,x_{n})$，若下式成立，则判别为正类。

$p(Y=c_{1})*\prod_{i}^{n}p(X^{(i)}=x_{i}|Y=c_{1})-p(Y=c_{2})*\prod_{i}^{n}p(X^{(i)}x_{i}|Y=c_{2})>0$  (1)

$\sum_{i=1}^{n}[ln p(x_{i}|c_{1})-ln p(x_{i}|c_{2})]>ln p(c_{2})-ln p(c_{1})$   (2)

对于属性值为布尔变量的朴素贝叶斯，令属性值为1或-1，可得

$p(x|c_{1})=\frac{1}{2}[p(1|c_{1})-p(-1|c_{1})]*x+\frac{1}{2}[p(1|c_{1})+p(-1|c_{1})]$  (3)

$p(x|c_{2})=\frac{1}{2}[p(1|c_{2})-p(-1|c_{2})]*x+\frac{1}{2}[p(1|c_{2})+p(-1|c_{2})]$   (4)

所以可得$p(x|c_{1})-p(x|c_{2})=\frac{1}{2}[p(1|c_{1})-p(-1|c_{1})-p(1|c_{2})+p(-1|c_{2})]*x+\frac{1}{2}[p(1|c_{1})+p(-1|c_{1})-p(1|c_{2})-p(-1|c_{2})]$

从而(2)式可转换为$\sum_{i=1}^{n}\frac{1}{2}[p(1|c_{1})-p(-1|c_{1})-p(1|c_{2})+p(-1|c_{2})]*x_{i}+\sum_{i}^{n}\frac{1}{2}[p(1|c_{1})+p(-1|c_{1})-p(1|c_{2})-p(-1|c_{2})]>ln p(c_{2})-ln p(c_{1})$    (5)

令$w_{i}=\frac{1}{2}[p(1|c_{1})-p(-1|c_{1})-p(1|c_{2})+p(-1|c_{2})]$   (6)

$w_{0}=\sum_{i}^{n}\frac{1}{2}[p(1|c_{1})+p(-1|c_{1})-p(1|c_{2})-p(-1|c_{2})]-ln p(c_{2})+ln p(c_{1})$  (7)

得到$\vec{x}*\vec{w}+w_{o}>0$  (8)

属性值为布尔变量的朴素贝叶斯分类器本质上找到了权值向量w,使得输入向量x和该权值向量w的点积成为分类器的准则。即，属性值为布尔变量的朴素贝叶斯分类器本质上是线性分类器。为什么只说本质上是线性分类器，而不说是线性分类器呢？主要原因是，朴素贝叶斯分类器并没有显式地求出权值向量w，只是其判别准则（不等式(1)）本质上可以看成输入向量x和权值向量w的点积（不等式(8)）。

 

 

待消化

不等式20表明普通的高斯朴素贝叶斯分类器并不是线性分类器(判别不等式与xi的二次方有关)。

 

 

 

我们不妨先看看朴素贝叶斯的假设。首先大家都知道的一个点就是词之间没有强相关性的假设。其实还有一个假设，可以理解为朴素贝叶斯在训练过程中淡化了文档的概念。在训练集上，朴素贝叶斯的训练数据最后是以类标-词的结构存储了不同的词在不同类标下的频率。
从概率图模型上，我们思考一下这个训练数据的产生过程。已两个类，6个词为例。
事实上数据的产生是通过一下步骤重复后产生的。
1，拿起一枚正反面不均匀的硬币，抛出，正面则取正面对应的一枚骰子，反之取另一枚骰子。
2，抛骰子，那个面朝上对应的单词频次+1。
事实上这个过程可以发现，模型本身需要知道的是硬币的正面概率，和两枚骰子的每个面的概率。因此朴素贝叶斯训练时要求解的参数也是这两块:类别的可能和每个类别单词出现的可能。
我们回顾一下《统计学习方法》上朴素贝叶斯的习题。第一题是MLE，第二题是贝叶斯估计。

MLE，相对来说就比较简单了，事实上数据生成的过程表明其实是服从多项式分布的。不过注意在求解MLE时要考虑到，每个类出现的可能和为1，每个类对应的骰子出现的概率和为1.通过拉格朗日乘子即可求解。
贝叶斯估计，如果看过PRML或者有概率统计基础应该就会知道，多项式分布的共轭分布式狄利克雷分布，因此只需要对狄利克雷分布做期望计算（分部积分）即可。而第二题的情况（拉普拉斯平滑），先验是都是1的狄利克雷分布。

 

参考资料：

1）Duda 《模式分类》

2）http://ask.julyedu.com/article/82

3）http://www.rustle.us/?p=173

4）李航  《统计学习方法》

5）http://cs.nyu.edu/faculty/davise/ai/linearSeparator.html   英文版出处

 

附录：

算法