在上一篇文章写到了EM算法的收敛性证明以后便匆匆的结尾,然后我出去玩了几天,玩的爽了,回来开始继续补之前的flag:

在上一篇文章中,当我们得到收敛的结果以后,就需要对收敛的速度捷星一个解释,下面可以考虑该方法的收敛阶数.可以看出,EM算法其实本质上是定义了一个映射:

当EM算法开始收敛时,如果收敛到映射的一个不动点,那么就可以认为

设上边函数的一阶导数为一个Jacobi矩阵,其(i,j)元素为

由公式可以得到下边的式子:

对公式进行Taylor展开得到:

根据其收敛特性可以知道,如果p=1,EM算法是线性收敛的,当p>1,如果观测的结果信息为正定的,那么收敛仍然可以认为是线性的.

EM收敛的收敛率可以定义为:

迭代算法的收敛率p是等于矩阵导数的最大特征根,Jacobi矩阵表示的是信息缺失的比例,所以p是一个可以有效的表示缺失信息的一个比例的标量,缺失信息的比例其实就是单位矩阵I 减去已经观测到的信息占完全信息的比例,其实就是:

EM算法的收敛速度与缺失信息比例这个量是紧密相关的,缺失信息比率其实就是EM算法中的映射的斜率,由这个斜率来控制EM的收敛的速度.缺失信息比率的最大特征值称为全局收敛率,但是p越大收敛速度是越慢的,所以定义了一个矩阵S = I - 缺失信息比率 为加速矩阵,s = 1-p称为全局加速,当缺失信息比例较大时,那么EM算法还是要经历比较慢的收敛速度的.比如与 牛顿法相比，EM的收敛速度会显得极端的慢尤其是当缺失信息所占的比 例很大时;但是因为EM算法的稳定性以及执行的方便,但是它依然有很强的吸 引力。之后我们将讨论EM算法的加速方法。

4:EM算法的改进

在介绍EM算法的历史的时候,我们就知道了EM算法之所以被广泛的应用其实就是因为他可以能够简单的执行然后能够通过稳定的上升的算法得到似然函数最优解或者是局部最优解,这样的话,就使得EM算法拥有极强的适用性和可操作性,但是依旧存有三个主要问题,所以接下来希望可以介绍一下为了将EM算法应用的更广泛,人们采取了哪些方法(这里将会分为两部分,一部分是介绍改进E步算法,另一部分是改进M步的部分)

改进E步

1:在之前的介绍中,我们可以理解M步其实基本和完全数据处理差不多,一般情况比较简单,但是E步的计算是需要在观测的数据的条件下求”缺失数据”的条件期望,然后再去求完全数据下的期望对数似然(这个之前有提到),但是在求期望的过程中,计算是最难的问题,因为在某些情况下获得期望的显式是很难很难的,这样就限制了算法的使用,因此就有了MCEM算法的产生,他是利用近似实现的方法来进行求解的,下面将详细的阐述下这个算法:

1:在计算过程中,第k+1个E步可以用下面的两步代替:

E1:由Py|x(y|x,0(k))中随机抽取m(k)个数,构成独立同分布的缺失数据集y1,y2,.......ym(k),集合中的每一个y(i)都是用来补充观测数据的,从而构成了一个完整的数据集合z(j)=(x,yj);

E2:计算下面的公式:

得到的结果其实就是对于Q(0|0(k))的Monte,Carlo估计,而且只要m足够的大,我们可以近似认为Q(0|0(k))和Q(0|0(k))的Monte,Carlo估计是基本相等的.

在完成上面的两个E步以后,就可以在M步中对Q(0|0(k))的Monte,Carlo估计进行极大化求解,从而得到0(k+1)代替0(k).

在使用MCEM算法中有几个考虑的地方:

1:首先是m(k)的确定,MCEM算法的结果精度主要依赖于所选择的m(k),从精度考虑m(k)自然越大越好，但是如果m(k)过大会导致计算速度变慢。所以m(t)的选择极 为重要，推荐策略是在初期的EM迭代中使用较小m(k)，并随着迭代的进行逐渐增大m(k)，以减小使用Monte Carlo毛E模拟计算Q导致的误差。

2:另外一点是对收敛性进行判断，MCEM算法和EM算法收敛方式不同，根据上 述理论，这样得到的0(k)不会收敛到一点，而是随着迭代的进行，0(k)的值最终在真实的最大值附近小幅跳跃，所以在MCEM算法中，往往需要借助图形来进行收敛性的判别。在经过多次迭代之后，假如估计序列围绕着0=0(*)上下小幅波动，就认为估计序列收敛了。

改进M步

1:ECM算法

针对EM算法的E步进行改进之后就会想到继续改进M步的计算。EM算法的吸引力之一就在于Q(0|0(k))的极大化计算通常比在不完全数据条件下 的极大似然估计简单，这是因为Q(OlO(k))与完全数据下的似然计算基本相同。然而，在某些情况下,M步没有简单的计算形式,Q(0|0(k))的计算并没 有那么容易实施,为此人们提出了多种改进策略，以便于M步的实施。改

