E and M steps
Section of Mixtures and the EM algorithm, part of Statistical learning
E and M steps
| Type | Section |
| Taught in | Mixtures and the EM algorithm |
| Part | Statistical learning |
Let \Psi^{(k)} be the parameter at iteration k. The update maximises the conditional expected complete log-likelihood. The expectation is over the latent indicators, drawn from their conditional distribution at \Psi^{(k)}, with the observations held fixed. That expectation is the Q function,
Q(\Psi;\Psi^{(k)}) =\mathbb{E}_{Z;\Psi^{(k)}}\bigl[\ell_C(\Psi)\bigm|X_{\mathrm{all}}\bigr].
The two arguments of Q have different jobs. The current value \Psi^{(k)} determines the distribution of the missing labels. The candidate \Psi is what varies during maximisation. Compute the memberships once in the E step, hold them fixed in the M step, then recompute them at the new parameter. Updating the memberships inside the M-step derivatives would be a different calculation.
The E step
Main article: E step
The complete log-likelihood is linear in the indicators, so the conditional expectation passes inside the sum. The expectation of a binary indicator is the probability that it equals one. Bayes’ rule for a discrete label and a continuous measurement identifies that probability with the posterior membership, evaluated at the current parameter:
\begin{align*} Q(\Psi;\Psi^{(k)}) &=\mathbb{E}\Biggl[ \sum_{i=1}^{n}\sum_{h=1}^{H}Z_{ih}\bigl[\ln\pi_h+\ln f_h(\mathbf{x}_i;\theta_h)\bigr] \Bigm|X_{\mathrm{all}} \Biggr]\\ &=\sum_{i=1}^{n}\sum_{h=1}^{H} \mathbb{E}(Z_{ih}\mid\mathbf{x}_i)\, \bigl[\ln\pi_h+\ln f_h(\mathbf{x}_i;\theta_h)\bigr]\\ &=\sum_{i=1}^{n}\sum_{h=1}^{H} \tau_h(\mathbf{x}_i;\Psi^{(k)})\, \bigl[\ln\pi_h+\ln f_h(\mathbf{x}_i;\theta_h)\bigr]. \end{align*}
The current parameter \Psi^{(k)} is held fixed inside \tau_h. The free parameter \Psi remains in \ln\pi_h+\ln f_h, which is what the M step maximises. Explicitly,
\tau_h\bigl(\mathbf{x}_i;\Psi^{(k)}\bigr) =\frac{\pi_h^{(k)}f_h\bigl(\mathbf{x}_i;\theta_h^{(k)}\bigr)} {\sum_{m=1}^{H}\pi_m^{(k)}f_m\bigl(\mathbf{x}_i;\theta_m^{(k)}\bigr)}.
The M step
Main article: M step
Maximise Q in \Psi, with the weights \tau_{ih}:=\tau_h(\mathbf{x}_i;\Psi^{(k)}) held at the values just computed. The objective separates into a term in the weights \pi_h and a weighted normal log-likelihood for each component. Write N_h=\sum_i\tau_{ih} for the effective sample size of component h.
Weights. Maximise \sum_h N_h\ln\pi_h subject to \sum_h\pi_h=1. The Lagrangian \sum_h N_h\ln\pi_h-\kappa\bigl(\sum_h\pi_h-1\bigr) has derivative N_h/\pi_h-\kappa. Set the derivative to zero, so \pi_h=N_h/\kappa. Sum over h. The identity \sum_h N_h=\sum_i\sum_h\tau_{ih}=n forces \kappa=n, and therefore
\pi_h^{(k+1)} =\frac1n\sum_{i=1}^{n}\tau_h\bigl(\mathbf{x}_i;\Psi^{(k)}\bigr) =\frac{N_h}{n}.
Means. The terms of Q that involve \boldsymbol\mu_h are -\tfrac12\sum_i\tau_{ih}(\mathbf{x}_i-\boldsymbol\mu_h)^\top\Sigma_h^{-1}(\mathbf{x}_i-\boldsymbol\mu_h). The gradient in \boldsymbol\mu_h is \Sigma_h^{-1}\sum_i\tau_{ih}(\mathbf{x}_i-\boldsymbol\mu_h). Set it to zero and multiply by \Sigma_h, which is positive definite at an interior point. The solution is the weighted mean,
\boldsymbol\mu_h^{(k+1)} =\frac{\sum_{i=1}^{n}\tau_{ih}\mathbf{x}_i}{\sum_{i=1}^{n}\tau_{ih}}.
Covariance matrices. Pass to the precision \Theta_h=\Sigma_h^{-1}. The terms that involve \Theta_h are \tfrac12 N_h\ln|\Theta_h|-\tfrac12\sum_i\tau_{ih}(\mathbf{x}_i-\boldsymbol\mu_h)^\top\Theta_h(\mathbf{x}_i-\boldsymbol\mu_h). The matrix derivatives \partial\ln|\Theta|/\partial\Theta=\Theta^{-1} and \partial(\mathbf{v}^\top\Theta\mathbf{v})/\partial\Theta=\mathbf{v}\mathbf{v}^\top produce
\frac12 N_h\Theta_h^{-1} -\frac12\sum_{i=1}^{n}\tau_{ih}(\mathbf{x}_i-\boldsymbol\mu_h)(\mathbf{x}_i-\boldsymbol\mu_h)^\top.
Set the derivative to zero and insert the updated mean. Then \Theta_h^{-1} equals the weighted matrix of squares and products, so
\Sigma_h^{(k+1)} =\frac{\sum_{i=1}^{n}\tau_{ih} \bigl(\mathbf{x}_i-\boldsymbol\mu_h^{(k+1)}\bigr) \bigl(\mathbf{x}_i-\boldsymbol\mu_h^{(k+1)}\bigr)^\top} {\sum_{i=1}^{n}\tau_{ih}}.
The formulas now have a familiar shape: proportions, means, and covariance matrices, with fractional membership replacing a hard group label. The divisor is N_h. Likelihood maximisation uses N_h in the denominator; an unbiased sample covariance would subtract one from a hard group size, and that correction is a different estimator. These updates require N_h>0 and positive definite updated covariance matrices. A collapsed component is a failure of those conditions.
Definition 1 (EM for a normal mixture) Choose initial values \Psi^{(0)}. For k=0,1,2,\ldots:
- E step: compute \tau_{ih}=\tau_h(\mathbf{x}_i;\Psi^{(k)}) for all i,h.
- M step: compute \pi_h^{(k+1)}, \boldsymbol\mu_h^{(k+1)}, and \Sigma_h^{(k+1)} from the three updates above.
- Stop when the change in \ell(\Psi^{(k)};X_{\mathrm{all}}) is smaller than a threshold.
Q(\Psi;\Psi^{(k)}), plus a constant independent of \Psi, is a lower bound on the observed log-likelihood, touching it at the current parameter. The constant matters for the touching statement, and it does not change the maximiser. EM is the minorisation–maximisation step for that bound (Lange, 2013).
Used in
See also
Finite mixture model · Posterior membership · Complete-data likelihood · EM for a normal mixture · Monotonicity of EM · Likelihood of a normal mixture · What the stationary equations suggest · E step