em算法及其改进

EM算法及其改进（二）第一部分：EM变尺度加速算法下降迭代算法•求解非线性最优化问题最常用算法•基本步骤：step1：选取初始数据，选取初始点，令k=0step2：构造搜索方向，按照一定规则，构造f在点处的下降方向（对于无约束最优化问题）或可行方向（对有约束问题）作为搜索方向。Xxtsxf..)(min0xkxkd下降迭代算法step3：确定搜索步长。确定以为起点沿搜索方向的适当步长，使目标函数值有某种意义的下降，通常是使step4：求出新迭代点，令step5：检验终止条件，判定是否满足终止条件，若满足，则停止迭代输出近似最优解；否则，令k:=k+1，转step2.kkkkdxx11kx1kxkxkdk)()(kkkkxfdxf牛顿法牛顿法的迭代公式：其中称为牛顿方向，它是第k+1次迭代的搜索方向，且步长为1.又可写作：其中，为黑塞矩阵。)()(121kkkkxfxfxx)()(12kkkxfxfd)()(11kkkkxfxHxx)(kxH牛顿法的优缺点优点：•对正定二次函数，迭代一次就可以得到极小点。•如果正定且初始点选取合适，算法很快收敛。缺点：•要求函数二阶可微•收敛性与初始点的选取依赖很大•每次都需要计算黑塞矩阵，计算了大•每次都需要解方程组方程组有时奇异或是病态的，无法确定是不是下降方向。H)()(2kkkxfxxfkd变尺度算法拟牛顿法是一种逼近牛顿法的方法，它在每次迭代的搜索方向满足，其中是一近似的矩阵，如果正定，拟牛顿法也称变尺度法。它的基本思想是利用梯度差及步长构造矩阵满足拟牛顿方程（变尺度方程）。变尺度法不必计算二阶导数。kd)(kKkxfGdkG12)(kxfkG变尺度算法拟牛顿条件：其中是近似于的矩阵为方便，记（并称其为校正矩阵）则拟牛顿条件可以写成：满足拟牛顿条件的校正矩阵并不是唯一的，所以拟牛顿算法是一族算法kkkkkxxxfxfG111)()(1kG112)(kxfkkkxxx1kkkkkxgxgxfxfg)()(11kkkGGG1kkkkkgGxgGQ度量意义下最速下降方向•设f可微，在向量范数为的度量意义下，f在点处的最速下降方向为•如果把向量空间中向量模定义为，其中Q为正定矩阵，那么从点出发在上述Q度量意义下沿哪个方向d搜索，f下降的最快？若令，则为牛顿方向。xxxTkx)(kxfQxxxTQkx)(1kkxfQd)(2kxfQkd变尺度算法拟牛顿法就是在度量意义下的最速下降法，只是向量范数的定义在各次迭代中是变化的，故这类算法又称为变度量法。拟牛顿法是一类特殊的变度量法。下面介绍两种常见的变度量法。1kGDFP算法校正矩阵的表达式：代入得到的搜索方向叫做DFP方向，每次迭代中都使用DFP方向进行一维搜索的拟牛顿法就成为DFP法。kkTkkTkkkkTkTkkkgGgGggGgxxxG)(kKkxfGdBFGS算法在推到拟牛顿条件时，一开始不考虑构造逼近的迭代矩阵，而是考虑逼近的迭代矩阵，可以得到校正矩阵：把BFGS公式产生的矩阵构造的搜索方向称为BFGS方向，每一次迭代都用BFGS方向进行一维搜索的拟牛顿法成为BFGS法。12)(kxfkG)(2kxfkBkkTkkTkkkkTkTkkkxBxBxxBxgggBkG)(kKkxfGd加速收敛算法的导入EM算法：E步：计算完全数据对数似然函数的条件期望M步：求，使其最大化，一般求时，可求解方程组得到参数的迭代公式。这种迭代公式通常使EM算法的收敛速度很慢，为加速收敛可考虑其他的方法求解。);(lnxf),);((ln)(*kkyxfEQ1k),(yQk1n0)(kQkkG1加速收敛算法的导入根据著名的Fisher公式这里的是不完全数据对数似然函数在处的梯度。于是问题转化为求使，从而可以使用非线性规划中的有效方法求解，达到加速收敛的目的。kkgQk)(kglkk0kg1.EMD加速算法1.EMD加速算法BFGS加速算法在EM算法的M步求解问题时采用DFP校正公式，由于一维搜索的不精确性和计算误差的积累可能导致某一次迭代中的奇异，给问题的解决带来不便。而BFGS公式对矩阵进行校正时对一维搜索的精度要求不高，并且由它产生的矩阵不易变为奇异矩阵。因此，BFGS公式比DFP公式具有这一好的数值稳定行，进而提出EMBE加速算法，它不但具有EMD加速算法的性质，而且在满足一定条件下其收敛速率是超线性的，所以此算法更具有实用性。kGkB2.EMB加速算法2.EMB加速算法3.EMDB算法•一般认为：•EMB加速算法采用不精确线性搜索时在收敛性质和数值计算方面均优于EMD加速算法•在计算过程中，EMD加速算法不必求解线性方程组这一点又优于EMB加速算法。•结合二者的优点提出一种新的EMDB加速算法，使EMB加速算法在求搜索方向时也不用求解线性方程组又能保持原来的性质。3.EMDB算法3.EMDB算法第二部分：适应大数据集的EM算法的改进方法EM算法的缺点•算法在一般情况下呈线性收敛，在未观察的样本对于以观察的样本的比值非常大的情况下，这种收敛是非常缓慢的。•算法每一步的迭代中需要遍历所有的现有样本点，因此如果数据集非常大，计算强度也会增加。4.增量EM算法增量EM算法是针对EM算法的第二个缺点进行改进的。增量EM算法将数据分块，然后在数据块之间循环计算，其主要意图是通过部分E步来减少计算的强度。4.增量EM算法用表示对数据集的一个特定的划分，该划分使得各个数据块相互之间是不重叠的，在进行M步之前，每一次迭代中对部分E步的操作仅仅只更新部分条件期望，算法的第n+1次迭代如下所示：Kyyy,...,14.增量EM算法E步：选择子数据集，其中i=n。计算联合分布概率设，forj≠i计算计算M步：选择，使得最大化，其中iy),(niiniyzpp),(),(1jnjjnjyQyQjnpjnjylEyQnj,(),(),(),(jnjjnyQyQ1n),(yQn4.增量EM算法在增量式EM算法中，部分E步增量式来构造Q函数，然后使其最大化。每一步迭代过程中，算法只是计算Q函数的一部分，即只是计算与有关的的值，对于其他的数据块，算法仅仅只是简单地接受以前的计算结果。为了计算上的高效，对于Q函数的增量式更新只需要加上新、旧值的不同就可以了，即：jyjQjQ),(),(),(),(11injinjnnyQyQyQyQ5.懒惰EM算法懒惰EM算法的一个前提假设就是：对于算法的每一次迭代，不是数据集中的所有数据都有同等重要的作用。给定数据，算法周期性地确定出重要的数据，然后针对这些重要的数据进行后面的迭代。用表示数据集中重要的数据子集，用表示余下的那个数据子集。Kyyy,...,1lazyylazyy5.懒惰EM算法算法中用完整E步或者懒惰E步来代替标准E步的计算。完整E步就是用所有的数据更新对数似然的期望并且确定重要的数据以便用于懒惰E步的迭代计算中。懒惰E步计算仅仅只是利用重要数据部分地更新Q函数，在懒惰EM算法中，E步在初始迭代中必须是完整E步计算。该算法n+1次迭代描述如下：5.懒惰EM算法•完整E步：得到确定数据集中的重要数据，得到构造nnyzpp,lazyy)(,ylEyQnpn5.懒惰EM算法•懒惰E步：得到令计算nlzaylazynlazyyzpp,),(),(1lazynlazynlazyyQyQlazynlazylazynlazynyQyQyQ,,,),(),(1lazynlazynlazyyQyQ5.懒惰EM算法•M步：选择，使得最大化其中与增量式EM算法一样，可以通过下面的式子得到更新后的Q函数：1n),(yQn),(),(),(),(11injinjnnyQyQyQyQ5.懒惰EM算法•确定哪些数据是重要数据的标准：对于有限混合模型，观察到当一个数据很明显是属于混合模型中的某个模型产生的，那么当这个模型的参数发生比较小的变化时，这个数据对于它所属的模型的参数并不敏感，即这类数据对确定模型参数的影响不大，可以被认为是不重要的数据。同理，一些明显不属于某个模型的数据对模型参数的影响也不大，也被认为是不重要的数据。5.懒惰EM算法根据上述观察，我们设定两个重要阈值和，通过下式可以得到一个数据相对一个模型的重要性：只有当时，数据才被认为是重要的。通过这个条件就可以对数据集进行约简，达到简化计算的目的。上ST下ST),(max)sup(niiXxyxpiii下上STySTi)sup(iy6.混合EM算法综合以上两种算法的优点，提出了混合EM算法，以进一步提高EM算法的计算强度。算法的主要思想是：首先用懒惰EM算法的完整E步确定出重要数据集，然后对重要数据集应用增量式EM算法，经过增量式EM算法的几次迭代后，通过一个判断标准，决定是否重新利用懒惰EM算法的完整E步对重要数据集做出调整。lazyylazyy6.混合EM算法＊完整E步：得到确定数据集中的重要数据，得到对重要数据集合进行划分，得到k个子数据集构造＊M步：M步：选择，使得最大化其中nnyzpp,lazyy)(,ylEyQnpnlazyylazyklazyilazyyyy,...,,...,11n),(yQn6.混合EM算法＊懒惰E步：fori=1tok得到令forj≠i计算＊M步：选择，使得最大化其中nlazyilazyinlazyiyzpp,),(),(1lazyinlazyinlazyiyQyQjnjlazyinlazyilazyinlazyinyQyQyQyQ,,,,),(),(1lazyinlazyinlazyiyQyQ),(),(1jnjjnjyQyQ1n),(yQn6.混合EM算法上述算法描述的是整体上进行第n+1次迭代的过程。并不是每次迭代都需要首先执行完整E步，可以在多次迭代懒惰E步后在应用完整E步进行调整。混合EM算法能很好地适应大数据集的情况，对于数据集较小的情况下其优势不明显，甚至在参数设置不合理的时候，性能还不如标准EM算法。7.递增EM算法•选取增量因子•初始子样本数量选取为•在子样本达到最佳拟合真实分别的前提下，加入新的样本，再次进行拟合，若为最佳拟合，再次加入新的样本。。。如此反复，直到子样本的数量与完全样本一致时停止增加。•在递增的过程中，子样本逐渐逼近完全样本的真实分布。2/lnNddNM/7.递增EM算法•令每次子样本新增样本数h=M/d•这里的M是样本增加前一次的M值，则更新后的M变为M+M/d，这种增量方式是逐步递增的过程。•令表示完整的数据集，是随机选择的大小为M的子样本，则可得到Q函数的近似Nxx,...,1),...,(,...,11NttxxxxM1tMQ7.递增EM算法•令表示t次迭代与t-1次迭代的似然差值，为一充分小的数。•若说明子样本集与其相应的子样本模型并不匹配，需要继续迭代；反之，说明子样本集与其相应的子样本模型匹配，而与完全样本集的高斯模型进行匹配还需要一段距离，因此需要增加额外的信息量进行样本估计，即新增加样本进行训练。)()(1tMtMQQBB7.IEM算法实现•给定高斯混合成分数K，增量因子d，初始子样本M=N/d，初始参