I describe a new Markov chain method for
sampling from the distribution of the state sequences in a non-linear
state space model, given the observation sequence. This method
updates all states in the sequence simultaneously using an embedded
Hidden Markov model (HMM). An update begins with the creation of a
``pool'' of *K* states at each time, by applying some Markov chain
update to the current state. These pools define an embedded HMM whose
states are indexes within this pool. Using the forward-backward
dynamic programming algorithm, we can then efficiently choose a state
sequence at random with the appropriate probabilities from the
exponentially large number of state sequences that pass through states
in these pools. I show empirically that when states at nearby times
are strongly dependent, embedded HMM sampling can perform better than
Metropolis methods that update one state at a time.

Technical Report No. 0304, Dept. of Statistics, University of Toronto (April 2003), 9 pages: postscript, pdf.

Also available from arXiv.org.

Neal, R. M., Beal, M. J., and Roweis, S. T. (2004) ``Inferring state sequences for non-linear systems with embedded hidden Markov models'', in S. Thrun, et al (editors),Advances in Neural Information Processing Systems 16(aka NIPS*2003), MIT Press, 8 pages: abstract, postscript, pdf.