1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Updated the inequality, sorry for the error. $\endgroup$ – Lerner Zhang May 11 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.