Maximum Likelihood Estimation

Expectation Maximization (EM)

It is a soft clustering algorithm. Unlike K-Means Clustering which is hard clustering.

The motivation behind this is the analytical derivation for MLE of GMMs has no closed form solutions (involves computing derivative of Log Likelihood of sums of gaussians). Instead of trying to maximize this log-likelihood directly, EM introduces latent variables for cluster assignments.

We can equivalently describe a GMM, with 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).$$

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).$$

• by chain rule?

The marginal probability of $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 EM updates. Then, that’s how we are able to use the equations 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)}$$

3. M-step (Maximization)
   Update parameters using weighted averages:

$${\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 (optional? they didn’t explain this in the video)

$${\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