Fast Inference and Learning in Large-State-Space HMMs

Sajid Siddiqi and Andrew Moore
Proceedings of the 22nd International Conference on Machine Learning (ICML), August, 2005.


Download
  • Adobe portable document format (pdf) (233KB)
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
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.

Notes
Number of pages: 8

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

BibTeX Reference
@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",
}