Gaussian Mixture Models and EM algorithm

1. Gaussian Mixture Model (GMM)
In an earlier post, it was shown that we can partition our dataset into different subgroups or clusters, or how we hierarchically partition them step by step. One fundamental flaw of the k-means algorithm is the assumption that the dataset is more or less spherical. If it is not, then the algorithm will not do the job well (it will still partition, wrongly!) Another limitation of the k-means algorithm is that it is a hard-clustering algorithm, i.e. the clusters don't overlap. It does not provide any possibility or probability that the point can belong to any of the clusters.

A finite mixture model is a model comprised of an unspecified combination of multiple, but finite number of probability distribution functions.

A mixture model where the probability distribution functions are Gaussian or normal is called a Gaussian Mixture Model (GMM). It exactly attempts to provide a soft-clustering approach where clusters tend to overlap, i.e. there is some probability that a particular point belongs to more than one cluster. As an example, the probability density function of a 1D univariate dataset with 3 mixture components (K = 3) is below.

Fig-1: Probability density function (pdf) of a 1D dataset consisting of 3 mixture components. Note that the separation is not complete between adjacent clusters, and thus it reflects some probabilistic nature in it. [Ref 1]


So, a finite Gaussian mixture model means that we represent the dataset as being composed of K Gaussian functions, each has its own set of model parameters grouped as θ_k = { π, μ, Σ }:
     (1) A mean μ that defines its center.
     (2) A covariance matrix Σ that defines its width.
     (3) A mixing probability π or mixing weights.
In a univariate sense, a Gaussian or Normal distribution is modeled by the mean and variance (μ, σ²), satisfying the sufficient statistics. However, for a D-dimensional multivariate Gaussian distribution, we have a D × D covariance matrix Σ to represent the spread instead. In practice, the covariance matrix Σ can be further decomposed into several parameters that define certain geometric properties which at the same time provide certain constraints in the model for easy estimation (out of scope, but see Fig-3).

The mixing probability defines the probability that a certain point belongs to any clusters (Σπ = 1), which is essentially the cluster assignment problem in k-means. The larger this value is, the wider the shape of the Gaussian function will be, as it provides a higher chance that more points will be included under that function. A cluster assignment problem is estimated by the marginal probability distribution of a point in the mixture model, i.e. a weighted sum of the individual Gaussian function (defined by its three parameters above, Fig-1), where x is our dataset.

Fig-2: (a) Probability density function of 1D GMM; (b) Multivariate 2D gaussian probability density function; (c) An example of finite GMM consisting of 3 mixture components.

Fig-3: Comparison between k-Means and model-based GMM clustering algorithms. In the model-based method, we are not limited to spherical data and can estimate the shape of the distribution through an iterative process called EM algorithm. 


Now, how do we obtain the values for these parameters bearing in mind that we have K Gaussian functions? Of course, if we know the grouping sources beforehand (Fig-1), we can easily fit the Gaussian functions, compute the mean and standard deviation of each function (μ, σ²). In practice, we don't know the grouping sources, and the task can be even more challenging for the multidimensional Gaussian functions. Fortunately, we can estimate the relevant parameters with the help of the maximum likelihood estimation (MLE).

Note: Due to the fact that we need to determine model parameters, the soft-clustering approach using GMM is often called the model-based algorithms.

2. Expectation-Maximization Algorithm
Suppose we have a dataset x with n number of points in a GMM comprising K functions. The data is combined and the distributions are similar enough that it is not obvious to which distribution a given point may belong. To draw a sample from x, we select one of the components having a certain mixing probability π_k. Then with the help of a latent variable, z, for cluster assignment, we define a new probability (or in fact, likelihood) as a form of joint-probability distribution of the dataset x assuming that each data point is i.i.d.

Expectation-Maximization algorithm (EM) is an approach for maximum likelihood estimation with some latent variables. EM algorithm is a way to find maximum-likelihood estimates (MLE) for model parameters when the data is either incomplete, hidden, or multidimensional. The algorithm alternates between two steps:

• The first mode attempts to estimate the missing or latent variables called the estimation-step or E-step.
• The second mode attempts to optimize or maximize the parameters of the model to best explain the data called the maximization-step or M-step.

Nice references:
(1) Gaussian Mixture Model explained (more Maths involved!).
(2) Comparisons between k-means and EM algorithm
(3) Gaussian mixture modeling
# Gentle Introduction to Expectation Maximization
https://www.youtube.com/watch?v=REypj2sy_5U&ab_channel=VictorLavrenko