em算法及其改进.ppt

《em算法及其改进.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、EM算法及其改进（二）第一部分：EM变尺度加速算法下降迭代算法求解非线性最优化问题最常用算法基本步骤：step1：选取初始数据，选取初始点，令k=0step2：构造搜索方向，按照一定规则，构造f在点处的下降方向（对于无约束最优化问题）或可行方向（对有约束问题）作为搜索方向。下降迭代算法step3：确定搜索步长。确定以为起点沿搜索方向的适当步长，使目标函数值有某种意义的下降，通常是使step4：求出新迭代点，令step5：检验终止条件，判定是否满足终止条件，若满足，则停止迭代输出近似最优解；否则，令k:=k+1，转step

2、2.牛顿法牛顿法的迭代公式：其中称为牛顿方向，它是第k+1次迭代的搜索方向，且步长为1.又可写作：其中，为黑塞矩阵。牛顿法的优缺点优点：对正定二次函数，迭代一次就可以得到极小点。如果正定且初始点选取合适，算法很快收敛。缺点：要求函数二阶可微收敛性与初始点的选取依赖很大每次都需要计算黑塞矩阵，计算了大每次都需要解方程组方程组有时奇异或是病态的，无法确定是不是下降方向。变尺度算法拟牛顿法是一种逼近牛顿法的方法，它在每次迭代的搜索方向满足，其中是一近似的矩阵，如果正定，拟牛顿法也称变尺度法。它的基本思想是利用梯度差及步长构造矩

3、阵满足拟牛顿方程（变尺度方程）。变尺度法不必计算二阶导数。变尺度算法拟牛顿条件：其中是近似于的矩阵为方便，记（并称其为校正矩阵）则拟牛顿条件可以写成：满足拟牛顿条件的校正矩阵并不是唯一的，所以拟牛顿算法是一族算法Q度量意义下最速下降方向设f可微，在向量范数为的度量意义下，f在点处的最速下降方向为如果把向量空间中向量模定义为，其中Q为正定矩阵，那么从点出发在上述Q度量意义下沿哪个方向d搜索，f下降的最快？若令，则为牛顿方向。变尺度算法拟牛顿法就是在度量意义下的最速下降法，只是向量范数的定义在各次迭代中是变化的，故这类算法又

4、称为变度量法。拟牛顿法是一类特殊的变度量法。下面介绍两种常见的变度量法。DFP算法校正矩阵的表达式：代入得到的搜索方向叫做DFP方向，每次迭代中都使用DFP方向进行一维搜索的拟牛顿法就成为DFP法。BFGS算法在推到拟牛顿条件时，一开始不考虑构造逼近的迭代矩阵，而是考虑逼近的迭代矩阵，可以得到校正矩阵：把BFGS公式产生的矩阵构造的搜索方向称为BFGS方向，每一次迭代都用BFGS方向进行一维搜索的拟牛顿法成为BFGS法。加速收敛算法的导入EM算法：E步：计算完全数据对数似然函数的条件期望M步：求，使其最大化，一般求时，可

5、求解方程组得到参数的迭代公式。这种迭代公式通常使EM算法的收敛速度很慢，为加速收敛可考虑其他的方法求解。加速收敛算法的导入根据著名的Fisher公式这里的是不完全数据对数似然函数在处的梯度。于是问题转化为求使，从而可以使用非线性规划中的有效方法求解，达到加速收敛的目的。1.EMD加速算法1.EMD加速算法BFGS加速算法在EM算法的M步求解问题时采用DFP校正公式，由于一维搜索的不精确性和计算误差的积累可能导致某一次迭代中的奇异，给问题的解决带来不便。而BFGS公式对矩阵进行校正时对一维搜索的精度要求不高，并且由它产生的

6、矩阵不易变为奇异矩阵。因此，BFGS公式比DFP公式具有这一好的数值稳定行，进而提出EMBE加速算法，它不但具有EMD加速算法的性质，而且在满足一定条件下其收敛速率是超线性的，所以此算法更具有实用性。2.EMB加速算法2.EMB加速算法3.EMDB算法一般认为：EMB加速算法采用不精确线性搜索时在收敛性质和数值计算方面均优于EMD加速算法在计算过程中，EMD加速算法不必求解线性方程组这一点又优于EMB加速算法。结合二者的优点提出一种新的EMDB加速算法，使EMB加速算法在求搜索方向时也不用求解线性方程组又能保持原来的性质

7、。3.EMDB算法3.EMDB算法第二部分：适应大数据集的EM算法的改进方法EM算法的缺点算法在一般情况下呈线性收敛，在未观察的样本对于以观察的样本的比值非常大的情况下，这种收敛是非常缓慢的。算法每一步的迭代中需要遍历所有的现有样本点，因此如果数据集非常大，计算强度也会增加。4.增量EM算法增量EM算法是针对EM算法的第二个缺点进行改进的。增量EM算法将数据分块，然后在数据块之间循环计算，其主要意图是通过部分E步来减少计算的强度。4.增量EM算法用表示对数据集的一个特定的划分，该划分使得各个数据块相互之间是不重叠的，在进

8、行M步之前，每一次迭代中对部分E步的操作仅仅只更新部分条件期望，算法的第n+1次迭代如下所示：4.增量EM算法E步：选择子数据集，其中i=n。计算联合分布概率设，forj≠i计算计算M步：选择，使得最大化，其中4.增量EM算法在增量式EM算法中，部分E步增量式来构造Q函数，然后使其最大化。每一步迭代过程中，算法只是计