M step
Section of Mixtures and the EM algorithm, part of Statistical learning
M step
| Type | Section |
| Taught in | Mixtures and the EM algorithm |
| Part | Statistical learning |
| Questions using it | 1 |
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
- Taught in Mixtures and the EM algorithm
- Questions that use it (1) — An M step
- All 7 questions on Mixtures and the EM algorithm
See also
EM algorithm · EM for a normal mixture · Finite mixture model · Posterior membership · Complete-data likelihood · Monotonicity of EM · Likelihood of a normal mixture · What the stationary equations suggest