P4 贝叶斯学习(2016)

1、第四部分第四部分 贝叶斯学习贝叶斯学习 参考书目参考书目 lTom M.Mitchell 机器学习机器学习 机械工业出版社机械工业出版社 l李连文李连文 郭海鹏郭海鹏 贝叶斯网络引论贝叶斯网络引论 科学出版社科学出版社 0 两个示例两个示例 树后有几只箱子？树后有几只箱子？ 可能的情况可能的情况 自然语言的二义性自然语言的二义性 lThe girl saw the boy with a telescope. lThe girl saw-with-a-telescope the boy. lThe girl saw the-boy-with-a-telescope. 1 贝叶斯公式贝叶斯公式 )

2、( )()|( )|( DP hPhDP DhP 先验概率和后验概率先验概率和后验概率 lP(h)：h的的先验概率先验概率。 表示在没有训练数据前表示在没有训练数据前 假设假设h拥有的拥有的初始概率初始概率； l先验概率反映了关于先验概率反映了关于h是一正确假设的机会的是一正确假设的机会的 背景知识。如果没有这一先验知识，可以简单背景知识。如果没有这一先验知识，可以简单 地将地将每一候选假设赋予相同的先验概率每一候选假设赋予相同的先验概率； lP(D)：训练数据：训练数据D的先验概率，的先验概率，P(D|h)表示假表示假 设设h成立时成立时D的概率；的概率； lP(h|D)： h的的后验概率后

3、验概率。表示给定。表示给定D时时h的成的成 立的概率。立的概率。 贝叶斯公式贝叶斯公式 l提供了从先验概率提供了从先验概率P(h)、P(D)和和P(D|h)计算后计算后 验概率验概率P(h|D)的方法，的方法， lP(h|D)随着随着P(h)和和P(D|h)的增长而增长，随着的增长而增长，随着 P(D)的增长而减少的增长而减少。 l即如果即如果D独立于独立于h时被观察到的可能性越大，时被观察到的可能性越大， 那么那么D对对h的支持度越小。的支持度越小。 极大后验假设（极大后验假设（MAP） l在候选假设集合在候选假设集合H中寻找给定数据中寻找给定数据D时，可时，可 能性最大的假设能性最大的假设

4、h； l确定确定MAP的方法是用贝叶斯公式计算每个的方法是用贝叶斯公式计算每个 候选假设的后验概率。候选假设的后验概率。 )()|(maxarg )( )()|( maxarg)|(maxarghPhDP DP hPhDP DhPh HhHhHh MAP 极大似然假设（极大似然假设（ML） l在某些情况下，可在某些情况下，可假定假定H中每个假设有相同中每个假设有相同 的先验概率的先验概率。 lP(D|h)常被称为给定常被称为给定h时数据时数据D的的似然度似然度， 而使而使P(D|h)最大的假设被称为极大似然假最大的假设被称为极大似然假 设；设； l假设空间假设空间H可扩展为任意的互斥命题集合，

5、可扩展为任意的互斥命题集合， 只要这些命题的概率之和为只要这些命题的概率之和为1。 )|(maxarghDPh Hh ML 示例示例- -医疗诊断医疗诊断 l有两个可选的假设：病人有癌症、病人无癌症 l可用数据来自化验结果：正+和负- l先验知识： l在所有人口中，患病率是0.008 l对确实有病的患者的化验准确率为98%， l对确实无病的患者的化验准确率为97% 先验知识的概率表示先验知识的概率表示 P(cancer) = 0.008, P(cancer) = 0.992 P(+|cancer) = 0.98, P(-|cancer) =0.02 P(+|cancer) = 0.03, P(

6、-|cancer) = 0.97 示例示例 l假定有一个病人，化验结果为正，是否应将病人断定 为有癌症？ l求后验概率P(cancer|+)和P(cancer|+) l极大后验假设 lP(+|cancer)P(cancer)=0.0078 lP(+|cancer)P(cancer)=0.0298 lhMAP=cancer l确切的后验概率：上面结果的归一化 P(canner|+)=0.0078/(0.0078+0.0298)=0.21 lP(cancer|-)=0.79 贝叶斯推理贝叶斯推理 贝叶斯推理的结果很大程度上依赖于先验概率贝叶斯推理的结果很大程度上依赖于先验概率 ，同时不是完全接受或

7、拒绝假设，只是在观察，同时不是完全接受或拒绝假设，只是在观察 到较多的数据后增大或减小了假设的可能性。到较多的数据后增大或减小了假设的可能性。 基本概率公式表基本概率公式表 乘法规则：乘法规则：(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) 全概率法则：如果事件全概率法则：如果事件A1.An互斥，且满足互斥，且满足 则则 n i ii APABPBP 1 )()|()( 1 1 n i i AP)( 贝叶斯法则贝叶斯法则 l贝叶斯法则为计算给定训练数

8、据下任一假设的 后验概率提供了原则性方法，因此可以直接将 其作为一个基本的学习方法：计算每个假设的 概率，再输出其中概率最大的。 2 极大似然与最小误差平方假设极大似然与最小误差平方假设 某些学习算法即使没有显式地使用贝叶斯规则，某些学习算法即使没有显式地使用贝叶斯规则， 或以某种形式计算概率，但它们或以某种形式计算概率，但它们输出的结果符合输出的结果符合 贝叶斯原理贝叶斯原理，是一个，是一个MAP假设；假设； 在特定前提下，任一学习算法如果使输出的假设在特定前提下，任一学习算法如果使输出的假设 预测和训练数据之间的误差平方和最小化，它将预测和训练数据之间的误差平方和最小化，它将 输出一极大似

9、然假设输出一极大似然假设； 对于许多神经网络和曲线拟合的方法，如果它们对于许多神经网络和曲线拟合的方法，如果它们 试图在训练数据上使误差平方和最小化，此结论试图在训练数据上使误差平方和最小化，此结论 提供了提供了基于贝叶斯的理论依据基于贝叶斯的理论依据。 最小误差平方假设最小误差平方假设 学习器学习器L工作在工作在实例空间实例空间X和和假设空间假设空间H上上 ，H中的假设为中的假设为X上定义的某种实数值函上定义的某种实数值函 数；数； L面临的问题是学习一个从面临的问题是学习一个从H中抽取出的中抽取出的 未知目标函数未知目标函数f，给定，给定m个训练样例的集个训练样例的集 合，每个样例的目标值

10、被某随机噪声干扰合，每个样例的目标值被某随机噪声干扰 ，此随机噪声服从正态分布；，此随机噪声服从正态分布； 最小误差平方假设最小误差平方假设 每个训练样例是序偶每个训练样例是序偶 ，di=f(xi)+ei， ei是代表噪声的随机变量，假定是代表噪声的随机变量，假定ei的值是的值是 独立抽取的，并且它们的分布服从独立抽取的，并且它们的分布服从0均值均值 的正态分布；的正态分布； 学习器的任务是在所有假设有相等的先验学习器的任务是在所有假设有相等的先验 概率前提下，输出极大似然假设（即概率前提下，输出极大似然假设（即 MAP假设）。假设）。 最小误差平方假设最小误差平方假设 最小误差平方假设最小误

11、差平方假设 l假定有一固定的训练实例集合，因此只考假定有一固定的训练实例集合，因此只考 虑相应的目标值序列虑相应的目标值序列D=，且，且 di=f(xi)+ei。 l假定训练样例是相互独立的，给定假定训练样例是相互独立的，给定h时，时， 可将可将P(D|h)写成各写成各p(di|h)的积：的积： m i i Hh ML hdph 1 )|(maxarg 最小误差平方假设最小误差平方假设 l如果误差如果误差ei服从服从0均值和未知方差均值和未知方差 2的正态的正态 分布，那么每个分布，那么每个di服从均值为服从均值为f(xi)，方差不，方差不 变的正态分布。因此，变的正态分布。因此，p(di|h

12、)可写为方差可写为方差 2、均值、均值f(xi)的正态分布的正态分布； l概率概率di的表达式是在的表达式是在h为目标函数为目标函数f的正确描的正确描 述条件下的，所以述条件下的，所以替换替换 =f(xi)=h(xi)。 最小误差平方假设最小误差平方假设 m i ii Hh m i ii Hh m i ii Hh )x(hd( m i Hh m i )d( Hh ML )x(hd(minarg )x(hd(maxarg )x(hd(lnmaxarg emaxarg emaxargh ii i 1 2 1 2 2 1 2 22 2 1 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2

13、1 2 2 2 2 最小误差平方假设最小误差平方假设 上式说明了极大似然假设等价于使训练值上式说明了极大似然假设等价于使训练值 和假设预测值之间误差的平方和最小的那和假设预测值之间误差的平方和最小的那 个假设。个假设。 这个结论的前提是：训练值等于真实目标这个结论的前提是：训练值等于真实目标 值加上随机噪声，其中随机噪声从一个均值加上随机噪声，其中随机噪声从一个均 值为值为0的正态分布中独立抽取。的正态分布中独立抽取。 采用正态分布的合理性采用正态分布的合理性 p数学计算的简洁性；数学计算的简洁性； p对许多物理系统的噪声都有良好的近似；对许多物理系统的噪声都有良好的近似； p中心极限定理显示

14、，足够多的独立同分布随机中心极限定理显示，足够多的独立同分布随机 变量的和服从正态分布；变量的和服从正态分布； p由许多独立同分布的因素的和所生成的噪声将由许多独立同分布的因素的和所生成的噪声将 成为正态分布。成为正态分布。 3 贝叶斯最优分类器贝叶斯最优分类器 l给定训练数据，最可能的假设是什么？给定训练数据，最可能的假设是什么？ l给定训练数据，对新实例的最可能的分类是什给定训练数据，对新实例的最可能的分类是什 么？么？ l第二个问题的解决可以将第一个问题的结果（第二个问题的解决可以将第一个问题的结果（ MAP）应用到新实例上得到；）应用到新实例上得到； l还存在更好的算法还存在更好的算法

15、. 一个例子一个例子 l一个包含三个假设一个包含三个假设h1, h2, h3的假设空间；的假设空间； l假定已知训练数据时三个假设的后验概率分别是假定已知训练数据时三个假设的后验概率分别是 0.4, 0.3, 0.3，因此，因此h1为为MAP假设。假设。 l若一新实例若一新实例x被被h1分类为正，被分类为正，被h2和和h3分类为反；分类为反； l计算所有假设，计算所有假设，x为正例的概率为为正例的概率为0.4，为反例的，为反例的 概率为概率为0.6； l这时最可能的分类与这时最可能的分类与MAP假设生成的分类不同假设生成的分类不同。 贝叶斯最优分类器贝叶斯最优分类器 l一般而言，一般而言，新实

16、例的最可能分类可通过合新实例的最可能分类可通过合 并所有假设的预测得到，权重为其后验概并所有假设的预测得到，权重为其后验概 率。率。 l如果新实例的可能分类可取某集合如果新实例的可能分类可取某集合V中的中的 任一值任一值vj，那么概率，那么概率P(vj|D)为新实例分类为新实例分类 为为vj的概率的概率 Hh iijj i DhPhvPDvP)|()|()|( 贝叶斯最优分类器贝叶斯最优分类器 u新实例的最优分类为使P(vj|D)最大的vj值 Hh iij Vv i j DhPhvP)|()|(maxarg 贝叶斯最优分类器贝叶斯最优分类器-示例示例 u新实例的可能分类集合为新实例的可能分类集

17、合为V=+,- uP(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1 uP(h2|D)=0.3, P(-|h2)=1, P(+|h2)=0 uP(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0 40.)|()|( Hh ii i DhPhP Hh iij Hhv i ij DhPhvP)|()|(maxarg , 60.)|()|( Hh ii i DhPhP 贝叶斯最优分类器贝叶斯最优分类器 使用相同的假设空间和相同的先验概率，使用相同的假设空间和相同的先验概率， 没有其他方法能比其平均性能更好。贝叶没有其他方法能比其平均性能更好。贝叶 斯最优分类器在给定可用

18、数据、假设空间斯最优分类器在给定可用数据、假设空间 及这些假设的先验概率下使新实例被正确及这些假设的先验概率下使新实例被正确 分类的可能性达到最大分类的可能性达到最大 Gibbs算法算法 贝叶斯最优分类器能从给定训练数据中获贝叶斯最优分类器能从给定训练数据中获 得最好的性能，但算法的开销很大。得最好的性能，但算法的开销很大。 一个替代的、非最优的方法是一个替代的、非最优的方法是Gibbs算法：算法： p按照按照H上的后验概率分布，从上的后验概率分布，从H中随机选择中随机选择 假设假设h； p使用使用h来预言下一个实例来预言下一个实例x的分类。的分类。 Gibbs算法算法 l在一定条件下，在一定

19、条件下，Gibbs算法的误分类率的期算法的误分类率的期 望值最多为贝叶斯最优分类器的望值最多为贝叶斯最优分类器的两倍两倍。确。确 切地讲，期望值是在随机抽取的目标概念切地讲，期望值是在随机抽取的目标概念 上作出的，抽取过程按照学习器假定的先上作出的，抽取过程按照学习器假定的先 验概率。验概率。 朴素贝叶斯分类器朴素贝叶斯分类器(Naive Bayes Classifier) l学习任务：学习任务：每个实例每个实例x可由可由属性值的合取属性值的合取描述描述 ，而目标函数，而目标函数f(x)从某有限集合从某有限集合V中取值。中取值。 l贝叶斯方法的新实例分类目标是在给定描述贝叶斯方法的新实例分类目

20、标是在给定描述 实例的属性值实例的属性值下，得到最可能的目下，得到最可能的目 标值标值vMAP： ),.,|(maxarg nj v MAP aavPv j 1 朴素贝叶斯分类器朴素贝叶斯分类器 )()|,.,(maxarg ),.,( )()|,.,( maxarg jjn Vv n jjn Vv MAP vPvaaP aaP vPvaaP v j j 1 1 1 朴素贝叶斯分类器朴素贝叶斯分类器 l基于训练数据估计两个数据项的值基于训练数据估计两个数据项的值 估计估计P(vj)很容易：计算每个目标值很容易：计算每个目标值vj出现在训出现在训 练数据中的频率。练数据中的频率。 u估计估计P(

21、a1,.an|vj)遇到数据稀疏问题，除非有一遇到数据稀疏问题，除非有一 个非常大的训练数据集，否则无法获得可靠的个非常大的训练数据集，否则无法获得可靠的 估计。估计。 朴素贝叶斯分类器朴素贝叶斯分类器 u朴素贝叶斯分类器引入一个简单的假定避免朴素贝叶斯分类器引入一个简单的假定避免 数据稀疏问题，数据稀疏问题，在给定目标值时，属性值之在给定目标值时，属性值之 间相互条件独立间相互条件独立 u朴素贝叶斯分类器的定义：朴素贝叶斯分类器的定义： i jij Vv NB vaPvPv j )|()(maxarg i jijn vaPvaaP)|()|,.,( 1 朴素贝叶斯分类器朴素贝叶斯分类器 l从

22、训练数据中估计不同从训练数据中估计不同P(ai|vj)项的数量比要估项的数量比要估 计计P(a1,.,an|vj)项所需的量小得多；项所需的量小得多； l只要条件独立性得到满足，朴素贝叶斯分类只要条件独立性得到满足，朴素贝叶斯分类 vNB等于等于MAP分类，否则是近似；分类，否则是近似； l朴素贝叶斯分类器与其他已介绍的学习方法的朴素贝叶斯分类器与其他已介绍的学习方法的 一个区别：没有明确地搜索可能假设空间的过一个区别：没有明确地搜索可能假设空间的过 程（假设的形成不需要搜索，只是简单地计算程（假设的形成不需要搜索，只是简单地计算 训练样例中不同数据组合的出现频率）。训练样例中不同数据组合的出

23、现频率）。 示例示例 DayOutlookTemperatureHumidityWindPlay Tennis D1SunnyHotHighWeakNo D2SunnyHotHighStrongNo D3OvercastHotHighWeakYes D4RainMildHighWeakYes D5RainCoolNormalWeakNo D6RainCoolNormalStrongYes D7OvercastCoolNormalStrongYes D8SunnyMildHighWeakNo D9SunnyCoolNormalWeakYes D10RainMildNormalWeakYes D1

24、1SunnyMildNormalStrongYes D12OvercastMildHighStrongYes D13OvercastHotNormalWeakYes D14RainMildHighStrongNo 示例示例 )|()|()|()|()(maxarg)|()(maxarg , jjjjj noyesv i jij noyesv NB vstrongPvhighPvcoolPvsunnyPvPvaPvPv jj u表中提供了目标概念表中提供了目标概念Play Tennis的的14个训练样例，给新个训练样例，给新 实例实例分类分类 u计算出上式需要的概率值计算出上式需要的概率值 lP

25、(yes)=9/14=0.64 lP(no)=5/14=0.36 lP(strong|yes)=3/9=0.33 lP(strong|no)=3/5=0.60 l. )|()|()|()|()(maxarg )|()(maxarg , , jjjjj noyesv i jij noyesv NB vstrongPvhighPvcoolPvsunnyPvP vaPvPv j j 示例示例 uvNB lP(yes) P(sunny|yes) P(cool|yes) P(high|yes) P(strong|yes)=0.0053 lP(no) P(sunny|no) P(cool|no) P(hi

26、gh|no) P(strong|no)=0.0206 lvNB =no u归一化归一化 0.0206/(0.0206+0.0053)=0.795 4 EM算法算法 在许多实际的学习问题框架中，相关实例特征在许多实际的学习问题框架中，相关实例特征 中只有一部分可观察到中只有一部分可观察到 已有许多方法被提出来处理存在未观察到变量已有许多方法被提出来处理存在未观察到变量 的问题的问题 l如果某些变量有时能观察到，有时不能，那么可以如果某些变量有时能观察到，有时不能，那么可以 用观察到该变量的实例去预测未观察到的实例中的用观察到该变量的实例去预测未观察到的实例中的 变量的值变量的值 EM算法算法 u

27、EM算法是存在隐含变量时广泛使用的一种学算法是存在隐含变量时广泛使用的一种学 习方法，可用于变量的值从来没有被直接观察习方法，可用于变量的值从来没有被直接观察 到的情形，只要这些变量所遵循的概率分布的到的情形，只要这些变量所遵循的概率分布的 一般形式已知一般形式已知 用于贝叶斯网的训练用于贝叶斯网的训练 用于马尔可夫模型的训练用于马尔可夫模型的训练 示例：估计示例：估计k k个高斯分布的均值个高斯分布的均值 n考虑考虑D是一个实例集合，它由是一个实例集合，它由k个不同正态个不同正态 分布的混合所得分布生成分布的混合所得分布生成 n每个实例使用一个两步骤的过程形成：每个实例使用一个两步骤的过程形

28、成： 首先，随机选择首先，随机选择k个正态分布中的一个个正态分布中的一个 其次，随机变量其次，随机变量xi按照此选择的分布生成按照此选择的分布生成 示例示例 u考虑一个简单情形：考虑一个简单情形： 单个正态分布的选择基于均匀的概率进行，且单个正态分布的选择基于均匀的概率进行，且k 个正态分布有相同的方差；个正态分布有相同的方差； 学习任务：输出一个假设学习任务：输出一个假设h=，描述，描述k 个分布中每个分布的均值，找到极大似然假设个分布中每个分布的均值，找到极大似然假设 ，即使得，即使得p(D|h)最大化的假设。最大化的假设。 隐藏变量隐藏变量 u当给定从一个正态分布中抽取的数据实例当给定从

29、一个正态分布中抽取的数据实例 x1,.,xm时，很容易计算该分布的均值的时，很容易计算该分布的均值的 极大似然假设：极大似然假设： u涉及涉及k个不同正态分布，而且不知道哪个实个不同正态分布，而且不知道哪个实 例是哪个分布产生的例是哪个分布产生的。这是一个涉及。这是一个涉及隐藏隐藏 变量变量的典型例子。的典型例子。 m i i m i iML x m x 11 2 1 )(minarg 两个正态分布的混合两个正态分布的混合 示例示例 u每个实例的完整描述是三元组每个实例的完整描述是三元组， 其中其中xi是第是第i个实例的观测值，个实例的观测值，zi1和和zi2表示表示 哪个正态分布被用来产生哪

30、个正态分布被用来产生xi，是隐藏变量。，是隐藏变量。 uEM算法根据当前假设算法根据当前假设，不断地再，不断地再 估计隐藏变量估计隐藏变量zij的期望值，然后用这些隐藏的期望值，然后用这些隐藏 变量的期望值重新计算极大似然假设。变量的期望值重新计算极大似然假设。 示例示例 n先将假设初始化为先将假设初始化为h= n计算每个隐藏变量计算每个隐藏变量zij的期望值的期望值Ezij，假定当前，假定当前 假设假设h=成立；成立； n计算一个新的极大似然假设计算一个新的极大似然假设h= ，假，假 定每个隐藏变量定每个隐藏变量zij所取值是第一步得到的期望所取值是第一步得到的期望 值值E zij。将假设替

31、换为。将假设替换为h= ，然后循，然后循 环。环。 示例：示例：步骤步骤1 Ezij正是实例正是实例xi由第由第j个正态分布生成的概个正态分布生成的概 率率 2 1 2 1 2 1 2 1 2 2 2 2 n x x n ni ji ij ni ji e e xxp xxp zE )( )( )|( )|( 示例：示例：步骤步骤2 使用第一步得到的使用第一步得到的Ezij来导出一新的极大来导出一新的极大 似然假设似然假设 m i ij m i iij j zE xzE 1 1 示例示例 n第二步中的表达式类似于单一正态分布均第二步中的表达式类似于单一正态分布均 值的计算，只是变成了加权样本均值

32、。值的计算，只是变成了加权样本均值。 nEM算法的要点：算法的要点：当前的假设用于估计未知当前的假设用于估计未知 变量，而这些变量的期望值再被用于改进变量，而这些变量的期望值再被用于改进 假设。假设。 n可以证明：算法的每一次循环中，可以证明：算法的每一次循环中，EM算法算法 能使似然能使似然P(D|h)增加，除非增加，除非P(D|h)达到局部达到局部 最大。因此算法收敛到一个局部最大似然最大。因此算法收敛到一个局部最大似然 假设。假设。 EM算法的一般表述算法的一般表述 l一般地，令待估计参数是一般地，令待估计参数是 ，全部数据，全部数据 Y=X Z，其中，其中X是可观察数据，是可观察数据，

33、Z是未观察是未观察 数据。数据。 lZ可看作一个随机变量，它的概率分布依赖可看作一个随机变量，它的概率分布依赖 于参数于参数 和已知数据和已知数据X。 lY也是一个随机变量，因为它由随机变量也是一个随机变量，因为它由随机变量Z 定义。定义。 EM算法的一般表述算法的一般表述 nEM算法通过搜寻使算法通过搜寻使ElnP(Y|h)最大的最大的h来寻找来寻找 极大似然假设极大似然假设h，其合理性是：，其合理性是： lP(Y|h)是给定假设是给定假设h下全部数据下全部数据Y的似然度，因此找到的似然度，因此找到 使得这个值最大的使得这个值最大的h是合理的；是合理的； l对数对数lnP(Y|h)最大化也使

34、最大化也使P(Y|h)最大化；最大化； l由于由于Y是一个随机变量，因此是一个随机变量，因此P(Y|h)无法计算，转而计无法计算，转而计 算它的期望值算它的期望值ElnP(Y|h)； nY的概率分布由待估计的参数决定，的概率分布由待估计的参数决定，EM算法使用算法使用 当前假设当前假设h代替实际参数，来估计代替实际参数，来估计Y的概率分布。的概率分布。 EM算法的一般形式算法的一般形式 u定义函数定义函数 Q(h|h)=ElnP(Y|h)|h,X EM算法的一般形式算法的一般形式 u重复下面的步骤，直至收敛重复下面的步骤，直至收敛 l估计估计(Expectation)步骤：使用当前假设步骤：使

35、用当前假设h和观和观 察到的数据察到的数据X来估计来估计Y上的概率分布以计算上的概率分布以计算 Q(h|h): Q(h|h)ElnP(Y|h)|h,X l最大化最大化(Maximization)步骤：将假设步骤：将假设h替换为使替换为使 Q函数最大化的假设函数最大化的假设h: hargmaxhQ(h|h) n当函数当函数Q连续时，连续时，EM算法收敛到似然函数算法收敛到似然函数 P(Y|h)的一个不动点，它保证收敛到一个局的一个不动点，它保证收敛到一个局 部最大值。部最大值。 K均值算法推导均值算法推导 u问题框架问题框架 要估计要估计k个正态分布的均值个正态分布的均值 = 观察到的数据是观察

36、到的数据是X= 隐藏变量隐藏变量Z=表示表示k个正态分布中哪个正态分布中哪 一个生成一个生成xi K均值算法推导均值算法推导 u单个实例的概率单个实例的概率 k j jiij xz ikiii ehzzxphyp 1 2 2 2 1 2 1 2 1 )( ) |,.,() |( K均值算法推导均值算法推导 u所有实例的概率的对数所有实例的概率的对数 m i k j jiij m i i m i i xz hyp hyphYP 11 2 2 2 1 1 2 1 2 1 )(ln ) |(ln ) |(ln) |(ln K均值算法推导均值算法推导 u计算期望值计算期望值 m i k j jiij

37、m i k j jiij xzE xzEhYPE 11 2 2 2 11 2 2 2 2 1 2 1 2 1 2 1 )(ln )(ln)|(ln K均值算法推导均值算法推导 u求使求使Q函数最大的假设函数最大的假设 m i k j j iij h m i k j j iij h h xzEminarg xzElnmaxarg)h| h(Qmaxarg 11 2 11 2 22 2 1 2 1 K均值算法推导均值算法推导 u解上式得到解上式得到 u其中其中 m i ij m i iij j zE xzE 1 1 k n )x( )x( ij ji ji e e zE 1 2 1 2 2 1 2

38、 2 2 5 Bayes网与网与Markov链链 n条件独立性条件独立性 令令X, Y和和Z为为3个离散值随机变量，当给定个离散值随机变量，当给定Z 值时值时X服从的概率分布独立于服从的概率分布独立于Y的值，称的值，称X在在 给定给定Z时条件独立于时条件独立于Y，即，即 简写：简写：P(X|Y,Z)=P(X|Z) )|(),|(, kikjikji zZxXPzZyYxXPzyx 条件独立性条件独立性 u变量集合的条件独立性变量集合的条件独立性 下面等式成立时，称变量集合下面等式成立时，称变量集合X1.Xl在给定变量集在给定变量集 合合Z1.Zn时条件独立于变量集合时条件独立于变量集合Y1.Ym ).|.().,