13.4 The MM Algorithm
The MM algorithm (Minorize-Maximize, or Majorize-Minimize) is a general framework for optimization. The EM algorithm can be treated as a special case of MM. We will show that both MM and EM have the ascend (or descend) property.
General Philosophy
Suppose we want to maximize the function \(f\left(\theta\right)\). We perform the optimization by recursively updating the \(\theta\) value.
At each iteration \(k\):
Let \(\theta^{(k)}\) represent the current parameter value.
We first find a function \(g\left(\theta|\theta^{(k)}\right)\) that minorizes \(f\left(\theta\right)\) (lies below \(f\) and touches it at the current point):
For all \(\theta\), \(g\left(\theta|\theta^{(k)} \right) \leq f\left(\theta\right)\) and \(g\left(\theta^{(k)}|\theta^{(k)} \right) = f \left(\theta^{(k)} \right)\).
Update \(\theta\) with \[\theta^{(k+1)} = \arg \max_{\theta} g\Bigl(\theta|\theta^{(k)} \Bigr) \]
Figure 13.1: MM Algorithm (Ref. Wikipedia)
13.4.1 Ascend Property
The MM algorithm is guaranteed to ascend: \[\begin{align*} f\left( \theta^{(k+1)} \right) &= g \left(\theta^{(k+1)} | \theta^{(k)}\right) + \Bigl(f\left( \theta^{(k+1)}\right) - g\left( \theta^{(k+1)}| \theta^{(k)} \right)\Bigr)\\ &\geq g\left( \theta^{(k+1)}| \theta^{(k)} \right)\\ &\geq g\left( \theta^{(k)}| \theta^{(k)} \right) = f(\theta^{(k)}) \end{align*}\]
If we instead minimize \(f\) using a majorizing surrogate \(g \geq f\), the same argument shows that the algorithm is guaranteed to descend.
Ascend Property: EM Algorithm
The EM algorithm is a special case of MM. We can show that \[\ell \Bigl(\theta^{(k+1)} | \mathbf{x} \Bigr) = \log p\Bigl(\mathbf{x}|\theta^{(k+1)} \Bigr) \geq \log p\Bigl(\mathbf{x}|\theta^{(k)} \Bigr) = \ell\Bigl(\theta^{(k)} | \mathbf{x}\Bigr) \]
The proof relies on Jensen’s inequality: \[\begin{align*} E\Bigl( f(X) \Bigr) &\geq f\Bigl( E(X) \Bigr), \, \text{ if } \, f\, \text{ is convex}\\ E\Bigl( f(X) \Bigr) &\leq f\Bigl( E(X) \Bigr), \, \text{ if } \, f\, \text{ is concave}\\ \end{align*}\]
Since \(\mathbf{x}\) is observed and \(\mathbf{z}\) is the missing part \[\ell(\theta|\mathbf{x}) = \log p(\mathbf{x}|\theta) = \log \frac{p(\mathbf{x}, \mathbf{z}|\theta)}{p(\mathbf{z}| \mathbf{x},\theta)}\] The difference of two likelihood functions under \(\theta^{(k)}\) and \(\theta^{(k+1)}\)
\[\begin{align*} \ell(\theta^{(k+1)}|\mathbf{x}) - \ell(\theta^{(k)}|\mathbf{x}) &= \log p(\mathbf{x}, \mathbf{z}|\theta^{(k+1)}) - \log p(\mathbf{x}, \mathbf{z}|\theta^{(k)}) \\ &\quad - \Bigl( \log p( \mathbf{z}|\mathbf{x},\theta^{(k+1)}) - \log p( \mathbf{z}| \mathbf{x}, \theta^{(k)})\Bigr) \end{align*}\]
This identity holds for every \(\mathbf{z}\). We take the expectation of both sides with respect to \(\mathbf{z}\) given \(\mathbf{x}\) and \(\theta^{(k)}\). The left-hand side does not depend on \(\mathbf{z}\), so it is unchanged.
The right-hand side becomes \[\begin{align*} & \underbrace{E \Bigl( \log p(\mathbf{x}, \mathbf{z}| \theta^{(k+1)}) - \log p(\mathbf{x}, \mathbf{z}| \theta^{(k)} )\,\Big|\, \mathbf{x}, \theta^{(k)} \Bigr)}_{g(\theta^{(k+1)}|\mathbf{x}, \theta^{(k)}) - g(\theta^{(k)}|\mathbf{x}, \theta^{(k)})} \\ & \quad - E \Bigl( \log p( \mathbf{z}| \mathbf{x},\theta^{(k+1)}) - \log p(\mathbf{z}| \mathbf{x}, \theta^{(k)}) \,\Big|\, \mathbf{x}, \theta^{(k)} \Bigr). \end{align*}\]
The first term is nonnegative because \(\theta^{(k+1)}\) maximizes \(g(\cdot|\mathbf{x}, \theta^{(k)})\) in the M-step.
The second term is \[ E \Biggl( \log \frac{ p( \mathbf{z}| \mathbf{x},\theta^{(k+1)})}{ p(\mathbf{z}| \mathbf{x}, \theta^{(k)} )} \Bigl |\; \mathbf{x}, \theta^{(k)} \Biggr). \] Since \(\log\) is concave, Jensen’s inequality gives \[\begin{align*} & E \Biggl( \log \frac{ p( \mathbf{z}| \; \mathbf{x},\theta^{(k+1)})}{ p(\mathbf{z}| \mathbf{x}, \theta^{(k)} ) } \Bigl | \;\mathbf{x}, \theta^{(k)} \Biggr) \\ &\leq \log E \Biggl(\frac{ p( \mathbf{z}| \; \mathbf{x},\theta^{(k+1)})}{ p(\mathbf{z}| \mathbf{x}, \theta^{(k)}) } \Bigl |\; \mathbf{x}, \theta^{(k)} \Biggr) \\ &= \log \int \frac{ p( \mathbf{z}|\; \mathbf{x},\theta^{(k+1)})}{ p(\mathbf{z}| \mathbf{x}, \theta^{(k)}) } p(\mathbf{z}| \mathbf{x}, \theta^{(k)}) d\mathbf{z}\\ &= \log(1) = 0. \end{align*}\] (The same quantity is \(-D_{\mathrm{KL}}\bigl(p(\mathbf{z}|\mathbf{x},\theta^{(k)}) \,\|\, p(\mathbf{z}|\mathbf{x},\theta^{(k+1)})\bigr) \leq 0\).)
Hence the difference of observed-data log-likelihoods is a nonnegative term minus a nonpositive term, and we have the ascend property \[\ell(\theta^{(k+1)}|\mathbf{x}) - \ell(\theta^{(k)}|\mathbf{x}) \geq 0.\]