RI Homepage Carnegie Mellon Homepage RI Homepage

The Robotics Institute

Carnegie Mellon Robotics Institute

Fast State Discovery for HMM Model Selection and Learning

Sajid Siddiqi, Geoffrey Gordon, and Andrew Moore
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AI-STATS), 2007.


Download
  • Adobe portable document format (pdf) (221KB)
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
Choosing the number of hidden states and their topology (model selection) and estimating model parameters (learning) are important problems for Hidden Markov Models. This paper presents a new state-splitting algorithm that addresses both these problems. The algorithm models more information about the dynamic context of a state during a split, enabling it to discover underlying states more effectively. Compared to previous top-down methods, the algorithm also touches a smaller fraction of the data per split, leading to faster model search and selection. Because of its efficiency and ability to avoid local minima, the state-splitting approach is a good way to learn HMMs even if the desired number of states is known beforehand. We compare our approach to previous work on synthetic data as well as several real-world data sets from the literature, revealing significant improvements in efficiency and test-set likelihoods. We also compare to previous algorithms on a sign-language recognition task, with positive results.

Notes

Text Reference
Sajid Siddiqi, Geoffrey Gordon, and Andrew Moore, "Fast State Discovery for HMM Model Selection and Learning," Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AI-STATS), 2007.

BibTeX Reference
@inproceedings{Siddiqi_2007_5687,
   author = "Sajid Siddiqi and Geoffrey Gordon and Andrew Moore",
   title = "Fast State Discovery for HMM Model Selection and Learning",
   booktitle = "Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AI-STATS)",
   year = "2007",
}

The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.
Contact Us | Update Instructions