Expectation-Maximisation Algorithm: A Complete Guide

Many of the most interesting machine learning problems involve data that is incomplete, ambiguous, or grouped into hidden categories we cannot directly observe. Customer purchase records do not come labelled with personality segments. Medical measurements do not arrive tagged with underlying biological subtypes. Astronomy datasets do not specify which star cluster each observation belongs to.

These are problems with latent variables, a hidden structure that influences the data but cannot be directly measured. Standard maximum likelihood estimation breaks down when latent variables are present, because the likelihood function becomes intractable to maximise directly.

The EM algorithm is an iterative optimisation procedure that finds maximum likelihood parameter estimates when data is incomplete or when the model contains latent variables. It alternates between two steps: the E-step, which computes the expected values of latent variables given current parameters, and the M-step, which updates parameters to maximise the expected log-likelihood. Together, these steps converge to a local maximum of the likelihood function.

This article explains the EM algorithm from first principles, demonstrates its application to Gaussian Mixture Model (GMM) training, and explores its properties, limitations, and real-world applications.

TL;DR

• The EM algorithm finds maximum likelihood parameter estimates when data contains latent (hidden) variables.
• The E-step computes soft assignments — the probability that each data point belongs to each latent component, given current parameters.
• The M-step updates parameters to maximise the expected log-likelihood computed using the soft assignments.
• EM is the training algorithm for Gaussian Mixture Models, the most important application in unsupervised machine learning.
• EM guarantees non-decreasing log-likelihood at every iteration but converges to a local maximum, not necessarily the global one.

The Problem EM Solves: Incomplete Data and Latent Variables

To understand why EM is necessary, it helps to understand the problem it was designed to solve.

Maximum Likelihood with Complete Data

When data is complete, every observation is fully observed and unambiguously labelled, and maximum likelihood estimation is straightforward. For a Gaussian distribution, the maximum likelihood estimates of the mean and variance are simply the sample mean and sample variance of the observed data. The optimisation has a closed-form solution.

The Incomplete Data Problem

Now, suppose the data comes from a mixture of two Gaussian distributions, two clusters, but the cluster membership of each data point is unknown. The observations are incomplete: you see the data values but not which Gaussian generated each value. The cluster memberships are latent variables.

In this case, the likelihood function for the observed data involves a sum over all possible cluster assignments for each data point. Maximising this directly is intractable, as the number of possible complete-data configurations grows exponentially with the number of data points.

This is the fundamental challenge that EM addresses. Instead of trying to maximise the intractable observed-data likelihood directly, EM introduces a two-step procedure that iteratively refines both the parameter estimates and the soft assignments of data points to latent components.

Soft vs. Hard Assignments

A key distinction in EM is between hard and soft assignments of data points to latent components.

•      Hard assignment (k-means approach): Each data point is assigned definitively to one cluster. The cluster membership is treated as known and fixed. This works when clusters are clearly separated, but fails when clusters overlap; ambiguous points are forced into one cluster regardless of uncertainty.

•   Soft assignment (EM approach): Each data point is assigned a probability of belonging to each latent component. A point near the boundary of two clusters might be 60% assigned to cluster 1 and 40% to cluster 2. All computations use these fractional, probabilistic assignments. This respects uncertainty and produces better parameter estimates for overlapping distributions.

The E-Step: Expectation

The E-step is the Expectation step, the part of the algorithm that computes the expected values of the latent variables given the current parameter estimates. For mixture models, this means computing the soft assignments of each data point to each component.

Computing Responsibilities in a GMM

In the context of a Gaussian Mixture Model with K components, the soft assignment of data point xi to component k is called the responsibility r_ik. It is the posterior probability that data point xi was generated by component k, given the current parameter estimates:

r_ik = πk * N(xi ; μ_k, Σ_k) / Σj [ πj * N(xi ; μ_j, Σ_j) ]

Where:

•      πk: The mixing weight of component k (the prior probability that a randomly drawn data point came from component k).

•   N(xi; μ_k, Σ_k): The probability density of data point xi under component k’s Gaussian distribution with mean μ_k and covariance Σ_k.

