M2-055M2: Classical Machine LearningClustering AlgorithmsMedium
⚡Flashcard Drill➔Mastery:

Derive the Expectation-Maximization (EM) Algorithm and Prove Its Monotonic Likelihood Ascent via Jensen's Inequality

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-056 →
📐 Mathematical Definition
Q(θ∣θt)=∑i∑kγiklog⁡p(xi,zi=k∣θ)γikQ(\theta\mid\theta^{t})=\sum_i\sum_k \gamma_{ik}\log\frac{p(x_i,z_i=k\mid\theta)}{\gamma_{ik}}
⚡ One-Sentence Core Answer
The EM algorithm maximizes incomplete log-likelihood with latent variables by iteratively constructing a tight Evidence Lower Bound (ELBO) in the E-step via q(z)=p(z∣x,θ)q(z) = p(z\mid x, \theta) and maximizing that lower bound in the M-step.

📌 Key Takeaways

  • •
    Latent Variable Log-Likelihood: log⁡p(X∣θ)=∑i=1Nlog⁡∑zp(xi,z∣θ)\log p(X\mid \theta) = \sum_{i=1}^N \log \sum_{z} p(x_i, z\mid \theta); intractable sum inside the logarithm.
  • •
    E-step (Expectation): Computes the posterior distribution of latent variables: q(z)=p(z∣x,θ(t))q(z) = p(z\mid x, \theta^{(t)}), making the ELBO touch the true likelihood.
  • •
    M-step (Maximization): Updates parameters by maximizing expected complete log-likelihood: θ(t+1)=arg⁡max⁡θEq[log⁡p(x,z∣θ)]\theta^{(t+1)} = \arg\max_\theta E_{q}[\log p(x, z\mid \theta)].
  • •
    Monotonic Guarantee: log⁡p(X∣θ(t+1))≥log⁡p(X∣θ(t))\log p(X\mid \theta^{(t+1)}) \ge \log p(X\mid \theta^{(t)}); guaranteed never to decrease likelihood.

📐 Mathematical Derivations

Proof of monotonic ascent via Jensen's Inequality: For any arbitrary latent distribution q(z)q(z): log⁡p(x∣θ)=log⁡∑zp(x,z∣θ)=log⁡∑zq(z)p(x,z∣θ)q(z)≥∑zq(z)log⁡p(x,z∣θ)q(z)≡L(q,θ)\log p(x\mid \theta) = \log \sum_z p(x, z\mid \theta) = \log \sum_z q(z) \frac{p(x, z\mid \theta)}{q(z)} \ge \sum_z q(z) \log \frac{p(x, z\mid \theta)}{q(z)} \equiv \mathcal{L}(q, \theta). Decomposing the difference: log⁡p(x∣θ)−L(q,θ)=∑zq(z)log⁡p(x∣θ)−∑zq(z)log⁡p(x,z∣θ)q(z)=∑zq(z)log⁡q(z)p(x∣θ)p(x,z∣θ)=∑zq(z)log⁡q(z)p(z∣x,θ)=DKL(q(z)∥p(z∣x,θ))\log p(x\mid \theta) - \mathcal{L}(q, \theta) = \sum_z q(z) \log p(x\mid \theta) - \sum_z q(z) \log\frac{p(x, z\mid \theta)}{q(z)} = \sum_z q(z) \log\frac{q(z) p(x\mid \theta)}{p(x, z\mid \theta)} = \sum_z q(z) \log\frac{q(z)}{p(z\mid x, \theta)} = D_{\text{KL}}(q(z) \parallel p(z\mid x, \theta)). Thus, log⁡p(x∣θ)=L(q,θ)+DKL(q(z)∥p(z∣x,θ))\log p(x\mid \theta) = \mathcal{L}(q, \theta) + D_{\text{KL}}(q(z) \parallel p(z\mid x, \theta)). In the E-step, setting q(z)=p(z∣x,θ(t))q(z) = p(z\mid x, \theta^{(t)}) drives DKL=0D_{\text{KL}} = 0, making L(q,θ(t))=log⁡p(x∣θ(t))\mathcal{L}(q, \theta^{(t)}) = \log p(x\mid \theta^{(t)}). In the M-step, we choose θ(t+1)=arg⁡max⁡θL(q,θ)\theta^{(t+1)} = \arg\max_\theta \mathcal{L}(q, \theta). Therefore: log⁡p(x∣θ(t+1))≥L(q,θ(t+1))≥L(q,θ(t))=log⁡p(x∣θ(t))\log p(x\mid \theta^{(t+1)}) \ge \mathcal{L}(q, \theta^{(t+1)}) \ge \mathcal{L}(q, \theta^{(t)}) = \log p(x\mid \theta^{(t)}), proving monotonic convergence.

🏭 Production Trade-offs

Classic instances of the EM algorithm in ML: (1) Gaussian Mixture Models (GMM): Latent variables zi∈{1,…,K}z_i \in \{1, \dots, K\}; E-step computes responsibilities γik=P(zi=k∣xi)\gamma_{ik} = P(z_i=k\mid x_i), M-step updates (πk,μk,Σk)(\pi_k, \mu_k, \Sigma_k). (2) Hidden Markov Models (Baum-Welch): Latent sequence states. (3) Variational Autoencoders (VAE): Amortized variational EM optimizing continuous latents.
⚠️ Common Interview Pitfalls
  • ✕
    Assuming EM converges to the global maximum (it is a local ascent algorithm that can get trapped in local maxima or saddle points).
  • ✕
    Singularities in GMM: If a Gaussian component collapses onto a single data point, variance σk2→0\sigma_k^2 \to 0, causing likelihood to diverge to +∞+\infty (must constrain covariance eigenvalues).
🎯 Interviewer Follow-up Inquiries
  • ?
    How does the Evidence Lower Bound (ELBO) in Variational Inference generalize the EM algorithm?
  • ?
    Why do GMM likelihood surfaces have unbounded singularities when covariance matrices approach zero?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-054: Compare K-Means, Gaussian Mixture Models (GMM), and DBSCAN Across Assumptions, Geometry, and Complexity📋 Back to BankNext →M2-056: Detail Unsupervised Clustering Evaluation: Internal Metrics vs. External Ground-Truth Metrics