模式识别课程讲义李君宝概率密函数估计学时学习教案.pptx

《模式识别课程讲义李君宝概率密函数估计学时学习教案.pptx》由会员分享，可在线阅读，更多相关《模式识别课程讲义李君宝概率密函数估计学时学习教案.pptx（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1模式识别课程讲义李君宝概率密函数估计学模式识别课程讲义李君宝概率密函数估计学时时第一页，编辑于星期二：点 五十一分。引言引言参数估计参数估计正态分布的参数估计正态分布的参数估计非参数估计非参数估计EM算法算法(期望最大化算法期望最大化算法)本章小结本章小结第1页/共70页第二页，编辑于星期二：点 五十一分。引言引言 第2页/共70页第三页，编辑于星期二：点 五十一分。【引言】贝叶斯决策公式贝叶斯决策公式 第3页/共70页第四页，编辑于星期二：点 五十一分。【引言】算法基本步骤算法基本步骤第4页/共70页第五页，编辑于星期二：点 五十一分。【引言】存在的问题：存在的问题：第5页/共70页

2、第六页，编辑于星期二：点 五十一分。【引言】问题的解决问题的解决第6页/共70页第七页，编辑于星期二：点 五十一分。【引言】参数估计的分类参数估计的分类第7页/共70页第八页，编辑于星期二：点 五十一分。【引言】参数估计的基本概念参数估计的基本概念第8页/共70页第九页，编辑于星期二：点 五十一分。参数估计参数估计 第9页/共70页第十页，编辑于星期二：点 五十一分。【参数估计】最大似然估计最大似然估计贝叶斯估计贝叶斯估计贝叶斯学习贝叶斯学习第10页/共70页第十一页，编辑于星期二：点 五十一分。【最大似然估计】基本假设基本假设第11页/共70页第十二页，编辑于星期二：点 五十一分。【最大似然

3、估计】基本概念基本概念第12页/共70页第十三页，编辑于星期二：点 五十一分。【最大似然估计】基本概念基本概念第13页/共70页第十四页，编辑于星期二：点 五十一分。【最大似然估计】基本原理基本原理第14页/共70页第十五页，编辑于星期二：点 五十一分。【最大似然估计】估计量估计量估计值估计值 第15页/共70页第十六页，编辑于星期二：点 五十一分。【最大似然估计】一元参数一元参数第16页/共70页第十七页，编辑于星期二：点 五十一分。【最大似然估计】多元参数多元参数第17页/共70页第十八页，编辑于星期二：点 五十一分。【最大似然估计】例子（梯度法不适合）：不成功！不成功！第18页/共70页

4、第十九页，编辑于星期二：点 五十一分。【贝叶斯估计】采用最小风险贝叶斯决策采用最小风险贝叶斯决策第19页/共70页第二十页，编辑于星期二：点 五十一分。【贝叶斯估计】第20页/共70页第二十一页，编辑于星期二：点 五十一分。【举例】假设假设结论：结论：第21页/共70页第二十二页，编辑于星期二：点 五十一分。【贝叶斯估计】第22页/共70页第二十三页，编辑于星期二：点 五十一分。【贝叶斯学习】第23页/共70页第二十四页，编辑于星期二：点 五十一分。【三种方法总结】第24页/共70页第二十五页，编辑于星期二：点 五十一分。【三种方法总结】第25页/共70页第二十六页，编辑于星期二：点 五十一分

5、。正态分布的参数估计正态分布的参数估计 第26页/共70页第二十七页，编辑于星期二：点 五十一分。【最大似然估计】基本假设基本假设第27页/共70页第二十八页，编辑于星期二：点 五十一分。【最大似然估计】单元正态分布：多元正态分布：最大似然估计方程：其中第28页/共70页第二十九页，编辑于星期二：点 五十一分。【贝叶斯估计】第29页/共70页第三十页，编辑于星期二：点 五十一分。【贝叶斯估计】第30页/共70页第三十一页，编辑于星期二：点 五十一分。非参数估计非参数估计 第31页/共70页第三十二页，编辑于星期二：点 五十一分。【基本思想】第32页/共70页第三十三页，编辑于星期二：点 五十一