•   The denominator: The total probability of xi under the full mixture model normalises the responsibilities to sum to 1 across all K components 

Interpreting Responsibilities

Responsibilities are posterior probabilities. They encode how much credit each component should receive for explaining each data point:

•      A data point deep in one Gaussian cluster will have responsibilities close to 1 for that component and close to 0 for all others.

•     A data point near the boundary between two clusters will have responsibilities split between the two, reflecting genuine uncertainty about which component generated it.

•   All responsibilities for a given data point sum to 1, ensuring they form a valid probability distribution over components.

This is the fundamental difference between EM and hard-assignment clustering like k-means. EM acknowledges and properly quantifies the uncertainty in cluster membership — a key reason why GMMs are more statistically principled than k-means for overlapping distributions.

The M-Step: Maximisation

The M-step is the Maximisation step, it uses the soft assignments computed in the E-step to update the model parameters so that they maximise the expected complete-data log-likelihood. For a GMM, this means updating the means, covariances, and mixing weights of all K components.

Updating the Mixing Weights

The new mixing weight for component k is the average responsibility that component k receives across all data points:

πk_new = (1/N) * Σi r_ik

Intuitively, the mixing weight of a component is proportional to the total amount of data it is responsible for explaining. A component that accumulates high responsibilities across many data points gets a higher mixing weight in the next iteration.

Updating the Means

The new mean of component k is the weighted average of all data points, weighted by their responsibilities to component k:

μ_k_new = Σi (r_ik * xi) / Σi r_ik

This is the weighted centroid of the data; each point xi contributes to the mean of component k in proportion to how much k is responsible for explaining it. A point far from the current cluster centre with low responsibility has minimal influence on the new mean.

Updating the Covariances

The new covariance matrix of component k is the weighted sample covariance, where each data point’s contribution is weighted by its responsibility:

Σ_k_new = Σi [ r_ik * (xi – μ_k_new)(xi – μ_k_new)^T ] / Σi r_ik

This captures both the spread and orientation of each component. A component responsible for a narrow, elongated cluster will have a covariance matrix that reflects that shape; a component responsible for a spherical cluster will have a covariance matrix close to the identity.

The Full EM Algorithm: Iterating to Convergence.

With both the E-step and M-step defined, the complete EM algorithm for GMM training follows a clear iterative cycle.

Initialisation

EM requires starting parameter values before the iteration begins. The choice of initialisation significantly affects which local maximum the algorithm converges to.

•      Random initialisation: Randomly assign parameters, random means within the data range, identity covariances, and uniform mixing weights. Simple but may converge to poor local maxima.

•     K-means initialisation: Run k-means clustering first and use the resulting cluster assignments and centroids to initialise the GMM parameters. This is the standard approach in scikit-learn’s GaussianMixture and typically produces better results than random initialisation.

•      Multiple restarts: Run the full EM algorithm multiple times with different initialisations and select the solution with the highest log-likelihood. This is the most robust approach for avoiding poor local maxima.

The Iteration Cycle

1.    E-step: For each data point xi and each component k, compute the responsibility r_ik using the current parameter estimates (πk, μ_k, Σ_k).

2.   M-step: Update all parameters πk, μ_k, and Σ_k for each component k using the responsibilities computed in the E-step.

3.    Compute log-likelihood: Evaluate the observed-data log-likelihood under the new parameters.

4.    Check convergence: If the change in log-likelihood between iterations falls below a threshold (typically 1e-6 to 1e-3), or the maximum number of iterations is reached, stop. Otherwise, return to step 1.

Convergence Guarantee

One of the most important theoretical properties of EM is its guaranteed convergence: the observed-data log-likelihood is guaranteed to be non-decreasing at every iteration. Each complete E-step/M-step cycle either increases the log-likelihood or leaves it unchanged.

This guarantee is mathematically proven through Jensen’s inequality applied to the lower bound of the log-likelihood. It ensures EM will never make things worse, but it does not guarantee convergence to the global maximum. EM converges to a local maximum, and which local maximum it finds depends on the initialisation.

EM for Gaussian Mixture Models: A Complete Example

