Okay, here is course material covering the Expectation-Maximization (EM) algorithm, suitable
for a module within a Machine Learning, Statistics, or related course.
Course Module: Parameter Estimation with Latent Variables
Topic: The Expectation-Maximization (EM) Algorithm
1. Introduction: The Problem of Missing Data / Latent Variables
In many real-world scenarios, the data we observe is incomplete or only tells part of the story.
We often encounter situations where:
Missing Data: Some data points have missing feature values.
Latent Variables: The observed data is generated by a process involving underlying
variables that we cannot directly observe. These are called latent variables.
Example: Imagine you have height measurements from a population containing both males and
females, but you don't know the gender for each measurement.
Observed Data (X): The height measurements.
Latent Variable (Z): The gender corresponding to each measurement.
Parameters (θ): The parameters of the height distributions for males and females (e.g.,
mean and variance for each group, proportion of males/females).
Our goal is often to estimate the parameters (θ) of the underlying model using Maximum
Likelihood Estimation (MLE). The likelihood function is P(X|θ). We want to find θ that
maximizes this likelihood:
θ_MLE = argmax_θ P(X|θ)
However, when latent variables Z are involved, the likelihood calculation requires summing (or
integrating) over all possible values of these latent variables:
P(X|θ) = Σ_Z P(X, Z|θ) (or ∫ P(X, Z|θ) dZ for continuous Z)
Maximizing log P(X|θ) = log [ Σ_Z P(X, Z|θ) ] directly is often difficult because the
summation/integral is inside the logarithm, preventing analytical solutions.
2. The Expectation-Maximization (EM) Intuition
EM provides an iterative approach to find MLE (or MAP - Maximum A Posteriori) estimates in
the presence of latent variables or missing data.
The Core Idea: If we knew the values of the latent variables Z, maximizing the "complete-data
log-likelihood" log P(X, Z|θ) would often be much easier. But we don't know Z.
So, EM alternates between two steps:
E-Step (Expectation): Estimate the latent variables Z based on the current guess of the
parameters θ^(t) and the observed data X. We don't get hard assignments for Z, but rather
their expected values or posterior distribution P(Z | X, θ^(t)).
M-Step (Maximization): Update the parameters θ to maximize the likelihood, assuming
the latent variables are given by the estimates from the E-step. Specifically, we maximize
the expected value of the complete-data log-likelihood.
This sounds like a chicken-and-egg problem, but by iterating these two steps, EM progressively
refines the parameter estimates, guaranteeing an increase (or stabilization) of the observed-data
likelihood P(X|θ) at each iteration.
3. The EM Algorithm Formulation
Let:
X be the observed data.
Z be the latent variables (or missing data).
θ be the model parameters we want to estimate.
θ^(t) be the parameter estimate at iteration t.
The algorithm proceeds as follows:
1. Initialization: Start with an initial guess for the parameters θ^(0).
2. Iteration (Repeat until convergence):
o E-Step (Expectation): Compute the expected value of the complete-data log-
likelihood, with respect to the conditional distribution of the latent variables Z
given the observed data X and the current parameter estimate θ^(t). This
expectation defines the Q-function:
Q(θ | θ^(t)) = E_{Z | X, θ^(t)} [ log P(X, Z | θ) ]
Q(θ | θ^(t)) = Σ_Z P(Z | X, θ^(t)) * log P(X, Z | θ) (for discrete Z)
Note: We are taking the expectation using the old parameters θ^(t) but evaluating
the log-likelihood using the new (variable) parameters θ.
o M-Step (Maximization): Find the parameters θ that maximize the Q-function
calculated in the E-step. This gives the updated parameter estimate for the next
iteration:
θ^(t+1) = argmax_θ Q(θ | θ^(t))
This step often reduces to a standard MLE problem for the complete data,
weighted by the posterior probabilities P(Z | X, θ^(t)) calculated in the E-step.
3. Convergence: Stop when the change in the log-likelihood log P(X|θ) or the change in the
parameters θ between iterations falls below a predefined threshold.
4. Key Properties and Guarantees
Monotonic Convergence: Each EM iteration is guaranteed to increase or maintain the
observed-data log-likelihood: log P(X | θ^(t+1)) ≥ log P(X | θ^(t)).
Convergence to Local Optimum: EM is guaranteed to converge, typically to a local
maximum (or saddle point) of the likelihood function.
Sensitivity to Initialization: Since it converges to a local optimum, the final result can
depend heavily on the initial parameter guess θ^(0). Running EM multiple times with
different initializations is common practice.
5. Classic Example: Gaussian Mixture Models (GMMs)
EM is famously used to fit GMMs.
Observed Data (X): A set of data points {x_1, ..., x_N}.
Model Assumption: The data comes from a mixture of K Gaussian distributions.
Parameters (θ): For each Gaussian component k: mean μ_k, covariance Σ_k, and mixing
coefficient π_k (prior probability of belonging to component k). Σ_k π_k = 1.
component generated it (z_i ∈ {1, ..., K}).
Latent Variable (Z): For each data point x_i, a variable z_i indicating which Gaussian
EM for GMMs:
1. Initialize: Guess initial μ_k, Σ_k, π_k for all k.
2. Iterate:
o E-Step: Calculate the "responsibility" that component k takes for data point x_i,
given the current parameters θ^(t). This is the posterior probability P(z_i = k | x_i,
θ^(t)):
γ(z_{ik}) = P(z_i = k | x_i, θ^(t)) = [ π_k^(t) * N(x_i | μ_k^(t), Σ_k^(t)) ] /
[ Σ_{j=1}^K π_j^(t) * N(x_i | μ_j^(t), Σ_j^(t)) ]
(where N(...) is the Gaussian PDF).
o M-Step: Update the parameters using the calculated responsibilities γ(z_{ik}) as
soft weights:
μ_k^(t+1) = [ Σ_i γ(z_{ik}) * x_i ] / [ Σ_i γ(z_{ik}) ] (Weighted mean)
Σ_k^(t+1) = [ Σ_i γ(z_{ik}) * (x_i - μ_k^(t+1))(x_i - μ_k^(t+1))^T ] /
[ Σ_i γ(z_{ik}) ] (Weighted covariance)
π_k^(t+1) = [ Σ_i γ(z_{ik}) ] / N (Mean responsibility for component k)
(where N is the total number of data points).
3. Repeat E and M steps until convergence.
6. Applications of EM
Besides GMMs, EM is widely used in:
Hidden Markov Models (HMMs): Baum-Welch algorithm is an instance of EM.
Probabilistic Latent Semantic Analysis (PLSA): Topic modeling.
Missing Data Imputation: Estimating missing values.
Machine Translation: IBM alignment models.
Medical Image Reconstruction: PET scans.
Quantitative Genetics: Estimating genetic parameters.
7. Advantages and Disadvantages
Advantages:
Conceptually simple and often easy to implement.
Guaranteed monotonic convergence of likelihood.
Often results in closed-form updates in the M-step (like in GMMs).
Naturally handles missing data problems.
Disadvantages:
Can converge slowly.
Guaranteed to find only a local optimum. Sensitive to initialization.
The E-step can be computationally intractable if the expectation is hard to compute
(requiring variational approximations or sampling in such cases - leading to Variational
EM or Monte Carlo EM).
8. Conclusion
The Expectation-Maximization algorithm is a powerful and widely applicable iterative method
for finding maximum likelihood estimates when data is incomplete or involves latent variables.
By alternating between estimating the missing information (E-step) and optimizing parameters
based on that estimation (M-step), EM provides an elegant way to tackle otherwise intractable
likelihood maximization problems. Understanding EM is fundamental for working with many
probabilistic models in machine learning and statistics.