贝叶斯分类器

贝叶斯决策理论

假设有N种可能的类别标记,即$y={c_1,c_2,…,c_N}$,$\lambda_{ij}$是将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失,基于后验概率$P(c_i|x)$可获得将样本x分类为$c_i$所产生的期望损失，即在样本x上的“条件风险”

$R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x)$

我们的任务是寻找一个判定准则h:X——>y以最小化总体风险

$R(h)=E_x[R(h(x)|x)]$

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

$h^* (x)=argmax_{c∈y}R(c|x)$

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

不难看出，欲使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率P(c|x)。然而，在现实任务中这通常难以直接获得.从这个角度来看，机器学习所要实现的是基于有限的样本集尽可能准确地估计出后验概率P(c|x).
总体来说，主要有两种策略,给定x,可通过直接建模P(c|x)来预测c,这样得到的是判别式模型；也可以先对联合概率分布P(x,c)建模,然后再由此获得P(c|x),这样得到的是”生成式模型”
对于声称是模型来说，必然考虑

$P(c|x)=\frac{P(x,c)}{P(x)}$

基于贝叶斯定理,P(c|x)可写为

$P(c|x)=\frac{P(c)P(x|c)}{P(x)}$

其中，P(c)是类”先验”概率;P(x|c)是样本x相对于类标记c的类条件概率，或称为”似然”，P(x)是用于归一化的”证据”因子.

对于类条件概率P(x|c)来说,由于它涉及关于x所有属性的联合概率，直接根据样本出现的频率来估计将会遇到严重的困难。例如，假设样本的d个属性都是2值得，则样本空间将有$2^d$种可能的取值，在现实应用中，这个值往往远大于训练样本数m，也就是说，很多样本取值在训练集中根本没有出现，直接使用频率来估计P(x|c)显然不可行,因为”未被观察到”与”出现概率为0”通常是不同的。

极大似然估计

估计类条件概率的一种常用策略是先假定其具有某种确定的概率分部形式,再基于训练模型对概率分布的参数进行估计.具体地,记关于类别c的类条件概率为P(x|c),假设P(x|c)具有确定的形式并且被参数向量$\theta_c$唯一确定，则我们的任务就是利用训练集D估计参数$\theta_c$.为明确起见,我们将P(x|c)记$P(x|\theta_c)$

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

本节介绍源自频率主义学派的极大似然估计
令$D_c$表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的则参数$\theta_c$对于数据集$D_c$的似然是

$P(D_c|\theta_c)=\prod_{x∈D_c}P(x|\theta_c)$

寻找能使上式最大化的参数值$\hat{\theta}_c$

朴素贝叶斯

基于贝叶斯公式来估计后验概率P(c|x)的主要困难在于:类条件概率P(x|c)是所有属性上的联合概率，难以从有限的训练样本中直接估计而得。为了避开这个障碍，朴素贝叶斯分类器采用了”属性条件独立性假设”:对已知类别,假设所有属性相互独立。换言之，假设每个属性独立地对分类结果产生影响

$P(c|x)=\frac{P(c)P(x|c)}{P(x)}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)$

半朴素贝叶斯分类器

为了降低贝叶斯公式中估计后验概率P(c|x)的困难,朴素贝叶斯分类器采用了属性条件独立性假设，但再现实任务中这个假设往往很难成立.于是,人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为”半朴素贝叶斯分类器”的学习方法。

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

$P(c|x)正比于P(c)\prod_{i=1}^dP(x_i|c,pa_i)$

其中$pa_i$为属性x_i所依赖的属性,称为$x_i$的父属性.此时，对每个属性$x_i$若其父属性$pa_i$已知,则可先估计出概率值$P(x_i|c,pa_i)$.于是,问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器

SPODE

TAN

AODE

贝叶斯网

贝叶斯网亦称”信念网”,它借助有向无环图(DAG)来刻画属性之间的依赖关系，并使用条件概率表(CPT)来描述属性的联合概率分布

具体来说，一个贝叶斯网B由结构G和参数$\theta$两部分组成,即$B=$.网络结构G是一个有向无环图,其每个结点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来;参数$\theta$定理描述这种依赖关系，假设属性$x_i$在G中的父结点集为$\pi_i$，则$\theta$包含了每个属性的条件概率表$\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)$

结构

贝叶斯网结构有效地表达了属性间地条件独立性。给定父结点集,贝叶斯网假设每个属性与它地非后裔属性独立,于是$B=$将属性$x_1,x_2,…,x_d$的联合概率分布为

$P_B(x_1,x_2,...,x_d)=\prod_{i=1}^dP_B(x_i|\pi_i)=\prod_{i=1}^d\theta_{x_i|\pi_i}$

