> Hi,
>
> Can anybody point me to some references for learning the structure of
> Markov chains and Hidden Markov Models from data?
>
> Also of interest would be some standard references discussing metrics or
> scoring functions for HMMs.
>
> Thanks,
> Denver.
> --
> http://www.sis.pitt.edu/~ddash
The following references describe a technique for learning the
structure of HMM's that works much better than simply applying EM to a
totally connected structure and looking for non-zero probability
transitions. The idea is to start with the maximum likelihood HMM for
a given set of data. This has a node for each symbol of each training
string and essentially looks like the collection of training strings
themselves running in parallel from the start state to the final
state. The algorithm then successively merges states together, always
greedily picking the pair to merge which maximizes the increase in the
Bayesian posterior probability. The merging stops when no merge can
increase the posterior further. In practice, we found that it robustly
finds the structure of many HMM's from very small amounts of data. A
similar approach can also be applied to learning the structure of more
complex stochastic grammars (such as stochastic context-free grammars).
Andreas Stolcke and Stephen M. Omohundro, "Hidden Markov Model
Induction by Bayesian Model Merging", in Advances in Neural
Information Processing Systems 5, ed. Steve J. Hanson and Jack D.
Cowan, J. D. and C. Lee Giles, Morgan Kaufmann Publishers, Inc., San
Mateo, California, 1993, pp. 11-18.
Andreas Stolcke and Stephen M. Omohundro, "Inducing Probabilistic
Grammars by Bayesian Model Merging", Proceedings of the International
Colloquium on Grammatical Inference, Alicante, Spain, Lecture Notes in
Artificial Intelligence 862, Springer-Verlag, Berlin, September 1994,
p. 106-118.
Andreas Stolcke and Stephen M. Omohundro, "Best-first Model Merging
for Hidden Markov Model Induction", ICSI Technical Report TR-94-003,
January 1994.
-- Steve
Stephen M. Omohundro om3@att.net
252 Hawthorne Avenue http://home.att.net/~om3/
Palo Alto CA, 94301-1110 650-328-7605
This archive was generated by hypermail 2b29 : Wed Jun 13 2001 - 15:20:10 PDT