We describe a Markov chain method for sampling from the distribution of the hidden state sequence in a non-linear dynamical system, given a sequence of observations. This method updates all states in the sequence simultaneously using an embedded Hidden Markov Model (HMM). An update begins with the creation of ``pools'' of candidate states at each time. We then define an embedded HMM whose states are indexes within these pools. Using a forward-backward dynamic programming algorithm, we can efficiently choose a state sequence with the appropriate probabilities from the exponentially large number of state sequences that pass through states in these pools. We illustrate the method in a simple one-dimensional example, and in an example showing how an embedded HMM can be used to in effect discretize the state space without any discretization error. We also compare the embedded HMM to a particle smoother on a more substantial problem of inferring human motion from 2D traces of markers.
In S. Thrun, et al (editors), Advances in Neural Information Processing Systems 16 (aka NIPS*2003), MIT Press, 8 pages: postscript, pdf.
Also available via the NIPS siteAssociated reference: For earlier work on the embedded HMM, see the following Technical Report:
Neal, R. M. (2003) ``Markov chain sampling for non-linear state space models using embedded hidden Markov models'', Technical Report No. 0304, Dept. of Statistics, University of Toronto, 9 pages: abstract, postscript, pdf.