What happens in the E step and the M step when EM fits a Gaussian mixture?

## Why an iterative algorithm at all The log-likelihood of a Gaussian mixture is ``` log L = sum_i log( sum_k pi_k * N(x_i | mu_k, Sigma_k) ) ``` The sum sits *inside* the logarithm. That is what breaks the usual trick of setting derivatives to zero and solving: the parameters of every component are tangled together in every term. If you knew which component produced each point, the problem would collapse — you would just fit one Gaussian per group with the ordinary sample mean and sample covariance. Expectation-Maximisation exploits exactly that: it invents the missing labels probabilistically, then does the easy fit. ## The E step: expectation Hold the current parameters `(pi, mu, Sigma)` fixed. For every point compute the posterior over components: ``` r_ik = pi_k * N(x_i | mu_k, Sigma_k) / sum_j ( pi_j * N(x_i | mu_j, Sigma_j) ) ``` That is the whole E step: one number per point per component, each row summing to 1. Formally, you are computing the expected value of the hidden indicator variable that says which component produced point `i` — hence "expectation". Nothing about the model changes here; only your belief about the hidden labels does. Practical note: the densities can underflow to zero in high dimensions, so real implementations work in log space and subtract the row maximum before exponentiating. That is a numerical detail, not a change to the algorithm. ## The M step: maximisation Now freeze the responsibilities and maximise. Because the responsibilities are treated as known weights, the maximisation decouples across components and every update has a closed form. Define the **effective count** ``` N_k = sum_i r_ik ``` which is how many points component `k` owns, counted fractionally — it need not be an integer, and the counts sum to `N`. Then: ``` pi_k = N_k / N mu_k = (1 / N_k) * sum_i r_ik * x_i Sigma_k = (1 / N_k) * sum_i r_ik * (x_i - mu_k)(x_i - mu_k)^T ``` Every one of these is the familiar sample estimator with each observation weighted by how much this component claims it. A point with responsibility 0.6 contributes 0.6 of a row to that component's mean and covariance. Use the *new* `mu_k` when forming the covariance. The order matters — weights, then means, then covariances about those means. ## The convergence guarantee, stated precisely Each full E-then-M sweep is guaranteed **never to decrease** the observed-data log-likelihood. This is the key theoretical property and the thing candidates most often overstate. What it does *not* say: - It does not say the likelihood strictly increases — at a fixed point it stays put. - It does not say you reach the global maximum. EM climbs to a local optimum or a saddle point, and mixture likelihoods are riddled with local optima. - It does not guarantee fast convergence. EM converges linearly and can crawl when components overlap heavily. Because of the local-optimum problem, you run EM several times from different starting parameters and keep the run with the highest final log-likelihood. Monitoring is straightforward: print the log-likelihood each iteration and stop when its improvement falls below a tolerance, or when a maximum iteration count is hit. If you ever see the log-likelihood *drop*, the implementation is buggy — that is a genuine invariant, not a heuristic. ## A worked 1-D trace Take five points `1.0, 1.5, 4.0, 4.5, 5.0` and start with two components at means 1.0 and 5.0, both with variance 1 and weight 0.5. The E step gives the two leftmost points responsibilities of essentially 1 on component 1 and the three rightmost essentially 1 on component 2 — the starting means are far apart, so the posterior is already sharp. The M step then pulls component 1's mean to about 1.28 with weight about 0.40, and component 2's to 4.5 with weight about 0.60, and shrinks both variances to match the spread each component now owns. One more sweep and the split has essentially settled. The attached snippet performs exactly this, in plain arithmetic. ## The relationship to hard partitioning If you replace the E step's soft responsibilities with a hard 1-for-the-best-component, 0-otherwise assignment and constrain all components to share one spherical covariance, the M step's weighted means become plain group means and the algorithm becomes the classic assign-then-recentre loop. EM is the soft, probabilistic generalisation: same alternating structure, but the assignment is a posterior rather than a winner-take-all, and the M step estimates covariance shape as well as location. ## What interviewers listen for The complete answer names both steps, states what is *held fixed* in each, gives the responsibility formula and at least the weighted-mean update, and gets the guarantee right — monotone non-decreasing likelihood, local optimum, initialisation-dependent. Saying "EM finds the maximum likelihood solution" without the word *local* is the single most common slip.