2
$\begingroup$

So the general set-up for the EM algorithm is the following recursion \begin{align} \theta^{(t+1)}&=\text{argmax}_\theta\sum_zp(z\;|\;x,\theta^{(t)})\log\frac{p(x,z\;|\;\theta)}{p(z\;|\;x,\theta^{(t)})}\\ &=\text{H}(Z\;|\;X,\theta^{(t)}) + \frac{1}{p(x\;|\;\theta^{(t)})}\text{argmax}_\theta\sum_zp(x,z\;|\;\theta^{(t)})\log p(x,z\;|\;\theta), \end{align}

where the expression increases monotonically towards a lower bound for $\log p(x\;|\;\hat{\theta})$.

However in the latter formulation, we see that our problem doesn't require us to compute $$p(x\;|\;\theta^{(t)})=\sum_zp(x,z\;|\;\theta^{(t)}).$$

So my question is, when we perform EM in order to find a point estimate of $\theta$ which approximates the marginal MLE, is it standard practice to run the algorithm on $$\theta^{(t+1)}=\text{argmax}_\theta\sum_zp(x,z\;|\;\theta^{(t)})\log p(x,z\;|\;\theta),$$ and then once it converges to a (possibly only local) maxima, then if we want an estimate for $p(z\;|\;x,\hat{\theta})$ or $p(x\;|\;\hat{\theta})$ we use $\theta^*\approx\hat{\theta}$ in order to compute it?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ @Xi'an as far as I can tell it's correct, and the algorithm I wrote based on it works. $\endgroup$
    – Set
    Mar 4, 2016 at 13:38
  • 1
    $\begingroup$ the reference I'm basing this off of is cs.cmu.edu/~awm/10701/assignments/EM.pdf, with (11) being basically the exact recursion I present. $\endgroup$
    – Set
    Mar 4, 2016 at 13:55
  • 1
    $\begingroup$ $E_{z|x,\theta^{(t)}}[\log p(x,z|\theta)]=\frac{1}{p(x\;|\;\theta^{(t)})}\sum_zp(x,z|\;\theta^{(t)})\log p(x,z\;|\;\theta)$ and then I take the argmax of this with respect to theta, so basically I combined the E and M steps into a single recursion. $\endgroup$
    – Set
    Mar 4, 2016 at 14:02
  • 1
    $\begingroup$ ya sorry I guess it's not the standard set-up, I'm just trying to dig down into the nitty-gritty so I know the best way to code it. $\endgroup$
    – Set
    Mar 4, 2016 at 14:06
  • 2
    $\begingroup$ I fear there may be some simplification in the E step which I'm missing then. As far as I understand it you have the joint $p(x,z|\theta^{(t)})$ immediately at your disposal for each iteration, but you don't have $p(z|x,\theta^{(t)})$ unless you compute $p(x|\theta^{(t)})$ for each iteration, which isn't necessary since it doesn't depend on $\theta$. So why compute it if you don't need to? $\endgroup$
    – Set
    Mar 4, 2016 at 14:15

2 Answers 2

Reset to default
2
$\begingroup$

The second decomposition of the EM objective function is quite correct and hence maximising one expression or another leads to the same update. Most often, however, the solution $\theta^{(n)}$ will appear as an expectation under the conditional distribution $p(z\;|\;x,\theta^{(t)})$. Check for instance the resolution of the Gaussian estimation problem on the Wikipedia page: all updates are conditional expectations.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ now I get it, the expectation $E_{z|x,\theta^{(t)}}[\log p(x_i,z_i|\theta)]$ reduces to $E_{z_i|x_i,\theta^{(t)}}[\log p(x_i,z_i|\theta)]$, which makes the conditional expectation tractable for large $N$. $\endgroup$
    – Set
    Mar 5, 2016 at 7:15
1
$\begingroup$

As a contribution, you might have situations where you are not receiving all the samples at once at each EM iteration.

To have a good estimate of the hyperparameters $\theta$, you would need all the samples which is not always the case in one iteration. For instance, you might perform a Stochastic Gradient Descent to update $\theta$, in which case the E step has to be update in a different manner as well.

You can find out more in Cappé and Moulines' work

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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