Stochastic Systems Group  

Professor Sam 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 nonlinear 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 forwardbackward 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 onedimensional 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.
Problems with this site should be emailed to jonesb@mit.edu