Supervised hidden Markov model learning using the state distribution oracle

Hidden Markov models (HMMs) are probabilistic models with applications across a large number of fields, most prominently Speech Recognition and Computational Biology. In this paper, we propose a polynomial-time algorithm for learning the parameters of a first order HMM by using a state distribution probability (SD) oracle. The SD oracle provides the learning algorithm with the state distribution corresponding to a query string in the target model. The SD oracle is necessary for efficient learning in the sense that the consistency problem for HMMs, where a training set of state distribution vectors such as those supplied by the SD oracle is used but without the ability to query on specific strings, is NP-complete. The algorithm proposed here is an extension to an algorithm described by Tzeng for learning probabilistic automata (PA) using the SD oracle.