Expectation-Maximization Algorithm (EM)

In the Expectation step, the algorithm computes the expected value of the log-likelihood function with respect to the current estimate of the parameters.

• It does not impute a single 'best' guess for the missing data; instead, it calculates a probability distribution over the latent variables.
• This creates a Q-function, which is a lower bound to the observed-data log-likelihood.
• The output is a soft assignment of fractional counts, reflecting the uncertainty of the latent variable assignments.

In the Maximization step, the algorithm updates the model parameters by maximizing the Q-function derived in the E-step.

• This is typically a standard maximum likelihood estimation problem, often solvable in closed form.
• The new parameters are guaranteed to increase the observed-data log-likelihood (or leave it unchanged).
• The M-step re-estimates the parameters as if the fractional counts from the E-step were the true, complete data.

The EM algorithm possesses a monotonic convergence property, ensuring the likelihood never decreases after an iteration.

• It converges to a local maximum of the likelihood function, not necessarily the global optimum.
• Convergence is typically detected when the change in log-likelihood or parameter values falls below a predefined threshold.
• The rate of convergence is linear and depends on the proportion of missing information in the data.

EM is the standard tool for models where the full data consists of observed variables X and unobserved latent variables Z.

• Classic examples include Gaussian Mixture Models (GMMs), where cluster assignments are latent.
• Also used in Hidden Markov Models (HMMs) for inferring hidden state sequences.
• The framework treats the latent variables as the 'missing data' that makes the complete-data log-likelihood easier to maximize.

Since EM converges to a local maximum, the final solution is highly sensitive to the starting parameters.

• Poor initialization can lead to degenerate solutions or low-quality local optima.
• Common strategies include running multiple random restarts and selecting the run with the highest final likelihood.
• A robust alternative is to initialize using the output of a faster, heuristic method like k-means clustering.

The EM algorithm is a specific instance of variational inference where the approximate posterior is exact.

• In the E-step, the variational distribution over the latent variables is set to the true posterior P(Z|X, θ).
• This makes the evidence lower bound (ELBO) tight, touching the log-likelihood at the current parameter values.
• Generalized EM (GEM) relaxes the requirement to fully maximize the M-step, requiring only an increase in the Q-function.

A foundational statistical method for estimating model parameters by maximizing the likelihood function, which measures how probable the observed data is under a given set of parameters. EM is an iterative technique specifically designed to find MLEs when the likelihood is intractable due to latent variables. In complete-data scenarios, MLE can be solved directly; EM extends this to incomplete-data scenarios by iteratively filling in the gaps.

Unobserved or hidden variables in a probabilistic model that influence the observed data. In the context of EM, these are the missing data points or unknown class memberships that make direct optimization difficult. The E-step computes a probabilistic guess for these latent variables, while the M-step updates model parameters as if the guesses were observed truth. Examples include topic assignments in LDA or cluster memberships in Gaussian Mixture Models.

An asymmetric measure of how one probability distribution diverges from a second, reference distribution. EM can be interpreted as a coordinate ascent algorithm that minimizes the KL divergence between the true posterior of latent variables and a tractable variational distribution. The E-step minimizes this divergence exactly, while the M-step maximizes a lower bound on the log-likelihood, known as the Evidence Lower Bound (ELBO).

A mathematical property of convex functions that provides the theoretical justification for the EM algorithm's convergence. It guarantees that the log-likelihood function increases monotonically with each iteration. Specifically, it is used to construct a tight lower bound on the log-likelihood during the E-step, which is then maximized in the M-step. This ensures the algorithm never decreases the likelihood.

A broader family of approximate inference techniques that turn posterior computation into an optimization problem. While standard EM computes the exact posterior in the E-step, Variational EM is used when this posterior is intractable, approximating it with a simpler distribution. This connects EM to modern Variational Autoencoders (VAEs) and Bayesian deep learning, where neural networks parameterize the approximate posterior.