Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Processes

Sebastian Thrun, John Langford, and Dieter Fox
Proc. of the 16th International Conference on Machine Learning (ICML'99), 1999.


Download
  • Adobe portable document format (pdf) (159KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We present a learning algorithm for non-parametric hidden Markov models with continuous state and observation spaces. All necessary probability densities are approximated using samples, along with density trees generated from such samples. A Monte Carlo version of Baum-Welch (EM) is employed to learn models from data. Regularization during learning is achieved 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. Once trained, Monte Carlo HMMs can be run in an any-time fashion. We prove that under mild assumptions, Monte Carlo Hidden Markov Models converge to a local maximum in likelihood space, just like conventional HMMs. In addition, we provide empirical results obtained in a gesture recognition domain.

Notes

Text Reference
Sebastian Thrun, John Langford, and Dieter Fox, "Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Processes," Proc. of the 16th International Conference on Machine Learning (ICML'99), 1999.

BibTeX Reference
@inproceedings{Thrun_1999_2666,
   author = "Sebastian Thrun and John Langford and Dieter Fox",
   title = "Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Processes",
   booktitle = "Proc. of the 16th International Conference on Machine Learning (ICML'99)",
   year = "1999",
}