4
$\begingroup$

Recently I've been working EM algorithms for MAP estimation in a problem where the expectation is intractable, but the maximization is easy. Further, draws from the distribution in the E-step are easily available through MCMC, so I've been experimenting with stochastic versions of EM. Let $X$ be the observed data, $Z$ be the missing data, and $\Theta$ be the parameters to be estimated. I'll use $\Theta_t$ for the current estimate of $\Theta$. Specifically I've looked at stochastic approximation EM and Monte Carlo EM, which estimate the E step like so:

1) MCEM: The $Q$ function is approximated with an average of $m_t$ MC draws $\hat Q(\Theta; \Theta_t) = \frac{1}{m_t}\sum_{i=1}^{m_t}\log(p(X,Z_i|\Theta)$ where $Z_i$ is drawn from $p(Z|X,\Theta_t)$

2) SAEM: $\hat Q(\Theta; \Theta_t) = \gamma_t \hat Q(\Theta; \Theta_{t_1}) + (1-\gamma_t)\frac{1}{m_t}\sum_{i=1}^{m_t}\log(p(X,Z_i|\Theta)$. In the context of exponential families, this amounts to using a weighted average of the "new" and "old" sufficient statistics at each step, compared to MCEM which takes a completely new average (ie $\gamma_t=0$)

Both have the same M step, with $\Theta_{t+1}$ chosen to maximize the approximate $Q$ function. My question is when does it make sense to average over the sequence of $\Theta_t$'s? Presumably this would further reduce the Monte Carlo error, and my understanding is that the convergence is (theoretically) unaffected since the $\Theta_t$'s are converging to a stationary point with appropriate conditions on $m_t$ and $\gamma_t$.

What I'm looking for is more practical advice, since averaging too early will bias the (finite sample) estimates and averaging too late is wasteful. Also the related question of assessing convergence; if we consider convergence criteria like $|\Theta_t - \Theta_{t-1}| \leq \epsilon$ should the difference be taken instead between the two averaged estimates? (Not the best criterion, I know, but super easy :) )

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.