机器学习_第6章_贝叶斯学习课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Date:,20.09.2023,File:ML1.,1,Machine Learning,Peng Kaixiang 2011. All rights reserved.,Machine,Learning for,Control Engineering,第6章 贝叶斯学习,(,Bayesian Learning,),第6章 贝叶斯学习,概述,贝叶斯推理提供了一种,概率,手段，基于如下的假定：,待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策,。,贝叶斯推理为,衡量多个假设的置信度,提供了定量的方法。,贝叶斯推理为直接操作概率的学习算法提供了基础，也,为其他算法的分析提供了理论框架。,概述贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量,简介,贝叶斯学习算法与机器学习相关的两个原因：,贝叶斯学习算法能够计算显,式,的假设概率，比如朴素贝叶斯分类器；,贝叶斯方法为,理解多数学习算法,提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如：,Find-S,候选消除算法,神经网络学习：选择使误差平方和最小化的神经网络,推导出另一种误差函数：交叉熵,可分析决策树的归纳偏置,可考察最小描述长度原则,简介贝叶斯学习算法与机器学习相关的两个原因：,贝叶斯学习方法的特性,观察到的每个训练样例可以,增量地,降低,或,升高,某假设的估计概率,。而,其他算法会在某个假设与任一样例不一致时完全去掉该假设,；（最大优点）,先验知识,可以与,观察数据,一起决定假设的最终概率,，先验知识的形式是：1）每个候选假设的先验概率；2）每个可能假设在可观察数据上的概率分布；,贝叶斯方法可允许假设做出,不确定性的预测,；,新的实例分类可由多个假设一起做出预测，,用它们的概率来加权,；,即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其他方法；,贝叶斯学习方法的特性观察到的每个训练样例可以增量地降低或升高,贝叶斯方法的难度,难度之一：,需要概率的初始知识,，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率；,难度之二：一般情况下，,确定贝叶斯最优假设的计算代价比较大,（在某些特定情形下，这种计算代价可以大大降低）。,贝叶斯方法的难度难度之一：需要概率的初始知识，当概率预先未知,内容安排,介绍贝叶斯理论；,定义,极大似然假设（ML）,和,极大后验概率假设（MAP）；,将此概率框架应用于,分析前面章节的相关问题和学习算法,；,介绍几种直接操作概率的学习算法；,贝叶斯最优分类器,Gibbs算法,朴素贝叶斯分类器,讨论,贝叶斯信念网,，这是存在未知变量时被广泛使用的学习算法。,内容安排介绍贝叶斯理论；,贝叶斯法则,机器学习的任务：在给定训练数据D时，确定假设空间H中的最佳假设。,最佳假设：一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的,最可能假设,。,贝叶斯理论提供了,一种计算假设概率的方法,，基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。,贝叶斯法则机器学习的任务：在给定训练数据D时，确定假设空间H,先验概率和后验概率,用P(h)表示在没有训练数据前假设h拥有的初始概率。P(h)被称为h的,先验概率,；,先验概率反映了关于h是一正确假设的机会的背景知识；,如果,没有,这一先验知识，可以简单地将每一候选假设赋予,相同的先验概率,；,类似地，P(D)表示训练数据D的先验概率，P(D|h)表示假设h成立时D的概率；,机器学习中，我们关心的是P(h|D)，即,给定D时h的成立的概率,，称为,h的后验概率,。,先验概率和后验概率用P(h)表示在没有训练数据前假设h拥有的,贝叶斯公式,贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法；,(6.1),P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即,如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小,。,贝叶斯公式贝叶斯公式提供了从先验概率P(h)、P(D)和P(,极大后验假设,学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为,极大后验假设,（MAP）；,确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下：,(6.2),最后一步，去掉了P(D)，因为它是不依赖于h的常量。,极大后验假设学习器在候选假设集合H中寻找给定数据D时可能性最,极大似然假设,在某些情况下，,可假定H中每个假设有相同的先验概率,，这样式子6.2可以进一步简化，只需考虑P(D|h)来寻找极大可能假设。,P(D|h)常被称为给定h时数据D的似然度，而使P(D|h)最大的假设被称为极大似然假设：,假设空间H可扩展为任意的互斥命题集合，只要这些命题的概率之和为1。,极大似然假设在某些情况下，可假定H中每个假设有相同的先验概率,举例：一个医疗诊断问题,有两个可选的假设：病人有癌症、病人无癌症,可用数据来自化验结果：正+和负-,有先验知识：在所有人口中，患病率是0.008,对确实有病的患者的化验准确率为98%，对确实无病的患者的化验准确率为97%,总结如下,P(cancer)=0.008, P(,cancer)=0.992,P(+|cancer)=0.98, P(-|cancer)=0.02,P(+|,cancer)=0.03, P(-|cancer)=0.97,举例：一个医疗诊断问题有两个可选的假设：病人有癌症、病人无癌,举例：一个医疗诊断问题（2）,问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率P(cancer|+)和P(cancer|+),利用式子6.2找到极大后验假设,P(+|cancer)P(cancer)=0.0078,P(+|,cancer)P(cancer)=0.0298,h,MAP,=cancer,确切的后验概率可将上面的结果归一化以使它们的和为1,P(canner|+)=0.0078/(0.0078+0.0298)=0.21,P(,cancer|+)=0.79,贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性,举例：一个医疗诊断问题（2）问题：假定有一个新病人，化验结果,基本概率公式表,乘法规则：P(A,B)=P(A|B)P(B)=P(B|A)P(A),加法规则：P(A,B)=P(A)+P(B)-P(,A,B),贝叶斯法则：P(h|D)=P(D|h)P(h)/P(D),全概率法则：如果事件A,1,.A,n,互斥，且满足 ，,则,基本概率公式表乘法规则：P(AB)=P(A|B)P(B)=,贝叶斯法则和概念学习,贝叶斯法则为计算,给定训练数据下任一假设的后验概率,提供了原则性方法，因此可以直接将其作为一个基本的学习方法：,计算每个假设的概率，再输出其中概率最大的,。这个方法称为Brute-Force贝叶斯概念学习算法。,将上面方法与第2章介绍的概念学习算法比较，可以看到：在特定条件下，它们学习得到相同的假设，不同的是第2章的方法不明确计算概率，而且效率更高。,贝叶斯法则和概念学习贝叶斯法则为计算给定训练数据下任一假设的,Brute-Force贝叶斯概念学习,概念学习问题：有限假设空间H定义在实例空间X上，任务是学习某个目标概念c。,Brute-Force MAP学习算法,对于H中每个假设h，计算后验概率,输出有最高后验概率的假设,上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其他概念学习算法的性能,Brute-Force贝叶斯概念学习概念学习问题：有限假设空,特定情况下的MAP假设,假定,训练数据D是无噪声的，即d,i,=c(x,i,),目标概念c包含在假设空间H中,每个假设的先验概率相同,求得,由于所有假设的概率之和是1，因此,由于训练数据无噪声，那么给定假设h时，与h一致的D的概率为1，不一致的概率为0,，因此,特定情况下的MAP假设假定,特定情况下的MAP假设（2）,考虑Brute-Force MAP算法的第一步,h与D不一致，,h与D一致， ，,VS,H,D,是关于D的变型空间（见第2章，即与D一致的假设集）,特定情况下的MAP假设（2）考虑Brute-Force MA,特定情况下的MAP假设（3）,P(D)的推导,P(D),图6-1,假设的概率演化情况如图6-1所示，初始时所有假设具有相同的概率，当训练数据逐步出现后，不一致假设的概率变为0，而整个概率的和为1，它们均匀分布到剩余的一致假设中,每个与D一致的假设都是MAP假设,h,P(h|D1,D2),P(h),P(h|D1),h,h,特定情况下的MAP假设（3）P(D)的推导hP(h|D1,D,MAP假设和一致学习器,一致学习器,：如果某个学习器输出的假设在训练样例上为0错误率，则称为一致学习器；,如果H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致学习器将输出一个MAP假设；,Find-S算法按照特殊到一般的顺序搜索假设空间H，并输出一个极大特殊的一致假设，因此可知在上面定义的P(h)和P(D|h)概率分布下，它输出MAP假设；,更一般地，对于先验概率偏袒于更特殊假设的任何概率分布，Find-S输出的假设都是MAP假设。,MAP假设和一致学习器一致学习器：如果某个学习器输出的假设在,MAP假设和一致学习器（2）,贝叶斯框架提出了一种刻画学习算法行为的方法，即便该学习算法不进行概率操作，通过确定算法输出最优假设时使用的概率分布P(h)和P(D|h)，可以刻画出算法具有最优行为时的隐含假定；,使用贝叶斯方法刻画学习算法，与揭示学习器中的归纳偏置在思想上是类似的；,在第2章，将学习算法的归纳偏置定义为断言集合B，通过它可充分地演绎推断出学习器所执行的归纳推理结果，即,学习器的输出是由其输入和隐含的归纳偏置所演绎得出的。,MAP假设和一致学习器（2）贝叶斯框架提出了一种刻画学习算法,MAP假设和一致学习器（3）,贝叶斯解释对于描述学习算法中的隐含假定提供了另一种方法，用基于贝叶斯理论的一个等效的概率推理系统来建模；,贝叶斯解释隐含的假定形式为：H上的先验概率由P(h)分布给出，数据拒绝或接受假设的强度由P(D|h)给出；,在已知这些假定的概率分布后，一个基于贝叶斯理论的概率推理系统将产生等效于Find-S、候选消除等算法的输入-输出行为；,MAP假设和一致学习器（3）贝叶斯解释对于描述学习算法中的隐,极大似然和最小误差平方假设（1）,前面分析表明：某些学习算法即使没有显示地使用贝叶斯规则，或以某种形式计算概率，但它们输出的结果符合贝叶斯原理，是一个MAP假设；,通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和训练数据之间的误差平方和最小化，它将输出一极大似然假设；,上面结论的意义是，对于许多神经网络和曲线拟合的方法，如果它们试图在训练数据上使误差平方和最小化，此结论提供了基于贝叶斯的理论依据。,极大似然和最小误差平方假设（1）前面分析表明：某些学习算法即,极大似然和最小误差平方假设（2）,问题框架：,学习器L工作在实例空间X和假设空间H上，H中的假设为X上定义的某种实数值函数。,L面临的问题是学习一个从H中抽取出的未知目标函数f，给定m个训练样例的集合，每个样例的目标值被某随机噪声干扰，此随机噪声服从正态分布；,更精确地讲，每个训练样例是序偶，d,i,=f(x,i,)+e,i,，e,i,是代表噪声的随机变量，假定e,i,的值是独立抽取的，并且它们的分布服从0均值的正态分布；,学习器的任务是在所有假设有相等的先验概率前提下，输出极大似然假设（即ML假设）；,极大似然和最小误差平方假设（2）问题框架：,极大似然和最小误差平方假设（3）,用一个简单情况，即线性函数来说明问题。如图所示，实线表示线性目标函数f，实点表示有噪声的训练样例集，虚线对应有最小平方训练误差的假设h,ML,，即极大似然假设。,对于e这样的连续变量上的概率，使用概率密度表示概率分布，它在所有值上的积分为1，用小写的p表示。有限概率P有时又称为,概率质量；,概率密度函数：,极大似然和最小误差平方假设（3）用一个简单情况，即线性函数来,极大似然和最小误差平方假设（4）,假定有一固定的训练实例集合，因此只考虑相应的目标值序列D=，这里d,i,=f(x,i,)+e,i,。,假定训练样例是,相互独立的,，给定h时，可将P(D|h)写成各p(d,i,|h)的积,如果误差e,i,服从0均值和未知方差,2,的正态分布，那么每个d,i,服从均值为f(x,i,)，方差不变的正态分布。因此，p(d,i,|h)可写为方差,2,、均值f(x,i,)的正态分布,使用第5章中的正态分布公式并将相应的参数代入，由于概率d,i,的表达式是在h为目标函数f的正确描述条件下的，所以替换=f(x,i,)=h(x,i,),极大似然和最小误差平方假设（4）假定有一固定的训练实例集合，,极大似然和最小误差平方假设（5）,h,ML,上式说明了,极大似然假设等价于使训练值和假设预测值之间的误差的平方和最小的那个假设,；,这个结论的,前提,是：训练值等于真实目标值加上随机噪声，其中随机噪声从一个均值为0的正态分布中独立抽取。,极大似然和最小误差平方假设（5）hML,采用正态分布的合理性,数学计算的简洁性；,对许多物理系统的噪声都有良好的近似；,第5章中心极限定律显示，,足够多的独立同分布随机变量的和,服从正态分布；,由许多独立同分布的因素的和所生成的噪声将成为正态分布（当然，现实中不同的分量对噪声的贡献也许不是同分布的）；,使,误差平方最小化,的方法经常被用于神经网络、曲线拟合及其他许多实函数逼近的算法中；,上面的分析只,考虑了训练样例的目标值中的噪声，而没有考虑实例属性值的噪声,。,采用正态分布的合理性数学计算的简洁性；,用于预测概率的极大似然假设,问题框架：,学习一个不确定性函数f: X,0,1，它有两个离散的值输出；,这种不可预测性来源于未能观察到的因素，导致目标函数的输出是输入的概率函数。,学习得到的神经网络（或其他实函数学习器）的输出是f(x)=1的概率，表示为,f: X,0,1，即f=P(f(x)=1),用于预测概率的极大似然假设问题框架：,用于预测概率的极大似然假设（2）,Brute-Force法,首先收集对x的每个可能值观察到的1和0的频率，然后训练神经网络，对每个x输出目标频率,可以直接从f的训练样例中训练神经网络，然后推导出f的极大似然假设,D=.,用于预测概率的极大似然假设（2）Brute-Force法,用于预测概率的极大似然假设（3）,h,ML,（6.13）,式子6.13与熵函数的一般式相似，因此它的负值常称为,交叉熵,用于预测概率的极大似然假设（3）,在神经网络中梯度搜索以达到似然最大化,前面讨论了利用式子6.13求极大似然假设，现用G(h,D)表示，为神经网络学习推导一个权值训练法则，使用梯度上升法使G(h,D)最大化,考虑简单的情况，假定神经网络从一个单层的sigmoid单元建立，则,在神经网络中梯度搜索以达到似然最大化前面讨论了利用式子6.1,在神经网络中梯度搜索以达到似然最大化（2）,因为要使P(D|h)最大化而不是最小化，因此执行梯度上升搜索，而不是梯度下降搜索。,与反向传播更新法则对比,使误差平方最小化的法则寻找到极大似然假设的前提是：,训练数据可以由目标函数值加上正态分布噪声来模拟,使交叉熵最小化的法则寻找极大似然假设基于的前提是：,观察到的布尔值为输入实例的概率函数,在神经网络中梯度搜索以达到似然最大化（2）,最小描述长度准则,奥坎姆剃刀可以概括为：为观察到的数据选择最短的解释,此处给出一个贝叶斯分析，提出最小描述长度准则，根据信息论中的基本概念来解释h,MAP,的定义,(6.16),上式可以解释为在特定的假设编码表示方案上“优先选择短的假设”,最小描述长度准则奥坎姆剃刀可以概括为：为观察到的数据选择最短,最小描述长度准则（2）,信息论中的编码理论,设想要为随机传送的消息设计一个编码，其中遇到消息i的概率是p,i,感兴趣的是，使得传输随机信息所需的最小期望传送位数的编码,直观上，为使期望的编码长度最小，可能性大的消息应该赋予较短的编码,Shannon & Weaver证明了最优编码对消息i的编码长度为-log,2,p,i,使用代码C来编码消息i所需的位数被称为消息i关于C的描述长度，记为L,C,(i),最小描述长度准则（2）信息论中的编码理论,最小描述长度准则（3）,使用编码理论的结论来解释等式6.16,-log,2,P(h)是在假设空间H的最优编码下h的描述长度。换言之，这是假设h使用其最优表示时的大小,，C,H,为假设空间H的最优编码,-log,2,P(D|h)是在给定假设h时，训练数据D的描述长度， ，C,D|h,是假定发送者和接送者都知道假设h时描述数据D的最优编码,因此式子6.16显示，h,MAP,是使假设描述长度和给定假设下数据描述长度之和最小化的假设,最小描述长度准则：,最小描述长度准则（3）使用编码理论的结论来解释等式6.16,最小描述长度准则（4）,如果选择C,1,为假设的最优编码C,H,，C,2,为最优编码C,D|h,，那么h,MDL,=h,MAP,可将MDL准则想象为选择最短的方法来重新编码训练数据，其中不仅计算假设的大小，并且计算给定假设时编码数据的附加开销,将MDL准则应用于决策树，如何选择假设和数据的表示C,1,和C,2,?,对于C,1,，很自然地选择某种明确的决策树编码方法，其中描述长度随着树中节点和边的增长而增加,对于C,2,，如果训练分类f(x,i,)与假设的预计相同，那么就不需要传输有关这些样例的任何信息；如果不同，则要传输更正消息,最小描述长度准则（4）如果选择C1为假设的最优编码CH，C2,最小描述长度准则（5）,MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设,上面讨论自然给出了一种处理数据过度拟合的方法,Quinlan & Rivest描述了应用MDL准则选择决策树大小的几个实验，报告指出，基于MDL的方法产生的决策树的精度相当于第3章中讨论的标准树修剪方法,最小描述长度准则（5）MDL准则提供了一种方法在假设的复杂性,贝叶斯最优分类器,前面我们讨论的问题是：,给定训练数据，最可能的假设是什么？,另一个相关的更有意义的问题是：,给定训练数据，对新实例的最可能的分类是什么？,显然，第二个问题的解决可以将第一个问题的结果（MAP）应用到新实例上得到，还存在更好的算法。,贝叶斯最优分类器前面我们讨论的问题是：给定训练数据，最可能的,贝叶斯最优分类器（2）,例子,考虑一个包含三个假设h,1, h,2, h,3,的假设空间。,假定已知训练数据时三个假设的后验概率分别是0.4, 0.3, 0.3，因此h,1,为MAP假设。,若一新实例x被h,1,分类为正，被h,2,和h,3,分类为反,计算所有假设，x为正例的概率为0.4，为反例的概率为0.6,因此，这时最可能的分类与MAP假设生成的分类不同,矛盾！,贝叶斯最优分类器（2）例子,贝叶斯最优分类器（3）,一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。,如果新实例的可能分类可取某集合V中的任一值v,j,，那么概率P(v,j,|D)表示新实例分类为v,j,的概率,新实例的最优分类为使P(v,j,|D)最大的v,j,值，,贝叶斯最优分类器,为：,（6.18),贝叶斯最优分类器（3）一般而言，新实例的最可能分类可通过合并,贝叶斯最优分类器（4）,例子,已知：,新实例的可能分类集合为V=+,-,P(h,1,|D)=0.4, P(-|h,1,)=0, P(+|h,1,)=1,P(h,2,|D)=0.3, P(-|h,2,)=1, P(+|h,2,)=0,P(h,3,|D)=0.3, P(-|h,3,)=1, P(+|h,2,)=0,因此：,贝叶斯最优分类器（4）例子,贝叶斯最优分类器（5）,贝叶斯最优分类器,在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大,；,贝叶斯最优分类器的一个属性：,它所做的分类可以对应于H中不存在的假设,；,使用式子6.18来分类X中的每个实例，按此定义的实例标注不一定对应于H中的任一单个假设h对实例的标注；,将贝叶斯分类器看成是不同于假设空间H的另一空间H，在其上应用贝叶斯公式。,H有效地包含了一组假设，它能在H中多个假设的线性组合所作的预言中进行比较,。,贝叶斯最优分类器（5）贝叶斯最优分类器在给定可用数据、假设空,Gibbs算法,贝叶斯最优分类器能从给定训练数据中获得最好的性能，但算法的,开销很大,；,一个替代的、非最优的方法是Gibbs算法，定义如下：,按照H上的后验概率分布，从H中随机选择假设h,使用h来预言下一个实例x的分类,在一定条件下，Gibbs算法的误分类率的期望值最多为贝叶斯最优分类器的两倍。确切地讲，期望值是在随机抽取的目标概念上作出的，抽取过程按照学习器假定的先验概率,对概念学习问题的一个启示：如果学习器假定H上有均匀的先验概率，而且如果目标概念实际上也按该分布抽取，那么当前变型空间中随机抽取的假设对下一实例分类的期望误差最多为贝叶斯分类器的两倍,Gibbs算法贝叶斯最优分类器能从给定训练数据中获得最好的性,朴素贝叶斯分类器,应用的学习任务：,每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中取值;,贝叶斯方法的,新实例分类,目标是在给定描述实例的属性值下，得到最可能的目标值v,MAP,使用贝叶斯公式变化上式,(6.19),朴素贝叶斯分类器应用的学习任务：每个实例x可由属性值的合取描,朴素贝叶斯分类器（2）,基于训练数据估计式(6.19)中的两个数据项的值,估计P(v,j,)很容易：计算每个目标值v,j,出现在训练数据中的频率；,估计P(a,1,.a,n,|v,j,)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计,朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：,在给定目标值时，属性值之间相互条件独立,，即,(6.20),朴素贝叶斯分类器（2）基于训练数据估计式(6.19)中的两个,朴素贝叶斯分类器（3）,朴素贝叶斯分类器的定义：,从训练数据中估计不同P(a,i,|v,j,)项的数量比要估计P(a,1,.,a,n,|v,j,)项所需的量小得多；,只要,条件独立性,得到满足，朴素贝叶斯分类v,NB,等于MAP分类，否则是,近似,；,朴素贝叶斯分类器与其他已介绍的学习方法的一个区别：,没有明确地搜索可能假设空间的过程,（假设的形成不需要搜索，只是简单地计算训练样例中,不同数据组合的出现频率,）,朴素贝叶斯分类器（3）朴素贝叶斯分类器的定义：,朴素贝叶斯分类器（4）,举例,表3-2提供了目标概念PlayTennis的14个训练样例，给新实例分类,根据表3-2，可以计算出上式需要的概率值,P(yes)=9/14=0.64,P(no)=5/14=0.36,P(strong|yes)=3/9=0.33,P(strong|no)=3/5=0.60,.,求v,NB,P(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053,P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206,v,NB,=no,朴素贝叶斯分类器（4）举例,机器学习_第6章_贝叶斯学习课件,朴素贝叶斯分类器（5）,估计概率,通过在全部事件基础上观察某事件出现的比例来估计概率,当样本很小时，采用,平滑技术，m-估计,p是将要确定的概率的先验估计，而m是一称为等效样本大小的常量；,在缺少其他信息时，选择p的一种典型的方法是均匀概率，比如某属性有k个可能值，那么p=1/k；,m被称为等效样本大小的原因是：式子6.22可被解释为将n个实际的观察扩大，加上m个按p分布的虚拟样本。,(6.22),朴素贝叶斯分类器（5）估计概率(6.22),举例：学习分类文本,利用贝叶斯方法学习目标概念，然后用于文本自动过滤，比如：,我感兴趣的电子新闻稿,讨论机器学习的因特网页,本节描述一个基于朴素贝叶斯分类器的文本分类的通用算法，它是目前所知的文本分类的最有效方法之一。,问题框架：实例空间X包含了所有的文本文档，给定某未知目标函数f(x)的一组训练样例，f(x)的值来自某有限集合V（作为示例，此处令V=like, dislike）,举例：学习分类文本利用贝叶斯方法学习目标概念，然后用于文本自,举例：学习分类文本（2）,应用朴素贝叶斯分类器的两个主要设计问题：,怎样将任意文档表示为属性值的形式,如何估计朴素贝叶斯分类器所需的概率,表示文档的方法,给定一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词,假定我们共有1000个训练文档，其中700个分类为dislike，300个分类为like，现在要对下面的新文档进行分类：,This is an example document for the naive Bayes classifier. This document contains only one paragraph, or two sentences.,举例：学习分类文本（2）应用朴素贝叶斯分类器的两个主要设计问,举例：学习分类文本（3）,计算式,注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的,虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。,另外实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好。,举例：学习分类文本（3）计算式,举例：学习分类文本（4）,需要估计概率项P(v,i,)和P(a,i,=w,k,|v,i,)。前一项可基于每一类在训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题,再引入一个假定以减少需要估计的概率项的数量：,假定单词w,k,出现的概率独立于单词所在的位置,，即P(a,i,=w,k,|v,i,)=P(w,k,|v,j,),作此假定的一个主要优点在于：,使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度,采纳m-估计方法，即有统一的先验概率并且m等于词汇表的大小，因此,举例：学习分类文本（4）需要估计概率项P(vi)和P(ai=,表6-2 用于学习和分类文本的朴素贝叶斯算法,Learn_Naive_Bayes_Text( Examples, V ),Examples为一组文本文档以及它们的目标值。V为所有可能目标值的集合。此函数作用是学习概率项P(w,k,|v,j,)和P(v,j,)。,收集Examples中所有的单词、标点符号以及其他记号,Vocabulary,在Examples中任意文本文档中出现的所有单词及记号的集合,计算所需要的概率项P(v,j,)和P(w,k,|v,j,),对V中每个目标值v,j,docs,j,Examples中目标值为v,j,的文档子集,P(v,j,),|docs,j,| / |Examples|,Text,j,将docs,j,中所有成员连接起来建立的单个文档,n在Text,j,中不同单词位置的总数,对Vocabulary中每个单词w,k,n,k,单词w,k,出现在Text,j,中的次数,P(w,k,|v,j,)(n,k,+1) / (n+|Vocabulary|),表6-2 用于学习和分类文本的朴素贝叶斯算法Learn_Na,用于学习和分类文本的朴素贝叶斯算法（2）,Classify_Naive_Bayes_Text( Doc ),对文档Doc返回其估计的目标值，a,i,代表在Doc中的第i个位置上出现的单词,positions,在Doc中的所有单词位置，它包含能在Vocabulary中找到的记号,返回v,NB,，,用于学习和分类文本的朴素贝叶斯算法（2）Classify_N,应用样例,Joachims将此算法用于,新闻组文章的分类,每一篇文章的分类是该文章所属的新闻组名称；,20个新闻组，每个新闻组有1000篇文章，共2万个文档；,2/3作为训练样例，1/3进行性能测量；,词汇表不包含最常用词（比如the、of）和罕见词（数据集中出现次数少于3）；,分类精度由随机分类5提高到89。,Lang用此算法学习目标概念“,我感兴趣的新闻组文章,”,NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的；,每天向用户展示前10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高34倍。,应用样例Joachims将此算法用于新闻组文章的分类,贝叶斯信念网,朴素贝叶斯分类器假定各个属性取值在给定目标值v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严格；,贝叶斯信念网描述的是,一组变量所遵从的概率分布，它通过一组条件概率来指定一组条件独立性假设,；,贝叶斯信念网中可表述变量的一个子集上的条件独立性假定，因此，贝叶斯信念网提供了一种中间的方法，它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行。,贝叶斯信念网朴素贝叶斯分类器假定各个属性取值在给定目标值v下,贝叶斯信念网（2）,贝叶斯信念网描述了一组变量上的概率分布；,考虑一任意的随机变量集合Y,1,.Y,n,，其中每个Y,i,可取的值集合为V(Y,i,)；,变量集合Y的联合空间为叉乘V(Y,1,),.,V(Y,n,)；,在此联合空间上的概率分布称为,联合概率分布,，联合概率分布指定了元组的每个可能的变量约束的概率；,贝叶斯信念网则对一组变量描述了联合概率分布。,贝叶斯信念网（2）贝叶斯信念网描述了一组变量上的概率分布；,条件独立性,精确定义条件独立性,令X, Y和Z为3个离散值随机变量，当给定Z值时X服从的概率分布独立于Y的值，称X在给定Z时条件独立于Y，即,上式通常简写成P(X|Y,Z)=P(X|Z),扩展到变量集合,下面等式成立时，称变量集合X,1,.X,l,在给定变量集合Z,1,.Z,n,时条件独立于变量集合Y,1,.Y,m,条件独立性与朴素贝叶斯分类器的之间的关系,条件独立性精确定义条件独立性,贝叶斯信念网的表示,贝叶斯信念网（简称贝叶斯网）,表示一组变量的联合概率分布,一般地说，贝叶斯网表示联合概率分布的方法是,指定一组条件独立性假定,（有向无环图）以及,一组局部条件概率集合,下页图，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息,网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继”,每个变量有一个条件概率表，描述了该变量在给定其立即前驱时的概率分布,贝叶斯信念网的表示贝叶斯信念网（简称贝叶斯网）表示一组变量的,Storm,BusTourGroup,Lightning,Thunder,ForestFire,Campfire,S,BS,BS,BS,B,C0.40.10.80.2,C0.60.90.20.8,Campfire,StormBusTourGroupLightningThun,贝叶斯信念网的表示（2）,对网络变量的元组赋以所希望的值(y,1,.y,n,)的联合概率计算公式如下：,所有变量的局部条件概率表以及由网络所描述的一组条件独立假定，描述了该网络的整个联合概率分布,贝叶斯信念网的表示（2）对网络变量的元组赋,贝叶斯信念网的推理,可以用贝叶斯网在给定其他变量的观察值时推理出某些目标变量的值,由于所处理的是随机变量，所以一般不会赋予目标变量一个确切的值,真正需要推理的是目标变量的概率分布,，它指定了在给予其他变量的观察值条件下，目标变量取每一个可能值的概率,在网络中所有其他变量都确切知道的情况下，这一推理步骤很简单,一般来说，贝叶斯网络可用于在知道某些变量的值或分布时计算网络中另一部分变量的概率分布,贝叶斯信念网的推理可以用贝叶斯网在给定其他变量的观察值时推理,贝叶斯信念网的推理（2）,对任意贝叶斯网络的概率的确切推理已经知道是一个NP难题；,Monte Carlo方法提供了一种近似的结果，通过对未观察到的变量进行随机采样；,理论上，即使是贝叶斯网络中的近似推理也可能是NP难题；,实践中许多情况下近似的方法被证明是有效的。,贝叶斯信念网的推理（2）对任意贝叶斯网络的概率的确切推理已经,学习贝叶斯信念网,从训练数据中学到贝叶斯信念网，有多种讨论的框架：,网络结构可以预先给出，或由训练数据中得到,所有的网络变量可以直接从每个训练样例中观察到，或某些变量不能观察到,如果网络结构已知且变量可以从训练样例中完全获得，那么得到条件概率表就比较简单；,如果网络结构已知，但只有一部分变量值能在数据中观察到，学习问题就困难多了。这类似于在人工神经网络中学习隐层单元的权值；,Russell（1995）提出了一个简单的梯度上升过程以学习条件概率表中的项，相当于对表项搜索极大似然假设。,学习贝叶斯信念网从训练数据中学到贝叶斯信念网，有多种讨论的框,贝叶斯网的梯度上升训练,令w,ijk,代表条件概率表的一个表项，即在给定父节点U,i,取值u,ik,时，网络变量Y,i,值为y,ij,的,概率,例如图6-3，w,ijk,为最左上方的表项，那么Y,i,为变量Campfire，U,i,是其父节点的元组，y,ij,=True，且u,ik,=,S,BS,BS,BS,B,C0.40.10.80.2,C0.60.90.20.8,Campfire,贝叶斯网的梯度上升训练令wijk代表条件概率表的一个表项，即,贝叶斯网的梯度上升训练（2）,lnP(D|h)的梯度由对每个w,ijk,求导数得到,例如，为计算图6-3中表右上方的表项的lnP(D|h)的导数，需要对D中每个训练样例d计算P(Campfire=True, Storm=False, BusTourGroup=False|d),当训练样例中无法观察到这些变量时，这些概率可用标准的贝叶斯网从d中观察到的变量中推理得到,这些量能够很容易地从贝叶斯网推理过程中得到，几乎不需要附加的开销,(6.25),贝叶斯网的梯度上升训练（2）lnP(D|h)的梯度由对每个w,贝叶斯网的梯度上升训练（3）,式子6.25的推导,用P,h,(D)来表示P(D|h),假定在数据集D中的各样例d都是独立抽取的,贝叶斯网的梯度上升训练（3）式子6.25的推导,机器学习_第6章_贝叶斯学习课件,贝叶斯网的梯度上升训练（4）,更新权值,归一化处理，保持在区间0,1之间，且,j,w,ijk,对所有i,k保持为1,这个算法只保证找到局部最优解，替代梯度上升的一个算法是EM算法,贝叶斯网的梯度上升训练（4）更新权值,学习贝叶斯网的结构,如果贝叶斯网的结构未知，那么需要学习贝叶斯网的结构,Cooper & Herskovits提出了一个贝叶斯评分尺度，以便从不同网络中进行选择,Cooper & Herskovits提出了算法K2，启发式算法，用于在数据完全可观察时学习网络结构,基于约束的学习贝叶斯网络结构：从数据中推导出独立和相关的关系，然后用这些关系来构造贝叶斯网,学习贝叶斯网的结构如果贝叶斯网的结构未知，那么需要学习贝叶斯,EM算法,在许多实际的学习问题框架中，相关实例特征中只有一部分可观察到,已有许多方法被提出来处理存在未观察到变量的问题,比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值,EM算法是,存在隐含变量时广泛使用的一种学习方法，可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知,用于贝叶斯网的训练,用于马尔可夫模型的训练,EM算法在许多实际的学习问题框架中，相关实例特征中只有一部分,估计k个高斯分布的均值,考虑D是一个实例集合，它由k个不同正态分布的混合所得分布生成,每个实例使用一个两步骤的过程形成：,首先，随机选择k个正态分布中的一个,其次，随机变量x,i,按照此选择的分布生成,考虑一个简单情形：,单个正态分布的选择基于均匀的概率进行，且k个正态分布有相同的方差,学习任务：输出一个假设h=，描述k个分布中每个分布的均值，找到极大似然假设，即使得p(D|h)最大化的假设,估计k个高斯分布的均值考虑D是一个实例集合，它由k个不同正态,估计k个高斯分布的均值（2）,当给定从一个正态分布中抽取的数据实例x,1,.,x,m,时，很容易计算该分布的均值的极大似然假设，它是前面介绍的最小误差平方假设的一个特例，表示如下,然而，现在的问题涉及k个不同正态分布，而且不知道哪个实例是哪个分布产生的。这是一个涉及隐藏变量的典型例子；,对于图6-4的例子，每个实例的完整描述是三元组，其中x,i,是第i个实例的观测值，z,i1,和z,i2,表示哪个正态分布被用来产生x,i,，是隐藏变量,(6.27,28),估计k个高斯分布的均值（2）当给定从一个正态分布中抽取的数据,图6-4,由两个具有相等方差的正态分布混合生成的例子,图6-4由两个具有相等方差的正态分布混合生成的例子,估计k个高斯分布的均值（3）,如果z,i1,和z,i2,的值可知，就可用式子6.27来解决，否则使用EM算法,EM算法根据当前假设，不断地再估计隐藏变量z,ij,的期望值，然后用这些隐藏变量的期望值重新计算极大似然假设,以图6-4为例，先将假设初始化为h=,计算每个隐藏变量z,ij,的期望值Ez,ij,，假定当前假设h=成立,计算一个新的极大似然假设h=，假定每个隐藏变量z,ij,所取值是第一步得到的期望值Ez,ij,。将假设替换为h=,，然后循环,估计k个高斯分布的均值（3）如果zi1和zi2的值可知，就可,两个步骤的计算式,Ez,ij,正是实例x,i,由第j个正态分布生成的概率,第二步，使用第一步得到的Ez,ij,来导出一新的极大似然假设,两个步骤的计算式Ezij正是实例xi由第j个正态分布生成,两个步骤的计算式（2）,第二步中的表达式类似于式6.28，只是变成了加权样本均值,EM算法的要点：,当前的假设用于估计未知变量，而这些变量的期望值再被用于改进假设,可以证明：算法的每一次循环中，EM算法能使似然P(D|h)增加，除非P(D|h)达到局部最大，因此算法收敛到一个局部最大似然假设,两个步骤的计算式（2）第二步中的表达式类似于式6.28，只是,EM算法的一般表述,EM算法可用于许多问题框架：,其中需要估计一组描述基准概率分布的参数，只给定了由此分布产生的全部数据中能观察到的一部分,。,上面的二均值问题中，感兴趣的参数是,=,，全部数据是三元组，而只能观察到xi,一般地，令待估计参数是,，全部数据Y=XZ，其中X是可观察数据，Z是未观察数据。,Z可看作一个随机变量，它的概率分布依赖于参数和已知数据X,Y也是一个随机变量，因为它由随机变量Z定义,EM算法的一般表述EM算法可用于许多问题框架：其中需要估计一,EM算法的一般表述（2）,EM算法通过搜寻使ElnP(Y|h)最大的h来寻找极大似然假设h，其合理性是：,P(Y|h)是给定假设h下全部数据Y的似然度，因此找到使得这个值最大的h是合理的,对数lnP(Y|h)最大化也使P(Y|h)最大化,由于Y是一个随机变量，因此P(Y|h)无法计算，转而计算它的期望值ElnP(Y|h),Y的概率分布由待估计的参数决定，EM算法使用当前假设h代替实际参数，来估计Y的概率分布,定义函数Q(h|h)=ElnP(Y|h)|h,X,EM算法的一般表述（2）EM算法通过搜寻使ElnP(Y|h,EM算法的一般表述（3）,EM算法的一般形式，重复下面的步骤，直至收敛,估计（E）步骤：使用当前假设h和观察到的数据X来估计Y上的概率分布以计算Q(h|h),Q(h|h),ElnP(Y|h)|h,X,最大化（M）步骤：将假设h替换为使Q函数最大化的假设h,h,argmax,h,Q(h|h),当函数Q连续时，EM算法收敛到似然函数P(Y|h)的一个不动点，它保证收敛到一个局部最大值,EM算法的一般表述（3）EM算法的一般形式，重复下面的步骤，,K均值算法的推导,问题框架,要估计k个正态分布的均值,=,观察到的数据是X=,隐藏变量Z=表示k个正态分布中哪一个生成x,i,用于K均值问题的表达式Q(h|h)的推导,单个实例的概率,K均值算法的推导问题框架,K均值算法的推导（2）,所有实例的概率的对数,计算期望值,K均值算法的推导（2）所有实例的概率的对数,K均值算法的推导（3）,求使Q函数最大的假设,解上式得到,另外,K均值算法的推导（3）求使Q函数最大的假设,小结,概率学习方法利用关于,不同假设的先验概率,，以及,在给定假设时观察到不同数据的概率,的知识,贝叶斯方法提供了概率学习方法的基础，基于这些先验和数据观察假定，赋予,每个假设一个后验概率,贝叶斯方法确定的,极大后验概率假设是最可能成为最优假设的假设,贝叶斯最优分类器,将所有假设的预测结合起来，并用后验概率加权,，以计算对新实例的最可能分类,朴素贝叶斯分类器增加了简化假定：,属性值在给定实例的分类时条件独立,贝叶斯信念网能够表示,属性的子集上的一组条件独立性假定,小结概率学习方法利用关于不同假设的先验概率，以及在给定假设时,小结（2）,贝叶斯推理框架可对其他不直接应用贝叶斯公式的学习方法的分析提供,理论基础,最小描述长度准则,建议选取这样的假设，它使假设的描述长度和给定假设下数据的描述长度的和最小化。贝叶斯公式和信息论中的基本结论提供了此准则的根据,EM算法提供了一个通用的算法，,在存在隐藏变量时进行学习,。算法开始于一个任意的初始假设，然后迭代地计算隐藏变量的期望值，再重新计算极大似然假设，这个过程收敛到一个局部极大似然假设和隐藏变量的估计值,小结（2）贝叶斯推理框架可对其他不直接应用贝叶斯公式的学习方,补充读物,Casella & Berger 1990在概率和统计方面的介绍性文章,Maisel 1971, Speigel 1991的快速参考书籍,Duda & Hart 1973对贝叶斯分类器和最小平方误差分类器的介绍,Domigos & Pazzani 1996分析了朴素贝叶斯分类器输出最优分类的条件,Cestnik 1990讨论了m-估计,Michie et al. 1994将不同贝叶斯方法与决策树等其他算法进行比较,Chauvin & Rumelhart1995提供了基于反向传播算法的神经网络的贝叶斯分析,Rissanen1 1983, 1989讨论了最小描述长度准则,Quinlan & Rivest 1989描述了利用最小描述长度准则避免决策树过度拟合的方法,补充读物Casella & Berger 1990在概率和统,