三个变量之间的典型依赖关系
1.同父结构
Bayes1
联合概率分布:P(a,b,c)=P(c)·P(a|c)·P(b|c)
1)c作为条件已知:
可得P(a,b|c)=P(a|c)·P(b|c)所以a和b条件独立
2)c未知
联合概率分布两边同时对c积分，得$P(a,b)=\sum_cP(c)·P(a|c)·P(b|c)$

2.V型结构:
Bayes2
联合概率分布:P(a,b,c)=P(a)·P(b)·P(c|a,b)
1）c作为条件已知:
联合概率分布两边同时对变量c积分,P(a,b)=P(a)·P(b),所以a,b相互独立
2)c未知
易得$P(a,b|c)=\frac{P(a)·P(b)·P(c|a,b)}{P(c)}$,不能分解成P(a|c)·P(b|c),所以a和b不条件独立.
但是P(a,b)=\sum_cP(a)P(b)P(c|a,b)=P(a)P(b),a与b是独立的。

3.顺序结构:
Bayes3
联合概率分布:P(a,b,c)=P(a)·P(c|a)·P(b|c)
1)c作为条件已知:
可得P(a,b|c)=P(a|c)P(b|c,a)=P(a|c)P(b|c)所以a,b条件独立
2)c未知
联合概率分布两边同时对c积分,可得$P(a,b)=P(a)·\sum_cP(c|a)·P(b|c)=P(a)·P(b|a)$所以a和b不独立

为了分析有向图中变量间的条件独立性,可使用”有向分离”，我们先把有向图转变为一个无向图：

找出有向图中的所有V型结构，在V型结构的两个父结点之间加上一条无向边;
将所有有向边改为无向边

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

基于道德图能直观、迅速地找到变量间地条件独立性.假定道德图中有变量x，y和变量集合$z={z_i}$若变量x和y之间能在图上被z分开,即从道德图中将变量集合z去除后,x和y分属两个连通分支,则称x和y倍z有向分离,x⊥y|z成立.

学习

若网络结构已知,即属性间地依赖关系已知,则贝叶斯网地学习过程相对简单,只需对训练样本”计数”，估计出每个结点的条件概率表即可.但在现实应用中,我们往往并不知晓网络结构,于是贝叶斯网络学习的首要任务就是根据训练数据集来找出结构最”恰当”的贝叶斯网。“评分搜索”是求解这一个问题的常用方法。

具体来说，我们先定义一个评分函数，以此来评估贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网.显然，评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好

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

给定训练集$D={x_1,x_2,…x_m}$,贝叶斯网$B=$在D上的评分函数可写为

$s(B|D)=f(\theta)|B|-LL(B|D)$

其中，|B|是贝叶斯网的参数个数;$f(\theta)$表示描述每个参数$\theta$所需的字节数;而

$LL(B|D)=\sum_{i=1}^mlogP_B(x_i)$

是贝叶斯网B的对数似然.这样将学习任务转化为一个优化任务，寻找一个贝叶斯网B使评分函数s(B|D)最小。

从所有可能的网络结构空间搜索最优贝叶斯网络结构是一个NP难,难以快速求解。有两种常用的策略能在有限时间内求得近似解:第一种是贪心法；第二种是通过给网络结构施加约束来削减搜索空间。

推断

贝叶斯网络训练好之后就能回答”查询”，即通过一些属性变量的观测值来推测其他属性变量的取值。若我们观测到西瓜色泽青绿、敲声浊响、根蒂蜷缩，想得知它是否成熟、甜度如何。这样通过已知变量观测值来推测待查询变量的过程称为”推断”，已知变量观测值称为”证据”.
最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验，不幸的是，这样的“精确推断”已被证明是NP难的；换言之，当网络节点较多、连接稠密时，难以进行精确推断，此时需借助”近似推断”,通过降低精度要求，在有限时间内求得近似解.在现实应用中,贝叶斯网的近似推断常使用吉布斯采样来完成，这是一种随机采样方法。

总结

根据对属性间依赖的涉及程度，贝叶斯分类器形成了一个”谱”：朴素贝叶斯分类器不考虑属性间依赖性，贝叶斯网能表示任意属性间的依赖性，二者分别位于谱的两端；介于两者之间的则是一些列半朴素贝叶斯分类器，它们基于各种假设和约束来对属性间的部份依赖进行建模。

贝叶斯分类器与一般意义上的“贝叶斯学习”有显著区别，前者通过最大后验概率进行单点估计，后者则是进行分布估计。

贝叶斯网络为不确定学习和推断提供了基本框架，隐其强大的表示能力，良好的可解释性而广受关注。贝叶斯网学习可分为结构学习和参数学习两部分。参数学习通常较为简单，而结构学习则被证明是NP难问题。贝叶斯网通常被看成生成模型。