EM算法简介课件.pptVIP

* EM算法简介 尤全增 ultimateyou@ * 提纲 算法介绍 EM算法 GEM算法性质 EM算法解释 EM不足及改进 * EM算法介绍 EM（expectation-maximization）算法是Dempster,Laird和Rubin(DLR)三个人在1977年正式提出的.主要是用于在不完全数据的情况下计算最大似然估计. 在EM算法正式提出以来，人们对EM算法的性质有更加深入的研究.并且在此基础上，提出了很多改进的算法. 在数理统计，数据挖掘，机器学习以及模式识别等领域有广泛的应用. * 问题提出 给定一些观察数据y，假设y符合如下的高斯分布 需要求出混合高斯分布的三组参数 * 问题简化 该混合高斯分布一共有K个分布函数，对于每一个观察到的样本y，如果知道它是属于K中的哪个分布，那么求这些参数就会变得很简单. 假如我们用 来表示这些高斯分布，那么我们的样本集中不仅仅是 ，而是 * 隐藏变量 由于实际问题中我们往往不知道每个y属于哪个分布，我们观察不到z，z是一个隐藏变量. 引入变量Z = 其中 取值为0或1 表示Z 的第k个分量为1，其它分量为0. 并且 . 于是 Z . (1) * 引入隐藏变量后的高斯分布 将Z引入后 (2) 最终得到 Z (3) * EM算法 首先引入如下变量 定义两个样本空间X和Y，其中X是完整数据空间，Y是观察数据（即incomplete data），令Z表示添加数据那么X = （Y，Z）; φ参数集合; 表示观察后验概率密度函数; 表示添加数据Z后得到的后验密度函数; 表示给定数据φ和观察数据y下x的条件密度函数. * EM算法 根据上面定义 (4) 定义似然函数 (5) 根据(4)式可知 (6) 定义函数 (7) * EM算法 定义函数 (8) 则有(4),(5),(7)式可得 (9) * EM算法 目的： 计算后验分布 的众数. EM算法如下进行 记 为第i+1次迭代开始时参数的估计值，则 第i+1次迭代的两步为： E-step 计算 M-step 最大化 . 即 . 重复上面两个步骤直至 或 充分小时，停止. * EM例子 有公式(1)(3)以及贝叶斯公式可得 ∝ 其中N表示观察样本数. 公式中 是未知的，需要求出它的期望 * 的期望估计 * 用 代替 将 代入 下面就应该使改式最大，也就是期望最大化. * 迭代描述 在迭代过程中我们需要不断的根据后验概率 Start * GEM算法 DLR提出GEM算法(General EM) EM的M-step可能比较复杂 M-step 定义映射 满足 ， M步可以描述为令 即 * GEM算法性质 引理1. 定理1. GEM算法满足 其中,等号成立当且仅当