Gaussian Mixture Models are the canonical application of the EM algorithm in unsupervised machine learning. A GMM assumes that the observed data were generated by K Gaussian distributions, each with its own mean, covariance, and mixing weight.

Why GMMs Need EM

If you knew which Gaussian generated each data point, fitting a GMM would be trivial, just fit one Gaussian to each cluster of points using standard MLE. But the cluster memberships are unobserved; they are latent variables. This is precisely the setting EM was designed for.

EM trains the GMM by alternating between estimating cluster memberships (E-step) and updating Gaussian parameters (M-step). After convergence, the result is a set of K Gaussian components that, combined with their mixing weights, define a probability distribution over the full data space.

GMMs vs. K-Means: Key Differences

•   Probabilistic assignments: GMMs use soft assignments; k-means uses hard assignments. GMMs naturally handle overlapping clusters and represent uncertainty in cluster membership.

•      Cluster shape: K-means assumes spherical clusters of equal size. GMMs can model clusters of arbitrary shape, orientation, and size through the full covariance matrix.

•    Covariance types in GMM: Scikit-learn’s GaussianMixture allows four covariance types: ‘full’ (unrestricted covariance matrix, most flexible), ‘tied’ (all components share the same covariance), ‘diagonal’ (only diagonal covariance elements assume uncorrelated features), and ‘spherical’ (each component is a sphere equivalent to k-means with soft assignments).

•   Model selection: GMMs support principled model selection using BIC (Bayesian Information Criterion) or AIC (Akaike Information Criterion) to determine the optimal number of components K, something k-means does not provide natively.

Applications of the EM Algorithm

The EM algorithm’s ability to handle latent variables and incomplete data makes it applicable across a wide range of domains beyond GMM clustering.

Image and Medical Image Segmentation

Image segmentation can be framed as a GMM problem: each pixel is a data point (characterised by colour values), and the latent variable is which tissue type or region the pixel belongs to. EM-trained GMMs segment MRI scans into tissue types (grey matter, white matter, cerebrospinal fluid), segment natural images into semantic regions, and cluster satellite imagery into land cover categories, all without labelled training data.

Bioinformatics and Genomics

Bioinformatics uses EM extensively for motif discovery (finding recurring sequence patterns in DNA) and gene expression analysis (clustering genes by expression profile). The MEME algorithm for transcription factor binding site discovery is built directly on EM for mixture models over sequence data. Gaussian mixture models fit via EM are used to cluster cells in single-cell RNA sequencing studies, identifying cell types from high-dimensional expression profiles.

Natural Language Processing

Many foundational NLP models use EM. Latent Semantic Analysis (LSA) uses a form of EM to discover latent topics in document collections. The Baum-Welch algorithm, the standard training procedure for Hidden Markov Models used in speech recognition and sequence labelling, is a specialisation of EM for HMM parameter estimation.

Missing Data Imputation

When a dataset has missing values, EM provides a principled imputation strategy. The E-step treats the missing values as latent variables and computes their expected values given the observed data and current model parameters. The M-step updates model parameters using both observed and imputed values. This produces maximum likelihood estimates that correctly account for the uncertainty introduced by the missing data, unlike simpler approaches like mean imputation that ignore this uncertainty.

Convergence, Limitations, and Practical Considerations

While the EM algorithm is elegant and widely applicable, several practical considerations affect its reliability and efficiency.

Local Maxima and Initialisation Sensitivity

EM is guaranteed to converge, but not to the global maximum. The algorithm can get stuck in poor local maxima, particularly when the number of components is large, components overlap significantly, or the initialisation is far from the true parameters.

The standard mitigation is multiple restarts: run EM from several different random initialisations and keep the solution with the highest converged log-likelihood. Scikit-learn’s GaussianMixture does this automatically via the n_init parameter.

Degeneracy: The Singular Covariance Problem

A GMM can degenerate when a Gaussian component collapses onto a single data point its mean equals that point’s value, and its covariance approaches zero. The likelihood of that one point becomes infinite, creating a likelihood singularity. In practice, this is addressed by adding a small regularisation term to the covariance matrix (reg_covar parameter in scikit-learn) and using k-means initialisation rather than random initialisation.

