EM Algorithm (Expectation-Maximization):

Iterative method for MLE in presence of latent variables $Z$ (e.g., mixture components, missing data). Maximizes $\log p(X|\theta)=\log\sum_Z p(X,Z|\theta)$ intractable directly.

Idea: Iteratively construct lower bound via Jensen, maximize it.

Steps:
Given data $X$, latent $Z$, parameters $\theta$.

• E-step (Expectation): Compute posterior $q(Z)=p(Z|X,\theta^{(t)})$ and expected complete log-likelihood $Q(\theta|\theta^{(t)})=E_{Z|X,\theta^{(t)}}[\log p(X,Z|\theta)] = \sum_Z p(Z|X,\theta^{(t)})\log p(X,Z|\theta)$
  Equivalent to computing responsibilities $\gamma_{nk}=p(z_k=1|x_n,\theta^{(t)})$.

• M-step (Maximization): $\theta^{(t+1)}=\arg\max_\theta Q(\theta|\theta^{(t)})$

Iterate until $\log p(X|\theta^{(t+1)})-\log p(X|\theta^{(t)})<\epsilon$. Guaranteed monotonic increase, converges to local optimum (not necessarily global; restart needed).

Example — Gaussian Mixture Model (GMM) with $K$ components:

Model: $p(x)=\sum_{k=1}^K \pi_k N(x|\mu_k,\Sigma_k)$, latent $z_{nk}\in\{0,1\}$ indicates component.

E-step: $\gamma_{nk}= \frac{\pi_k N(x_n|\mu_k,\Sigma_k)}{\sum_j \pi_j N(x_n|\mu_j,\Sigma_j)}$

M-step: $N_k=\sum_n\gamma_{nk}$, $\pi_k^{new}=N_k/N$, $\mu_k^{new}=\frac1{N_k}\sum_n\gamma_{nk}x_n$, $\Sigma_k^{new}=\frac1{N_k}\sum_n\gamma_{nk}(x_n-\mu_k^{new})(x_n-\mu_k^{new})^T$

Example numbers: Data {1,2,10}, $K=2$ init $\mu_1=1,\mu_2=10$ → E-step assigns 1,2 to component1 ($\gamma\approx1$), 10 to component2 → M-step updates $\mu_1\to1.5$, $\mu_2\to10$ → iterates.

EM also used in HMM (Baum-Welch), k-means is hard-assignment limit of GMM-EM with spherical $\Sigma\to0$.