DanWang Blog

贝叶斯分类器

内容来自于《机器学习》

贝叶斯决策论

贝叶斯决策论是概率框架下实施决策的基本方法。对分类任务来说，在所有相关概率都是已知的理想情形下，贝叶斯决策论考虑如何基于这些概率和午盘损失来选择最优的类别标记。

假设有N种可能的类别标记，即Y={c1,c2,…,cN},lambdaij是将一个真实标记为cj的阉割版误分类为ci的损失。基于后验概率P（ci x）可获得将样本x分类为ci所产生的期望损失，即在样本x上的条件风险。

任务是寻找一个判定准则：最小化总体风险

显然对于每个样本x，若h能最小化风险R(h(x) x)，则总体风险R(h)也将被最小化，这就产生了贝叶斯判定准则：为最小化总体风险，只需要在每个样本上选择那个能使条件风险R(c x)最小的类别标记，即：

此时h称为贝叶斯最优分类器（Bayes optimal classifier），与之对应的总体风险R(h)称为贝叶斯风险，1-R(h*)反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

若目标是最小化分类错误率，误判损失lambdaij可以写为：

此时条件风险

最小化分类错误率的贝叶斯最优分类器为：

对每个样本x，选择能使后验概率P(c x)最大的类别标记。
要获取后验概率P(c x)，大体来说，主要有两种策略：给定x，可以通过直接建模P(c x)来预测c，这样得到的是判别式模型（discriminative models）;
也可以先对联合概率分布P(x,c)建模，然后再由此获得P(c x)，这样得到的是生成式模型（generative models）。显然，前面介绍的决策树、BP神经网络、支持向量机等，都可归入判别式模型的范畴。

对于生成式模型来说，必然考虑：

基于贝叶斯定理，也可以写为：

其中P(c)是类先验概率，P(x c)是样本相对于类标记c的类条件概率(class-conditional probability)，或者称为 似然。

极大似然估计

概率模型的训练过程就是参数估计过程。对于参数估计，统计学界的两个学派分别提供了不同的解决方案：频率主义学派认为参数虽然未知，但却是客观存在的固定值，因此，可以通过优化似然函数等准则来确定参数值，贝叶斯学派则认为参数是未观察到的随机变量，其本身也可有分布，因此，可以假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。

源自频率注意学派的极大似然估计（Maximum Likelihood Estimation，MLE），这是根据数据采样来估计概率分布参数的经典的方法。

朴素贝叶斯分类器

朴素贝叶斯分类器采用了属性条件独立性假设(attribute conditional independence assumption)：对已知类别，假设所有属性相互独立，换言之，假设每个属性独立地对分类结果发生影响。

基于属性条件独立性假设：

其中d为属性数目，xi为x在第i个属性上的取值。

对于所有类别来说，P(x)相同，因此贝叶斯判定准则：

这是朴素贝叶斯分类器的表达式。

显然，朴素贝叶斯分类器的训练过程就是基于训练集D来估计类先验概率P(c)，并为每个属性估计条件概率P(xi c).

另Dc表示训练集D中c类样本组成的集合，若有充足的独立同分布样本，则了很容易地估计出类先验概率：

对离散属性而言，令Dc,xi表示Dc中在第i个属性上取值为xi的样本组成的集合，则条件概率可以估计为：

对连续属性可考虑概率密度函数：

需要注意的是，若某个属性值在训练集中没有与某个类别同时出现过，则直接进行概率估计，会出现为0的情况，导致最终结果为0.

为了避免其他属性携带的信息被训练集中未出现的属性值抹去，在估计概率值时通常要进行平滑，常用拉普拉斯修正（laplacian correction）。具体来说，令N表示训练集D中可能的类别数,Ni表示第i个属性可能的取值数：

显然拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值。

在现实任务中朴素贝叶斯分类器有多种使用方式，例如当任务对预测速率较高，则对给定训练集，可以将朴素贝叶斯分类器涉及的所有概率估值实现计算好存储起来，这样在进行预测时只需要“查表”即可进行判别，若任务数据更替频繁，则可采用懒惰学习方式。先不进行任务训练，待收到预测请求时再根据当前数据集进行概率估值，若数据不断增加，则可在现有估值的基础上，仅对新增样本属性值所涉及的概率估值进行计数修正即可实现增量学习。

半朴素贝叶斯分类器

为了降低贝叶斯中估计后验概率的困难，朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中，这个假设往往很难成立，浴室，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类成为“半朴素贝叶斯分类器” 的学习方法。

半朴素贝叶斯分类器的基本相符是适当考虑一部分属性间的相互依赖信息，从而既不需要进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。读依赖估计（One Dependent Estimator,ODE）是半朴素贝叶斯分类器最常用的一种策略。所谓读依赖就是假设每个属性在类别之外最多仅依赖于一个其他属性，即：

