em算法和改进课件.ppt

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

2、xx11kx1kxkxkdk)()(kkkkxfdxf牛顿法牛顿法的迭代公式：其中 称为牛顿方向，它是第k+1次迭代的搜索方向，且步长为1.又可写作：其中，为黑塞矩阵。)()(121kkkkxfxfxx)()(12kkkxfxfd)()(11kkkkxfxHxx)(kxH牛顿法的优缺点优点：对正定二次函数，迭代一次就可以得到极小点。如果 正定且初始点选取合适，算法很快收敛。缺点：要求函数二阶可微 收敛性与初始点的选取依赖很大 每次都需要计算黑塞矩阵，计算了大 每次都需要解方程组 方程组有时奇异或是病态的，无法确定 是不是下降方向。H)()(2kkkxfxxfkd变尺度算法拟牛顿法是一种逼近牛顿

3、法的方法，它在每次迭代的搜索方向 满足 ，其中 是一近似 的矩阵，如果 正定，拟牛顿法也称变尺度法。它的基本思想是利用梯度差及步长构造矩阵满足拟牛顿方程（变尺度方程）。变尺度法不必计算二阶导数。kd)(kKkxfGdkG12)(kxfkG变尺度算法拟牛顿条件：其中 是近似于 的矩阵 为方便，记 （并称其为校正矩阵）则拟牛顿条件可以写成：满足拟牛顿条件的校正矩阵并不是唯一的，所以拟牛顿算法是一族算法 kkkkkxxxfxfG111)()(1kG112)(kxfkkkxxx1kkkkkxgxgxfxfg)()(11kkkGGG1kkkkkgGxgGQ度量意义下最速下降方向 设f可微，在向量范数为

4、的度量意义下，f在点 处的最速下降方向为 如果把向量空间中向量模定义为 ，其中Q为正定矩阵，那么从点 出发在上述 Q度量意义下沿哪个方向d搜索，f下降的最 快？若令 ，则 为牛顿方向。xxxTkx)(kxfQxxxTQkx)(1kkxfQd)(2kxfQkd变尺度算法拟牛顿法就是在 度量意义下的最速下降法，只是向量范数的定义在各次迭代中是变化的，故这类算法又称为变度量法。拟牛顿法是一类特殊的变度量法。下面介绍两种常见的变度量法。1kGDFP算法校正矩阵的表达式：代入 得到的搜索方向叫做DFP方向，每次迭代中都使用DFP方向进行一维搜索的拟牛顿法就成为DFP法。kkTkkTkkkkTkTkkkg

5、GgGggGgxxxG)(kKkxfGdBFGS算法在推到拟牛顿条件时，一开始不考虑构造逼近 的迭代矩阵 ，而是考虑逼近 的迭代矩阵 ，可以得到校正矩阵：把BFGS公式产生的矩阵 构造的搜索方向 称为BFGS方向，每一次迭代都用BFGS方向进行一维搜索的拟牛顿法成为BFGS法。12)(kxfkG)(2kxfkBkkTkkTkkkkTkTkkkxBxBxxBxgggBkG)(kKkxfGd加速收敛算法的导入EM算法：E步：计算完全数据对数似然函数 的条件期望M步：求 ，使其最大化 ，一般求 时，可求解方程组 得到参数的迭代公式 。这种迭代公式通常使EM算法的收敛速度很慢，为加速收敛可考虑其他的方

6、法求解。);(lnxf),);(ln)(*kkyxfEQ1k),(yQk1n0)(kQkkG1加速收敛算法的导入根据著名的Fisher公式这里的 是不完全数据对数似然函数在 处的梯度。于是问题转化为求 使 ，从而可以使用非线性规划中的有效方法求解，达到加速收敛的目的。kkgQk)(kg lkk0kg1.EMD加速算法1.EMD加速算法BFGS加速算法在EM算法的M步求解问题时采用DFP校正公式，由于一维搜索的不精确性和计算误差的积累可能导致某一次迭代中 的奇异，给问题的解决带来不便。而BFGS公式对矩阵进行校正时对一维搜索的精度要求不高，并且由它产生的矩阵 不易变为奇异矩阵。因此，BFGS公式

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

8、情况下呈线性收敛，在未观察的样本对于以观察的样本的比值非常大的情况下，这种收敛是非常缓慢的。算法每一步的迭代中需要遍历所有的现有样本点，因此如果数据集非常大，计算强度也会增加。4.增量EM算法增量EM算法是针对EM算法的第二个缺点进行改进的。增量EM算法将数据分块，然后在数据块之间循环计算，其主要意图是通过部分E步来减少计算的强度。4.增量EM算法用 表示对数据集的一个特定的划分，该划分使得各个数据块相互之间是不重叠的，在进行M步之前，每一次迭代中对部分E步的操作仅仅只更新部分条件期望，算法的第n+1次迭代如下所示：Kyyy,.,14.增量EM算法E步：选择子数据集 ，其中i=n。计算联合分布

9、概率 设 ，for ji 计算 计算M步：选择 ，使得最大化 ，其中iy),(niiniyzpp),(),(1jnjjnjyQyQjnpjnjylEyQnj,(),(),(),(jnjjnyQyQ1n),(yQn4.增量EM算法在增量式EM算法中，部分E步增量式来构造Q函数，然后使其最大化。每一步迭代过程中，算法只是计算Q函数的一部分，即只是计算与 有关的 的值，对于其他的数据块，算法仅仅只是简单地接受以前的计算结果。为了计算上的高效，对于Q函数的增量式更新只需要加上新、旧 值的不同就可以了，即：jyjQjQ),(),(),(),(11injinjnnyQyQyQyQ5.懒惰EM算法懒惰EM算

10、法的一个前提假设就是：对于算法的每一次迭代，不是数据集中的所有数据都有同等重要的作用。给定数据 ，算法周期性地确定出重要的数据，然后针对这些重要的数据进行后面的迭代。用 表示数据集中重要的数据子集，用 表示余下的那个数据子集。Kyyy,.,1lazyylazyy5.懒惰EM算法算法中用完整E步或者懒惰E步来代替标准E步的计算。完整E步就是用所有的数据更新对数似然的期望并且确定重要的数据以便用于懒惰E步的迭代计算中。懒惰E步计算仅仅只是利用重要数据部分地更新Q函数，在懒惰EM算法中，E步在初始迭代中必须是完整E步计算。该算法n+1次迭代描述如下：5.懒惰EM算法 完整E步：得到 确定数据集中的重

11、要数据，得到 构造nnyzpp,lazyy)(,ylEyQnpn5.懒惰EM算法 懒惰E步：得到 令 计算nlzaylazynlazyyzpp,),(),(1lazynlazynlazyyQyQlazynlazylazynlazynyQyQyQ,),(),(1lazynlazynlazyyQyQ5.懒惰EM算法 M步：选择 ，使得最大化 其中与增量式EM算法一样，可以通过下面的式子得到更新后的Q函数：1n),(yQn),(),(),(),(11injinjnnyQyQyQyQ5.懒惰EM算法 确定哪些数据是重要数据的标准：对于有限混合模型，观察到当一个数据很明显是属于混合模型中的某个模型产生的

12、，那么当这个模型的参数发生比较小的变化时，这个数据对于它所属的模型的参数并不敏感，即这类数据对确定模型参数的影响不大，可以被认为是不重要的数据。同理，一些明显不属于某个模型的数据对模型参数的影响也不大，也被认为是不重要的数据。5.懒惰EM算法根据上述观察，我们设定两个重要阈值 和 ，通过下式可以得到一个数据相对一个模型的重要性：只有当 时，数据 才被认为是重要的。通过这个条件就可以对数据集进行约简，达到简化计算的目的。上ST下ST),(max)sup(niiXxyxpiii下上STySTi)sup(iy6.混合EM算法综合以上两种算法的优点，提出了混合EM算法，以进一步提高EM算法的计算强度。

13、算法的主要思想是：首先用懒惰EM算法的完整E步确定出重要数据集 ，然后对重要数据集应用增量式EM算法，经过增量式EM算法的几次迭代后，通过一个判断标准，决定是否重新利用懒惰EM算法的完整E步对重要数据集 做出调整。lazyylazyy6.混合EM算法完整E步：得到 确定数据集中的重要数据，得到 对重要数据集合 进行划分，得到k个子 数据集 构造M步：M步：选择 ，使得最大化 其中nnyzpp,lazyy)(,ylEyQnpnlazyylazyklazyilazyyyy,.,.,11n),(yQn6.混合EM算法懒惰E步：for i=1 to k 得到 令 for ji 计算M步：选择 ，使得最

14、大化 其中nlazyilazyinlazyiyzpp,),(),(1lazyinlazyinlazyiyQyQjnjlazyinlazyilazyinlazyinyQyQyQyQ,),(),(1lazyinlazyinlazyiyQyQ),(),(1jnjjnjyQyQ1n),(yQn6.混合EM算法上述算法描述的是整体上进行第n+1次迭代的过程。并不是每次迭代都需要首先执行完整E步，可以在多次迭代懒惰E步后在应用完整E步进行调整。混合EM算法能很好地适应大数据集的情况，对于数据集较小的情况下其优势不明显，甚至在参数设置不合理的时候，性能还不如标准EM算法。7.递增EM算法 选取增量因子 初始

15、子样本数量选取为 在子样本达到最佳拟合真实分别的前提下，加入新的样本，再次进行拟合，若为最佳拟合，再次加入新的样本。如此反复，直到子样本的数量与完全样本一致时停止增加。在递增的过程中，子样本逐渐逼近完全样本的真实分布。2/ln Nd dNM/7.递增EM算法 令每次子样本新增样本数h=M/d 这里的M是样本增加前一次的M值，则更新后的M变为M+M/d，这种增量方式是逐步递增的过程。令 表示完整的数据集，是随机选择的大小为M 的子样本，则可得到Q函数的近似Nxx,.,1),.,(,.,11NttxxxxM1tMQ7.递增EM算法 令 表示t次迭代与t-1次迭代的似然差值，为一充分小的数。若 说明

16、子样本集与其相应的子样本模型并不匹配，需要继续迭代；反之，说明子样本集与其相应的子样本模型匹配，而与完全样本集的高斯模型进行匹配还需要一段距离，因此需要增加额外的信息量进行样本估计，即新增加样本进行训练。)()(1tMtMQQBB7.IEM算法实现 给定高斯混合成分数K，增量因子d，初始子样本M=N/d，初始参数 ，令 为一充分小的数，IEM聚类算法的具体步骤为：step1：对大小M的子样本，计算step2：计算参数step3：如果 ，将参数 返回step1进行计算step4：如果 ，令M取值M=M+M/d01tijptititiBtititiB7.IEM算法实现step5:如果MN，将参数

17、返回到step1进行计算step6：如果 ，令M=N，执行下列操作：计算 计算参数若 执行step1，否则算法停止NM tijptititi1ti1ti1tiB第三部分：EM算法的应用-递增EM算法的图像聚类图像聚类图像聚类就是在给出的图像集合中，根据图像的内容，在无先验知识的条件下，将图像分成有意义的簇。对于图像聚类，最引人注目的特征属性是颜色、纹理和形状等。图像聚类图像聚类其中a,d是初始图像，经数据预处理后，a图共有222个灰度级，d图共有253个灰度级。以下比较EM算法和IEM算法的聚类效果：令2个测试的聚类数都为3，即灰度值聚类为0（黑），120（浅灰），255（白）三类。设 ，令某一灰度值为r，若 ，则r=0；若 ，则r=120;若 ，则r=255。321,1r21 r2r图像聚类EM算法与IEM算法的初始参数都设为对于IEM而言，由于ln222/2ln253/23，故令d=3，2幅图的初始样本大小分别从M=74和M=84开始，每次以几何级数增加个样本，其中M取值3/1,3/1,3/10160,120,50030,150,800dMM/MM谢谢观看！2020