The Nested EM Algorithm
Statistica Sinica
David A. van Dyk
Department of Statistics, Harvard University, Cambridge, MA
02138, U.S.A.
Computing posterior modes (e.g.,
maximum likelihood estimates) for
models involving latent variables (e.g.,
missing data) often involves
complicated optimization procedures.
By splitting this task into two simpler parts, however,
(i.e., expectation over the latent variables, and maximization
over the model parameters given the ``complete data'')
EM-type algorithms can
often accomplish this optimization in a simple manner. Although this
approach has often proven useful, in some settings even these
simpler tasks are computationally challenging.
Significant progress has been made towards further
simplifying calculations involving
the model parameters (e.g., replacing the maximization
step with a sequence of conditional maximization steps as in the ECM and
AECM algorithms) but computations involving the latent variables are
typically more difficult
to simplify. Thus, in models with complicated latent variable structures
(e.g., hierarchical models) computationally intensive methods are
often required for the expectation step of EM (e.g., Monte-Carlo EM,
or even nested Gibbs samplers). This paper describes how nesting
two (or more) EM algorithms can take advantage of closed form conditional
expectations and
leads to algorithms which tends to be faster to converge
(cutting computational time in half in two examples),
are straight forward to implement, and enjoy stable convergence
(e.g., monotone convergence in likelihood or posterior). Methodology
to monitor convergence of nested EM algorithms which is also useful
for validation of both (nested) EM algorithms and the corresponding
Gibbs samplers
is developed using importance and bridge sampling.
The strategy is applied to both hierarchical probit and t regression models
to derive algorithms which incorporate aspects of Monte-Carlo EM,
PX-EM (i.e., parameter expansion), and nesting in order to combine
computational efficiency with easy implementation.
Keywords: Bridge Sampling,
Efficient Data Augmentation,
Gibbs Sampler, GLMM, Importance Sampling, Hierarchical Models,
MCEM Algorithm, MCMC, Probit Models, t-Models, Working Parameters
Return to David van Dyk's homepage.