其中pai为属性xi所依赖的属性，成为xi的福属性。此时，对每个属性xi，如果父属性pai已知，则可以估计概率值P(xi, c,pai)，于是，问题的关键就转化为如何确定每个属性的福属性，不同的做法产生不同的独依赖分类器。

最直接的做法是假设所有属性都依赖于同一个属性，成为“超父”，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE（super-parent ODE）方法。

TAN（Tree Augmented naive Bayes）则是在最大带权生成树(maximum weighted spanning tree)算法的基础上，通过以下步骤将属性间依赖关系约简为属性结构：

（1）计算任意两个属性之间的条件互信息（conditional mutual information）

（2）以属性为结点构建完全图，任意两个结点之间边的权重设为I(xi,xj y)；

（3）构建此完全图的最大带权生成树，挑选根变量，将边置位有向；

（4）加入类别结点y，增加从y到每个属性的有向边

条件互信息I(xi,xj y)刻画了属性xi和xj在已知类别情况下的相关性，因此，通过最大生成树算法，TAN实际上保留了强相关属性之间的依赖性。

AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制、更为强大的依赖分类器。与SPODE通过模型选择确定那些超父属性不同，AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果，即：

Dxi是在第i个属性上取值为xi的样本集合，m’为阈值常数：

其中Ni是第i个属性可能的取值数，Dc,xi是类别为c且在第i个属性上取值为xi的样本集合，Dc,xi,xj是类别为c且在第i个属性和第j个属性上分别取值为xi和xj的样本集合。

不难看出，与朴素贝叶斯分类器类似，AODE的训练过程也是计数，即在训练数据集上对符合条件的样本进行计数的过程。与朴素贝叶斯分类器相似，AODE无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方法在预测时在进行计数并且易于实现增量学习。

贝叶斯网

贝叶斯网亦称为信念网，借助有向无环图（Directed Acyclic Graph，DAG）来刻画属性之间的依赖关系，并使用条件概率表（Conditional Probability Table，CPT）来描述属性的联合概率分布。

一个贝叶斯网B由结构G和参数theta两部分构成，即B=<G,theta>，网络结构G是一个有向无环图，其每个结点对应于一个属性若两个属性有直接依赖关系，则它们由一条边连接起来，参数theta定量描述这种依赖关系，假设属性xi在G中的父结点集为πi，则theta包含了每个属性的条件概率为表示：

贝叶斯网络结构有效表达了属性间的条件独立性。给定父结点集，贝叶斯网假设每个属性与它的非后裔属性独立，于是B=<G,theta>将属性x1,x2,…,xd的联合概率分布定义为：

在同父结构中，给定父结点x1的取值，则x3与x4条件独立。在顺序结构中，给定x的值，则y与z条件独立。V型结构亦称为冲撞结构，给定x4的取值，x1与x2必不独立，若x4的取值完全未知，则v型结构下x1与x2确实相互独立的。这样的独立性称为边际独立性（marginal independence）,记为：

为了分析有向图中变量间的条件独立性，可使用“有向分离”，现在有向图转变为一个无向图：

由此产生的无向图成为道德图，令父结点相连接的过程成为道德化。

现实应用中我们往往并不知道网络结构，于是贝叶斯网学习的首要任务就是根据训练数据集来找出结构最恰当的贝叶斯网。“评分搜索”是求解这一问题的常用方法。具体来说，先定义一个评分函数，以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。显然，评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好。

常用的评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需字节的长度。对于贝叶斯网学习而言，模型就是一个贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码。于是我们应该选择哪个综合编码长度（包括描述网络和编码数据）最短的贝叶斯网。这就是最小描述长度（Minimal Description Length, MDL）准则。

通过已知变量观测值来推测带查询变量的过程称为推断，已知变量观测值称为“证据”。

最理想是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但是这样的精确推断，已经被证明是NP难的，换言之，当网络节点较多、连接稠密时，难以进行精确推断，此时，需要借助近似推断，通过降低精度要求，在有限时间内求得近似解。通过降低精度要求，在有限时间内求得近似解，在现实应用中，贝叶斯网的近似推断常使用吉布斯采样（Gibbs sampling）来完成，这是一种随机采样方法。

EM 算法

现实任务中，有些属性值是无法观测到的。

未观测变量的学名是隐变量（latent variable）.令X表示已观测变量集，Z表示隐变量集，theta表示模型参数，若欲对theta做极大似然估计，应该最大化对数似然。

然而由于Z是隐变量，上式无法直接求解，此时我们可以通过对Z计算期望，来最大化已观测数据的对数 边际似然。

EM（Expectation-Maximization）算法是最常用的估计参数隐变量的丽日，它是一种迭代式的方法，其基本想法是：若参数theta一直，则可以根据训练数据推断出最优隐变量Z的值（E步），反之，若Z的值一直，就可以方便地对参数theta做极大似然估计。