The EM AlgorithmOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

The Expectation-Maximization Algorithm

GMMs have latent variables (which component generated each point?) that we never observe. The EM algorithm handles this by iteratively guessing the latent variables and optimizing parameters. It is the optimization slot for models with hidden structure, where plain gradient descent is awkward but a guaranteed-to-improve alternating scheme works beautifully.

Real-world examples: Missing data imputation, topic modeling (LDA), hidden Markov models, clustering with partial labels.

The latent variable problem

In a GMM, we observe xi\mathbf{x}_i but not ziz_i (which component generated it). If we knew ziz_i, we could easily compute the MLE:

μk=∑i:zi=kxi∑i:zi=k1\boldsymbol{\mu}_k = \frac{\sum_{i: z_i = k} \mathbf{x}_i}{\sum_{i: z_i = k} 1}

But we don't know ziz_i. EM solves this by alternating between two steps.

Intuition

Imagine you're a detective. You don't know who committed the crime (latent variable), but you have suspects (components). First, you estimate the probability each suspect did it (E-step). Then you update your theory of the crime based on those probabilities (M-step). Repeat until your theory stabilizes.

The two steps

E-step (Expectation)

Compute the expected value of the latent variables given current parameters:

γik=P(zi=k∣xi,θ(t))=πk(t)⋅N(xi∣μk(t),Σk(t))∑jπj(t)⋅N(xi∣μj(t),Σj(t))\gamma_{ik} = P(z_i = k \mid \mathbf{x}_i, \theta^{(t)}) = \frac{\pi_k^{(t)} \cdot \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k^{(t)}, \boldsymbol{\Sigma}_k^{(t)})}{\sum_{j} \pi_j^{(t)} \cdot \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j^{(t)}, \boldsymbol{\Sigma}_j^{(t)})}

M-step (Maximization)

Update parameters using the responsibilities as "soft" assignments:

μk(t+1)=∑iγikxi∑iγik\boldsymbol{\mu}_k^{(t+1)} = \frac{\sum_i \gamma_{ik} \mathbf{x}_i}{\sum_i \gamma_{ik}} Σk(t+1)=∑iγik(xi−μk(t+1))(xi−μk(t+1))T∑iγik\boldsymbol{\Sigma}_k^{(t+1)} = \frac{\sum_i \gamma_{ik} (\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})(\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})^T}{\sum_i \gamma_{ik}} πk(t+1)=∑iγikn\pi_k^{(t+1)} = \frac{\sum_i \gamma_{ik}}{n}
Python
import numpy as np
from scipy.stats import multivariate_normal

def em_gmm(X, K, max_iter=100, tol=1e-6):
    n, d = X.shape
    
    # Initialize parameters randomly
    indices = np.random.choice(n, K, replace=False)
    means = X[indices].copy()
    covs = [np.eye(d) for _ in range(K)]
    weights = np.ones(K) / K
    
    log_likelihoods = []
    
    for iteration in range(max_iter):
        # E-step: compute responsibilities
        responsibilities = np.zeros((n, K))
        for k in range(K):
            responsibilities[:, k] = weights[k] * multivariate_normal.pdf(X, means[k], covs[k])
        responsibilities /= responsibilities.sum(axis=1, keepdims=True)
        
        # M-step: update parameters
        N_k = responsibilities.sum(axis=0)
        for k in range(K):
            means[k] = (responsibilities[:, k:k+1].T @ X) / N_k[k]
            diff = X - means[k]
            covs[k] = (responsibilities[:, k:k+1] * diff).T @ diff / N_k[k]
            covs[k] += 1e-6 * np.eye(d)  # regularization
        weights = N_k / n
        
        # Compute log-likelihood
        ll = 0
        for k in range(K):
            ll += weights[k] * multivariate_normal.pdf(X, means[k], covs[k])
        log_likelihoods.append(np.log(ll + 1e-10).sum())
        
        if iteration > 0 and abs(log_likelihoods[-1] - log_likelihoods[-2]) < tol:
            print(f"Converged at iteration {iteration}")
            break
    
    labels = responsibilities.argmax(axis=1)
    return labels, means, covs, weights, log_likelihoods

