em算法及其改进.ppt

文档介绍：EM算法及其改进（二）
1
精选ppt
第一部分：EM变尺度加速算法
2
精选ppt
下降迭代算法
求解非线性最优化问题 最常用算法
基本步骤：
step1：选取初始数据，选取初始点 ，从而可以使用非线性规划中的有效方法求解，达到加速收敛的目的。
16
精选ppt

17
精选ppt

18
精选ppt
BFGS加速算法
在EM算法的M步求解问题时采用DFP校正公式，由于一维搜索的不精确性和计算误差的积累可能导致某一次迭代中 的奇异，给问题的解决带来不便。
而BFGS公式对矩阵进行校正时对一维搜索的精度要求不高，并且由它产生的矩阵 不易变为奇异矩阵。因此，BFGS公式比DFP公式具有这一好的数值稳定行，进而提出EMBE加速算法，它不但具有EMD加速算法的性质，而且在满足一定条件下其收敛速率是超线性的，所以此算法更具有实用性。
19
精选ppt

20
精选ppt

21
精选ppt

一般认为：
EMB加速算法采用不精确线性搜索时在收敛性质和数值计算方面均优于EMD加速算法
在计算过程中，EMD加速算法不必求解线性方程组这一点又优于EMB加速算法。
结合二者的优点提出一种新的EMDB加速算法，使EMB加速算法在求搜索方向时也不用求解线性方程组又能保持原来的性质。
22
精选ppt

23
精选ppt

24
精选ppt
第二部分：适应大数据集的EM算法的改进方法
25
精选ppt
EM算法的缺点
算法在一般情况下呈线性收敛，在未观察的样本对于以观察的样本的比值非常大的情况下，这种收敛是非常缓慢的。
算法每一步的迭代中需要遍历所有的现有样本点，因此如果数据集非常大，计算强度也会增加。
26
精选ppt

增量EM算法是针对EM算法的第二个缺点进行改进的。
增量EM算法将数据分块，然后在数据块之间循环计算，其主要意图是通过部分E步来减少计算的强度。
27
精选ppt

用 表示对数据集的一个特定的划分，该划分使得各个数据块相互之间是不重叠的，在进行M步之前，每一次迭代中对部分E步的操作仅仅只更新部分条件期望，算法的第n+1次迭代如下所示：
28
精选ppt

E步：选择子数据集 ，其中i=n。
计算联合分布概率
设 ，for j≠i
计算
计算
M步：选择 ，使得最大化 ，
其中
29
精选ppt

在增量式EM算法中，部分E步增量式来构造Q函数，然后使其最大化。每一步迭代过程中，算法只是计算Q函数的一部分，即只是计算与
有关的 的值，对于其他的数据块，算法仅仅只是简单地接受以前的计算结果。为了计算上的高效，对于Q函数的增量式更新只需要加上新、旧 值的不同就可以了，即：
30
精选ppt

懒惰EM算法的一个前提假设就是：对于算法的每一次迭代，不是数据集中的所有数据都有同等重要的作用。给定数据 ，算法周期性地确定出重要的数据，然后针对这些重要的数据进行后面的迭代。用 表示数据集中重要的数据子集，用 表示余下的那个数据子集。
31
精选ppt

算法中用完整E步或者懒惰E步来代替标准E步的计算。完整E步就是用所有的数据更新对数似然的期望并且确定重要的数据以便用于懒惰E步的迭代计算中。懒惰E步计算仅仅只是利用重要数据部分地更新Q函数，在懒惰EM算法中，E步在初始迭代中必须是完整E步计算。该算法n+1次迭代描述如下：
32
精选ppt

完整E步：
得到
确定数据集中的重要数据，得到
构造
33
精选ppt

懒惰E步：
得到
令
计算
34
精选ppt

M步：选择 ，使得最大化
其中
与增量式EM算法一样，可以通过下面的式子得到更新后的Q函数：
35
精选ppt