6、分。n n令令令令R R是包含样本点是包含样本点是包含样本点是包含样本点x x的一个区域，其体积为的一个区域，其体积为的一个区域，其体积为的一个区域，其体积为V V，设，设，设，设有有有有n n个训练样本，其中有个训练样本，其中有个训练样本，其中有个训练样本，其中有k k个落在区域个落在区域个落在区域个落在区域R R中，则可对概中，则可对概中，则可对概中，则可对概率密度作出一个估计：率密度作出一个估计：率密度作出一个估计：率密度作出一个估计：相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x的估计，的估计，是一种数据的平滑。是一种数据的平滑。【基本思想】第33页/共70页

7、第三十四页，编辑于星期二：点 五十一分。n n当当当当n n固定时，固定时，固定时，固定时，V V的大小对估计的效果影响很大，过大则平的大小对估计的效果影响很大，过大则平的大小对估计的效果影响很大，过大则平的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本滑过多，不够精确；过小则可能导致在此区域内无样本滑过多，不够精确；过小则可能导致在此区域内无样本滑过多，不够精确；过小则可能导致在此区域内无样本点，点，点，点，k=0k=0。此方法的有效性取决于样本数量的多少，以及区域此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。体积选择的合适。第34页/共70

8、页第三十五页，编辑于星期二：点 五十一分。n n构造一系列包含构造一系列包含构造一系列包含构造一系列包含x x的区域的区域的区域的区域R1,R2,R1,R2,，对应，对应，对应，对应n=1,2,n=1,2,，则对则对则对则对p(x)p(x)有一系列的估计：有一系列的估计：有一系列的估计：有一系列的估计：当满足下列条件时，当满足下列条件时，pn(x)收敛于收敛于p(x)：第35页/共70页第三十六页，编辑于星期二：点 五十一分。n nParzenParzen窗法：区域体积窗法：区域体积窗法：区域体积窗法：区域体积V V是样本数是样本数是样本数是样本数n n的函数，如：的函数，如：的函数，如：的函

9、数，如：K-近邻法：落在区域内的样本数近邻法：落在区域内的样本数k是总样本数是总样本数n的函的函数，如：数，如：【Parzen窗法和K-近邻法】第36页/共70页第三十七页，编辑于星期二：点 五十一分。【Parzen窗法和K-近邻法】第37页/共70页第三十八页，编辑于星期二：点 五十一分。n n定义窗函数定义窗函数定义窗函数定义窗函数【Parzen窗法】第38页/共70页第三十九页，编辑于星期二：点 五十一分。n n超立方体中的样本数：超立方体中的样本数：超立方体中的样本数：超立方体中的样本数：【Parzen窗法】概率密度估计：概率密度估计：第39页/共70页第四十页，编辑于星期二：点 五十

10、一分。n n上述过程是一个内插过程，样本上述过程是一个内插过程，样本上述过程是一个内插过程，样本上述过程是一个内插过程，样本xixi距离距离距离距离x x越近，对越近，对越近，对越近，对概率密度估计的贡献越大，越远贡献越小。概率密度估计的贡献越大，越远贡献越小。概率密度估计的贡献越大，越远贡献越小。概率密度估计的贡献越大，越远贡献越小。n n只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数：【Parzen窗法】第40页/共70页第四十一页，编辑于星期二：点 五十一分。【Parzen窗法】窗函数第41页

11、/共70页第四十二页，编辑于星期二：点 五十一分。n nhn称为窗的宽度【Parzen窗法】第42页/共70页第四十三页，编辑于星期二：点 五十一分。【Parzen窗法】第43页/共70页第四十四页，编辑于星期二：点 五十一分。n n保存每个类别所有的训练样本；保存每个类别所有的训练样本；保存每个类别所有的训练样本；保存每个类别所有的训练样本；n n选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数n n选择窗函选择窗函选择窗函选择窗函数的数的数的数的h h宽度；宽度；宽度；宽度；n n识别时，利用每个类别的训练样本

12、计算待识别样本识别时，利用每个类别的训练样本计算待识别样本识别时，利用每个类别的训练样本计算待识别样本识别时，利用每个类别的训练样本计算待识别样本x x的的的的类条件概率密度：类条件概率密度：类条件概率密度：类条件概率密度：n n采用采用采用采用BayesBayes判别准则进行分类。判别准则进行分类。判别准则进行分类。判别准则进行分类。【Parzen窗法】第44页/共70页第四十五页，编辑于星期二：点 五十一分。EM(期望最大化期望最大化)算法算法第45页/共70页第四十六页，编辑于星期二：点 五十一分。1 EM算法的介绍算法的介绍2 EM算法依据的理论算法依据的理论3 EM算法的不足和改进的

