Learning hidden Markov models from the state distribution oracle

A Hidden Markov Model (HMM) is a probabilistic model that has been widely applied to a number of fields since its inception over 30 years ago. Computational Biology, Speech Recognition, and Image Processing are but a few of the application areas of HMMs. We propose an efficient algorithm for learning the parameters of a first order HMM from a state distribution (SD) oracle. The SD oracle provides the learner with the state distribution vector corresponding to a query string in the model. The SD oracle is shown to be necessary for polynomial-time learning in the sense that the consistency problem involving learning HMM parameters from a training set of state distribution vectors without the ability to query the SD oracle, is NP-complete. The learning algorithm proposed is based on an algorithm described by Tzeng for learning Probabilistic Automata.