The Expectation Maximisation (EM) algorithm is widely used to optimise non-convex likelihood functions with hidden variables. Many authors modified its simple design to fit more specific situations. For instance the Expectation (E) step has been replaced by Monte Carlo (MC) approximations, Markov Chain Monte Carlo approximations, tempered approximations... Most of the well-studied approximations belong to the stochastic class. By comparison, the literature is lacking when it comes to deterministic approximations. In this paper, we introduce a theoretical framework, with state-of-the-art convergence guarantees, for any deterministic approximation of the E step. We analyse theoretically and empirically several approximations that fit into this framework. First, for cases with intractable E steps, we introduce a deterministic alternative to the MC-EM, using Riemann sums. This method is easy to implement and does not require the tuning of hyper-parameters. Then, we consider the tempered approximation, borrowed from the Simulated Annealing optimisation technique and meant to improve the EM solution. We prove that the tempered EM verifies the convergence guarantees for a wide range of temperature profiles. We showcase empirically how it is able to escape adversarial initialisations. Finally, we combine the Riemann and tempered approximations to accomplish both their purposes.
翻译:期望最大化算法( EM) 被广泛用于优化非混凝土概率功能 。 许多作者修改其简单设计以适应更具体的情况。 例如, 期待( E) 步骤已经被蒙特卡洛( Monte Carlo) 近似值、 Markov 链锁 蒙特卡洛( Monte Clo) 近近似值、 温和近近似值所取代... 大多数经过充分研究的近似值都属于随机类。 相比之下, 文献在确定性近似时缺乏。 本文中, 我们引入了一个理论框架, 配有最先进的趋同保证, 用于确定 E 步骤的任何确定性近似值。 我们分析了符合这个框架的理论和经验性( E) 步骤。 首先, 对于具有棘手 E 步骤的案例中, 我们引入了一种确定性替代 MC- EM 的替代方法 。 这个方法很容易实施, 并且不需要调整超分辨度的准度。 然后, 我们考虑从模拟的安纳纳罗纳化优化技术中借用的调近似, 目的是改进EM 解决方案的解决方案。 我们证明精准性EM 最终能够将精准度测试其升级到升级 。