13、算法算法的不足和改进的算法4 EM算法举例算法举例【EM算法】第46页/共70页第四十七页，编辑于星期二：点 五十一分。n nEMEM英文叫英文叫expectation-maximizationexpectation-maximization，是一种，是一种聚类算法。聚类算法。（即根据给定观察数据自动对数据进行分类）即根据给定观察数据自动对数据进行分类）n nEMEM算法是算法是Dempster,LairdDempster,Laird和和Rubin(DLR)Rubin(DLR)三个人在三个人在19771977年正式提出年正式提出的，主要是用于在不完全数据的情况下计算最大似然估计。的，主要是用于

14、在不完全数据的情况下计算最大似然估计。n n在在EMEM算法正式提出以来，对算法正式提出以来，对EMEM算法的性质有更加深入的研算法的性质有更加深入的研究，并且在此基础上，提出了很多改进的算法。究，并且在此基础上，提出了很多改进的算法。n nEMEM算法在数理统计，数据挖掘，机器学习以及模式识别等领域算法在数理统计，数据挖掘，机器学习以及模式识别等领域有广泛的应用。有广泛的应用。【1 EM算法的介绍算法的介绍】第47页/共70页第四十八页，编辑于星期二：点 五十一分。n n极大拟然估计法极大拟然估计法 引例引例:某位同学与一位猎人外出打猎，一只野兔从前方窜过，某位同学与一位猎人外出打猎，一只野

15、兔从前方窜过，只听一声枪响，野兔应声倒下，如果要你推测，这一发命中的只听一声枪响，野兔应声倒下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人命中的。概率一般大于这位同学命中的概率，看来这一枪是猎人命中的。这个例子所作的推断就体现了极大拟然法的基本思想。这个例子所作的推断就体现了极大拟然法的基本思想。【2 EM算法的理论依据算法的理论依据】第48页/共70页第四十九页，编辑于星期二：点 五十一分。n n极大拟然法的定义极大拟然法的定义 观测变量观测变量X X，

