The connection between the expectation in expectation maximization and the importance sampling?

Question

The log-likelihood of the EM algorithm can be expressed as

\begin{align} \ell(\theta, x) &= \log p(x|\theta) \\ &= \log \sum_z p(x, z|\theta) \\ &= \log \sum_z \frac{q(z|x)}{q(z|x)}p(x,z|\theta)\\ &= \log \sum_z q(z|x)\frac{p(x,z|\theta)}{q(z|x)}\\ &\ge \sum_z q(z|x)\log\frac{p(x,z|\theta)}{q(z|x)} \end{align}

It seems that the third equality is very like the importance sampling, and $q(z|x)$ is like the proposal distribution and the $\frac{p(x,z|\theta)}{q(z|x)}$ is like the sampling ratio or sampling weight. Since the $q(z|x)$ is known after the expectation step can we utilize the MCMC to do the maximization? I know expectation maximization is simpler and computing cheaper than importance sampling, but I wonder if they have a connection in that way?

Answer 1

While the EM algorithm does not involve arbitrary importance distributions, in that $q(z|x)$ is usually defined as $p(z|x,\theta^{(t)})$, if $\theta^{(t)}$ denotes the value of the parameter at the $t$-th step of the algorithm, it happens that, as detailed in the Wikipedia page on the EM algorithm, [where I copied the description and HTML code,] following Neal and Hinton (1999), the algorithm can be described as two successive maximization steps. Defining $$F(q,\theta) = \mathbb{E}_q [ \log L (\theta ; x,Z) ] + H(q),$$ where $q$ is an arbitrary probability density and $H(q)$ its entropy, the E-step can be reformulated as solving $$ q^{(t)} = \arg\max_q \ F(q,\theta^{(t)})$$ The M-step is then the symmetric resolution of $$\theta^{(t+1)} = \arg\max_\theta \ F(q^{(t)},\theta)$$

Concerning importance sampling, this generic method is used for the approximation of expectations, while EM is based on exact conditional $\mathbb{E}_{\theta_0}[\log p(x,Z|\theta)|X]$. The above decomposition is thus unrelated with importance sampling.

However, importance sampling can be used to approximate the E step of the EM algorithm as in MCEM and MCMCEM versions.