Expectation-Maximization

EM stands for Expectation-Maximization. It is an iterative algorithm used to find maximum-likelihood estimates of parameters in statistical models that depend on unobserved (hidden or latent) variables.

EM is used to estimate the parameters of a probabilistic model when some data is missing or hidden (latent variables). It finds parameter values that maximize the likelihood of the observed data even though the latent variables are unknown.

A latent variable is a hidden variable that is not directly observed in the data but influences it, such as which cluster a data point belongs to. EM treats these unknown assignments as the missing information it must infer.

EM alternates between the E-step (Expectation) and the M-step (Maximization). In the E-step it estimates the expected values of the latent variables using current parameters, and in the M-step it updates the parameters to maximize the expected likelihood.

In the E-step, EM computes the expected value of the latent variables given the observed data and the current parameter estimates. For clustering, this means computing the probability (responsibility) that each data point belongs to each cluster.

In the M-step, the model parameters are re-estimated to maximize the expected log-likelihood computed in the E-step. Using the responsibilities, it updates quantities like cluster means, variances, and mixing weights.

A responsibility is the probability that a given data point was generated by a particular component (cluster), computed in the E-step. Each point has a set of responsibilities that sum to 1 across all clusters, representing soft membership.

EM seeks to maximize the likelihood (or equivalently the log-likelihood) of the observed data under the model. Each iteration is guaranteed not to decrease this log-likelihood.

Each EM iteration is guaranteed never to decrease the log-likelihood; it either increases it or keeps it the same. This monotonic property is why EM reliably converges, though only to a local optimum.

EM is only guaranteed to converge to a local optimum of the likelihood, not necessarily the global one. The result can depend on the initial parameter values, so multiple restarts are often used.

Because EM converges to a local optimum that depends on the starting point, running it several times from different random initializations and keeping the best result helps avoid poor local optima. The run with the highest final log-likelihood is usually chosen.

Gaussian Mixture Models (GMMs) are commonly fit using EM. EM estimates the means, covariances, and mixing weights of the Gaussian components that best explain the data.

K-Means can be viewed as a special, simplified ('hard') case of EM for Gaussian mixtures, where each point is assigned fully to its nearest cluster instead of getting soft probabilities. The assignment step is like the E-step and the centroid update is like the M-step.

Hard assignment puts each point entirely into one cluster (like K-Means), while soft assignment gives each point a probability of belonging to every cluster (like EM for GMMs). EM uses soft assignments through responsibilities.

EM is typically stopped when the change in log-likelihood between iterations falls below a small threshold, or when a maximum number of iterations is reached. This indicates the parameters have effectively converged.

The mixing weight is the prior probability that a randomly chosen data point comes from a particular Gaussian component. All mixing weights are non-negative and sum to 1 across the components.

The new mean of a component is computed as a weighted average of all data points, where the weights are the responsibilities of that component for each point. Points the component is more responsible for influence the mean more.

With latent variables, the likelihood involves a sum (or integral) over all possible hidden states, which usually makes direct maximization mathematically intractable or has no closed-form solution. EM sidesteps this by iteratively optimizing a simpler expected complete-data likelihood.

It is the log-likelihood we would compute if we knew both the observed data and the latent variables. Since the latent variables are unknown, the E-step takes its expectation over the latent variables, and the M-step maximizes that expectation.

The GaussianMixture class in sklearn.mixture fits a Gaussian Mixture Model using the EM algorithm. It provides methods like fit, predict, and predict_proba for soft assignments.

from sklearn.mixture import GaussianMixture
import numpy as np
X = np.array([[1.0],[1.2],[5.0],[5.3]])
gm = GaussianMixture(n_components=2, random_state=0).fit(X)
print(gm.means_)
print(gm.predict_proba(X))

The predict_proba method returns, for each data point, the probability of belonging to each component (the responsibilities). The predict method instead returns the single most likely component (hard assignment).

from sklearn.mixture import GaussianMixture
import numpy as np
X = np.array([[0.0],[0.1],[9.0],[9.2]])
gm = GaussianMixture(n_components=2, random_state=0).fit(X)
soft = gm.predict_proba(X)
print(soft)

EM iteratively improves a lower bound (often derived using Jensen's inequality) of the log-likelihood: the E-step tightens the bound for the current parameters, and the M-step maximizes that bound. Alternating these two steps increases the true log-likelihood.

Jensen's inequality is central to the EM derivation. For the concave log function it lets the log of an expectation be bounded below by the expectation of the log, producing a tractable lower bound on the log-likelihood.

EM treats missing values as latent variables: in the E-step it estimates their expected values given the observed data and current parameters, and in the M-step it updates the parameters as if those estimates were the data. This lets it learn from incomplete datasets.

The latent variable is the identity of which coin produced each set of flips, since this is hidden. EM estimates the probability each coin was used (E-step) and then updates each coin's bias (M-step).

The likelihood can blow up to infinity, a problem called a singularity, where a component collapses onto one data point with near-zero variance. This is why regularization or covariance floors are used to keep EM well-behaved.

EM is widely used to fit Gaussian Mixture Models for tasks like clustering, density estimation, image segmentation, and speech recognition. Its ability to handle hidden structure makes it valuable across many domains.

When used for clustering with mixture models, EM is unsupervised because it works without labeled outputs, discovering hidden group structure from the data alone. The cluster assignments are inferred, not given.

The updated mixing weight of a component equals the sum of that component's responsibilities over all data points, divided by the total number of points. It is essentially the average responsibility, the effective fraction of data assigned to that component.

EM gives probabilistic (soft) memberships, expressing uncertainty when a point lies between clusters, and it can model clusters of different shapes and sizes via covariances. This is more flexible than K-Means' rigid spherical, hard assignments.

A poor initialization can cause EM to converge to a suboptimal local optimum, giving worse clusters or a lower final log-likelihood. This is why methods like k-means++ style initialization or multiple restarts are used to choose good starting points.

You can fit GMMs with different numbers of components and compare them using model-selection criteria like the BIC (Bayesian Information Criterion) or AIC, which balance fit against complexity. The number of components giving the lowest BIC/AIC is usually preferred.

from sklearn.mixture import GaussianMixture
import numpy as np
X = np.random.randn(200,2)
for k in range(1,5):
    gm = GaussianMixture(n_components=k, random_state=0).fit(X)
    print(k, round(gm.bic(X),1))

It is called the Expectation step because it computes the expected value of the complete-data log-likelihood with respect to the latent variables, using the current parameter estimates. Practically, this means calculating expected latent assignments (responsibilities).

EM often makes rapid progress early but can slow down considerably (linear convergence) as it nears a local optimum. This is a known characteristic, sometimes prompting hybrid or accelerated methods for the final refinement.