Fast Inference and Learning in Large-State-Space HMMs

August 2005

Fast Inference and Learning in Large-State-Space HMMs

Authors:

Sajid Siddiqi and Andrew Moore
Conference Paper
Proceedings of (ICML) International Conference on Machine Learning

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.
@conference{Siddiqi-2005-9248,
author = {Sajid Siddiqi And Andrew Moore},
title = {Fast Inference and Learning in Large-State-Space HMMs},
booktitle = {Proceedings of (ICML) International Conference on Machine Learning},
year = {2005},
month = {August},
pages = {800 - 807},
}
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.