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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
\n The Expectation-Maximisation (EM) algorithm is an iterative statistical optimization method used to estimate model parameters when data is incomplete or contains hidden variables. It works in two repeating stages: the Expectation step (E-step), which estimates the missing or latent variables using the current model parameters, and the Maximisation step (M-step), which updates the parameters to maximize the expected likelihood calculated in the E-step. By alternating between these two steps, the EM algorithm gradually improves the model and converges toward a local maximum likelihood solution.\n <\/p>\n\n <\/div>\n\n<\/div>\n\n\n\n
To understand why EM is necessary, it helps to understand the problem it was designed to solve.<\/p>\n\n\n\n
When data is complete, every observation is fully observed and unambiguously labelled, and maximum likelihood estimation is straightforward. For a Gaussian distribution<\/a>, 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n A key distinction in EM is between hard and soft assignments of data points to latent components.<\/p>\n\n\n\n \u2022 Hard assignment (k-means approach): <\/strong>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.<\/p>\n\n\n\n \u2022 Soft assignment (EM approach): <\/strong>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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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:<\/p>\n\n\n\n r_ik = \u03c0k * N(xi ; \u03bc_k, \u03a3_k) \/ \u03a3j [ \u03c0j * N(xi ; \u03bc_j, \u03a3_j) ]<\/strong><\/p>\n\n\n\n Where:<\/p>\n\n\n\n \u2022 \u03c0k: <\/strong>The mixing weight of component k (the prior probability that a randomly drawn data point came from component k).<\/p>\n\n\n\n \u2022 N(xi; \u03bc_k, \u03a3_k): <\/strong>The probability density of data point xi under component k’s Gaussian distribution with mean \u03bc_k and covariance \u03a3_k.<\/p>\n\n\n\n \u2022 The denominator: <\/strong>The total probability of xi under the full mixture model normalises the responsibilities to sum to 1 across all K components <\/p>\n\n\n\n Responsibilities are posterior probabilities. They encode how much credit each component should receive for explaining each data point:<\/p>\n\n\n\n \u2022 A data point deep in one Gaussian cluster will have responsibilities close to 1 for that component and close to 0 for all others.<\/p>\n\n\n\n \u2022 A data point near the boundary between two clusters will have responsibilities split between the two, reflecting genuine uncertainty about which component generated it.<\/p>\n\n\n\n \u2022 All responsibilities for a given data point sum to 1, ensuring they form a valid probability distribution over components.<\/p>\n\n\n\n This is the fundamental difference between EM and hard-assignment clustering like k-means. EM acknowledges and properly quantifies the uncertainty in cluster membership \u2014 a key reason why GMMs are more statistically principled than k-means for overlapping distributions.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n The new mixing weight for component k is the average responsibility that component k receives across all data points:<\/p>\n\n\n\n \u03c0k_new = (1\/N) * \u03a3i r_ik<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n The new mean of component k is the weighted average of all data points, weighted by their responsibilities to component k:<\/p>\n\n\n\n \u03bc_k_new = \u03a3i (r_ik * xi) \/ \u03a3i r_ik<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n The new covariance matrix of component k is the weighted sample covariance, where each data point’s contribution is weighted by its responsibility:<\/p>\n\n\n\n \u03a3_k_new = \u03a3i [ r_ik * (xi – \u03bc_k_new)(xi – \u03bc_k_new)^T ] \/ \u03a3i r_ik<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n \n The Expectation-Maximisation (EM) algorithm<\/strong> was formally introduced in the landmark 1977 paper<\/strong> \u201cMaximum Likelihood from Incomplete Data via the EM Algorithm\u201d<\/em> by Arthur Dempster<\/strong>, Nan Laird<\/strong>, and Donald Rubin<\/strong>. The paper established a general iterative framework for estimating parameters when data contains missing values or hidden variables. Since then, EM has become one of the most influential optimization techniques in statistics and machine learning, powering applications such as Gaussian Mixture Models<\/strong>, clustering, topic modeling, medical imaging, and probabilistic graphical models.\n <\/p>\n<\/div>\n\n\n\n With both the E-step and M-step defined, the complete EM algorithm for GMM training follows a clear iterative cycle.<\/p>\n\n\n\n EM requires starting parameter values before the iteration begins. The choice of initialisation significantly affects which local maximum the algorithm converges to.<\/p>\n\n\n\n \u2022 Random initialisation: <\/strong>Randomly assign parameters, random means within the data range, identity covariances, and uniform mixing weights. Simple but may converge to poor local maxima.<\/p>\n\n\n\n \u2022 \u00a0 \u00a0 K-means initialisation: <\/strong>Run k-means clustering<\/a> 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.<\/p>\n\n\n\n \u2022 Multiple restarts: <\/strong>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.<\/p>\n\n\n\n 1. E-step: <\/strong>For each data point xi and each component k, compute the responsibility r_ik using the current parameter estimates (\u03c0k, \u03bc_k, \u03a3_k).<\/p>\n\n\n\n 2. M-step: <\/strong>Update all parameters \u03c0k, \u03bc_k, and \u03a3_k for each component k using the responsibilities computed in the E-step.<\/p>\n\n\n\n 3. Compute log-likelihood: <\/strong>Evaluate the observed-data log-likelihood under the new parameters.<\/p>\n\n\n\n 4. Check convergence: <\/strong>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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Why GMMs Need EM<\/strong><\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n \u2022 Probabilistic assignments: <\/strong>GMMs use soft assignments; k-means uses hard assignments. GMMs naturally handle overlapping clusters and represent uncertainty in cluster membership.<\/p>\n\n\n\n \u2022 Cluster shape: <\/strong>K-means assumes spherical clusters of equal size. GMMs can model clusters of arbitrary shape, orientation, and size through the full covariance matrix.<\/p>\n\n\n\n \u2022 Covariance types in GMM: <\/strong>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).<\/p>\n\n\n\n \u2022 Model selection: <\/strong>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.<\/p>\n\n\n\n The EM algorithm’s ability to handle latent variables and incomplete data makes it applicable across a wide range of domains beyond GMM clustering.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n 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.<\/p>\n\n\n\nThe Incomplete Data Problem<\/strong><\/h3>\n\n\n\n
Soft vs. Hard Assignments<\/strong><\/h3>\n\n\n\n
The E-Step: Expectation<\/strong><\/h2>\n\n\n\n
Computing Responsibilities in a GMM<\/strong><\/h3>\n\n\n\n
Interpreting Responsibilities<\/strong><\/h3>\n\n\n\n
The M-Step: Maximisation<\/strong><\/h2>\n\n\n\n
Updating the Mixing Weights<\/strong><\/h3>\n\n\n\n
Updating the Means<\/strong><\/h3>\n\n\n\n
Updating the Covariances<\/strong><\/h3>\n\n\n\n
The Full EM Algorithm: Iterating to Convergence<\/strong>.<\/em><\/strong><\/h2>\n\n\n\n
Initialisation<\/strong><\/h3>\n\n\n\n
The Iteration Cycle<\/strong><\/h3>\n\n\n\n
Convergence Guarantee<\/strong><\/h3>\n\n\n\n
EM for Gaussian Mixture Models: A Complete Example<\/strong><\/h2>\n\n\n\n
GMMs vs. K-Means: Key Differences<\/strong><\/h3>\n\n\n\n
Applications of the EM Algorithm<\/strong><\/h2>\n\n\n\n
Image and Medical Image Segmentation<\/strong><\/h3>\n\n\n\n
Bioinformatics and Genomics<\/strong><\/h3>\n\n\n\n
Natural Language Processing<\/strong><\/h3>\n\n\n\n