机器学习(周志华)第7章贝叶斯分类器

周志华先生《机器学习》一书学习笔记
记录学习过程
本博客记录Chapter7

1 贝叶斯决策论

假设有N种可能的类别标记,即Y%3D%5C%7Bc_1%2Cc_2%2C%E2%80%A6%2Cc_N%5C%7D%5Clambda_%7Bij%7D是将一个真实标记为c_j的样本误分类到c_i的损失。基于后验概率P%28c_i%7C%5Cbold%20x%29可获得将样本%5Cbold%20x误分类到c_i所产生的期望损失(expected loss),即在样本%5Cbold%20x上的“条件风险”(conditional risk)(P%28c_j%7C%5Cbold%20x%29:表示样本%5Cbold%20xc_j的概率):
R%28c_i%7C%5Cbold%20x%29%3D%5Csum_%7Bj%3D1%7D%5EN%5Clambda_%7Bij%7DP%28c_j%7C%5Cbold%20x%29
我们的任务是找到一个判别标准h%3A%5Cchi%20%5Cmapsto%20Y来最小化整体风险:
R%28h%29%3DE_X%5BR%28h%28%5Cbold%20x%29%7C%5Cbold%20x%29%5D
显然,对于每一个样本%5Cbold%20x,若h能最小化条件风险R%28h%28%5Cbold%20x%29%7C%5Cbold%20x%29,则总体风险R%28h%29就能最小化。这体现了贝叶斯判定准则(Bayes decision rule):为最小化总体风险,只需要在每个样本上选择哪个能使条件风险R%28c%7C%5Cbold%20x%29最小的类别标记:
h%5E%2A%28%5Cbold%20x%29%20%3D%20%5Cmathop%7B%5Carg%5Cmin%7D_%7Bc%20%5Cin%20Y%7D%5Cspace%20R%28c%7C%5Cbold%20x%29
此时,h%5E%2A被称为贝叶斯最优分类器(Bayes optimal classifier),与之对应的总体风险R%28h%5E%2A%29对应贝叶斯风险(Bayes risk)。1-R%28h%5E%2A%29反映了分类器所能达到的最好性能。

+++

如果预期损失%5Clambda_%7Bij%7D满足:
%5Clambda_%7Bij%7D%3D%5Cbegin%7Bcases%7D%200%2C%5Cspace%5Cspace%5Cspace%20if%20%5Cspace%5Cspace%20i%3Dj%5C%5C%201%2C%5Cspace%5Cspace%5Cspace%20otherwise%20%5Cend%7Bcases%7D
此时有条件风险R%28c%7C%5Cbold%20x%29%3D1-P%28c%7C%5Cbold%20x%29

然后,最小化分类错误率的贝叶斯最优分类器:
h%5E%2A%28%5Cbold%20x%29%3D%5Cmathop%7B%5Carg%5Cmin%7D_%7Bc%5Cin%20Y%7D%5Cspace%20P%28c%7C%5Cbold%20x%29
即选择具有最大后验概率P%28c%7C%5Cbold%20x%29的类标签。

+++

不难看出,为了使用贝叶斯准则来最小化决策风险,第一步是获得后验概率P%28c%7Cx%29。然而,这通常很难在现实世界的任务中直接获得。从这个角度来看,机器学习想要实现的是基于有限的训练样本集,尽可能准确地估计后验概率P%28c%7C%20x%29。从广义上讲,主要有两种策略:

  • 给定x,可通过直接建模P%28c%7C%20x%29来预测c,这样得到的是“判别式模型”(discriminativemodels)
  • 也可先对联合概率分布P%28x%2Cc%29建模,然后再由此获得P%28c%20%7C%20x%29,这样得到的是“生成式模型’(generative models)

