13.3 EM Algorithm: General Framework
Suppose that we want to maximize the log-likelihood \(\log p(\mathbf{x}|\theta)\). Under some scenarios, this likelihood can be difficult to derive. For example, \(X\) are generated from a mixture of several models, however, we do not know which is the underlying true model for each observation. Or, \(X\) contains missing values, where we have \(\mathbf{X} = (\mathbf{X}_{obs}, \mathbf{X}_{mis})\). In such cases, it would be easier if we introduced a latent variable \(Z\), such that the joint likelihood of \(p(\mathbf{x}, \mathbf{z}| \theta)\) is much easier to derive.
For example, if \(Z\) represents the hidden label, then \[p(\mathbf{x}, \mathbf{z}|\theta) = p(\mathbf{z}|\theta) \, p(\mathbf{x}|\mathbf{z}, \theta)\] where both probabilities are easier to write out given the underlying model. In general, for a discrete case of \(Z\), we need to maximize the log-likelihood \[\log p(\mathbf{x}|\theta) = \log \sum_z p(\mathbf{x}, \mathbf{z}|\theta)\] For a continuous case, we maximize the log-likelihood \[\log p(\mathbf{x}|\theta) = \log \int_z p(\mathbf{x}, \mathbf{z}|\theta) d\mathbf{z}\]
This can still be difficult to solve since there is a summation in the \(\log\) function. The Expectation - Maximization (EM) algorithm is designed to solve this problem (Dempster, Laird, and Rubin, 1977).
General EM Algorithm
E-Step: Under the current value of \(\theta\), denoted as \(\theta^{(k)}\), find \(p(\mathbf{z}|\mathbf{x}, \theta^{(k)})\), the distribution of the unobserved variables given the data and \(\theta^{(k)}\). Then calculate the conditional expectation: \[\begin{align*} g(\theta) &= \mathbf{E}_{\mathbf{Z}|\mathbf{x}, \theta^{(k)}} \log p(\mathbf{x}, \mathbf{Z} |\theta)\\ &= \begin{cases} & \sum_{\mathbf{z}} P(\mathbf{Z} = \mathbf{z}| \mathbf{x}, \theta^{(k)}) \log p(\mathbf{x}, \mathbf{z}|\theta)\\ & \int_{\mathbf{z}} P(\mathbf{Z} = \mathbf{z}| \mathbf{x}, \theta^{(k)}) \log p(\mathbf{x}, \mathbf{z}|\theta) dz\\ \end{cases} \end{align*}\]
M-Step: Re-estimate the parameter \(\theta\) to maximize \(g(\theta)\): \[\theta^{(k+1)} = \arg \max_{\theta} g(\theta)\]
To summarize, three components are involved in an EM algorithm: 1. The outcome variable \(\mathbf{X}\), with observed values \(\mathbf{x}\). 2. The distribution parameters \(\theta\) 3. The latent variables \(\mathbf{Z}\)
The EM algorithm bounces back and forth between two processes:
E-step: Given the current parameters and the observed data, estimate the (conditional mean of) latent variables.
M-step: Given the observed data and the latent variables, estimate the parameters.