Computer Science Department
School of Computer Science, Carnegie Mellon University


Monte Carlo Hidden Markov Models

Sebastian Thrun, John Langford

December 1998

Keywords: Annealing, any-time algorithms, Baum-Welch, density trees, early stopping, EM, hidden Markov models, machine learning, maximum likelihood estimation, Monte Carlo methods, temporal signal processing

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 an 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. 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, which illustrate the appropriateness of the approach in practice.

35 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by