TR-IIS-07-012    Fulltext

The Expectation-Maximization (EM) algorithm is one of the most popular algorithms for parameter estimation from incomplete data, but its convergence can be slow for some large-scale or complex machine learning problems. Extrapolation methods can effectively accelerate EM, but to ensure stability, the learning rate of extrapolation must be compromised. This paper describes the TJ²aEM algorithm, a targeted aggressive extrapolation method that can make much more aggressive extrapolations without causing instability problems. We show that for a wide variety of probabilistic models, TJ²aEM can converge many times faster than other acceleration methods under different data distributions and initial conditions. In addition to EM, TJ²aEM can also be applied to other bound optimization methods, including generalized iterative scaling, non-negative matrix factorization and concave-convex procedure.

Keywords: Expectation-Maximization (EM), Aitken Acceleration, Extrapolation, Optimization, Triple-Jump Acceleration