EM Algorithm

The Expectation-Maximization (EM) algorithm is an iterative method for finding maximum likelihood estimates of parameters in statistical models with latent (hidden) variables.

Overview

The EM algorithm alternates between two steps:

1. E-step (Expectation): Compute the expected value of the log-likelihood with respect to the conditional distribution of latent variables given observed data and current parameter estimates
2. M-step (Maximization): Find parameter values that maximize the expected log-likelihood computed in the E-step

Algorithm

Initialization

• Start with initial parameter estimates θ⁽⁰⁾

Iteration (Repeat until cOnvergence)

E-step: Compute Q(θ | θ⁽ᵗ⁾)

$$Q(\theta |{\theta }^{(t)})=E_{Z|X,{\theta }^{(t)}}[\log L(\theta ;X,Z)]$$

M-step: Update parameters

$${\theta }^{(t+1)}=\arg \underset{\theta }{\max }Q(\theta |{\theta }^{(t)})$$

Properties

• Monotonic improvement: Likelihood increases with each iteration
• Convergence: Guaranteed to converge to a local maximum
• Not guaranteed to find global maximum: May depend on initialization

Common Applications

1. Gaussian Mixture Models (GMM): Clustering with soft assignments
2. Hidden Markov Models (HMM): Speech recognition, bioinformatics
3. Factor Analysis: Dimensionality reduction
4. Missing Data Problems: Imputation and parameter estimation

Example: Gaussian Mixture Model

• E-step: Compute responsibilities (posterior probabilities) for each data point belonging to each cluster
• M-step: Update cluster means, covariances, and mixing coefficients based on weighted data points

Advantages

• Handles missing or incomplete data naturally
• Provides probabilistic cluster assignments
• Mathematically elegant and well-founded

Disadvantages

• Sensitive to initialization
• Can converge to local optima
• Computational complexity for large datasets