机器学习-西瓜书-全书16章--Chap07贝叶斯分类器.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,霍轩,第七章：贝叶斯分类器,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,贝叶斯决策论,贝叶斯决策论（,Bayesian decision theory,）是在概率框架下实施决策的基本方法。,在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。,贝叶斯决策论,贝叶斯决策论（,Bayesian decision theory,）是在,概率,框架下实施决策的基本方法。,在分类问题情况下，在所有,相关概率都已知,的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。,假设有 种可能的类别标记，即 ，是将一个真实标记为 的样本,误分,类为 所产生的,损失,。基于后验概率 可获得将样本 分类为 所产生的,期望损失,（,expected loss,）或者称,条件风险,（,conditional risk,）,我们的任务是,寻找,一个判定准则 以最小化总体风险,贝叶斯决策论,显然，对每个样本 ，若 能最小化条件风险 ，则总体风险 也将被最小化。,贝叶斯决策论,显然，对每个样本 ，若 能最小化条件风险 ，则总体风险 也将被最小化。,这就产生了贝叶斯判定准则（,Bayes decision rule,）：为最小化总体风险，只需在,每个样本,上选择那个能使条件风险 最小的类别标记，即,此时，被称为贝叶斯最优分类器,(Bayes optimal classifier),，与之对应的总体风险 称为贝叶斯风险,(Bayes,risk),反映了分类起所能达到的,最好,性能，即通过机器学习所能产生的模型精度的理论上限。,贝叶斯决策论,具体来说，若目标是最小化分类,错误率,，则误判损失 可写为,贝叶斯决策论,具体来说，若目标是最小化分类错误率，则误判损失 可写为,此时条件风险,贝叶斯决策论,具体来说，若目标是最小化分类错误率，则误判损失 可写为,此时条件风险,于是，最小化分类错误率的贝叶斯,最优,分类器为,即对每个样本 ，选择能使后验概率 最大的类别标记。,贝叶斯决策论,不难看出，使用贝叶斯判定准则来最小化决策风险，首先要获得,后验,概率 。,然而，在现实中通常,难以直接,获得。机器学习所要实现的是基于有限的训练样本尽可能准确地,估计,出后验概率 。,主要有两种策略：,判别式模型（,discriminative models,）,给定 ，通过直接建模,来预测,决策树，,BP,神经网络，支持向量机,生成式模型（,generative models,）,先对,联合,概率分布 建模，再由此获得,生成式模型考虑,贝叶斯决策论,生成式模型,贝叶斯决策论,生成式模型,基于,贝叶斯,定理，可写成,贝叶斯决策论,生成式模型,基于贝叶斯定理，可写成,先验概率,样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）,贝叶斯决策论,生成式模型,基于贝叶斯定理，可写成,先验概率,样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）,“证据”,（,evidence,）,因子，与类标记无关,贝叶斯决策论,生成式模型,基于贝叶斯定理，可写成,先验概率,样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定理）,“证据”,（,evidence,）,因子，与类标记无关,类标记,相对于样本 的“类条件概率,”(,class-conditional probability,),或称“似然”。,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,极大似然估计,估计类条件概率的常用策略：,先假定,其具有,某种,确定的,概率分布,形式，再基于,训练样本,对概率分布参数估计。,记关于类别 的类条件概率为 ，,假设 具有确定的形式被参数 唯一确定，我们的任务就是利用训练集 估计参数,极大似然估计,估计类条件概率的常用策略：先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布参数估计。,记关于类别 的类条件概率为 ，,假设 具有确定的形式被参数 唯一确定，我们的任务就是利用训练集 估计参数,概率模型的训练过程就是参数估计过程，统计学界的两个学派提供了不同的方案：,频率学派,(frequentist),认为参数虽然未知，但却存在客观值，因此可通过优化似然函数等准则来确定参数值,贝叶斯学派,(Bayesian),认为参数是未观察到的随机变量、其本身也可由分布，因此可假定参数服从一个先验分布，然后基于观测到的数据计算参数的后验分布。,极大似然估计,令 表示训练集中第 类样本的组合的集合，假设这些样本是,独立,的，则参数 对于数据集 的似然是,对 进行极大似然估计，寻找能最大化似然 的参数值 。直观上看，极大似然估计是试图在 所有可能的取值中，找到一个使数据出现的“可能性”最大值。,极大似然估计,令 表示训练集中第 类样本的组合的集合，假设这些样本是独立的，则参数 对于数据集 的似然是,对 进行极大似然估计，寻找能最大化似然 的参数值 。直观上看，极大似然估计是试图在 所有可能的取值中，找到一个使数据出现的“可能性”最大值。,式,(7.9),的连乘操作易造成下溢，通常使用,对数似然,(log-likelihood),此时参数 的极大似然估计 为,极大似然估计,例如，在连续属性情形下，假设概率密度函数 ，则参数 和 的极大似然估计为,也就是说，通过极大似然法得到的正态分布均值就是样本均值，方差就是 的均值，这显然是一个符合直觉的结果。,需注意的是，这种参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,朴素贝叶斯分类器,估计,后验概率 主要困难：类条件概率 是所有属性上的,联合概率,难以从有限的训练样本估计获得。,朴素贝叶斯分类器,估计,后验概率 主要困难：类条件概率 是所有属性上的,联合概率,难以从有限的训练样本估计获得。,朴素贝叶斯分类器,(Nave Bayes Classifier),采用了“属性,条件独立性,假设”,(attribute conditional independence assumption),：每个属性,独立地,对分类结果发生影响。,朴素贝叶斯分类器,估计,后验概率 主要困难：类条件概率 是所有属性上的,联合概率,难以从有限的训练样本估计获得。,朴素贝叶斯分类器,(Nave Bayes Classifier),采用了“属性,条件独立性,假设”,(attribute conditional independence assumption),：每个属性,独立地,对分类结果发生影响。,基于属性条件独立性假设，,(7.8),可重写为,其中,为属性数目，为 在第 个属性上的取值。,朴素贝叶斯分类器,朴素贝叶斯分类器,由于对所有类别来说 相同，因此基于式,(7.6),的贝叶斯判定准则有,这就是朴素贝叶斯分类器的,表达式,朴素贝叶斯分类器,朴素贝叶斯分类器的训练器的训练过程就是基于训练集 估计类先验概率 并为每个属性估计条件概率 。,令 表示训练集 中第 类样本组合的集合，若有充足的独立同分布样本，则可容易地,估计出,类先验概率,对离散属性而言，令 表示 中在第 个属性上取值为 的样本组成的集合，则条件概率,可估计,为,对连续属性而言可考虑概率密度函数，假定 ，其中 和 分别是第 类样本在第 个属性上取值的均值和方差，则有,朴素贝叶斯分类器,例子：用西瓜数据集,3.0,训练一个朴素贝叶斯分类器，对测试例“测,1,”进行分类,(p151,西瓜数据集,p84,表,4.3),拉普拉斯,修正,若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，,.,比如“敲声,=,清脆”测试例，训练集中没有该样例，因此连乘式计算的概率值为,0,，无论其他属性上明显像好瓜，分类结果都是“好瓜,=,否”，这显然不合理。,拉普拉斯修正,若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题，,.,比如“敲声,=,清脆”测试例，训练集中没有该样例，因此连乘式计算的概率值为,0,，无论其他属性上明显像好瓜，分类结果都是“好瓜,=,否”，这显然不合理。,为了避免其他属性携带的信息被训练集中未出现的属性值“,抹去,”，在估计概率值时通常要进行“,拉普拉斯修正,”（,Laplacian correction,）,令 表示训练集 中可能的类别数，表示第 个属性可能的取值数，则式,(,7.16,),和,(,7.17,),分别修正为,现实任务中，朴素贝叶斯分类器的使用情形：,速度要求高,，“查表”；,任务数据更替频繁,，“懒惰学习”,(lazy learning),；,数据不断增加,，增量学习等等。,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,半朴素贝叶斯分类器,为了降低贝叶斯公式中估计后验概率的困难，朴素贝叶斯分类器采用的属性条件独立性假设；对属性条件独立假设进行一定程度的,放松,，由此产生了一类称为“半朴素贝叶斯分类器”,(,semi-nave Bayes classifiers,),半朴素贝叶斯分类器,为了降低贝叶斯公式中估计后验概率的困难，朴素贝叶斯分类器采用的属性条件独立性假设；对属性条件独立假设记性一定程度的放松，由此产生了一类称为“半朴素贝叶斯分类器”,(,semi-nave Bayes classifiers,),半朴素贝叶斯分类器最常用的一种策略：“独依赖估计”,(One-Dependent Estimator,简称,ODE),，假设每个属性在类别之外最多仅依赖一个其他属性，即,其中 为属性 所依赖的,属性,，称为 的,父属性,对每个属性 ，若其父属性 已知，则可估计概值 ，于是问题的关键转化为如何确定每个属性的,父,属性,SPODE,最,直接,的做法是假设所有属性都依赖于,同一,属性，称为“超父”,(super-parenet),，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了,SPODE,(Super-Parent ODE),方法。,图,7.1,朴素贝叶斯分类器与两种半朴素分类器所考虑的属性依赖关系,在图,7.1(b),中，,是超父属性。,TAN,TAN(Tree augmented Nave Bayes)Friedman et al.,1997,则在最大带权生成树,(Maximum,weighted,spanning tree),算法,Chow and Liu,1968,的基础上，通过以下步骤将属性间依赖关系简约为图,7.1(c),。,计算任意两个,属性,之间的条件,互信息,(CMI,：,conditional mutual information),以属性为结点构建,完全图,，任意两个结点之间边的权重设为,构建此完全图的最大带权生成树,以每个属性为节点,(nodenode),，,CMI,为边,(edgeedge),形成一张图。找到这张图的,最大带权生成树,。即找到一个节点之间的连接规则，这个规则满足,三个,条件：,1.,能够连接所有节点；,2.,使用最少数目的边；,3.,边长,(CMI),总和最大,最大带权生成树,再把节点连接关系设置为,有向,，即从父节点指向子节点。在这里把,最先,出现的属性设置为,根,节点，再由根节点,出发,来确定边的方向,TAN,TAN(Tree augmented Nave Bayes)Friedman et al.,1997,则在最大带权生成树,(Maximum,weighted,spanning tree),算法,Chow and Liu,1968,的基础上，通过以下步骤将属性间依赖关系简约为图,7.1(c),。,计算任意两个,属性,之间的条件,互信息,(conditional mutual information),以属性为结点构建,完全图,，任意两个结点之间边的权重设为,构建此完全图的最大带权生成树，挑选,根,变量，将边设为,有向,；,加入类别节点,y,，,增加,从,y,到每个属性的,有向,边。,AODE,AODE(Averaged One-Dependent Estimator)Webb et al.2005,是一种基于集成学习机制、且更为强大的分类器。,尝试将,每个,属性,作为,超父,构建,SPODE-,共,d,个,将具有足够训练数据支撑的,SPODE,集群起来作为,最终结果,其中，是在第 个属性上取值 的样本的集合，为阈值常数,其中，是在第 个属性上取值数，是类别为 且在第 个属性上取,值为 的样本集合，是类别为 且在第,i,个属性上取,值，第,j,个属性上取,值为的样本集合,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,贝叶斯网,贝叶斯网,(,Bayesian network,),亦称“信念网”,(,brief network,),，它借助,有向无环图,(,Directed Acyclic Graph,DAG,),来刻画属性间的依赖关系，并使用条件概率表,(,Conditional Probability Table,CPT,),来表述,属性的联合概率分布,。,贝叶斯网,贝叶斯网,(,Bayesian network,),亦称“信念网”,(,brief network,),，它借助,有向无环图,(,Directed Acyclic Graph,DAG,),来刻画属性间的依赖关系，并使用条件概率表,(,Conditional Probability Table,CPT,),来表述,属性的联合概率分布,。,贝叶斯网：结构,贝叶斯网有效地表达了,属性间,的条件独立性。给定父结点集，贝叶斯网,假设,每个,属性与他的,非后裔,属性独立,。,将属性,的联合概率分布定义为,图,7.2,的,联合概率分布,定义为：,显然，,和,在,给定,的取值时,独立，,和,在给定,的取值时独立，记为,和 。,贝叶斯网有效地表达了,属性间,的条件独立性。,给定,父结点集，贝叶斯网,假设,每个,属性与他的,非后裔,属性独立,。,将属性,的联合概率分布定义为,图,7.2,的,联合概率分布,定义为：,显然，,和,在,给定,的取值时,独立，,和,在给定,的取值时独立，记为,和 。,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,V,型结构,顺序结构,同父结构,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,同父结构,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,顺序结构,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,顺序结构,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,V,型结构,贝叶斯网：结构,贝叶斯网中三个变量之间的,典型,依赖关系：,V,型结构,贝叶斯网：结构,贝叶斯网中三个变量之间的典型依赖关系：,分析有向图中变量间的条件独立性，可使用“有向分离”,(,Directed-separation,),将一个有向图转化为无向图,V,型结构父结点相连,有向边变成无向边,由此产生的图称为道德图,(moral graph),同父结构,V,型结构,顺序结构,(,好瓜,),(,敲声,),(,甜度,),(,色泽,),(,根蒂,),条件独立性分析,-,“,有向分离,”,法,分析有向图中变量间的条件独立性，可使用“有向分离”,(,Directed-separation,),将一个有向图转化为无向图,V,型结构父结点相连,有向边变成无向边,由此产生的图称为,道德图,(moral graph),(,好瓜,),(,敲声,),(,甜度,),(,色泽,),(,根蒂,),-,将父结点相连的过程称为“,道德化,”过程,“,道德化,”就是孩子的父母应建立牢靠的关系，否者不道德,条件独立性分析,-,道德图,贝叶斯网：学习,-,寻找,到这个贝叶斯网,贝叶斯网络首要任务：根据,训练集,找出结构最“恰当”的贝叶斯,网,。,我们用,评分函数,评估贝叶斯网与训练数据的契合程度。,贝叶斯网：学习,贝叶斯网络首要任务：根据训练集找出结构最“恰当”的贝叶斯网。,我们用评分函数评估贝叶斯网与训练数据的契合程度。,“最小描述长度”（,Minimal Description Length,MDL,）综合编码长度（包括描述网路和编码数据）最短,给定训练集 ，贝叶斯网,在,上的,评价函数,可以写为,其中，,是贝叶斯网的,参数个数,；,表示描述每个参数 所需的字节数，而,是贝叶斯网的对数似然。,学习任务：寻找一个合适的网络使得,s,最小,学习任务：寻找一个合适的网络使得,s,最小,学习任务：寻找一个合适的网络使得,s,最小,贝叶斯网：推断,通过已知变量,观测值,来推测其他变量的取值过程称为“推断”,(,inference,），已知变量观测值称为“,证据,”,(,evidence,),。,最理想的是根据贝叶斯网络定义的,联合概率分布,来精确计算后验概率，在现实应用中，贝叶斯网的近似推断常使用,吉布斯,采样,(Gibbs sampling),来完成,。,贝叶斯网：推断、,Gibbs,采样,通过已知变量观测值来推测待推测查询变量的过程称为“推断”,(,inference,），已知变量观测值称为“证据”,(,evidence,),。,最理想的是,根据,贝叶斯网络定义的,联合概率,分布来精确计算后验概率，在现实应用中，贝叶斯网的近似推断常使用吉布斯采样,(Gibbs sampling),来完成,。,吉布斯采样,就是随机产生一个与证据,一致,的,样本,作为初始点，然后每步从,当前样本,出发产生,下一个样本,。采样,概率,由贝叶斯网,B,决定。假定经过,次采样的得到与,一致,的样本共有,个，则可近似估算出后验概率,吉布斯采样可以看做，每一步仅依赖于前一步的状态,贝叶斯网：推断,图,7.5,吉布斯采样算法,章节目录,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,EM,算法,“不完整”的样本：西瓜已经脱落的根蒂，无法看出是“蜷缩”还是“坚挺”,则训练样本的“根蒂”属性变量值未知，如何计算？,EM,算法,“不完整”的样本：西瓜已经脱落的根蒂，无法看出是“蜷缩”还是“坚挺”,则训练样本的“根蒂”属性变量值未知，如何计算？,未观测的变量称为“,隐变量,”,(,latent variable,),。令,表示已观测变量集，,表示隐变量集，若预对模型参数,做极大似然估计，,则应最大化,对数似然,函数,EM,算法,“不完整”的样本：西瓜已经脱落的根蒂，无法看出是“蜷缩”还是“坚挺”,则训练样本的“根蒂”属性变量值未知，如何计算？,未观测的变量称为“隐变量”,(,latent variable,),。令,表示已观测变量集，,表示隐变量集，若,预对模型参数,做极大似然估计，,则应最大化对数似然函数,由于,是隐变量，上式无法直接求解。此时我们可以通过对,计算,期望,，来最大化已观测数据的对数“边际似然”,(,marginal likelihood,),EM,算法,EM(Expectation-Maximization),算法,Dempster et al.,1977,是常用的估计,参数隐变量,的利器。,当参数 已知,根据训练数据推断出最优隐变量,的值,(,E,步,),当,已知,对,做极大似然估计,(,M,步,),EM,算法,EM(Expectation-Maximization),算法,Dempster et al.,1977,是常用的估计参数隐变量的利器。,当参数 已知,根据训练数据推断出最优隐变量,的值,(,E,步,),当,已知,对,做极大似然估计,(,M,步,),于是，以初始值,为起点，对式子,(7.35),可,迭代执行,以下步骤直至收敛：,基于,推断隐变量,的期,望,记为,;,基于已观测到变量,和,对参数 做极大似然估计，记为,;,这就是,EM,算法的,原,型。,EM,算法,进一步，,若,我们不是取,Z,的期望，,而,是基于 计算隐变量,的概率分布 ，则,EM,算法的两个步骤是：,E,步,(,Expectation,):,以当前参数 推断隐变量分布 ，并计算对数似然,关于,的期,望,:,M,步,(,Maximization,):,寻找参数最大化期望似然，即,EM,算法使用两个步骤,交替,计算：第一步计算期望,(,E,步,),，利用当前估计的参数值计算对数似然的参数值；第二步最大化,(,M,步,),，寻找能使,E,步产生的似然期望最大化的参数值,直至收敛到全局最优解。,小结,贝叶斯决策论,极大似然估计,朴素贝叶斯分类器,半朴素贝叶斯分类器,贝叶斯网,EM,算法,