16、针对，针对n n个观测样本为个观测样本为(x1,x2,xnx1,x2,xn）,它们之间满足它们之间满足独立同分布独立同分布 ，参数变量为模型的一系列参数，参数变量为模型的一系列参数 但是在某些问题中由于存在隐含的随机变量Z 所以【2 EM算法的理论依据算法的理论依据】第49页/共70页第五十页，编辑于星期二：点 五十一分。EMEM收敛到最大似然的收敛到最大似然的收敛到最大似然的收敛到最大似然的2 2种证明种证明种证明种证明第一种证明是通过不断提高下界的思路来证，更能表达第一种证明是通过不断提高下界的思路来证，更能表达EMEM的本质；的本质；而第二种证明却是我们常在实际中应用而第二种证明却是我们

17、常在实际中应用EMEM的思路。的思路。n n(1)(1)拆分拆分n n(2)(2)等式两边同乘以等式两边同乘以q(Z)q(Z)，并对，并对Z Z求和（积）：求和（积）：【2 EM算法的理论依据算法的理论依据】第50页/共70页第五十一页，编辑于星期二：点 五十一分。n n(3)(3)由于由于Z Z与与 独立独立.且且 ，于是，于是，n n(4)(4)引入两个函数引入两个函数：n n这时，可以简化为：【2 EM算法的理论依据算法的理论依据】第51页/共70页第五十二页，编辑于星期二：点 五十一分。2、Expectation：依次取观察数据x，比较x在K个高斯函数 中概率的大小，把x归类到这K个高

18、斯中概率最大的一个。1、用随机函数初始化K个高斯分布的参数，同时保证EMEM算法过程：算法过程：【2 EM算法的理论依据算法的理论依据】第52页/共70页第五十三页，编辑于星期二：点 五十一分。4、返回第2步用第3步新得到的参数来对观察数据x重新分类。直到下式概率（最大似然函数）达到最大。Maximum 3、用最大似然估计，即简单问题的求法。【2 EM算法的理论依据算法的理论依据】第53页/共70页第五十四页，编辑于星期二：点 五十一分。【2 EM算法的理论依据算法的理论依据】第54页/共70页第五十五页，编辑于星期二：点 五十一分。n nEMEM主要缺点主要缺点n nEMEM算法比算法比K-

19、meansK-means算法计算复杂，收敛速度慢算法计算复杂，收敛速度慢 n n算法高度依赖初始值的选择，不适于大规模数据集算法高度依赖初始值的选择，不适于大规模数据集和高维数据和高维数据 n n改进的算法改进的算法n nPX-EM C Liu,DB Rubin and Wu.(1997).Parameter Expansion to Accelerate EM-the PXEmalgorithm.PX-EM C Liu,DB Rubin and Wu.(1997).Parameter Expansion to Accelerate EM-the PXEmalgorithm.n nXli Me

20、ng,DB Rubin.(1993).Maximum likelihood estimation via the ECM algorithm:A general Xli Meng,DB Rubin.(1993).Maximum likelihood estimation via the ECM algorithm:A general framework.framework.n nC Liu,DB Rubin.(1994).The ECME algorithm:A simple extension of EM and ECM with faster monotone C Liu,DB Rubin

21、.(1994).The ECME algorithm:A simple extension of EM and ECM with faster monotone convergence.convergence.【3 EM算法的不足和改进的算法算法的不足和改进的算法】第55页/共70页第五十六页，编辑于星期二：点 五十一分。n n Variational EM Variational EM Variational EM Variational EM 有些时候，有些时候，是不能显式的计算出来，这个时是不能显式的计算出来，这个时候最大化候最大化 就显得相当困难。这个时候，可以就显得相当困难。这个时候

22、，可以考虑不一定保证考虑不一定保证JensenJensen不等式一定要取等号，如果给定不等式一定要取等号，如果给定 某种形式，就得到某种形式，就得到variational EMvariational EM算法。算法。n n EM for MAP EM for MAP EM for MAP EM for MAP 上面讲的是针对上面讲的是针对MLEMLE估计的估计的EMEM算法，其实也有针对算法，其实也有针对MAPMAP估计的估计的EMEM算法。算法。n nOnline EM Online EM Online EM Online EM 上面讲的是上面讲的是EMEM可以归于可以归于batch EMb

23、atch EM一类，还有文献介一类，还有文献介绍关于绍关于online EMonline EM的论述。可以在文献的论述。可以在文献22中阅读到有关中阅读到有关online EMonline EM的内容。的内容。【3 EM算法的不足和改进的算法算法的不足和改进的算法】第56页/共70页第五十七页，编辑于星期二：点 五十一分。n nEMEM算算法法就就是是通通过过迭迭代代地地最最大大化化完完整整数数据据的的对对数数似似然然函函数数的的期期望望，来来最最大大化化不不完完整整数数据据的的对对数数似似然然函函数数。当当然然，针针对对各各种种EMEM的变形，它们又有各自的应用景。的变形，它们又有各自的应用

24、景。n n举例：举例：n n设设有有n n个个样样本本，它它们们是是由由高高斯斯混混合合分分布产生；布产生；n n高高斯斯混混合合分分布布是是由由k k个个不不同同的的高高斯斯分分布混合生成，每个分布都相互独立。布混合生成，每个分布都相互独立。n n用用EMEM算算法法估估计计高高斯斯混混合合分分布布参参数数：确确定定每每个个高高斯斯分分布布的的（1 1）均均值值和和（2 2）方差及（）方差及（3 3）先验概率；）先验概率；【4 EM算法举例算法举例】第57页/共70页第五十八页，编辑于星期二：点 五十一分。极大似然估计与极大似然估计与极大似然估计与极大似然估计与EMEM算法的关系算法的关系算

25、法的关系算法的关系n n计算极大似然估计计算极大似然估计(maximum likelihood estimate,MLE)maximum likelihood estimate,MLE)，需要求需要求似然函数的极值似然函数的极值o o解析法解析法:如求正态分布均值和方差的如求正态分布均值和方差的MLEMLEo o数值计算：如高斯混合模型数值计算：如高斯混合模型EMEM算法算法【4 EM算法举例算法举例】第58页/共70页第五十九页，编辑于星期二：点 五十一分。极大似然估计极大似然估计极大似然估计极大似然估计(MLE)MLE)n n独立同分布独立同分布(IID)IID)的数据的数据其概率密度函数

