EM算法new课件.pptVIP

一 EM算法的介绍 EM英文叫expectation-maximization，是一种聚类算法。（即根据给定观察数据自动对数据进行分类） EM算法是Dempster,Laird和Rubin(DLR)三个人在1977年正式提出的，主要是用于在不完全数据的情况下计算最大似然估计。 在EM算法正式提出以来，人们对EM算法的性质有更加深入的研究，并且在此基础上，提出了很多改进的算法。 EM算法在数理统计，数据挖掘，机器学习以及模式识别等领域有广泛的应用。 二 EM算法的理论依据 极大拟然估计法 引例:某位同学与一位猎人外出打猎，一只野兔从前方窜过，只听一声枪响，野兔应声倒下，如果要你推测，这一发命中的子弹是谁打的？你就会想，只发一枪便打中，由于猎人命中的概率一般大于这位同学命中的概率，看来这一枪是猎人命中的。 这个例子所作的推断就体现了极大拟然法的基本思想。 极大拟然法的定义 观测变量X，针对X所获得的n个观测样本为( ) 它们之间满足独立同分布 ，参数变量为模型的一系列参数 EM因什么而存在？ 定义：观测变量X，针对X所获得的n个观测样本为( ), 随机变量Z，是与观测变量对应的隐含变量，在所取n个样本中对应的取值为( ) ,参数变量 依照最大似然估计形式化定义为： 由于存在隐含的随机变量Z, 这时需要另辟蹊径，而EM正是解决这类问题的有力武器。 EM收敛到最大似然的2种证明 第一种证明是通过不断提高下界的思路来证，更能表达EM的本质；而第二种证明却是我们常在实际中应用EM的思路。 (1) 拆分 (2) 等式两边同乘以q(Z)，并对Z求和（积）： (3) 由于Z与 独立.且 ， 于是， (4) 引入两个函数： 这时， 可以简化为： 注意， ，等号在p=q时成立。所以 是 的下界。而EM算法的思路就是靠不断的提高下界 ，来找到 的最大值。再回顾一下，直接计算 有时候是件困难/复杂的事情。不过计算 是比较容易的。那么如何提高下呢？EM算法的E步和M步正是来实现这个目标的。 E步：假设当前的参数为 ，固定 ，找一个分布q(Z)，使得 最大。但是注意到 与Z无关，所以使 最大，等价于使 最小(=0)，也就是说 。 M步：固定q(Z)，找新参数 ，使得 最大。当然， 的增大可能来自于两部分： 和 ，毕竟此时 和 一般是不同的，所以 。 三 EM算法的不足和改进的算法 EM主要缺点 EM算法比K-means算法计算复杂，收敛速度慢 算法高度依赖初始值的选择，不适于大规模数据集和高维数据 改进的算法 PX-EM C Liu,DB Rubin and Wu.(1997). Parameter Expansion to Accelerate EM---the PX—Emalgorithm. 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. Variational EM 有些时候， 是不能显式的计算出来，这个时候最大化 就显得相当困难。这个时候，可以考虑不一定保证Jensen不等式一定要取等号，如果给定 某种形式，就得到variational EM算法。 EM for MAP 上面讲的是针对MLE估计的EM算法，其实也有针对MAP估计的EM算法。 Online EM 上面讲的是EM可以归于batch EM一类，还有文献介绍关于online EM的论述。可以在文献[2]中阅读到有关online EM的内容。 四 EM算法