Maximum Likelihood Estimation

Expectation Maximization (EM)

EM is a soft clustering algorithm that iteratively estimates parameters of latent-variable models by alternating expectation and maximization steps.

Why EM instead of direct MLE on a GMM?

The analytical MLE for a GMM has no closed form (the derivative of a log of a sum of Gaussians is ugly). EM introduces latent cluster assignments so each M-step has a closed form

Unlike K-Means Clustering (hard clustering), EM assigns soft probabilities of cluster membership.

Intuition

Chicken-and-egg. If you knew which Gaussian each point came from, fitting the means and variances is trivial (just MLE per cluster). If you knew the means and variances, assigning points is trivial (pick the most likely cluster). EM alternates: given current params, soft-assign points (E-step); given soft assignments, refit params (M-step). Each full pass provably increases the data log-likelihood, so you climb a hill in parameter space until it stops moving.

We can equivalently describe a GMM with latent variables:

$$z_i\sim \text{Categorical}({\pi }_1,\dots ,{\pi }_K),x_i\mid z_i=k\sim \mathcal{N}({\mu }_k,{\sigma }_k^2)$$

where:

• $z_i$ is the (hidden) cluster assignment for point $i$
• ${\pi }_k$ is the prior probability of cluster $k$

The joint distribution of observed $x_i$ and hidden $z_i$ is

$$p(x_i,z_i\mid \theta )={\pi }_{z_i}\mathcal{N}(x_i\mid {\mu }_{z_i},{\sigma }_{z_i}^2)$$

The marginal $p(x_i|\theta )$:

$$p(x_i\mid \theta )=\sum _{k=1}^{K}p(x_i,z_i=k\mid \theta )=\sum _{k=1}^K{\pi }_k\mathcal{N}(x_i\mid {\mu }_k,{\sigma }_k^2)$$

If the latent $z_i$ were observed, the complete-data log-likelihood would be

$${\ell }_c(\theta )=\sum _{i=1}^n\sum _{k=1}^K{z}_{ik}[\log {\pi }_k+\log \mathcal{N}(x_i\mid {\mu }_k,{\sigma }_k^2)]$$

which is easy to optimize in closed form. Since $z_i$ are hidden, EM replaces them with their expected values (responsibilities ${\gamma }_{ik}$), leading to the iterative updates below.

This lecture is really good:

• Full playlist: https://www.youtube.com/playlist?list=PLBv09BD7ez_4e9LtmK626Evn1ion6ynrt

Resources

• https://arxiv.org/pdf/cs/0412015
• https://chrischoy.github.io/posts/Expectation-Maximization-and-Variational-Inference/
• Paper tutorial: https://ieeexplore-ieee-org.proxy.lib.uwaterloo.ca/stamp/stamp.jsp?tp=&arnumber=543975

You first assume there are a set of Gaussians that the data $x$ is sampled from.

Basic EM Algorithm for Gaussian Mixture

1. Initialization: assume $N$ Gaussians with parameters ${\theta }_i=({\mu }_i,{\sigma }_i^2)$. Initialize ${\mu }_i,{\sigma }_i^2$, and mixing weights ${\pi }_i$ randomly
2. E-step (Expectation): compute the Posterior Probability (responsibility) that point $x_j$ belongs to component $i$

$${\gamma }_{ij}=P({\theta }_i\mid x_j)=\frac{{\pi }_i\mathcal{N}(x_j\mid {\mu }_i,{\sigma }_i^2)}{{\sum }_{k=1}^2{\pi }_k\mathcal{N}(x_j\mid {\mu }_k,{\sigma }_k^2)}$$

The responsibility ${\gamma }_{ij}$ is the softmax-looking answer to “how much does cluster $i$ claim point $x_j$?“. Numerator is “how likely cluster $i$ would have produced $x_j$”; denominator normalizes across clusters.

3. M-step (Maximization): update parameters using weighted averages. This is the standard Gaussian MLE, except each point $x_j$ contributes with weight ${\gamma }_{ij}$ instead of 0/1. A point sitting between two clusters pulls both means partially toward itself.

$${\mu }_i=\frac{{\sum }_j{\gamma }_{ij}{x}_j}{{\sum }_j{\gamma }_{ij}}$$ $${\sigma }_i^2=\frac{{\sum }_j{\gamma }_{ij}(x_j-{\mu }_i{)}^2}{{\sum }_j{\gamma }_{ij}}$$

Mixing weights:

$${\pi }_i=\frac{1}{N}\sum _j{\gamma }_{ij}$$

4. Repeat: alternate E-step and M-step until convergence (parameters stabilize or log-likelihood stops improving)

Related

• Variational Inference