Computational Cost

Each EM iteration requires computing the responsibility of each data point for each component, an O(N × K × D²) operation where N is the number of data points, K is the number of components, and D is the data dimensionality. For large datasets, high K, or high-dimensional data, this can be computationally expensive. Mini-batch EM and online EM variants address this by processing subsets of data per iteration.

Model Selection: Choosing K

The number of components K is a hyperparameter that must be chosen. Since maximising log-likelihood always favours more components, raw log-likelihood cannot be used for model selection, as it would always prefer the largest K.

The standard approach is to use information criteria that penalise model complexity:

• BIC (Bayesian Information Criterion): BIC = -2 * log-likelihood + k * log(N). Penalises the number of parameters k by the log of the dataset size N. Generally preferred for selecting GMMs — tends to select simpler models.
• AIC (Akaike Information Criterion): AIC = -2 * log-likelihood + 2k. Penalises model complexity less severely than BIC, tending to favour more components.

Fit GMMs for a range of K values (e.g. 1 to 15) and select the K that minimises BIC. This is the most principled approach to GMM model selection available in practice.

If you want practical experience working with activation functions, neural networks, and deep learning models, HCL GUVI’s AI and ML programs can help you understand how concepts like sigmoid, backpropagation, and gradient descent are implemented using frameworks such as TensorFlow and PyTorch through hands-on projects. 

Conclusion

The Expectation-Maximisation algorithm is one of the most elegant and broadly applicable ideas in statistical machine learning. By decomposing the intractable problem of maximum likelihood estimation with latent variables into two tractable alternating steps, computing soft assignments in the E-step and updating parameters in the M-step, it turns an impossible direct optimisation into a guaranteed convergent iterative procedure.

Its most prominent application is Gaussian Mixture Model training, where it enables probabilistic, flexible clustering that correctly handles overlapping distributions and represents uncertainty in cluster membership capabilities that hard-assignment methods like k-means fundamentally lack. But EM’s reach extends far beyond GMMs: it underpins Hidden Markov Model training for speech recognition, motif discovery in bioinformatics, topic modelling in NLP, and principled missing data imputation across every domain of data science.

Understanding EM means understanding latent variables, soft assignments, and the geometry of log-likelihood landscapes. It is foundational knowledge for any practitioner who works with probabilistic models, unsupervised learning, or incomplete data, which is to say, any serious machine learning practitioner.

FAQs

1. What is the difference between the E-step and M-step?

The E-step (Expectation step) computes the expected values of the latent variables in a GGMM. This means computing the responsibility (soft assignment probability) of each data point to each component, given current parameters. The M-step (Maximisation step) updates all model parameters to maximise the expected log-likelihood computed using the responsibilities from the E-step.

2. Why does EM converge to a local maximum rather than the global maximum?

EM is guaranteed to increase the observed-data log-likelihood at every iteration (via Jensen’s inequality), ensuring convergence. However, the log-likelihood surface for mixture models has multiple local maxima. EM follows the gradient of the lower bound, so it converges to whichever local maximum is nearest to the starting parameters determined by initialisation.

3. What is the difference between GMM and k-means clustering?

K-means makes hard assignments (each point belongs to exactly one cluster) and assumes spherical, equal-sized clusters. GMM uses soft assignments (probabilistic membership across all components) and can model clusters of arbitrary shape, orientation, and size through full covariance matrices, making GMMs more flexible and statistically principled for overlapping distributions.

4. How do I choose the number of components K for a GMM?

Fit GMMs for a range of K values and select the K that minimises the Bayesian Information Criterion (BIC). BIC penalises model complexity by the log of the dataset size, balancing goodness-of-fit against the risk of overfitting to noise. Scikit-learn’s GaussianMixture computes BIC directly via the .bic() method.

5. What are the main limitations of the EM algorithm?

EM’s main limitations are: sensitivity to initialisation (different starting points may converge to different local maxima), slow convergence near the optimum (small steps as the algorithm refines the solution), computational cost scaling with dataset size and number of components, and potential degeneracy when a component collapses onto a single data point.