第七章|第七章贝叶斯分类器第七章贝叶斯分类器

贝叶斯分类器是一类分类算法的总称，是各种分类器中分类错误概率最小的分类器，而贝叶斯定理是这类算法的核心。
贝叶斯决策论贝叶斯决策论是概率框架下实施决策的基本方法，而贝叶斯分类器的理论框架基于贝叶斯决策论。对于分类任务，在所有相关概率都已知的情况下，贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。
在解释其基本原理之前，再次了解一下何为先验概率、条件概率和后验概率。
先验概率：根据以往的经验和分析得到的概率，也即根据客观事实和统计频率得出的概率；
条件概率：在某种条件下某件事发生的概率；
后验概率：事件已经发生，而要得到这件事情发生的原因是某个因素引起的可能性，即由结果推原因。
对于二者，举个例子：
假设出不了门有以下两种原因：
1、脚崴了
2、要学习
先验概率：求出不了门的概率；
后验概率：求已经确定出不了门，是因为脚崴了的概率；
条件概率：求已知脚崴了的条件下，出不了门的概率。
贝叶斯判定准则：决策目标是最小化总体风险，即分类器错误率，于是要对每个样本x选择使得后验概率P(c|x)最大的类别标记（即使条件风险R(c|x)最小的类别标记）
贝叶斯分类器使用生成式模型的策略（朴素贝叶斯），而前面提到的决策树、BP神经网络、支持向量机等属于判别式模型
生成式模型：即对联合概率分布P(x,c)先建立模型，再得到P(c|x)
判别式模型：即是给定了x，然后建立模型P(c|x)来预测c
回到贝叶斯定理（考虑生成式模型以及基于贝叶斯定理）:

该式子将求后验概率转化为求先验概率P(c)和条件概率P(x|c)。
那么如何求得P(c)和P(x|c)？

对于类先验概率P(c)，其表示样本空间中各类样本所占比例，根据大数定律，当训练集包含了足够的独立同分布的样本时，可通过各类样本出现的概率进行估计；
对于类条件概率P(x|c)，其参数估计方法是极大似然函数。因其涉及关于x所有属性的联合概率，难以直接根据样本出现的概率来进行估计，例如有d个属性，其属性值皆为二值，于是样本空间有种可能取值，显然这个数量往往是大于训练样本的。这就造成了许多的样本取值在训练集中不会出现，不能用来直接估计P(x|c)（“未被观测到”与“出现概率为零”通常是不同的）。对于这种情况，估计类条件概率的一种常用策略是先假定具有某种确定的概率分部形式，再基于训练样本对概率分布的参数进行估计。

极大似然估计

极大似然估计：采用极大似然估计来根据数据采样来估计概率分布参数，极大似然估计是对类条件概率的分布形式进行假设，然后通过计算来对概率分布参数进行近似的方法，其是在对联合概率上的求解。

朴素贝叶斯分类器（样本属性条件独立时的P(x|c)求解）朴素贝叶斯分类器采用了“属性条件独立性假设”：对已知类别，假设所有属性间相互独立，以避开联合概率这个障碍。换而言之，假设每个属性独立地对分类结果发生影响。
因此类条件概率可表示：

其中d为属性数目，是x在第i个属性上的取值。
显然，朴素贝叶斯分类器的训练过程就是基于训练集D来估计类先验概率，并为每个属性估计类条件概率。
令表示训练集D中第c类样本组合成的集合，令表示中在第i个属性上取值为的样本组成的集合，如果有足够的独立同分布样本，则可以估计出类先验概率和条件概率：

在属性条件独立假设下，类条件概率表示每个单独属性的概率的乘积，当其中任意一个属性的概率为0时（即某个属性值在训练集中没有出现于某个类同时出现过），会导致总的类条件概率 P( x | c ) 为0，这显然不符合我们的所求。为了避免其他属性携带的信息被训练集未出现的属性值抹去，在估计概率值时，通常要进行平滑，通常用"拉普拉斯修正"。
拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题。具体为：
N表示D中可能的类别数，令表示第i个属性可能的取值，则上式中可修正为：

半朴素贝叶斯分类器（样本属性独依赖时的 P( x | c ) 求解）对于朴素贝叶斯，其有一个属性条件独立的假设基础，这在现实任务中显然很难成立，于是人们对朴素贝叶斯的假设进行一定的放松，从而产生了“半朴素贝叶斯分类器”的学习方法。
其中，半朴素贝叶斯学习器最常用的一种策略是独依赖估计，即假设每个属性在类别之外最多仅依赖于一个其它属性。此时，类条件概率：