26、为其概率密度函数为似然函数定义为似然函数定义为loglog似然函数定义为似然函数定义为其极大似然估计为其极大似然估计为【4 EM算法举例算法举例】第59页/共70页第六十页，编辑于星期二：点 五十一分。完整数完整数据据n n观测数据：观测到的随机变量观测数据：观测到的随机变量 的的IIDIID样本样本n n缺失数据：未观测到的随机变量缺失数据：未观测到的随机变量 的值的值在在GMMGMM中，若中，若 来自第来自第k k个成分，则个成分，则n n完整数据：包含观测到的随机变量完整数据：包含观测到的随机变量 和未观测到的随机变量和未观测到的随机变量 的数据，的数据，【4 EM算法举例算法举例】第6

27、0页/共70页第六十一页，编辑于星期二：点 五十一分。完整似然函完整似然函数数若隐含变量若隐含变量 的值已知，得到完整数据的的值已知，得到完整数据的loglog似然函数为：似然函数为：【4 EM算法举例算法举例】第61页/共70页第六十二页，编辑于星期二：点 五十一分。步骤步骤1.EMExpectationn n观测数据观测数据X X已知，参数的当前值已知，参数的当前值 已知，在完整似然函数中，缺失数据已知，在完整似然函数中，缺失数据(隐含变隐含变量量)Y Y未知，完整未知，完整loglog似然函数对似然函数对Y Y求期望。求期望。n n定义定义 其中其中 是待确定的参数是待确定的参数n n通

28、过求期望，去掉了完整似然函数中的变量通过求期望，去掉了完整似然函数中的变量Y Y。即即EMEM的的E E步。步。【4 EM算法举例算法举例】第62页/共70页第六十三页，编辑于星期二：点 五十一分。步骤步骤2.EMMaximizationn n对对E E步计算得到的完整似然函数的期望求极大值（步计算得到的完整似然函数的期望求极大值（EMEM的的MM步），得到参数新的估计值，即步），得到参数新的估计值，即n n每次参数更新会增加非完整似然值每次参数更新会增加非完整似然值n n反复迭代后，会收敛到似然的局部最大值反复迭代后，会收敛到似然的局部最大值【4 EM算法举例算法举例】第63页/共70页第六

29、十四页，编辑于星期二：点 五十一分。EM的的收敛性收敛性n n其中，其中，n n当当QQ取极大值时，观测数据的似然也在相同点取极大取极大值时，观测数据的似然也在相同点取极大值值n nEMEM算法会收敛到似然的局部极大值算法会收敛到似然的局部极大值【4 EM算法举例算法举例】第64页/共70页第六十五页，编辑于星期二：点 五十一分。混合模型中的混合模型中的混合模型中的混合模型中的EMEMEMEM算法算法算法算法n n完整似然函数：完整似然函数：n n根据贝叶斯公式，根据贝叶斯公式，Y Y的条件分布：的条件分布：【4 EM算法举例算法举例】第65页/共70页第六十六页，编辑于星期二：点 五十一分。

30、混合模型中的混合模型中的EM算法算法n nE E步步 将完整似然函数和将完整似然函数和Y Y的条件分布代入的条件分布代入QQ函数中，经过函数中，经过复杂的变换得到，复杂的变换得到，n nMM步步 求求QQ函数最大时的参数函数最大时的参数n n反复迭代，直到收敛反复迭代，直到收敛【4 EM算法举例算法举例】第66页/共70页第六十七页，编辑于星期二：点 五十一分。GMM中的中的EM算法算法n n高斯分布：高斯分布：n n代入高斯分布的密度函数，计算得到如下的迭代公式：代入高斯分布的密度函数，计算得到如下的迭代公式：n n第第t t次的估计为次的估计为n n则第则第t+1t+1次的估计为次的估计为【4 EM算法举例算法举例】第67页/共70页第六十八页，编辑于星期二：点 五十一分。GMMGMMGMMGMM中中中中EMEMEMEM算法的迭代过程算法的迭代过程算法的迭代过程算法的迭代过程【4 EM算法举例算法举例】第68页/共70页第六十九页，编辑于星期二：点 五十一分。