em算法及其改进

1、EM算法及其改进 E步： 对 或 求条件期望，从而把Z 去掉，即 M步： 将 极大化，找到一个点 ，使 即 反复迭代，直到 或 充分小时停止迭代。 dzYzfzYfYZYfEQ i Yy i z i ),(),(log(,),(log),( )()( ),(ZYf),(logZYf ),( i Q 1i ),(max),( 1iii QQ ),(maxarg )() 1(ii Q ii 1 ),(),( 1iiii QQ EM算法 优点：其一,M步仅涉及完全数据极大似然,通常计算 比较简单;其二,它的收敛是稳定的,因为每次迭代似 然函数是不断增加的. 缺点：当缺失的信息量很大或完全数据对数似然

2、的 估计本身比较复杂时,EM算法的收敛速度将很缓慢。 基于EM算法的缺点产生了各种改进的算法，这些改 进的算法都着眼于改善收敛速度和保证收敛性质。 EM算法优缺点 在很多问题中，若对参数施加一定的函数约束，可 以使完全数据极大似然估计变得相对简单。ECM算 法中E步采用和EM算法相同的计算过程，用几个简 单的CM步来代替EM算法的M步，CM步中每步都是 在对应参数约束下，使得EM算法定义的Q函数达到 最大。 ECM算法 其中的CM步定义如下：把参数 划分为 ， 是关于 的函数，当第t+1次迭代时， 分别在 的约束下找到 ，使之在 中最大化 。在EMC算法中下 一次迭代的初始值 。 S s t

3、ss gg )1( )( )( S s t S s t s )1( ( ) 1 ( S s t Q )( )1( S s t t ECM算法 ),.,( 21s )( s g),.,( 21s 要保证ECM算法的收敛性质， 的选取十分重要 的，一个常用的选则是 ， 即在M步的第k+1次迭代中，要进行s次估计，每次 估计出 中的一个参数。当估计 时，假定其他s-1 个估计的参数不变，然后采用一般的似然估计的方 法估计它，接着用新的估计值代替原来的估计值进 行对参数 的估计，并保持其他参数不变。以此类 推完成对 的估计。 )( s g ),.,.,()( 111Ssss g 1 2 s (1)当M

4、步没有显式的表达式时,CM步通常有 显式的表达式. (2)即使CM步没有显式的表达式,但ECM算法 通常更加稳定,因为它的极大化是在更低维度 的参数空间中进行的. ECM算法优点 它是ECM算法的推广，在ECM算法中，CM步是对 完全数据对数似然函数的期望进行极大化。同样， 可以把这种思想运用到观察数据对数似然上，也就 是说，在CM步上，可以考虑在一定的约束条件下， 对对数似然函数进行极大化，因此就产生了ECME 算法。 ECME算法 ECME算法形式化定义： ECME算法的第t+1次迭代步骤如下： E步：与ECM算法的E步相同。 CM步：当 时，求出 ，使得 当 时，求出 ，使得 ECME算

5、法 Ss LQ ,.,2 , 1 Q sS st ),(),( tt S st QQ )()( 1 S s t ss gg L s S st )()(LL S st )()( 1 S s t ss gg Aitken-ECM法： 首先在参数估计的初始阶段采用ECM算法，当算法的收敛速 度比较缓慢的时候我们切入Aitken算法来提速。考虑到Aitken在 附近无法稳定收敛，则再转入ECM算法进行最后的稳定收敛过程。 A-ECM算法 方法方法优点优点缺点缺点 ECM法 保证EM收敛的基本条件 下收敛到一个稳定点 后期收敛速度不理想 Aitken 法 末尾使用Aitken法收敛速 度很快，迭代过程中不保 证似然是稳定增长的 当参数离ML较远时效果不好， 有时候会在收敛值附近振荡 Aitken算法的第k+1次迭代是按照如下步骤进行的： （1） 是Aitken第k次迭代的估计值 （2）以 为标准EM算法的初始值，进行迭代计算第k+1步 估计值 （3）然后将 带入公式进行计算得到第k+1步的Aitken 估计值 （4）重复以上的步骤直至收敛为止 Aitken加速收敛算 法 n n nn x x xx 2 2 1 )( k k 1k EM 1k EM 1k （1）ECM算法收敛速度进入缓慢阶段，切换为 Aitken算法的判定可以根据以下准则： （2）可以根据似然函数 的