## Inferring State Sequences for Non-linear Systems
with Embedded Hidden Markov Models

**Radford M. Neal,
Matthew J. Beal,
Sam T. Roweis,
Dept. of Computer Science, University of Toronto**

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 site**Associated 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.