EM Algorithm

Definition

The EM (Expectation-Maximization) algorithm is an iterative method for maximum likelihood estimation when data are incomplete or can be treated as incomplete by augmenting the observed data with latent variables. Each iteration alternates between an E-step (compute expected sufficient statistics of the complete data given the observed data and current parameter estimates) and an M-step (maximize the completed-data log-likelihood given those expectations). Formalized in general by Dempster, Laird, and Rubin (1977), anticipated for latent class models by Goodman (1974) and for general exponential families by Sundberg (1974, 1976).

Key Ideas

Incomplete data formulation: Define a complete data vector $(x, z)$ where $x$ is observed and $z$ is latent (missing). The complete-data distribution is a tractable exponential family with sufficient statistic $T = t(x, z)$ . The observed data is $y = \varphi(x)$ .
Sundberg likelihood equation (1974): For an exponential family with sufficient statistic $T$ , if $y = \varphi(x)$ is observed rather than $x$ , the likelihood equation for parameter $\omega$ takes the form $E_\omega[T|y] = E_\omega[T]$ .
DLR iteration (Dempster-Laird-Rubin 1977): Given current estimate $\hat{\omega}^{(n)}$ $\overset{ω}{^}^{(n)}$ :
- E-step: $t^{(n)} = E_{\hat{\omega}^{(n)}}[T | y]$
- M-step: Solve $E_\omega[T] = t^{(n)}$ for $\omega$ to give $\hat{\omega}^{(n+1)}$
Monotone convergence: Each iteration weakly increases the observed-data log-likelihood; the sequence converges to a stationary point (local maximum or saddle point), not necessarily the global maximum.
Model flexibility (Goodman 1974): Imposing equality constraints on a latent class model merges the corresponding EM equations — constrained model algorithms are derived by addition, not re-derivation.
EM vs. Newton-Raphson: EM converges more slowly (linear rate vs. quadratic) but does not require computing or inverting the Hessian. Particularly advantageous in high dimensions or when the Hessian is expensive to compute.
Standard errors: Not a direct EM output. Options: Louis (1982) observed information formula using complete-data Fisher information and missing information; parametric bootstrap; or Markov Chain Monte Carlo (MCMC).

How It Works

Latent Class Model

Complete data: augment the observed $I\times J\times K\times L$ table with a latent class dimension, creating $X_{ijklv}$ for $v=1,\ldots,m$ . The multinomial of $X_{ijklv}$ is an exponential family with canonical parameters $\theta_{iv}^A = \ln\pi_{iv}^A - \ln\pi_{Iv}^A$ , etc.

E-step: Compute posterior class membership for each observed cell: $\pi^*_{ijklv} = \frac{\pi_{iv}^A\pi_{jv}^B\pi_{kv}^C\pi_{lv}^D\varphi_v}{\sum_{v'}\pi_{iv'}^A\pi_{jv'}^B\pi_{kv'}^C\pi_{lv'}^D\varphi_{v'}}$ Expected marginals: $p_{iv}^{A(n)} = \sum_{jkl} x_{ijkl}\pi^*_{ijklv}$ , $f_v^{(n)} = \sum_{ijkl} x_{ijkl}\pi^*_{ijklv}$ .

M-step: $\pi_{iv}^A \leftarrow p_{iv}^{A(n)} / \sum_i p_{iv}^{A(n)}$ , $\varphi_v \leftarrow f_v^{(n)}/n$ .

Item Response Theory (Pure Rasch Model)

Complete data: $(y_i, \theta_i)$ for each person $i$ , where $\theta_i$ is latent ability. Sufficient statistics $t_1 = \sum_i\theta_i$ , $t_2 = \sum_i\theta_i^2$ .

E-step: $t_1^{(n)} = \sum_i E[\theta_i|y_i]$ , $t_2^{(n)} = \sum_i E[\theta_i^2|y_i]$ via one-dimensional numerical integration.

M-step: $\hat{\mu}_\theta = t_1^{(n)}/n$ , $\hat{\sigma}_\theta^2 = t_2^{(n)}/n - \hat{\mu}_\theta^2$ .

Mixture of Normals

Complete data: $(x_i, z_i)$ where $z_i \in \{1,\ldots,K\}$ is component membership. E-step: $r_{ik} = p_k\phi(x_i|\mu_k,\sigma_k^2)/\sum_{k'}p_{k'}\phi(x_i|\mu_{k'},\sigma_{k'}^2)$ . M-step: update $p_k, \mu_k, \sigma_k^2$ from weighted sample moments.

Why It Matters

The EM algorithm transformed inference for latent variable models: ML equations that Lazarsfeld (1950) deemed intractable were shown by Goodman (1974) to have a simple iterative solution. The framework unifies latent class, mixture model, item response, and hidden Markov model estimation under a single computational paradigm. Its monotone convergence property and avoidance of matrix inversion make it a default estimator for high-dimensional mixture problems in statistics and machine learning.

Open Questions

Multiple local maxima: persistent issue for latent class models with many classes; different random initializations can yield different solutions; theoretical conditions for unimodality are restrictive.
Slow convergence: linear convergence rate near flat likelihood surfaces; accelerated variants (Expectation Conditional Maximization [ECM], ECM-Either [ECME], SEM) and quasi-Newton combinations address this at the cost of implementation complexity.
Standard errors: Louis (1982) formula is elegant but requires additional E-step computations; in practice, bootstrapping is common.