You are here

Binary hidden Markov models and varieties

Journal Name:

Publication Year:

Abstract (Original Language): 
This paper closely examines HMMs in which all the hidden random variables are binary. Its main contributions are (1) a birational parametrization for every such HMM, with an explicit inverse for recovering the hidden parameters in terms of observables, (2) a semialgebraic model membership test for every such HMM, and (3) minimal de ning equations for the 4-node fully binary model, comprising 21 quadrics and 29 cubics, which were computed using Grobner bases in the cumulant coordinates of Sturmfels and Zwiernik. The new model parameters in (1) are rationally identi able in the sense of Sullivant, Garcia-Puente, and Spielvogel, and each model's Zariski closure is therefore a rational projective variety of dimension 5. Grobner basis computations for the model and its graph are found to be considerably faster using these parameters. In the case of two hidden states, item (2) supersedes a previous algorithm of Schonhuth which is only generically de ned, and the de ning equations (3) yield new invariants for HMMs of all lengths  4. Such invariants have been used successfully in model selection problems in phylogenetics, and one can hope for similar applications in the case of HMMs.
1
30

REFERENCES

References: 

[1] J. Baker. The DRAGON system { An overview. Acoustics, Speech and Signal Pro-
cessing, IEEE Transactions on, 23(1):24 { 29, Feb 1975.
[2] Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W.
Wampler. Bertini: Software for numerical algebraic geometry. Available at
http://www.nd.edu/sommese/bertini.
[3] Daniel J. Bates, Jonathan D. Hauenstein, Chris Peterson, and Andrew J. Sommese.
Numerical decomposition of the rank-deciency set of a matrix of multivariate polyno-
mials, pages 55{77. Texts and Monographs in Symbolic Computation. Spinger-Verlag,
2010.
[4] L.E. Baum and T. Petrie. Statistical inference for probabilistic functions of nite
state Markov chains. Ann. Math. Stat., 37:1554{1563, 1966.
[5] Nicholas Bray and Jason Morton. Equations dening hidden Markov models. In Al-
gebraic Statistics for Computational Biology, chapter 11. Cambridge Univerisy Press,
2005.
[6] M. Casanellas and J. Fernandez-Sanchez. Performance of a new invariants method on
homogeneous and non-homogeneous quartet trees. Molecular Biology and Evolution,
24:288{293, 2006.
[7] David A. Cox, John B. Little, and Don O'Shea. Ideals, Varieties, and Algorithms,
Third Edition. Springer New York, 2007.
[8] Vesselin Drensky. Computing with matrix invariants. Math. Balkanica, 21:141{172,
2007.
[9] Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on algebraic statistics.
Oberwolfach Seminars 39, 2009.
[10] Nicholas Eriksson. Using invariants for phylogenetic tree construction. In Emerging
Applications of Algebraic Geometry. I.M.A. Volumes in Mathematics and its Applications,
2008.
[11] Daniel R. Grayson and Michael E. Stillman. Macaulay2, a software system for research
in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.
[12] Alexandre Grothendieck and Jean Dieudonne. Elements de geometrie algebrique
(rediges avec la collaboration de Jean Dieudonne) IV. Etude locale des schemas et
des morphismes de schemas, Troisieme partie. Publications Mathmatiques de l'IHES,
1966.
[13] Anders Krogh, I. Saira Mian, and David Haussler. A Hidden Markov Model that
nds genes in E. coli DNA. Nucleic Acids Research, pages 4768{4778, 1994.
[14] Nicolette Meshkat, Marisa Eisenberg, and Joseph J. DiStefano. An algorithm for
nding globally identiable parameter combinations of nonlinear ode models using
Grobner bases. Mathematical Biosciences, 222(2):61 { 72, 2009.
[15] Lior Pachter and Bernd Sturmfels. Algebraic Statistics for Computational Biology.
Cambridge Univerisy Press, 2005.
[16] Giovanni Pistone, Eva Riccomagno, and Henry P. Wynn. Computational commutative
algebra in discrete statistics. Chapman and Hall / CRC, 2001.
[17] Alexander Schonhuth. Generic identication of binary-valued hidden Markov processes.
arXiv:1101.3712, 2011.
[18] K.S. Sibirskii. Algebraic invariants for a set of matrices. Siberian Mathematical
Journal, 9:115{124, 1968. ISSN 0037-4466.
[19] Jim Q. Smith and Piotr Zwiernik. Tree cumulants and the geometry of binary tree
models, 2010. arXiv:1004.4360v3.
[20] Ruslan L. Stratonovich. Conditional Markov Processes. Theory of Probability and its
Applications, pages 156{178, 1960.
[21] Bernd Sturmfels and Piotr Zwiernik. Binary cumulant varieties, 2011.
arXiv:1103.0153.
[22] Seth Sullivant, Luis David Garcia-Puente, and Sarah Spielvogel. Identifying causal
eects with computer algebra. Proceedings of the 26th Conference of Uncertainty in
Articial Intelligence, 2010.

Thank you for copying data from http://www.arastirmax.com