Graphics enhanced version of this site

Fast Inference and Learning in Large-State-Space HMMs
S. Siddiqi and A. Moore
Proceedings of the 22nd International Conference on Machine Learning (ICML), August, 2005.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [233 KB]
Compressed postscript (ps.gz) [196 KB]

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.

For Hidden Markov Models (HMMs) with fully connected transition models, the three fundamental problems of evaluating the likelihood of an observation sequence, estimating an optimal state sequence for the observations, and learning the model parameters, all have quadratic time complexity in the number of states. We introduce a novel class of non-sparse Markov transition matrices called Dense-Mostly-Constant (DMC) transition matrices that allow us to derive new algorithms for solving the basic HMM problems in sub-quadratic time. We describe the DMC HMM model and algorithms and attempt to convey some intuition for their usage. Empirical results for these algorithms show dramatic speedups for all three problems. In terms of accuracy, the DMC model yields strong results and outperforms the baseline algorithms even in domains known to violate the DMC assumption.

Number of pages: 8

S. Siddiqi and A. Moore, "Fast Inference and Learning in Large-State-Space HMMs," Proceedings of the 22nd International Conference on Machine Learning (ICML), August, 2005.

@inproceedings{Siddiqi_2005_5098,
   author = "Sajid Siddiqi and Andrew Moore",
   title = "Fast Inference and Learning in Large-State-Space HMMs",
   booktitle = "Proceedings of the 22nd International Conference on Machine Learning (ICML)",
   month = "August",
   year = "2005"
}