显然,前面介绍的决策树、BP神经网络、支持向量机等,都可归入判别式模型的范畴。对生成式模型来说,必然考虑
P%28c%7Cx%29%3D%5Cfrac%7BP%28x%2Cc%29%7D%7BP%28x%29%7D%3D%5Cfrac%7BP%28x%7Cc%29P%28c%29%7D%7BP%28x%29%7D
其中,P%28c%29是先验(prior)概率,P%28x%7Cc%29是样本x对于类标记c的类条件概率,或称为似然(likelihood);P%28x%29是用于归一化的证据因子(evidence)。对于给定样本,证据因子和类标记无关,因此估计P%28c%7Cx%29的问题就转化为如何基于训练数据D估计先验P%28c%29和似然P%28x%7Cc%29。根据大数定理,P%28c%29可以用各类样本出现的频率来进行估计;对于类条件概率P%28x%7Cc%29来说,由于其涉及关于x所有属性的联合概率,直接根据样本出现频率来估计会遭到严重困难。

2 极大似然估计

假设P%28x%7Cc%29有一个确定的形式并且由参数%5Ctheta_c唯一确定,我们的任务是使用训练集D估计参数%5Ctheta_c

事实上,概率模型训练过程就是参数估计(parameter estimation)。对于参数训练过程,有频率学主义学派和贝叶斯学派。前者认为参数虽然未知,但是是客观存在的固定值,可以优化似然函数来确定参数;后者认为参数是未观察到的随机变量,其本身可以有分布,因此可以假定参数服从一个先验分布,然后基于观测到的数据来计算参数的后验分布。

这一节我们采用频率主义学派的极大似然估计(MLE)方法:
LL%28%5Ctheta_c%29%3D%5Clog%20P%28D_c%7C%5Ctheta_c%29%3D%5Csum_%7Bx%5Cin%20D_c%7D%5Clog%20P%28x%7C%5Ctheta_c%29
此时参数%5Ctheta_c的最大似然估计为%5Chat%20%7B%5Ctheta_c%7D
%5Chat%20%5Ctheta_c%20%3D%20%5Cmathop%7B%5Carg%20%5Cmax%7D_%7B%5Ctheta_c%7D%5Cspace%20LL%28%5Ctheta_c%29
需要注意的是,虽然这种参数化方法可以使类条件概率估计相对简单,但估计结果的准确性在很大程度上取决于假设的概率分布形式是否符合底层的真实数据分布。在实际应用中,为了做出能够更好地逼近潜在真实分布的假设,往往需要在一定程度上利用应用任务本身的经验知识。误导性的结果。

3 朴素贝叶斯分类器

朴素贝叶斯分类器(naive Bayes classifier)采用了“属性条件独立性假设”,即假设对已知的类别,所有的属性相互独立。因此,后验概率可以写为:
P%28c%7Cx%29%3D%5Cfrac%7BP%28x%7Cc%29P%28c%29%7D%7BP%28x%29%7D%3D%5Cfrac%7BP%28c%29%7D%7BP%28x%29%7D%5Cprod_%7Bi%3D1%7D%5EdP%28x_i%7Cc%29
其中,d为属性个数,即x的维度。

