模式识别课程讲义李君宝3. 概率密度函数估计3学时.ppt
,哈尔滨工业大学,主讲人：李君宝,第3章 概率密度函数估计,主要内容,引言参数估计正态分布的参数估计非参数估计EM算法(期望最大化算法)本章小结,引言,【引言】,【引言】,【引言】,【引言】,【引言】,【引言】,参数估计,【参数估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,【最大似然估计】,例子（梯度法不适合）：,不成功！,【贝叶斯估计】,【贝叶斯估计】,【举例】,假设,结论：,【贝叶斯估计】,【贝叶斯学习】,【三种方法总结】,【三种方法总结】,正态分布的参数估计,【最大似然估计】,【最大似然估计】,单元正态分布：,多元正态分布：,【贝叶斯估计】,【贝叶斯估计】,非参数估计,【基本思想】,令R是包含样本点x的一个区域，其体积为V，设有n个训练样本，其中有k个落在区域R中，则可对概率密度作出一个估计：,相当于用R区域内的平均性质来作为一点x的估计，是一种数据的平滑。,【基本思想】,当n固定时，V的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，k=0。,此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。,构造一系列包含x的区域R1,R2,，对应n=1,2,，则对p(x)有一系列的估计：,当满足下列条件时，pn(x)收敛于p(x)：,Parzen窗法：区域体积V是样本数n的函数，如：,K-近邻法：落在区域内的样本数k是总样本数n的函数，如：,【Parzen窗法和K-近邻法】,【Parzen窗法和K-近邻法】,定义窗函数,【Parzen窗法】,超立方体中的样本数：,【Parzen窗法】,概率密度估计：,上述过程是一个内插过程，样本xi距离x越近，对概率密度估计的贡献越大，越远贡献越小。只要满足如下条件，就可以作为窗函数：,【Parzen窗法】,【Parzen窗法】,窗函数,hn称为窗的宽度,【Parzen窗法】,【Parzen窗法】,保存每个类别所有的训练样本；选择窗函数的形式，根据训练样本数n选择窗函数的h宽度；识别时，利用每个类别的训练样本计算待识别样本x的类条件概率密度：采用Bayes判别准则进行分类。,【Parzen窗法】,EM(期望最大化)算法,1 EM算法的介绍,2 EM算法依据的理论,3 EM算法的不足和改进的算法,4 EM算法举例,【EM算法】,EM英文叫expectation-maximization，是一种聚类算法。（即根据给定观察数据自动对数据进行分类）EM算法是Dempster,Laird和Rubin(DLR)三个人在1977年正式提出的，主要是用于在不完全数据的情况下计算最大似然估计。在EM算法正式提出以来，对EM算法的性质有更加深入的研究，并且在此基础上，提出了很多改进的算法。EM算法在数理统计，数据挖掘，机器学习以及模式识别等领域有广泛的应用。,【1 EM算法的介绍】,极大拟然估计法 引例:某位同学与一位猎人外出打猎，一只野兔从前方窜过，只听一声枪响，野兔应声倒下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人命中的。这个例子所作的推断就体现了极大拟然法的基本思想。,【2 EM算法的理论依据】,极大拟然法的定义 观测变量X，针对n个观测样本为(x1,x2,xn）,它们之间满足独立同分布，参数变量为模型的一系列参数,但是在某些问题中由于存在隐含的随机变量Z,所以,【2 EM算法的理论依据】,EM收敛到最大似然的2种证明,第一种证明是通过不断提高下界的思路来证，更能表达EM的本质；而第二种证明却是我们常在实际中应用EM的思路。(1)拆分(2)等式两边同乘以q(Z)，并对Z求和（积）：,【2 EM算法的理论依据】,(3)由于Z与 独立.且，于是，(4)引入两个函数：这时，可以简化为：,【2 EM算法的理论依据】,2、Expectation：依次取观察数据x，比较x在K个高斯函数 中概率的大小，把x归类到这K个高斯中概率最大的一个。,1、用随机函数初始化K个高斯分布的参数，同时保证,EM算法过程：,【2 EM算法的理论依据】,4、返回第2步用第3步新得到的参数来对观察数据x重新分类。直到下式概率（最大似然函数）达到最大。,Maximum 3、用最大似然估计，即简单问题的求法。,【2 EM算法的理论依据】,【2 EM算法的理论依据】,EM主要缺点EM算法比K-means算法计算复杂，收敛速度慢 算法高度依赖初始值的选择，不适于大规模数据集和高维数据 改进的算法PX-EM C Liu,DB Rubin and Wu.(1997).Parameter Expansion to Accelerate EM-the PXEmalgorithm.Xli Meng,DB Rubin.(1993).Maximum likelihood estimation via the ECM algorithm:A general framework.C Liu,DB Rubin.(1994).The ECME algorithm:A simple extension of EM and ECM with faster monotone convergence.,【3 EM算法的不足和改进的算法】,Variational EM 有些时候，是不能显式的计算出来，这个时候最大化 就显得相当困难。这个时候，可以考虑不一定保证Jensen不等式一定要取等号，如果给定 某种形式，就得到variational EM算法。EM for MAP 上面讲的是针对MLE估计的EM算法，其实也有针对MAP估计的EM算法。Online EM 上面讲的是EM可以归于batch EM一类，还有文献介绍关于online EM的论述。可以在文献2中阅读到有关online EM的内容。,【3 EM算法的不足和改进的算法】,EM算法就是通过迭代地最大化完整数据的对数似然函数的期望，来最大化不完整数据的对数似然函数。当然，针对各种EM的变形，它们又有各自的应用景。举例：设有n个样本，它们是由高斯混合分布产生；高斯混合分布是由k个不同的高斯分布混合生成，每个分布都相互独立。用EM算法估计高斯混合分布参数：确定每个高斯分布的（1）均值和（2）方差及（3）先验概率；,【4 EM算法举例】,极大似然估计与EM算法的关系,计算极大似然估计(maximum likelihood estimate,MLE)，需要求似然函数的极值解析法:如求正态分布均值和方差的MLE数值计算：如高斯混合模型EM算法,【4 EM算法举例】,极大似然估计(MLE),独立同分布(IID)的数据其概率密度函数为似然函数定义为log似然函数定义为其极大似然估计为,【4 EM算法举例】,完整数据,观测数据：观测到的随机变量 的IID样本缺失数据：未观测到的随机变量 的值在GMM中，若 来自第k个成分，则完整数据：包含观测到的随机变量 和未观测到的随机变量 的数据，,【4 EM算法举例】,完整似然函数,若隐含变量 的值已知，得到完整数据的log似然函数为：,【4 EM算法举例】,步骤1.EMExpectation,观测数据X已知，参数的当前值 已知，在完整似然函数中，缺失数据(隐含变量)Y未知，完整log似然函数对Y求期望。定义 其中 是待确定的参数通过求期望，去掉了完整似然函数中的变量Y。即EM的E步。,【4 EM算法举例】,步骤2.EMMaximization,对E步计算得到的完整似然函数的期望求极大值（EM的M步），得到参数新的估计值，即每次参数更新会增加非完整似然值反复迭代后，会收敛到似然的局部最大值,【4 EM算法举例】,EM的收敛性,其中，当Q取极大值时，观测数据的似然也在相同点取极大值EM算法会收敛到似然的局部极大值,【4 EM算法举例】,混合模型中的EM算法,完整似然函数：根据贝叶斯公式，Y的条件分布：,【4 EM算法举例】,混合模型中的EM算法,E步 将完整似然函数和Y的条件分布代入Q函数中，经过复杂的变换得到，M步 求Q函数最大时的参数反复迭代，直到收敛,【4 EM算法举例】,GMM中的EM算法,高斯分布：代入高斯分布的密度函数，计算得到如下的迭代公式：第t次的估计为则第t+1次的估计为,【4 EM算法举例】,GMM中EM算法的迭代过程,【4 EM算法举例】,本章结束,
