Global Analysis of Expectation Maximization for Mixtures of Two Gaussians
Expectation Maximization (EM) is among the most popular algorithms for estimating parameters of statistical models. However, EM, which is an iterative algorithm based on the maximum likelihood principle, is generally only guaranteed to find stationary points of the likelihood objective, and these points may be far from any maximizer. This article addresses this disconnect between the statistical principles behind EM and its algorithmic properties. Specifically, it provides a global analysis of EM for specific models in which the observations comprise an i.i.d. sample from a mixture of two Gaussians. This is achieved by (i) studying the sequence of parameters from idealized execution of EM in the infinite sample limit, and fully characterizing the limit points of the sequence in terms of the initial parameters; and then (ii) based on this convergence analysis, establishing statistical consistency (or lack thereof) for the actual sequence of parameters produced by EM.
In many applications, each step is intuitive and can be performed very efficiently.
Despite the popularity of EM, as well as the numerous theoretical studies of its behavior, many important questions about its performance-such as its convergence rate and accuracy-have remained unanswered. The goal of this paper is to address these questions for specific models (described in Section 1.2) in which the observation Y is an i.i.d. sample from a mixture of two Gaussians.
Towards this goal, we study an idealized execution of EM in the large sample limit, where the E-step is modified to be computed over an infinitely large i.i.d. sample from a Gaussian mixture distribution in the model. In effect, in the formula forQ(η |η t ), we replace the observed data Y with a random variable Y ∼ f (y; η ) for some Gaussian mixture parameters η and then take its expectation. The resulting E-and M-steps in iteration t are E-step:
M-step:
This sequence of parameters (η t ) t≥0 is fully determined by the initial setting η 0 . We refer to this idealization as Population EM, a procedure considered in previous works of Srebro (2007) and Balakrishnan et al. (2014). Not only does Population EM shed light on the dynamics of EM in the large sample limit, but it can also reveal some of the fundamental limitations of EM. Indeed, if Population EM cannot provide an accurate estimate for the parameters η , then intuitively, one would not expect the EM algorithm with a finite sample size to do so either. (To avoid confusion, we refer the original EM algorithm run with a finite sample as Sample-based EM.)
The authors provide an analysis of the EM algorithm for two toy Gaussian mixture models characterizing the initial parameter values that lead to convergence. To this end, they use the true Q function-- obtained as an expectation instead of doing a sample average-- to give the ideal parameter sequence from a given initial value. This sequence is used for the characterization of the initial parameter values that lead to the true parameter. They also demonstrate that the actual sequence of real run converges to the idealized sequence in probability. Later they use this analysis to explore the shape of the expected log likelihood in the neighborhood of its stationary points.
Congratulations to the authors for a good paper!  Quality: The paper is technically sound with non trivial results. The conclusions of the paper are well supported by the theory. The condition on the initial parameter that leads to convergence to the the true parameter are particularly interesting.   Clarity: This is a very well written paper and it reads well. The math, though not trivial, is very accessible because of the presentation. The authors have provided adequate commentary that aids intuition and understanding.   Originality: The idea of the paper to analyze an idealized execution of the EM algorithm, by using the true Q function, instead of the one obtained by sample average is quite novel. The authors have provided adequate discussion of the relevant literature to inform the reader about the state of the art and evaluate their work in the right context.   Significance: The results of the paper are very interesting, they help understand the sensitivity of EM  (Gaussian mixtures) to initial parameters. Though the models considered are too restrictive for real world data, but they work more like a proof of concept for the analysis technique. It remains to see if the technique would work for more general models.   Strengths: Solid analysis  Weakness: Restrictive model.   Comments: In line 188-192 authors claim that their analysis for EM provides understanding for other ascent algorithm. However, in the justification that follows the conclusions about G(\eta) are still made using the Q function, which is in the EM framework. It is not clear what the authors want to claim about other algorithms.  Overall, I would recommend accepting the paper without reservations.