由于P%28x%29对于所有类都相同,因此贝叶斯准则为:
h_%7Bnb%7D%28x%29%3D%5Cmathop%7B%5Carg%5Cmax%7D_%7Bc%5Cin%20Y%7D%20%5Cspace%20P%28c%29%5Cprod_%7Bi%3D1%7D%5EdP%28x_i%7Cc%29
朴素贝叶斯的训练过程是根据训练集D估计类先验概率P%28c%29,估计每个属性的条件概率P%28x_i%7Cc%29。在
P%28c%29%3D%5Cfrac%7B%7CD_C%7C%7D%7B%7CD%7C%7D%5C%5C%20P%28x_i%7Cc%29%3D%5Cfrac%7B%7CD_%7Bc%2Cx_i%7C%7D%7D%7B%7CD_c%7C%7D
对于连续属性,可以考虑概率密度函数,假设P%28x_i%7Cc%29%5Cthicksim%20N%28%5Cmu_%7Bc%2Ci%7D%2C%5Csigma_%7Bc%2Ci%7D%5E2%29,其中%5Cmu_%7Bc%2Ci%7D%5Csigma_%7Bc%2Ci%7D%5E2分别是c样本在i属性上的值的均值和方差,分别有:
p%28x_i%7Cc%29%3D%5Cfrac%7B1%7D%7B%5Csqrt%7B2%5Cpi%7D%5Csigma_%7Bc%2Ci%7D%7De%5E%7B-%5Cfrac%7B%28x_i-%5Cmu_%7Bc%2Ci%7D%29%5E2%7D%7B2%5Csigma_%7Bc%2Ci%7D%5E2%7D%7D
为了防止其他属性携带的信息被没有出现在训练集中的属性值“擦除”,通常在估计概率值时进行平滑处理,我​​们使用拉普拉斯校正。即使N表示训练集中可能类别的数量D;令N_i表示第i个属性可能取值的个数,则:
%5Chat%20P%28c%29%3D%5Cfrac%7B%7CD_C%7C%2B1%7D%7B%7CD%7C%2BN%7D%5C%5C%20%5Chat%20P%28x_i%7Cc%29%3D%5Cfrac%7B%7CD_%7Bc%2Cx_i%7C%2B1%7D%7D%7B%7CD_c%7C%2BN_i%7D
朴素贝叶斯分类器在现实世界的任务中以多种方式使用。例如:

  • 如果任务需要高预测速度,那么对于给定的训练集,可以估计朴素贝叶斯分类器中涉及的所有概率。先计算存储,这样在做预测的时候,只需要“查表”就可以做出判断
  • 若任务数据更替频繁,则可采用“懒惰学习”(lazy learning) 方式,先不进行任何训练,待收到预测请求时再根据当前数据集进行概率估值
  • 如果数据不断增加,只需要在已有估计的基础上,对新增样本的属性值所涉及的概率估计进行统计和修正,就可以实现增量学习。

4 半朴素贝叶斯分类器

朴素贝叶斯采用的属性条件独立假设在现实中往往难以成立,因此人们试图在一定程度上放松属性条件独立的假设,使用“半朴素贝叶斯分类器”。

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

几种常用方法:

  • SPOED方法(super-parent ODE):
    所有属性都依赖于同一个属性
    ,被称为“超父”
  • TAN方法(Tree Augmented naive Bayes):在最大带权生成树的基础上,
    通过计算任意两个属性之间的互信息,构造最大加权生成树。
    互信息计算公式:
    I%28x_i%2Cx_j%7Cy%29%3D%5Csum_%7Bx_i%2Cx_j%3Bc%5Cin%20Y%7DP%28x_i%2Cx_j%7Cc%29%5Clog%20%5Cfrac%7BP%28x_i%2Cx_j%7Cc%29%7D%7BP%28x_i%7Cc%29P%28x_j%7Cc%29%7D
  • ADOE(Averaged One-Dependent Estimator):基于集成学习机制,更为强大的独依赖分类器。
    ADOE尝试将每个属性作为超父来构建SPODE,将具有足够训练数据支撑的SPODE集成起来作为最终结果。

image.png

5 贝叶斯网

贝叶斯网称为“信念网”(belief network),借助有向无环图(Directed Acyclic Graph,DAG)来刻画属性之间的依赖关系,并使用条件概率表(Contional Probability Table,CPT)来描述属性的联合概率分布。

贝叶斯网络由两部分组成:结构G和参数%5Ctheta。 (B%3D%3CG%2C%5Ctheta%3E)。
G是一个有向无环图,每个节点对应一个属性,如果两个属性有直接依赖关系,那么它们之间用一条边连接。 %5Ctheta 定量描述依赖关系,假设G中属性x_i的父节点集为%5Cpi_i,则%5Ctheta包含每个属性的条件概率表%5Ctheta_%7Bx_i%7C%5Cpi_i%7D%3DP%28x_i%7C%5Cpi_i%29

image.png

5.1 结构

