Simple and globally convergent methods for accelerating the convergence of any EM algorithm
Simple and globally convergent methods for accelerating the convergence of any EM algorithm
复制标题
DOI：
10.1111/j.1467-9469.2007.00585.x
复制
发表时间：
2008-06-01
影响因子：
1
通讯作者：
Roland, Christophe
中科院分区：
文献类型：
--
作者：
Varadhan, Ravi;Roland, Christophe
期望最大化（EM）算法由于其简单性和稳定性（如似然单调增加），是不完全数据问题中获得最大似然估计的一种流行方法。然而，在许多应用中，EM的稳定性是以缓慢的线性收敛为代价的。我们已经开发了一类新的迭代方案，称为平方迭代方法（SQUAREM），以加速EM，而不影响简单性和稳定性。SQUAREM通常在具有大部分缺失信息的问题中实现超线性收敛。通过将SQUAREM看作EM的延拓，可以很容易地得到全局收敛的格式。SQUAREM在高维问题中特别有吸引力，并且在无法获得特定于模型的分析见解的问题中特别有吸引力。SQUAREM可以很容易地实现为任何EM类型算法的“现成”加速器，因为它只需要EM参数更新。我们提出了四个例子来证明SQUAREM的有效性。有一个通用的实现（用R编写）。
The expectation-maximization (EM) algorithm is a popular approach for obtaining maximum likelihood estimates in incomplete data problems because of its simplicity and stability (e.g. monotonic increase of likelihood). However, in many applications the stability of EM is attained at the expense of slow, linear convergence. We have developed a new class of iterative schemes, called squared iterative methods (SQUAREM), to accelerate EM, without compromising on simplicity and stability. SQUAREM generally achieves superlinear convergence in problems with a large fraction of missing information. Globally convergent schemes are easily obtained by viewing SQUAREM as a continuation of EM. SQUAREM is especially attractive in high-dimensional problems, and in problems where model-specific analytic insights are not available. SQUAREM can be readily implemented as an 'off-the-shelf' accelerator of any EM-type algorithm, as it only requires the EM parameter updating. We present four examples to demonstrate the effectiveness of SQUAREM. A general-purpose implementation (written in R) is available.