Why it works and worked example

The E-step and M-step are coordinate ascent on the ELBO — an evidence lower bound on the log-likelihood obtained via Jensen's inequality. Each E-step makes the bound tight (zero KL gap); each M-step pushes the bound up. Chaining these two moves proves the log-likelihood never decreases, guaranteeing convergence to a local optimum.

For the full ELBO derivation, the monotonic proof, and a complete one-iteration hand trace on X={1,2,4,5}X=\{1,2,4,5\} with K=2K=2 (including every responsibility calculation and parameter re-estimate), see:

Deep dive
The EM Algorithm
Includes runnable notebook

Worked example: 2D GMM

Python
import matplotlib.pyplot as plt
from sklearn.mixture import GaussianMixture

# Generate mixture data
np.random.seed(42)
X1 = np.random.multivariate_normal([0, 0], [[1, 0], [0, 1]], 200)
X2 = np.random.multivariate_normal([5, 5], [[2, 0.5], [0.5, 2]], 200)
X = np.vstack([X1, X2])

# Fit GMM
gmm = GaussianMixture(n_components=2, covariance_type='full', n_init=10)
labels = gmm.fit_predict(X)

plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='coolwarm', s=10, alpha=0.7)
plt.scatter(gmm.means_[:, 0], gmm.means_[:, 1], c='black', marker='X', s=200)
plt.title('GMM Clustering')

plt.subplot(1, 2, 2)
probs = gmm.predict_proba(X)
plt.scatter(X[:, 0], X[:, 1], c=probs[:, 1], cmap='coolwarm', s=10, alpha=0.7)
plt.colorbar(label='P(component 2)')
plt.title('Soft Assignments (probabilities)')
plt.tight_layout()
plt.show()

EM beyond GMMs

EM is a general framework for latent variable models:

ModelLatent variablesWhat EM does
GMMCluster assignments ziz_iSoft clustering
HMMHidden statesForward-backward algorithm
Topic models (LDA)Topic assignmentsTopic inference
Missing dataMissing valuesImputation

EM is not clustering alone

EM finds maximum likelihood parameters for latent variable models. Clustering is just one application. The same framework powers speech recognition (HMMs), topic modeling (LDA), and missing data analysis.

Exercise

What guarantee does the EM algorithm provide at each iteration?

Need a hint?

Think about what EM optimizes and whether it can get worse.

Exercise

In the EM algorithm, what does the E-step compute?

Need a hint?

E stands for Expectation.

Exercise

Why is initialization important for EM?

Need a hint?

EM converges to a local optimum.

Common mistakes

  1. Bad initialization: Random initialization can converge to poor local optima. Use K-Means++ initialization or run multiple times.
  2. Singular covariances: If a component collapses to a single point, the covariance becomes singular. Add regularization: Σk←Σk+ϵI\boldsymbol{\Sigma}_k \leftarrow \boldsymbol{\Sigma}_k + \epsilon I.
  3. Not enough data per component: EM needs sufficient data to estimate parameters. Rule of thumb: at least 10d10d points per component.
  4. Ignoring convergence criteria: Don't just run for a fixed number of iterations. Check if the log-likelihood change is below a threshold.

Key takeaways

  • EM alternates an E-step (soft responsibilities) and M-step (re-estimate parameters).
  • It handles latent variables, which component generated each point is unknown.
  • The log-likelihood is non-decreasing; EM finds a local optimum (use restarts).
  • The same E/M pattern powers HMMs, missing-data imputation, and more.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
The EM AlgorithmClusteringPCA & Dimensionality Redu…Probability & StatisticsGaussian Mixture ModelsHidden Markov ModelsNaive BayesVariational AutoencodersFactor AnalysisIndependent Component Ana…The EM AlgorithmThe Baum–Welch Algorithm