进M步的一个好的方法是避免出现迭代的M步，可以选择在每次M步计算中 使得Q函数增大，即Q(0(k+1|0(k))>Q(0(k)|0(k))，而不是极大化它。GEM算 法就基于这个原理，在每个迭代步骤中GEM算法增大似然函数的值，但缺 少函数增大的过程细节，所以不能保证收敛性。Meng和Rubin与1993年提出 的ECM算法是GEM算法的子类，但是有更广泛的应用。

ECM算法为了避免出现迭代的M步，用一系列计算较简单的条件极大

化(CM)步来代替M步，它每次对p求函数Q的极大化，都被设计为一个简 单的优化问题，我们称这一系列较简单的条件极大化步的集合为一个CM循环，因此认为ECM算法的第k次迭代中包括第k个E步和第k次CM循环。

这样M步的步骤也分为两个:

1:令S表示每个CM循环里CM步的个数，对s=1，2，…，S，第k次迭代过 程的第k次CM循环过程里，第s个CM步需要在约束条件

下求函数Q(0|0(k))的最大化，其0(k+(s-1)/s)是第k次CM循环的第s一 1个CM步得到的估计值.

2:当完成了S次的CM步的循环，令0(k+l)=O(k+S/S)，并进行第七+1次 的ECM算法的E步迭代

因为每一次CM步都增加了函数Q，Q(0(k+s/S)|0(k))>Q(0(k)|0(k))，所 以显然ECM算法是GEM的一种。为了保证ECM算法的收敛性，需要确保

每次的CM步的循环都是在任意的方向上搜索函数Q(0|0(k))的最大值点，这 样ECM算法当被允许在p的原始空间上进行极大化，可以保证在EM收敛的基本同样的条件下收敛到一个稳定点，和EM算法一样，ECM算法也不能 保证一定收敛到全局极大点或者局部最优值。下面考虑ECM算法的收敛速度，与EM算法相似，ECM算法的全局收敛速度表示如下:

迭代算法的收敛率P等于矩阵(0*)的最大特征值，由于P值越大也就是缺失信息比例越大，收敛速度越慢，因此算法的收敛速度定义为1一P。通过 计算看出，ECM算法的迭代速度通常和EM算法相同或者相近，但是就迭代 次数来说，ECM算法要比EM算法快。

根据ECM算法理论，可以看出构造有效的ECM算法是需要技巧的，

需要对约束条件进行选择。习惯上可以自然的把0分成S个子向量0=(01,02,03,,,,,0s)。然后在第8个CM步中，固定0其余的元素对以求函数Q的 极大化。这相当于用g(0)=(01,02,,,,,,0s)作为约束条件。这种策略被称为迭代条件模式。

根据ECM算法的特点,可以看出ECM算法的优点:

1:如果碰见M步没有简单化形式，CM循环通常能简化计算2:ECM算法是在护的原始参数空间进行极大化，更加稳定，能稳定收敛.

ECME算法:

ECME算法是Lin和Rubin在1994年为了替换ECM算法的某些CM步而提

出来的，它是ECM算法的一种改进形式，ECME算法的特点就是在在CM步

极大化的基础上，即针对受约束的完全数据对数似然函数的期望Q(0|0(k)) 进行极大似然估计，并且在一些步上极大化对应的受约束的实际似然函数L(0|Z)。

ECME算法的第k+1次迭代的M步形式:

E步和CM步不断重复，迭代完后，得到0(k+1)，继续进行第k+2步的E步 计算，直至收敛。

从这里可以看出，这一算法拥有EM和ECM两种算法的稳定单调收敛特 性，以及相对较快的收敛方法。即实现EM算法的基本的简单性，另外可以看出ECME能比EM和ECM算法拥有更快的收敛速度，从迭代数以及迭代至 收敛所需时间都要快。这一改进主要有两个原因，第一，在ECME算法中的 某些极大化步，居于完全数据的实际似然函数被条件极大化了，而不是像之前的EM和ECM算法那样近似;第二，ECME算法可以在极为有效的地方， 对那些受到约束的极大化进行快速收敛的数值计算。

和EM、ECM算法一样，对ECME算法，0(k)-0(k+1)映射在0*上的导数 也就是斜率决定着ECME的收敛速度，由已观测数据、缺失数据、完全数据 信息阵来计算，经过计算证实ECME算法比EM、ECM算法的收敛速度快， 计算方法比较复杂;但是可以从直观上看，因为在CM步上极大化实际似 然函数L(0|z)而不是完全数据对数似然函数的期望Q(0|0(k))，显然要更为精确，因为Q函数是近似的。总的来说，就迭代次数以及实际需要的时间来看，ECME算法是优于EM、ECM两种算法的，尤其是问题比较复杂时候。

AECM:

EM算法的另一种变型，期望条件极大化(AECM)算法，是在ECME算

法的基础上，对应于ECM、ECME算法AECM算法在CM步，会极大化一些与L，Q不同的函数。极大化函数三是数据无缺失下的特殊情况，AECM的迭代也是由一系列循环组成的，每个循环由一个带有完全数据和缺失数据的特别定义的E步，以及对应那个特别定 义的CM步组成的，如此一系列循环构成的集合确定了一个完整的AECM迭 代，该循环集合在ECM参数化的意义上是空间充满的极大化，和ECME一 样，能够产生很高的计算效率。

PX-EM算法:

1998年提出的参数扩展EM算法(PX.EM)极大的 加快了EM算法的收敛速度，PX-EM算法主导思想是为了修正M步进行协方 差的调整，得到完全数据的额外信息。可以看出，在EM算法中，完全数据下p(z|0)和观测数据下p(xl0)，有不同的参数，所以PX-EM算法通过引进 附加参数口，对参数集进行了扩充，如果在原模型中参数为0，新扩展的参数空间=(0*，a)，此时0*与EM算法中护是相同维数的，且当a=a(0)时，限制口0*=0，得到原来的模型，即有p(z|0)=p(zl参数空间)。

使用时,应当要满足两个条件:

1.存在某个己知的变换R，使得0=R(0*,a)

2.当a=a(0)时，选择扩展模型，使得在已观测到的数据X上不存在a的信 息，即

3.在扩展模型中，参数≯对完全数据Z=(X，y)是可识别的PX-EM算法作为EM算法的扩展模型，它的第k+1次迭代形式:

1:PX-E:

计算下列式子:

2:PX-M步:

计算下式:

,然后令PX-E,PX-M步不断地重复,直到收敛.

PX-EM算法的每一步都增大p(x|0*,a)，由于当a=a0时，它等 于p(xlO)，因此PX-EM算法的每一步都增大了有关的似然函数p(xlO)，而 且PX-EM算法的收敛性质与EM算法是平行的，PX-EM算法最终将收敛到 一个稳定点和局部最大值点。下面需要考虑的是PX-EM算法的收敛速度为

什么比EM算法更快。

在适当的变换0=R(0*,a)下，从≯=(0*,a)到(0，a)的参数化是比较 接近的。之前提到对一切a，a’存在p(x|0*,a)=p(x|0*，a’)，可以看出根据p(z|0，a)能得到已观测数据和完全数据下的信息矩阵:

与EM算法的收敛结论相似，缺失信息比率为:

这两个矩阵之差为半正定的意义下,这与之前EM算法中的缺失信息比例要小:

由于之前提到过,缺失信息比例越大,收敛速度越慢,所以PX-EM算法的收敛速度是要比EM要快的,其实也就是拓展参数空间,增加参数a的作用是将完全信息量进行改变,相应的缺失信息也会减少,这样对减少的缺失信息所占比例起到作用,从而使EM算法加速:

这样的话可以看出PX-EM的优点来:

1:只要对EM算法基础小的修改,设计比较简单

2:充分利用有效信息拓展完全数据,估计参数,保持了EM算法的单调收敛性,并且收敛速度快.

EM算法作为处理不完全数据参数估计问题的一种重要方迭代法，因为 其实现简单，方法易于操作，估计结果稳定上升，收敛性好，所以有着极 为广泛的应用。但是算法依然存在一些不尽如人意的地方，比如收敛速度 慢、E步积分期望计算困难、M步没有显式的计算形式等等，面对EM算法 主要存在的三个问题，本章节主要内容就是在EM算法发展过程中，人们 为了克服以上问题对其进行的改进以及变型，提出了目前流行的一些算法 的原理、算法、性质以及实例应用。比如为了改进E步提出的Monte Carlo EM算法;改进M步的ECM、ECME、AECM算法;加快收敛速度的方法以 及PX-EM算法。

在下一篇文章中,我们将会探讨下EM算法的一些实际应用.

参考文献:

[1】Mark B L，Ephraim Y.An EM algorithm for continuous-time bivariate

Markov chains[J].Computational Statistics&Data Analysis，2013，57(1): 504-517.

【2】Ryd6n T.An EM algorithm for estimation in Markov-modulated Poisson

processes[J].Computational Statistics&Data Analysis，1996，21(4):431— 447.

[3]连军艳.EM算法及其改进在混合模型参数估计中的应用研究【D】.长安 大学，2006.

[4]杨基栋.EM算法理论及其应用【J1.安庆师范学院学报:自然科学版， 2009，15(4):30—35.

【5】王爱平，张功营，刘方.EM算法研究与应用【J1.计算机技术与发展，2009， 19(9):108-110.

【6】茹正亮，高安力。EM算法在不完全数据参数估计中的应用【J】.南京工程 学院学报:自然科学版，2009，6(4):9—12.

[7] EM算法原理与讲解 山东大学论文