In Chapter 2, Introduction to Semi-Supervised Learning, we discussed the generative Gaussian mixture model in the context of semi-supervised learning. In this paragraph, we're going to apply the EM algorithm to derive the formulas for the parameter updates.

Let's start considering a dataset, X, drawn from a data generating process, p_data:

We assume that the whole distribution is generated by the sum of k Gaussian distributions so that the probability of each sample can be expressed as follows:

In the previous expression, the term w_j = P(N=j) is the relative weight of the j^th Gaussian, while μ_j and Σ_j are the mean and the covariance matrix. For consistency with the laws of probability, we also need to impose the following:

Unfortunately, if we try to solve the problem directly, we need to manage the logarithm of a sum and the procedure becomes very complex. However, we have learned that it's possible to use latent variables as helpers, whenever this trick can simplify the solution.

Let's consider a single parameter set θ=(w_j, μ_j, Σ_j) and a latent indicator matrix Z where each element z_ij is equal to 1 if the point x_i has been generated by the j^th Gaussian, and 0 otherwise. Therefore, each z_ij is Bernoulli distributed with parameters equal to p(j|x_i, θ_t).

The joint log-likelihood can hence be expressed using the exponential-indicator notation, as follows:

The index, i, is referred to the samples, while j refers to the Gaussian distributions. If we apply the chain rule and the properties of a logarithm, the expression becomes as follows:

The first term represents the probability of x_i under the j^th Gaussian, while the second one is the relative weight of the j^th Gaussian. We can now compute the Q(θ;θ_t) function using the joint log-likelihood:

Exploiting the linearity of E[•], the previous expression becomes as follows:

The term p(j|x_i, θ_t) corresponds to the expected value of z_ij considering the complete data, and expresses the probability of the j^th Gaussian given the sample x_i. It can be simplified considering Bayes' theorem:

The first term is the probability of x_i under the j^th Gaussian with parameters θ_t, while the second one is the weight of the j^th Gaussian considering the same parameter set θ_t. In order to derive the iterative expressions for the parameters, it's useful to write the complete formula for the logarithm of a multivariate Gaussian distribution:

To simplify this expression, we use the trace trick. In fact, as (x_i - μ_j)^T Σ^-1 (x_i - μ_j) is a scalar, we can exploit the properties tr(AB) = tr(BA) and tr(c) = c where A and B are matrices and c ∈ ℜ:

Let's start considering the estimation of the mean (only the first term of Q(θ;θ_t) depends on mean and covariance):

Setting the derivative equal to zero, we get the following:

In the same way, we obtain the expression of the covariance matrix:

To obtain the iterative expressions for the weights, the procedure is a little bit more complex, because we need to use the Lagrange multipliers (further information can be found in http://www.slimy.com/~steuard/teaching/tutorials/Lagrange.html). Considering that the sum of the weights must always be equal to 1, it's possible to write the following equation:

Setting both derivatives equal to zero, from the first one, considering that wj = p(j|θ), we get the following:

While from the second derivative, we obtain the following:

The last step derives from the fundamental condition: 

Therefore, the final expression of the weights is as follows:

At this point, we can formalize the Gaussian mixture algorithm:

• Set random initial values for w_j⁽⁰⁾, θ⁽⁰⁾_j and Σ⁽⁰⁾_j
• E-Step: Compute p(j|x_i, θ_t) using Bayes' theorem: p(j|x_i, θ_t) = α w^(t)_j p(x_i|j, θ_t)
• M-Step: Compute w_j^(t+1), θ^(t+1)_j and Σ^(t+1)_j using the formulas provided previously

The process must be iterated until the parameters become stable. In general, the best practice is using both a threshold and a maximum number of iterations.