第6章贝叶斯学习与EM算法课件.ppt

第6章 贝叶斯学习与EM算法( Bayesian Learning and EM Algorithm ),概述,贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。贝叶斯推理为衡量多个假设的置信度提供了定量的方法。贝叶斯推理为直接操作概率的学习算法提供了基础，也为其它算法的分析提供了理论框架。,简介,贝叶斯学习算法与机器学习相关的两个原因：贝叶斯学习算法能够计算显示的假设概率，比如朴素贝叶斯分类器；贝叶斯方法为理解多数学习算法提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如：Find-S候选消除算法神经网络学习：选择使误差平方和最小化的神经网络推导出另一种误差函数：交叉熵可分析决策树的归纳偏置可考察最小描述长度原则,贝叶斯学习方法的特性,观察到的每个训练样例可以增量地降低或升高某假设的估计概率。而其它算法会在某个假设与任一样例不一致时完全去掉该假设；（最大优点）先验知识可以与观察数据一起决定假设的最终概率，先验知识的形式是：1）每个候选假设的先验概率；2）每个可能假设在可观察数据上的概率分布；贝叶斯方法可允许假设做出不确定性的预测；新的实例分类可由多个假设一起做出预测，用它们的概率来加权；即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其它方法；,贝叶斯方法的难度,难度之一：需要概率的初始知识，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率；难度之二：一般情况下，确定贝叶斯最优假设的计算代价比较大（在某些特定情形下，这种计算代价可以大大降低）。,内容安排,介绍贝叶斯理论；定义极大似然假设（ML）和极大后验概率假设（MAP）；将此概率框架应用于分析前面章节的相关问题和学习算法；介绍几种直接操作概率的学习算法；贝叶斯最优分类器Gibbs算法朴素贝叶斯分类器讨论EM算法，一类参数估计的方法。,统计推断中可用的三种信息,美籍波兰统计学家耐曼(E.L.Lehmann18941981) 高度概括了在统计推断中可用的三种信息：,1总体信息，即总体分布或所属分布族给我们的信息。譬如“总体视察指数分布”或“总体是正态分布”在统计推断中都发挥重要作用，只要有总体信息，就要想方设法在统计推断中使用2样本信息，即样本提供我们的信息，这是任一种统计推断中都需要,3先验信息，即在抽样之前有关统计推断的一些信息。 譬如，在估计某产品的不合格率时，假如工厂保存了过去抽检这种产品质量的资料，这些资料（包括历史数据）有时估计该产品的不合格率是有好处的。这些资料所提供的信息就是一种先验信息。 又如某工程师根据自己多年积累的经验对正在设计的某种彩电的平均寿命所提供的估计也是一种先验信息。 由于这种信息是在“试验之前”就已有的，故称为先验信息。,假设 随机变量X有一个密度函数p（x；），其中是一个参数，不同的对应不同的密度函数，故从贝叶斯观点看，p（x；）是在给定后是个条件密度函数，因此记为p（x）更恰当一些。这个条件密度能提供我们的有关的信息就是总体信息。,假设 当给定后，从总体p（x）中随机抽取一个样本 ,该样本中含有的有关信息。这种信息就是样本信息。,贝叶斯公式的密度函数形式,假设 对参数已经积累了很多资料，经过分析、整理和加工，可以获得一些有关的有用信息，这种信息就是先验信息。参数不是永远固定在一个值上，而是一个事先不能确定的量。从贝叶斯观点来看，未知参数是一个随机变量。而描述这个随机变量的分布可从先验信息中归纳出来，这个分布称为先验分布，其密度函数用（）表示。,前面的分析总结如下：人们根据先验信息对参数已有一个认识，这个认识就是先验分布（）。通过试验，获得样本。从而对的先验分布进行调整，调整的方法就是使用上面的贝叶斯公式，调整的结果就是后验分布 。后验分布是三种信息的综合。获得后验分布使人们对的认识又前进一步，可看出，获得样本的的效果是把我们对的认识由（）调整到 。所以对的统计推断就应建立在后验分布 的基础上。,贝叶斯法则,机器学习的任务：在给定训练数据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)、P(D)和P(D|h)计算后验概率P(h|D)的方法； (6.1)P(h|D)随着P(h)和P(D|h)的增长而增长，随着P(D)的增长而减少，即如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小。,极大后验假设,学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h，h被称为极大后验假设（MAP）；确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下： (6.2) 最后一步，去掉了P(D)，因为它是不依赖于h的常量。,极大似然假设,在某些情况下，可假定H中每个假设有相同的先验概率，这样式子6.2可以进一步简化，只需考虑P(D|h)来寻找极大可能假设。P(D|h)常被称为给定h时数据D的似然度，而使P(D|h)最大的假设被称为极大似然假设：假设空间H可扩展为任意的互斥命题集合，只要这些命题的概率之和为1。,举例：一个医疗诊断问题,有两个可选的假设：病人有癌症、病人无癌症可用数据来自化验结果：正+和负-有先验知识：在所有人口中，患病率是0.008对确实有病的患者的化验准确率为98%，对确实无病的患者的化验准确率为97%总结如下P(cancer)=0.008, P(cancer)=0.992P(+|cancer)=0.98, P(-|cancer)=0.02P(+|cancer)=0.03, P(-|cancer)=0.97,举例：一个医疗诊断问题（2）,问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率P(cancer|+)和P(cancer|+)利用式子6.2找到极大后验假设P(+|cancer)P(cancer)=0.0078P(+|cancer)P(cancer)=0.0298hMAP=cancer确切的后验概率可将上面的结果归一化以使它们的和为1P(canner|+)=0.0078/(0.0078+0.0298)=0.21P(cancer|+)=0.79贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性,基本概率公式表,乘法规则：P(AB)=P(A|B)P(B)=P(B|A)P(A)加法规则：P(AB)=P(A)+P(B)-P(AB)贝叶斯法则：P(h|D)=P(D|h)P(h)/P(D)全概率法则：如果事件A1.An互斥，且满足 ， 则,贝叶斯法则和概念学习,贝叶斯法则为计算给定训练数据下任一假设的后验概率提供了原则性方法，因此可以直接将其作为一个基本的学习方法：计算每个假设的概率，再输出其中概率最大的。这个方法称为Brute-Force贝叶斯概念学习算法。将上面方法与第2章介绍的概念学习算法比较，可以看到：在特定条件下，它们学习得到相同的假设，不同的是第2章的方法不明确计算概率，而且效率更高。,Brute-Force贝叶斯概念学习,概念学习问题：有限假设空间H定义在实例空间X上，任务是学习某个目标概念c。Brute-Force MAP学习算法对于H中每个假设h，计算后验概率输出有最高后验概率的假设上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其它概念学习算法的性能,特定情况下的MAP假设,假定训练数据D是无噪声的，即di=c(xi)目标概念c包含在假设空间H中每个假设的先验概率相同求得由于所有假设的概率之和是1，因此由于训练数据无噪声，那么给定假设h时，与h一致的D的概率为1，不一致的概率为0，因此,特定情况下的MAP假设（2）,考虑Brute-Force MAP算法的第一步h与D不一致，h与D一致， ，VSH,D是关于D的变型空间（见第2章，即与D一致的假设集）,特定情况下的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假设和一致学习器,一致学习器：如果某个学习器输出的假设在训练样例上为0错误率，则称为一致学习器；如果H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致学习器将输出一个MAP假设；Find-S算法按照特殊到一般的顺序搜索假设空间H，并输出一个极大特殊的一致假设，因此可知在上面定义的P(h)和P(D|h)概率分布下，它输出MAP假设；更一般地，对于先验概率偏袒于更特殊假设的任何概率分布，Find-S输出的假设都是MAP假设。,MAP假设和一致学习器（2）,贝叶斯框架提出了一种刻画学习算法行为的方法，即便该学习算法不进行概率操作，通过确定算法输出最优假设时使用的概率分布P(h)和P(D|h)，可以刻画出算法具有最优行为时的隐含假定；使用贝叶斯方法刻画学习算法，与揭示学习器中的归纳偏置在思想上是类似的；在第2章，将学习算法的归纳偏置定义为断言集合B，通过它可充分地演绎推断出学习器所执行的归纳推理结果，即学习器的输出是由其输入和隐含的归纳偏置所演绎得出的。,MAP假设和一致学习器（3）,贝叶斯解释对于描述学习算法中的隐含假定提供了另一种方法，用基于贝叶斯理论的一个等效的概率推理系统来建模；贝叶斯解释隐含的假定形式为：H上的先验概率由P(h)分布给出，数据拒绝或接受假设的强度由P(D|h)给出；在已知这些假定的概率分布后，一个基于贝叶斯理论的概率推理系统将产生等效于Find-S、候选消除等算法的输入-输出行为；,极大似然和最小误差平方假设（1）,前面分析表明：某些学习算法即使没有显示地使用贝叶斯规则，或以某种形式计算概率，但它们输出的结果符合贝叶斯原理，是一个MAP假设；通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和训练数据之间的误差平方和最小化，它将输出一极大似然假设；上面结论的意义是，对于许多神经网络和曲线拟合的方法，如果它们试图在训练数据上使误差平方和最小化，此结论提供了基于贝叶斯的理论依据。,极大似然和最小误差平方假设（2）,问题框架：学习器L工作在实例空间X和假设空间H上，H中的假设为X上定义的某种实数值函数；L面临的问题是学习一个从H中抽取出的未知目标函数f，给定m个训练样例的集合，每个样例的目标值被某随机噪声干扰，此随机噪声服从正态分布；更精确地讲，每个训练样例是序偶，di=f(xi)+ei，ei是代表噪声的随机变量，假定ei的值是独立抽取的，并且它们的分布服从0均值的正态分布；学习器的任务是在所有假设有相等的先验概率前提下，输出极大似然假设（即ML假设）；,极大似然和最小误差平方假设（3）,用一个简单情况，即线性函数来说明问题。如图所示，实线表示线性目标函数f，实点表示有噪声的训练样例集，虚线对应有最小平方训练误差的假设hML，即极大似然假设。对于e这样的连续变量上的概率，使用概率密度表示概率分布，它在所有值上的积分为1，用小写的p表示。有限概率P有时又称为概率质量；概率密度函数：,极大似然和最小误差平方假设（4）,假定有一固定的训练实例集合，因此只考虑相应的目标值序列D=，这里di=f(xi)+ei。假定训练样例是相互独立的，给定h时，可将P(D|h)写成各p(di|h)的积如果误差ei服从0均值和未知方差2的正态分布，那么每个di服从均值为f(xi)，方差不变的正态分布。因此，p(di|h)可写为方差2、均值f(xi)的正态分布；使用第5章中的正态分布公式并将相应的参数代入，由于概率di的表达式是在h为目标函数f的正确描述条件下的，所以替换=f(xi)=h(xi),极大似然和最小误差平方假设（5）,hML上式说明了极大似然假设等价于使训练值和假设预测值之间的误差的平方和最小的那个假设；这个结论的前提是：训练值等于真实目标值加上随机噪声，其中随机噪声从一个均值为0的正态分布中独立抽取。,采用正态分布的合理性,数学计算的简洁性；对许多物理系统的噪声都有良好的近似；第5章中心极限定理显示，足够多的独立同分布随机变量的和服从正态分布；由许多独立同分布的因素的和所生成的噪声将成为正态分布（当然，现实中不同的分量对噪声的贡献也许不是同分布的）；使误差平方最小化的方法经常被用于神经网络、曲线拟合及其他许多实函数逼近的算法中；上面的分析只考虑了训练样例的目标值中的噪声，而没有考虑实例属性值的噪声。,用于预测概率的极大似然假设,问题框架：学习一个不确定性函数f: X0,1，它有两个离散的值输出；这种不可预测性来源于未能观察到的因素，导致目标函数的输出是输入的概率函数。学习得到的神经网络（或其它实函数学习器）的输出是f(x)=1的概率，表示为： f: X0,1，即f=P(f(x)=1),用于预测概率的极大似然假设（2）,Brute-Force法首先收集对x的每个可能值观察到的1和0的频率，然后训练神经网络，对每个x输出目标频率可以直接从f的训练样例中训练神经网络，而且能推导出f的极大似然假设D=.,用于预测概率的极大似然假设（3）,hML （6.13）式子6.13与熵函数的一般式相似，因此它的负值常称为交叉熵,在神经网络中梯度搜索以达到似然最大化,前面讨论了利用式子6.13求极大似然假设，现用G(h,D)表示，为神经网络学习推导一个权值训练法则，使用梯度上升法使G(h,D)最大化考虑简单的情况，假定神经网络从一个单层的sigmoid单元建立，则,在神经网络中梯度搜索以达到似然最大化（2）,因为要使P(D|h)最大化而不是最小化，因此执行梯度上升搜索，而不是梯度下降搜索。与反向传播更新法则对比使误差平方最小化的法则寻找到极大似然假设的前提是：训练数据可以由目标函数值加上正态分布噪声来模拟使交叉熵最小化的法则寻找极大似然假设基于的前提是：观察到的布尔值为输入实例的概率函数,最小描述长度准则,奥坎姆剃刀可以概括为：为观察到的数据选择最短的解释；此处给出一个贝叶斯分析，提出最小描述长度准则，根据信息论中的基本概念来解释hMAP的定义 (6.16)上式可以解释为在特定的假设编码表示方案上“优先选择短的假设”,最小描述长度准则（2）,信息论中的编码理论设想要为随机传送的消息设计一个编码，其中遇到消息i的概率是pi感兴趣的是，使得传输随机信息所需的最小期望传送位数的编码直观上，为使期望的编码长度最小，可能性大的消息应该赋予较短的编码Shannon & Weaver证明了最优编码对消息i的编码长度为-log2pi使用代码C来编码消息i所需的位数被称为消息i关于C的描述长度，记为LC(i),最小描述长度准则（3）,使用编码理论的结论来解释等式6.16-log2P(h)是在假设空间H的最优编码下h的描述长度。换言之，这是假设h使用其最优表示时的大小 ，CH为假设空间H的最优编码-log2P(D|h)是在给定假设h时，训练数据D的描述长度， ，CD|h是假定发送者和接送者都知道假设h时描述数据D的最优编码因此式子6.16显示，hMAP是使假设描述长度和给定假设下数据描述长度之和最小化的假设最小描述长度准则：,最小描述长度准则（4）,如果选择C1为假设的最优编码CH，C2为最优编码CD|h，那么hMDL=hMAP可将MDL准则想象为选择最短的方法来重新编码训练数据，其中不仅计算假设的大小，并且计算给定假设时编码数据的附加开销将MDL准则应用于决策树，如何选择假设和数据的表示C1和C2?对于C1，很自然地选择某种明确的决策树编码方法，其中描述长度随着树中节点和边的增长而增加对于C2，如果训练分类f(xi)与假设的预计相同，那么就不需要传输有关这些样例的任何信息；如果不同，则要传输更正消息,最小描述长度准则（5）,MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设上面讨论自然给出了一种处理数据过度拟合的方法Quinlan & Rivest描述了应用MDL准则选择决策树大小的几个实验，报告指出，基于MDL的方法产生的决策树的精度相当于第3章中讨论的标准树修剪方法,分类问题？,能否利用MAP解决分类问题？假设类别为Ci，其后验概率公式如何表述？如何选取判别函数？假设p(x|Ci)为高斯分布，其参数如何求取？先验概率P（Ci）如何求取？,贝叶斯最优分类器,前面我们讨论的问题是：给定训练数据，最可能的假设是什么？另一个相关的更有意义的问题是：给定训练数据，对新实例的最可能的分类是什么？显然，第二个问题的解决可以将第一个问题的结果（MAP）应用到新实例上得到，还存在更好的算法？,贝叶斯最优分类器（2）,例子考虑一个包含三个假设h1, h2, h3的假设空间。假定已知训练数据时三个假设的后验概率分别是0.4, 0.3, 0.3，因此h1为MAP假设。若一新实例x被h1分类为正，被h2和h3分类为反计算所有假设，x为正例的概率为0.4，为反例的概率为0.6因此，这时最可能的分类与MAP假设生成的分类不同矛盾！,贝叶斯最优分类器（3）,一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。如果新实例的可能分类可取某集合V中的任一值vj，那么概率P(vj|D)表示新实例分类为vj的概率新实例的最优分类为使P(vj|D)最大的vj值，贝叶斯最优分类器为： （6.18),贝叶斯最优分类器（4）,例子已知：新实例的可能分类集合为V=+,-P(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1P(h2|D)=0.3, P(-|h2)=1, P(+|h2)=0P(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0因此：,贝叶斯最优分类器（5）,贝叶斯最优分类器在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大；贝叶斯最优分类器的一个属性：它所做的分类可以对应于H中不存在的假设；使用式子6.18来分类X中的每个实例，按此定义的实例标注不一定对应于H中的任一单个假设h对实例的标注；将贝叶斯分类器看成是不同于假设空间H的另一空间H，在其上应用贝叶斯公式。H有效地包含了一组假设，它能在H中多个假设的线性组合所作的预言中进行比较。,Gibbs算法,贝叶斯最优分类器能从给定训练数据中获得最好的性能，但算法的开销很大；一个替代的、非最优的方法是Gibbs算法，定义如下：按照H上的后验概率分布，从H中随机选择假设h使用h来预言下一个实例x的分类在一定条件下，Gibbs算法的误分类率的期望值最多为贝叶斯最优分类器的两倍。确切地讲，期望值是在随机抽取的目标概念上作出的，抽取过程按照学习器假定的先验概率对概念学习问题的一个启示：如果学习器假定H上有均匀的先验概率，而且如果目标概念实际上也按该分布抽取，那么当前变型空间中随机抽取的假设对下一实例分类的期望误差最多为贝叶斯分类器的两倍,朴素贝叶斯分类器,应用的学习任务：每个实例x可由属性值的合取描述，而目标函数f(x)从某有限集合V中取值;贝叶斯方法的新实例分类目标是在给定描述实例的属性值下，得到最可能的目标值vMAP使用贝叶斯公式变化上式,(6.19),朴素贝叶斯分类器（2）,基于训练数据估计式(6.19)中的两个数据项的值估计P(vj)很容易：计算每个目标值vj出现在训练数据中的频率；估计P(a1,.,an|vj)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即,(6.20),朴素贝叶斯分类器（3）,朴素贝叶斯分类器的定义：从训练数据中估计不同P(ai|vj)项的数量比要估计P(a1,.,an|vj)项所需的量小得多；只要条件独立性得到满足，朴素贝叶斯分类vNB等于MAP分类，否则是近似；朴素贝叶斯分类器与前面已介绍的学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率）,朴素贝叶斯分类器（4）,举例表3-2提供了目标概念PlayTennis的14个训练样例，给新实例分类 根据表3-2，可以计算出上式需要的概率值P(yes)=9/14=0.64P(no)=5/14=0.36P(strong|yes)=3/9=0.33P(strong|no)=3/5=0.60.求vNBP(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206vNB=no,朴素贝叶斯分类器（5）,估计概率通过在全部事件基础上观察某事件出现的比例来估计概率当样本很小时，采用平滑技术，m-估计p是将要确定的概率的先验估计，而m是一称为等效样本大小的常量；在缺少其它信息时，选择p的一种典型的方法是均匀概率，比如某属性有k个可能值，那么p=1/k；m被称为等效样本大小的原因是：式子6.22可被解释为将n个实际的观察扩大，加上m个按p分布的虚拟样本。,(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.,举例：学习分类文本（3）,计算式注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好。,举例：学习分类文本（4）,需要估计概率项P(vi)和P(ai=wk|vi)。前一项可基于每一类在训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题再引入一个假定以减少需要估计的概率项的数量：假定单词wk出现的概率独立于单词所在的位置，即P(ai=wk|vi)=P(wk|vj)作此假定的一个主要优点在于：使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度采纳m-估计方法，即有统一的先验概率并且m等于词汇表的大小，因此,表6-2 用于学习和分类文本的朴素贝叶斯算法,Learn_Naive_Bayes_Text( Examples, V )Examples为一组文本文档以及它们的目标值。V为所有可能目标值的集合。此函数作用是学习概率项P(wk|vj)和P(vj)。收集Examples中所有的单词、标点符号以及其他记号Vocabulary在Examples中任意文本文档中出现的所有单词及记号的集合计算所需要的概率项P(vj)和P(wk|vj)对V中每个目标值vjdocsjExamples中目标值为vj的文档子集P(vj)|docsj| / |Examples|Textj将docsj中所有成员连接起来建立的单个文档n在Textj中不同单词位置的总数对Vocabulary中每个单词wknk单词wk出现在Textj中的次数P(wk|vj)(nk+1) / (n+|Vocabulary|),用于学习和分类文本的朴素贝叶斯算法（2）,Classify_Naive_Bayes_Text( Doc )对文档Doc返回其估计的目标值，ai代表在Doc中的第i个位置上出现的单词positions在Doc中的所有单词位置，它包含能在Vocabulary中找到的记号返回vNB，,应用样例,Joachims将此算法用于新闻组文章的分类每一篇文章的分类是该文章所属的新闻组名称；20个新闻组，每个新闻组有1000篇文章，共2万个文档；2/3作为训练样例，1/3进行性能测量；词汇表不包含最常用词（比如the、of）和罕见词（数据集中出现次数少于3）；分类精度由随机分类5提高到89。Lang用此算法学习目标概念“我感兴趣的新闻组文章”NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的；每天向用户展示前10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高34倍。,贝叶斯信念网,朴素贝叶斯分类器假定各个属性取值在给定目标值v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严格；贝叶斯信念网描述的是一组变量所遵从的概率分布，它通过一组条件概率来指定一组条件独立性假设；贝叶斯信念网采用联合概率分布，它允许在变量的子集间定义类条件独立性，它提供因果关系图形。因此，贝叶斯信念网提供了一种中间的方法，它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行。,贝叶斯信念网（2）,贝叶斯信念网描述了一组变量上的概率分布；考虑一任意的随机变量集合Y1.Yn，其中每个Yi可取的值集合为V(Yi)；变量集合Y的联合空间为叉乘V(Y1). V(Yn)；在此联合空间上的概率分布称为联合概率分布，联合概率分布指定了元组的每个可能的变量约束的概率；贝叶斯信念网则对一组变量描述了联合概率分布。,条件独立性,精确定义条件独立性令X, Y和Z为3个离散值随机变量，当给定Z值时X服从的概率分布独立于Y的值，称X在给定Z时条件独立于Y，即上式通常简写成P(X|Y,Z)=P(X|Z)扩展到变量集合下面等式成立时，称变量集合X1.Xl在给定变量集合Z1.Zn时条件独立于变量集合Y1.Ym条件独立性与朴素贝叶斯分类器的之间的关系,贝叶斯信念网的表示,贝叶斯信念网（简称贝叶斯网）表示一组变量的联合概率分布一般地说，贝叶斯网表示联合概率分布的方法是指定一组条件独立性假定（有向无环图）以及一组局部条件概率集合下页图，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继”每个变量有一个条件概率表，描述了该变量在给定其立即前驱时的概率分布,贝叶斯信念网的表示（2）,对网络变量的元组赋以所希望的值(y1.yn)的联合概率计算公式如下：所有变量的局部条件概率表以及由网络所描述的一组条件独立假定，描述了该网络的整个联合概率分布,贝叶斯信念网的推理,可以用贝叶斯网在给定其它变量的观察值时推理出某些目标变量的值由于所处理的是随机变量，所以一般不会赋予目标变量一个确切的值真正需要推理的是目标变量的概率分布，它指定了在给予其他变量的观察值条件下，目标变量取每一个可能值的概率在网络中所有其它变量都确切知道的情况下，这一推理步骤很简单一般来说，贝叶斯网络可用于在知道某些变量的值或分布时计算网络中另一部分变量的概率分布,学习贝叶斯信念网,从训练数据中学到贝叶斯信念网，有多种讨论的框架：网络结构可以预先给出，或由训练数据中得到所有的网络变量可以直接从每个训练样例中观察到，或某些变量不能观察到如果网络结构已知且变量可以从训练样例中完全获得，那么得到条件概率表就比较简单；如果网络结构已知，但只有一部分变量值能在数据中观察到，学习问题就困难多了。这类似于在人工神经网络中学习隐层单元的权值；Russell（1995）提出了一个简单的梯度上升过程以学习条件概率表中的项，相当于对表项搜索极大似然假设。,贝叶斯网的梯度上升训练,令wijk代表条件概率表的一个表项，即在给定父节点Ui取值uik时，网络变量Yi值为yij的概率例如图6-3，wijk为最右上方的表项，那么Yi为变量Campfire，Ui是其父节点的元组，yij=True，且uik=,贝叶斯网的梯度上升训练（2）,lnP(D|h)的梯度由对每个wijk求导数得到例如，为计算图6-3中表右上方的表项的lnP(D|h)的导数，需要对D中每个训练样例d计算P(Campfire=True, Storm=False, BusTourGroup=False|d)当训练样例中无法观察到这些变量时，这些概率可用标准的贝叶斯网从d中观察到的变量中推理得到这些量能够很容易地从贝叶斯网推理过程中得到，几乎不需要附加的开销,(6.25),贝叶斯网的梯度上升训练（3）,式子6.25的推导用Ph(D)来表示P(D|h)假定在数据集D中的各样例d都是独立抽取的,贝叶斯网的梯度上升训练（4）,更新权值归一化处理，保持在区间0,1之间，且jwijk对所有i,k保持为1这个算法只保证找到局部最优解，替代梯度上升的一个算法是EM算法,学习贝叶斯网的结构,如果贝叶斯网的结构未知，那么需要学习贝叶斯网的结构Cooper & Herskovits提出了一个贝叶斯评分尺度，以便从不同网络中进行选择Cooper & Herskovits提出了算法K2，启发式算法，用于在数据完全可观察时学习网络结构基于约束的学习贝叶斯网络结构：从数据中推导出独立和相关的关系，然后用这些关系来构造贝叶斯网,EM算法,EM（ Expectation Maximization algorithm）期望最大化算法；处理存在未观察到变量的问题比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值EM算法可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的形式已知用于马尔可夫模型的训练，估计HMM的参数；可用于混合模型的参数估计（如GMM）用于贝叶斯网的训练聚类分析方法,单变量数据样本,Sampling,极大似然（ML）,Sampling,给定 x, 它是 和 2 函数,目的是 将其最大化.,取对数的极大似然函数,将该最大化变换为对数形式,只需使,且,对数似然函数求极大值,对数似然函数求极大值,数据缺失,Sampling,Missing data,E-Step,令,为tth迭代的估计值,E-Step,令,为tth迭代的估计值,M-Step,令,为tth迭代的估计值,混合模型,如果采集的数据是属于混合模型情况；可描述成以下形式：,且,混合模型,令 yi1, M 代表数据源于那个模型.,混合模型,其中 yi1, M代表数据源于那个模型.,混合模型,混合模型,混合模型,给定 x 和 , y 的条件概率可被计算.,完整数据的似然函数,期 望,g: 估计,期 望,g: 估计,期 望,当yi l 为0,期 望,期 望,期 望,1,最大化,给定初始估计值 g,需要找到合适参数 , 使得期望最大化,实际上, 就是反复迭代.,混合高斯模型,高斯模型为 d 维，第 j个模型 可表示为:,该GMM有 M 个模型:,目 标,混合模型,其中，,最大化:,目 标,混合模型,其中,最大化:,仅与 l 相关.,仅与 l 相关.,求 l,由于有 l的约束,为典型求条件极值问题，故引入拉格朗日乘子 , 并构成以下等式.,求l,1,N,1,求 l,求 l,Only need to maximizethis term,考虑 GMM,unrelated,求 l,Only need to maximizethis term,因此, 需最大化:,unrelated,为什么?,主要是基于矩阵代数知识.,求 l,因此, 需最大化:,小结,针对高斯混合模型 GMM的EM算法,给定初始估计值 g, 寻找新的参数 new 如下：,不收敛,估计k个高斯分布的均值,考虑D是一个实例集合，它由k个不同正态分布的混合所得分布生成每个实例使用一个两步骤的过程形成：首先，随机选择k个正态分布中的一个其次，随机变量xi按照此选择的分布生成考虑一个简单情形：单个正态分布的选择基于均匀的概率进行，且k个正态分布有相同的方差学习任务：输出一个假设h=，描述k个分布中每个分布的均值，找到极大似然假设，即使得p(D|h)最大化的假设,估计k个高斯分布的均值（2）,当给定从一个正态分布中抽取的数据实例x1,.,xm时，很容易计算该分布的均值的极大似然假设，它是前面介绍的最小误差平方假设的一个特例，表示如下然而，现在的问题涉及k个不同正态分布，而且不知道哪个实例是哪个分布产生的。这是一个涉及隐藏变量的典型例子；对于图6-4的例子，每个实例的完整描述是三元组，其中xi是第i个实例的观测值，zi1和zi2表示哪个正态分布被用来产生xi，是隐藏变量,(6.27,28),图6-4,由两个具有相等方差的正态分布混合生成的例子,估计k个高斯分布的均值（3）,如果zi1和zi2的值可知，就可用式子6.27来解决，否则使用EM算法EM算法根据当前假设，不断地再估计隐藏变量zij的期望值，然后用这些隐藏变量的期望值重新计算极大似然假设以图6-4为例，先将假设初始化为h=计算每个隐藏变量zij的期望值Ezij，假定当前假设h=成立计算一个新的极大似然假设h=，假定每个隐藏变量zij所取值是第一步得到的期望值Ezij。将假设替换为h=，然后循环,两个步骤的计算式,Ezij正是实例xi由第j个正态分布生成的概率第二步，使用第一步得到的Ezij来导出一新的极大似然假设,两个步骤的计算式（2）,第二步中的表达式类似于式6.28，只是变成了加权样本均值EM算法的要点：当前的假设用于估计未知变量，而这些变量的期望值再被用于改进假设可以证明：算法的每一次循环中，EM算法能使似然P(D|h)增加，除非P(D|h)达到局部最大，因此算法收敛到一个局部最大似然假设,EM算法的一般表述,EM算法可用于许多问题框架：其中需要估计一组描述基准概率分布的参数，只给定了由此分布产生的全部数据中能观察到的一部分。上面的二均值问题中，感兴趣的参数是=，全部数据是三元组，而只能观察到xi一般地，令待估计参数是，全部数据Y=XZ，其中X是可观察数据，Z是未观察数据。Z可看作一个随机变量，它的概率分布依赖于参数和已知数据XY也是一个随机变量，因为它由随机变量Z定义,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