The expectation–maximization algorithm, usually abbreviated EM, is an iterative algorithm for maximum likelihood estimation in statistical models involving missing observations or unobserved variables. It alternates between calculating expectations under the current model and updating model parameters to maximize an expected complete-data log-likelihood. Its general formulation accommodates mixture models, missing-data problems, and other applications in statistics and machine learning. Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin presented and named the general framework in 1977, drawing together methods previously developed for particular problems. (doi.org)
Statistical formulation
Let (x) denote observed data, (z) denote unobserved quantities, and (\theta) denote model parameters. A model specifies the joint probability distribution (p(x,z\mid\theta)). The observed-data likelihood function is obtained by marginalizing over (z):
[ p(x\mid\theta)=\sum_z p(x,z\mid\theta), \qquad \ell(\theta)=\log p(x\mid\theta). ]
For continuous (z), the sum becomes an integral. Directly maximizing this expression can be difficult, whereas the complete-data log-likelihood (\log p(x,z\mid\theta)) may have a simpler structure. EM exploits that difference. The unobserved quantities need not be literally missing measurements: in a mixture model, they can indicate which component generated each observation. (arxiv.org)
Unlike ordinary missing-data imputation, EM does not generally replace unknown values with fixed estimates and then treat them as observed. Its expectation step averages the complete-data log-likelihood over the entire conditional distribution of the unknown quantities. This distinction matters when that log-likelihood depends on second moments or other nonlinear functions of missing values. (support.sas.com)
Expectation and maximization steps
Starting from an initial parameter value (\theta^{(0)}), EM repeats two operations:
Expectation step, or E-step. Calculate
[ Q(\theta\mid\theta^{(t)})
\mathbb{E}_{z\mid x,\theta^{(t)}} [\log p(x,z\mid\theta)]. ]
This conditional expectation uses the current posterior distribution of (z), conditional on the observed data. The distribution is fixed during this step, while (\theta) remains the argument of the function being constructed. Thus, the E-step produces a function of candidate parameters, not merely one expected numerical value. (support.sas.com)
Maximization step, or M-step. Set
[ \theta^{(t+1)} \in \operatorname*{arg,max}_{\theta} Q(\theta\mid\theta^{(t)}). ]
Some models yield closed-form updates; others require numerical optimization. In suitable exponential-family models, computing expectations of complete-data sufficient statistics is enough to perform the update. Iteration continues until a stopping condition is satisfied, often based on changes in likelihood or parameters. (math.pku.edu.cn)
Why likelihood does not decrease
EM can be understood through Jensen’s inequality and the evidence lower bound. For a distribution (q(z)), define
[ \mathcal{F}(q,\theta)
\mathbb{E}_q[\log p(x,z\mid\theta)]
\mathbb{E}_q[\log q(z)]. ]
The identity
[ \ell(\theta)
\mathcal{F}(q,\theta) + D_{\mathrm{KL}}!\left( q(z),|,p(z\mid x,\theta) \right) ]
expresses the gap between the bound and the log-likelihood as a nonnegative Kullback–Leibler divergence. The E-step selects the exact conditional distribution, making the bound tight at the current parameters. The M-step increases this bound while holding (q) fixed. Consequently, exact EM does not decrease the observed-data likelihood. (cs229.stanford.edu)
Monotonicity is not a guarantee of a global optimum or of convergence of the parameter sequence. Under appropriate regularity conditions, limit points are stationary points; they can include local maxima or saddle points. C. F. Jeff Wu’s 1983 analysis established convergence results under explicit assumptions, distinguishing likelihood convergence from parameter convergence. (markirwin.net)
Example: Gaussian mixtures
A standard application is fitting a Gaussian mixture model for density estimation or probabilistic cluster analysis. Suppose
[ p(x_i\mid\theta)
\sum_{k=1}^{K} \pi_k,\mathcal{N}(x_i\mid\mu_k,\Sigma_k), ]
where mixture weights satisfy (\pi_k\geq0) and (\sum_k\pi_k=1). Each component has a mean (\mu_k) and covariance matrix (\Sigma_k). Component memberships are unobserved, making this an unsupervised learning setting. (cs229.stanford.edu)
The E-step computes responsibilities, the conditional probabilities that observations belong to components:
[ r_{ik}
\frac{ \pi_k^{(t)} \mathcal{N}(x_i\mid\mu_k^{(t)},\Sigma_k^{(t)}) }{ \sum_j \pi_j^{(t)} \mathcal{N}(x_i\mid\mu_j^{(t)},\Sigma_j^{(t)}) }. ]
With (N_k=\sum_i r_{ik}), the M-step updates
[ \pi_k^{(t+1)}=\frac{N_k}{n}, \qquad \mu_k^{(t+1)}=\frac{\sum_i r_{ik}x_i}{N_k}, ]
[ \Sigma_k^{(t+1)}
\frac{1}{N_k} \sum_i r_{ik} (x_i-\mu_k^{(t+1)}) (x_i-\mu_k^{(t+1)})^\top. ]
Responsibilities permit fractional membership rather than forcing each observation into one cluster. These weighted updates illustrate how unobserved assignments become expected counts and moments. (cs229.stanford.edu)
Extensions and limitations
Generalized EM replaces exact maximization with an update that merely increases (Q), preserving the likelihood-ascent property. Monte Carlo EM approximates an intractable E-step by simulation, sometimes using Markov chain Monte Carlo. Simulation error means individual updates need not increase the exact likelihood, and convergence requires additional conditions. (math.pku.edu.cn)
EM also supports maximum a posteriori estimation by adding the log prior density to the M-step objective. Original applications included censored and truncated observations, variance-component estimation, and factor analysis. (doi.org)
Practical limitations include initialization sensitivity, multiple likelihood optima, and potentially slow numerical convergence. A small change between iterations does not establish global optimality. The ease of implementation also depends on the chosen complete-data representation: introducing unobserved quantities is useful only when the resulting expectations and maximization problems are computationally manageable. (markirwin.net)