Monte Carlo Hidden Markov Models

Sebastian Thrun and John Langford

We present a learning algorithm for hidden Markov models with continuous state and observation spaces. All necessary probability density functions are approximated using samples, along with likelihood trees generated from such samples. Our representation is proven to be asymptotically consistent with the ``true'' density. A Monte Carlo version of Baum-Welch (EM) is employed to learn models from data, just as in regular HMM learning. Regularization during learning is obtained using an exponential shrinking technique. The shrinkage factor, which determines the effective capacity of the learning algorithm, is annealed down over multiple iterations of Baum-Welch, and early stopping is applied to select the right model. Empirical results are provided in a gesture recognition domain which illustrates the robustness of the approach. After training, our approach can be used in an any-time fashion that trades off computation time and accuracy.

Click here to obtain the full paper (235,893 bytes, 35 pages).

@INPROCEEDINGS{Thrun99j,
  AUTHOR         = {Thrun, S.},
  TITLE          = {Monte Carlo Hidden Markov Models},
  YEAR           = {1999},
  BOOKTITLE      = {Proceedings of the Snowbird Workshop "Machines That 
                    Learn"},
  ORGANIZATION   = {NIPS Foundation},
  ADDRESS        = {Snowbird, UT},
  NOTE           = {Extended abstract}
}