Let’s now look at a more principled method of learning from input data. In Gaussian Mixture Models (GMMs), we assume that the data is a mixture of Gaussians, each with its own mean and variance. What does that mean precisely? It means that we assume that there are Gaussians that each data point could be generated by. We assume that each data point was generated by a two-step process: first, you select one of the Gaussians according to a prior distribution, , where . We read this as “probability of , parameterized by G, where has a Multinomial distribution”. Essentially, is the set of the parameters for our model. After selecting one of the Gaussians, we generate a data point. We assume that this process was repeated for every data point. This method should remind you of the Gaussian Discriminant Analysis model we discussed–however, here, we don’t know the class labels.

We can now write the probability distribution of our inputs. Note that this is simply the law of total probability:

The parameters of our model are .

To solve for these parameters, we use an iterative algorithm called the Expectation-Maximization (EM) algorithm. We’ll talk more about this algorithm later, but it provides a general method to find maximum likelihood (ML) or maximum a posteriori (MAP) estimates of parameters, where the model depends on some unobservable variables. In our case, the unobservable (or latent) variables are the priors, since we can only see the s, not the s. In fact, if we had known the s, we could write down the likelihood, and get the same MLEs that we got for GDA. The EM algorithm has two steps:

Expectation (E) step: Here, we compute the posterior distribution of for each . For each , we set

Maximization (M) step: In this step, we use the results of the E step to update the parameters of our model.

Note that in the M step, the update formulas are similar to the GDA ones, except that the indicator functions have been replaced with the posterior distribution values. Also, note that the EM algorithm expects that you have all the data at once, making it a batch learning algorithm, while k-means is an online learning algorithm, which means you can give the data in parts, and it will work correctly. The EM algorithm, like k-means, is also susceptible to local optima.