13.2 EM Algorithm
Instead of directly optimizing the log-likelihood \(\ell(\mathbf{x}|\theta)\), we introduce the latent variable \(Z\), and write the joint log-likelihood as
\[\begin{align*} \ell(\mathbf{x}, \mathbf{z}|\theta) &= \sum_{i=1}^{n} \Bigl( (1-z_i)\log \phi_{\mu_1}(x_i) + z_i \log \phi_{\mu_2}(x_i)\Bigr)\\ & \quad + \sum_{i=1}^{n} \Bigl( (1-z_i) \log(1-\pi) + z_i \log \pi\Bigr) \end{align*}\]
EM algorithm: We optimize this likelihood function by iteratively updating the unknowns: \(\mathbf{z}\) and \(\theta\).
E-step (Expectation): we treat both \(\mathbf{x}\) and \((\mu_1, \mu_2, \pi)\) as known, and calculate the conditional probability of each \(z_i\).
M-step (Maximization): we treat \(\mathbf{x}\) and \(\mathbf{z}\) as known, and solve the parameters by maximizing the likelihood.
EM Algorithm: E-Step
If both \(\mathbf{x}\) and \(\theta=(\mu_1, \mu_2, \pi)\) are known, then the conditional probability of each \(z_i\) can be calculated as: \[\begin{align*} P\left( Z_i=1|\theta^{(k)}, \mathbf{x} \right) &= \frac{P \Bigl(Z_i=1, x_i|\theta^{(k)} \Bigr) }{p\Bigl(x_i|\theta^{(k)}\Bigr)}\\ &= \frac{\pi^{(k)}\,\phi_{\mu_2^{(k)}}(x_i)}{(1-\pi^{(k)})\,\phi_{\mu_1^{(k)}}(x_i) + \pi^{(k)}\,\phi_{\mu_2^{(k)}}(x_i)} \end{align*}\]
This is simple since we just need to calculate the density functions of each \(x_i\) under the current parameter \(\theta^{(k)}\) for each possible label (\(z_i=0\) or \(1\)).
EM Algorithm: M-Step
We already have \(P\Bigl(\mathbf{Z} = \mathbf{z}|\mathbf{x}, \theta^{(k)}\Bigr)\), we can replace all the \(z_i\) values (since they are unknown anyways) in the likelihood function \(\ell(\mathbf{x}, \mathbf{z}|\theta)\) by their expectations (from the E-step): \[\hat{p}_i = P\left(Z_i=1|\mathbf{x}, \theta^{(k)}\right)\]
After this, what remains in the likelihood only involves \(\mathbf{x}\) and \(\theta\), so we can solve (the M-step) for the MLE of \(\theta\) based on this new likelihood function.
It turns out that these estimators are just weighted means:
\[\hat{\mu}_1 = \frac{\sum_{i=1}^{n}(1-\hat{p}_i)x_i}{\sum_{i=1}^{n}(1-\hat{p}_i)},\quad \hat{\mu}_2 = \frac{\sum_{i=1}^{n}\hat{p}_i x_i}{\sum_{i=1}^{n} \hat{p}_i},\quad \hat{\pi} = \frac{1}{n}\sum_{i=1}^{n} \hat{p}_i \]
We will then iterate the E- and M- steps until convergence.
Connection with \(k\)-Means
Suppose in the E-step, we do not use the “soft” label (the probability), instead, we use a “hard” label: \[\mathbf{1}_{\bigl\{P\bigl(Z_i = 1|\mathbf{x}, \theta^{(k)}\bigr) > 0.5\bigr\}}\]
This is essentially comparing the two densities and seeing which one is larger. Notice that, with equal variance, the log density of a Gaussian differs from a constant only by the squared Euclidean norm, so we are just choosing the “closer” cluster mean (of the previous iteration). The M-step is just re-calculating the cluster means based on the new assignments. In that sense, \(K\)-means is a hard-assignment, equal-covariance version of EM for a Gaussian mixture. If the component variances are allowed to differ, the hard assignment is no longer “nearest mean.”
The same EM argument extends immediately to \(K\) components in \(p\) dimensions, \[p(x) = \sum_{k=1}^{K} \pi_k\,\phi(x;\,\mu_k, \Sigma_k),\] with \(\sum_k \pi_k = 1\). The E-step produces responsibilities \(\hat{p}_{ik} = P(Z_i=k|x_i,\theta^{(k)})\), and the M-step updates each \(\pi_k\), \(\mu_k\), and \(\Sigma_k\) as weighted means and weighted covariances. Constraining \(\Sigma_k = \sigma^2 I\) recovers spherical clusters; allowing a common \(\Sigma\) or free \(\Sigma_k\) lets clusters be elliptical. The observed-data likelihood is then available, so the number of components can be chosen by AIC or BIC, which is the model-based counterpart of the gap and silhouette statistics from the previous chapter. In practice one often initializes EM from a \(K\)-means run.
Responsibilities, labels, and choosing \(K\)
The numbers \(\hat{p}_{ik}\) are the reason to prefer a mixture model over \(K\)-means when the model is plausible. They are soft cluster memberships: \(\hat{p}_{ik}\) is the estimated probability that observation \(i\) belongs to component \(k\), given the current fit. One can report a hard label \(\arg\max_k \hat{p}_{ik}\), but one can also keep the vector \((\hat{p}_{i1},\ldots,\hat{p}_{iK})\) as a measure of uncertainty. Points with two comparable \(\hat{p}_{ik}\) sit on the boundary between clusters; \(K\)-means has no analogue of that statement.
Two caveats come with the likelihood. First, \(\ell(\theta|\mathbf{x})\) is unchanged if we permute the component labels, so the maximizer is not unique; this is label switching. Second, the observed-data likelihood is not concave, so EM converges to a local maximum. Different \(K\)-means starts (or several random starts) can yield different fits; one keeps the run with the largest \(\ell(\theta|\mathbf{x})\).
Once a fit is in hand, the same observed-data log-likelihood is what we use to choose \(K\). With \(\ell_K\) the maximized log-likelihood of a \(K\)-component mixture and \(d_K\) the number of free parameters, \[\begin{align*} \mathrm{AIC}(K) &= -2\ell_K + 2d_K,\\ \mathrm{BIC}(K) &= -2\ell_K + d_K\log n. \end{align*}\] For a \(p\)-dimensional Gaussian mixture with free mixing weights, means, and covariances, \[d_K = (K-1) + Kp + K\cdot\frac{p(p+1)}{2}.\] Constraints on \(\Sigma_k\) (spherical, diagonal, or shared across \(k\)) reduce \(d_K\). We select the \(K\) that minimizes AIC or BIC. BIC penalizes complexity more heavily and is the more common default for mixtures. This is a different answer to “how many clusters?” than gap or silhouette: here \(K\) indexes a list of probability models, and we score those models on the observed data.