How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models
How well do SEM algorithms imitate EM algorithms? A non-asymptotic analysis for mixture models
复制标题
DOI：
10.1007/s11634-019-00366-7
复制
发表时间：
2019-07
影响因子：
1.6
通讯作者：
Johannes Blömer;Sascha Brauer;Kathrin Bujna;Daniel Kuntze
中科院分区：
文献类型：
--
作者：
Johannes Blömer;Sascha Brauer;Kathrin Bujna;Daniel Kuntze
在本文中，我们对不同混合模型的 EM 和 SEM 算法进行了理论和实验比较。 SEM 算法是 EM 算法的随机变体。 SEM 算法背后的定性直觉很简单：如果观测数量足够大，那么我们期望随机 SEM 算法的更新步骤与确定性 EM 算法的相应更新步骤类似。在本文中，我们量化了这种直觉。我们证明，只要输入集满足某些属性，任何类 EM 算法及其随机变体的更新方程都有很大概率是相似的。例如，这个结果适用于众所周知的高斯混合模型的 EM 和 SEM 算法以及多元幂指数分布的类 EM 和 SEM 启发法。我们的实验证实，我们的理论结果也适用于大量连续的更新步骤。因此，我们补充了 SEM 算法的已知渐近结果。我们还表明，对于多元高斯和多元拉普拉斯混合模型，SEM 更新步骤的运行速度几乎是 EM 更新集的两倍。
In this paper, we present a theoretical and an experimental comparison of EM and SEM algorithms for different mixture models. The SEM algorithm is a stochastic variant of the EM algorithm. The qualitative intuition behind the SEM algorithm is simple: If the number of observations is large enough, then we expect that an update step of the stochastic SEM algorithm is similar to the corresponding update step of the deterministic EM algorithm. In this paper, we quantify this intuition. We show that with high probability the update equations of any EM-like algorithm and its stochastic variant are similar, given that the input set satisfies certain properties. For instance, this result applies to the well-known EM and SEM algorithm for Gaussian mixture models and EM-like and SEM-like heuristics for multivariate power exponential distributions. Our experiments confirm that our theoretical results also hold for a large number of successive update steps. Thereby we complement the known asymptotic results for the SEM algorithm. We also show that, for multivariate Gaussian and multivariate Laplacian mixture models, an update step of SEM runs nearly twice as fast as an EM update set.