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.