贝叶斯网络结构有效地表达了属性之间的条件独立性。给定父节点集,贝叶斯网络假设每个属性都独立于其非后代属性,所以B%3D%3CG%3B%5Ctheta%3E定义属性x_1%2Cx_2%2C%E2%80%A6%2Cx_d的联合概率分布为:
P_B%28x_1%2Cx_2%2C%E2%80%A6%2Cx_d%29%3D%5Cprod_%7Bi%3D1%7D%5EdP_B%28x_i%7Ci_i%29%3D%5Cprod_%7Bi%3D1%7D%5Ed%5Ctheta_%7Bx_i%7C%5Cpi_i%7D
贝叶斯网络中存在三种典型的依赖关系:

image.png

  • 同父关系:给定父节点x_1的值,x_3x_4条件独立
  • 顺序结构:给定x的值,yz是条件独立的
  • V型结构:也叫冲撞结构,给定x_4的取值,x_1x_2必定不独立;但x_4的值如果完全位置,则x_1x_2是相互独立的。这种独立性称为“边际独立性”。

要分析图中变量之间的条件独立性,可以使用“有向分离”:

  • 找到所有V型结构,在V型结构的两个父结点之间加上一条无向边
  • 将所有有向边更改为无向边

由此产生的图叫道德图(moral graph),将父结点相连的过程称为“道德化”。(孩子的父母之间应该有牢靠的关系,不然是不道德的)

根据道德图,可以直观、快速地找到变量之间的条件独立性。假设道德图中有变量x%2Cy和变量集z%3D%7Bz%7D,如果变量xy在图上可以用z隔开,即从道德图中去掉变量集z后,xy属于两个相连的分支,则称为变量xy方向由z隔开。

5.2 学习

贝叶斯学习网络的首要任务是根据训练数据集找到最“合适”的贝叶斯网络结构。

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

评分函数可以写为如下(其中,|B|是贝叶斯网的参数个数,f%28%5Ctheta%29表示描述每个参数%5Ctheta​所需要的编码位数),第一项是计算编码贝叶斯网的编码位数,第二项是描述概率分布P_B对数据集D的拟合程度。
s%28B%7CD%29%3Df%28%5Ctheta%29%7CB%7C-LL%28B%7CD%29%5C%5C%20LL%28B%7CD%29%3D%5Csum_%7Bi%3D1%7D%5Em%5Clog%20P_B%28x_i%29
f%28%5Ctheta%29为1,则对应AIC评分函数;若f%28%5Ctheta%29%3D%5Cfrac%7B1%7D%7B2%7D%5Clog%20m为,则对应BIC评分函数;若%5Ctheta为0,则对应极大似然估计。

不幸的是,从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题,难以快速求解。有两种常用的策略能在有限时间内求得近似解:第一种是贪心法,例如从某个网络结构出发,每次调整一条边(增加、 删除或调整方向),直到评分函数值不再降低为止;第二种是通过给网络结构施加约束来削减搜索空间,例如将网络结构限定为树形结构等。

5.3 推断

贝叶斯网络训练好之后能用来回答“查询”,即通过一些属性变量的观测值来推测其他属性变量的取值。通过已知变量来推测待查询变量的过程称为“推断”(inference),已知变量观测值称为“证据”(evidence)。

根据贝叶斯网定义的联合概率分布来精确计算后验概率是NP难的问题,需要借助“近似推断”,降低精度要求,在有限时间内求得近似解。我们常采用吉布斯采样(Gibbs sampling):

  • Q%3D%5C%7BQ_1%2CQ_2%2C%E2%80%A6%2CQ_n%20%5C%7D表示要查询的变量,E%3D%5C%7BE_1%2CE_2%2C%E2%80%A6%2CE_k%5C%7D为证据变量,已知值为e%3D%5C%7Be_1%2Ce_2%2C%E2%80%A6%2Ce_k%5C%7D。目标是计算后验概率P%28Q%3Dq%7CE%3De%29
  • 吉布斯采样先随机产生一个与证据E%3De一致的样本q%5E0作为初始点,然后每步从当前样本出发产生下一个样本。在第t次采样,我们先假设q%5Et%3Dq%5E%7Bt-1%7D,然后对非证据变量逐个进行采样改变其取值,采样概率根据贝叶斯网B和其他变量的当前取值计算获得。假定经过T次采样得到的与q一致的样本共有n_q个,近似估算出后验概率:
    P%28Q%3Dq%7CE%3De%29%3D%5Cfrac%7Bn_q%7D%7BT%7D

