EM Algorithm

EM (expectation-maximization) is a general framework for maximum likelihood estimation in models with latent variables, alternating between an E-step and an M-step until convergence. The E-step fixes the current parameters $\theta^{(t)}$ and forms the expected complete-data log-likelihood under the latent posterior (a lower bound): $Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]$; the M-step maximizes it to obtain $\theta^{(t+1)} = \arg\max_{\theta} Q(\theta \mid \theta^{(t)})$.By Jensen's inequality (log is concave), $\log p(X \mid \theta) \ge \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)] + H$, where $H$ is a constant w.r.t. $\theta$ (the entropy of the latent posterior) — every iteration raises this lower bound, so $\log p(X \mid \theta)$ never decreases, though only a local optimum is guaranteed.

GMM, HMM (Baum-Welch), missing-data imputation, factor analysis / probabilistic PCA, MT alignment; interviews always probe the E/M step definitions, the Jensen bound, and convergence.

directly maximizing $\log p(X \mid \theta)$ requires summing/integrating over latent variables, which is usually intractable; EM splits the hard problem via the “completed-data” trick — the E-step computes the latent posterior (soft completion), the M-step updates parameters in closed form on the completed sufficient statistics, each step being feasible while the likelihood rises monotonically. The cost: initialization-sensitive and only locally optimal (K-Means is a common GMM init).

Write the E-step $Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]$ and M-step; why is it called expectation-maximization?

Use Jensen's inequality to prove EM never decreases $\log p(X \mid \theta)$; when is the lower bound tight?

Does EM reach a global or local optimum? Why is it initialization-sensitive? Common strategies such as K-Means to initialize GMM?

When is EM applicable — what are latent variables? How does EM handle missing data? vs direct gradient ascent?

How does E-step cost scale with the number of latent states? Which EM specializations are GMM and HMM (Baum-Welch)?