其中是属性所依赖的属性，即为其父属性。对每个属性，若其父属性已知，则可采用类似拉普拉斯修正的方法来估计概率值
那么如何确定每个属性的父属性？做法不同产生不同的依赖分类器：
1、SPODE方法，让所有属性都依赖于同一属性；
2、TAN方法在最大带权生成树算法的基础上构建依赖；
3、AODE方法基于集成学习机制，将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支持的SPODE集成起来作为最终结果。
随着依赖属性数量增多，准确估计所需的训练样本数将以指数增加。因此，若训练数据非常充分，泛化性能有可能提升；但在有限样本条件下，则又会陷入估计高阶联合概率的泥沼。
贝叶斯网贝叶斯网亦称“信念网”，它借助有向图来刻画属性之间的依赖关系，并使用条件概率表来描述属性的联合概率分布。
一个贝叶斯网B由结构G和参数Θ两部分构成，即B= ，网络结构G是一个有向无环图，其每个结点对应于一个属性，若两个属性有直接依赖关系，则他们由一条边连接起来，即一条边表示一个直接依赖关系；参数Θ定量描述这种依赖关系，其包含了每个属性的条件概率表。
结构贝叶斯网假设每个属性与其非后裔属性独立，则B= 将属性的联合概率分布定义为：

即每个具体属性在其父结点集下的条件概率的乘积。

第七章|第七章贝叶斯分类器

文章图片
学习贝叶斯网的学习过程只需要对训练样本进行计数，估计出每个结点的条件概率表即可。但由于现实应用中我们往往不知晓网络结构，于是贝叶斯学习的首要任务就是要根据训练数据集找出结构最恰当的贝叶斯网。具体操作是先定义一个评分函数，以此评估贝叶斯网与训练数据的契合程度，然后基于这个函数来寻找结构最优的贝叶斯网。但是从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，就是在NP-C问题(NP完全问题)中不需要满足它是一个NP问题这一定义而满足定义所有的NP问题都可以约化到它。（即所有的NP问题都能约化到它，但是他不一定是一个NP问题）
题外话，既然提到了NP-C问题，就列一下七大千僖难题：

“千僖难题”之一：P （确定性多项式算法）对NP （非确定性多项式算法）
“千僖难题”之二：霍奇（Hodge）猜想
“千僖难题”之三：庞加莱（Poincare）猜想
“千僖难题”之四：黎曼（Riemann）假设
“千僖难题”之五：杨－米尔斯（Yang-Mills）存在性和质量缺口
“千僖难题”之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性
“千僖难题”之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton-Dyer）猜想

回到从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，无法快速求解。于是有两种常用策略能在有限时间内求得近似解：
1、贪心法，例如从某个网络结构出发，每次调整一条边，直到评分函数不下降为止；
2、通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构等等。
推断训练好贝叶斯网后就可以用来回答“查询”，即通过一些属性变量的观测值来推测其它属性变量的取值。最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但是这样的推断也是NP-hard的，所以要借助“近似推断”，来降低精度需要，在有限时间内求得近似解。贝叶斯网的近似推断常用吉布斯采样（一种随机采样方法）来完成。
其工作过程：
令表示待查询变量，为证据变量，其取值为.目标是计算后验概率,其中是待查询变量的一组取值。
即判断在属性Q上会出现取值q的概率是多少。
于是运用贝叶斯网和吉布斯采样的整个推断过程大致如下：
1、对Q进行随机取值以产生一个与证据E=e一致的在属性Q上的初始状态 ;
2、将当前属性Q上的取值与e结合起来，用贝叶斯网去推断下一时刻属性Q上的取值；
3、若新生成的Q与我们要进行预测的q一致，则计数器n加一；
4、重复上面3个步骤次，然后计算可以近似得到的值。
上述步骤即吉布斯采样算法：

第七章|第七章贝叶斯分类器

文章图片

EM算法在上面，我们一直假设训练样本的所有属性值都被观测到，但在现实情况中，我们会遇到不完整的训练样本（缺失值），即存在未观测的变量，所有对概率分布的概率似然估计便无法进行。
EM算法（迭代）是常常用来的估计参数隐变量的，其使用两个步骤交替计算：
1、期望步：利用当前估计的参数值来计算对数似然的期望值（求隐变量的期望）；
2、最大化步：寻找能使期望步产生的似然期望最大化的参数值（寻找参数最大似然估计），然后新的到的参数值重新被用于期望步，直到收敛到局部最优解。
【第七章|第七章贝叶斯分类器】参考阅读：
贝叶斯分类器