实质上,吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据E%3De一致的子空间中进行 “随机漫步”(random wallk)。每一步仅依赖于前一步的状态,这是一个“马尔可夫链”(Markov chain)。在一定条件下,无论从什么初始状态开始,马尔可夫链第t步的状态分布在t%E2%86%92%5Cinfty时必收敛于一个平稳分布(stationary distribution); 对于吉布斯采样来说,这个分布恰好是P%28Q%20%7C%20E%3De%29。因此,在T很大时,吉布斯采样相当于根据P%28Q%7CE%3De%29采样,从而保证了式(17)收敛于P%28Q%3Dq%7CE%3D%20e%29

image.png

6 EM算法

在现实生活中,我们经常会遇到样本“不完整”的情况。未观测变量的学名是“隐变量”,设X代表观测变量集,Z代表潜变量集,%5Ctheta代表模型参数。如果进行%5Ctheta的最大似然估计,则应最大化对数似然:
LL%28%5Ctheta%7CX%2CZ%29%3Dln%20P%28X%2CZ%7C%5Ctheta%29
由于Z是隐变量,因此无法直接求解,这时我们可以通过对Z计算期望,来最大化已观测数据的对数“边际似然”:
LL%28%5Ctheta%7CX%29%3DlnP%28X%7C%5Ctheta%29%3Dln%5Csum_ZP%28X%2CZ%7C%5Ctheta%29
EM算法是常用的估计参数隐变量的利器。其基本思想:**若%5Ctheta已知,则可根据训练数据推断出最优隐变量的值(E步);反之,若Z的值已知,则可方便地对%5Ctheta做极大似然估计。**步骤如下:

  • 以初始值%5Ctheta%5E0为起点,对式(19),可以迭代执行以下步骤直到收敛:
  • 基于%5Ctheta%5Et推断潜变量Z的期望,注Z_t
  • 根据观测到的变量XZ,对参数%5Ctheta进行最大似然估计,记为%5Ctheta%5E%7Bt%2B1%7D

进一步,若我们不是取Z的期望,而是基于%CE%B8%5Et计算隐变量Z的概率分布P%28Z%7C%20X%2C%20%5Ctheta%5Et%29,则EM算法的两个步骤是:

  • E步(Expectation):以当前参数%CE%B8%5Et推断隐变量分布P%28Z%20%7C%20X%2C%5Ctheta%5Et%29,并计算对数似然LL%28%5Ctheta%7C%20X%2CZ%29关于Z的期望
    Q%28%5Ctheta%7C%5Ctheta%5Et%29%3DE_%7BZ%7CX%2C%5Ctheta%5Et%7DLL%28%5Ctheta%7CX%2CZ%29
  • M步(Maximization):寻找参数最大化期望似然,即
    %5Ctheta_%7Bt%2B1%7D%3D%5Cmathop%7B%5Carg%5Cmax%7D_%7B%5Ctheta%7D%5Cspace%20Q%7B%5Ctheta%7C%5Ctheta%5Et%7D

简要来说, EM算法使用两个步骤交替计算:第一步是期望(E)步,利用当前估计的参数值来计算对数似然的期望值;第二步是最大化(M)步,寻找能使E步产生的似然期望最大化的参数值,然后,新得到的参数值重新被用于E步,直至收敛到局部最优解。
事实上,隐变量估计问题也可通过梯度下降等优化算法求解,但由于求和的项数将随着隐变量的数目以指数级上升,会给梯度计算带来麻烦;而EM算法则可看作一种非梯度优化方法。

版权声明:本文为博主YJY131248原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/YJY131248/article/details/123391026

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
青葱年少的头像青葱年少普通用户
上一篇 2022年3月11日 下午1:13
下一篇 2022年3月11日

相关推荐