Implicit inequality constraints in a binary tree model. (English) Zbl 1274.62355

Summary: In this paper we investigate the geometry of a discrete Bayesian network whose graph is a tree all of whose variables are binary and the only observed variables are those labeling its leaves. We provide the full geometric description of these models which is given by a set of polynomial equations together with a set of complementary implied inequalities induced by the positivity of probabilities on hidden variables. The phylogenetic invariants given by the equations can be useful in the construction of simple diagnostic tests. However, in this paper we point out the importance of also incorporating the associated inequalities into any statistical analysis. The full characterization of these inequality constraints derived in this paper helps us determine how and why routine statistical methods can break down for this model class.


62H05 Characterization and structure theory for multivariate probability distributions; copulas
62E15 Exact distribution theory in statistics
62F15 Bayesian inference
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
Full Text: DOI arXiv Euclid


[1] Allman, E. S. and Rhodes, J. A. (2007). Phylogenetic invariants. In, Reconstructing evolution 108-146. Oxford Univ. Press, Oxford.
[2] Allman, E. S. and Rhodes, J. A. (2008). Phylogenetic ideals and varieties for the general Markov model., Adv. in Appl. Math. 40 127-148. · Zbl 1131.92046 · doi:10.1016/j.aam.2006.10.002
[3] Auvray, V., Geurts, P. and Wehenkel, L. (2006). A Semi-Algebraic Description of Discrete Naive Bayes Models with Two Hidden Classes. In, Proc. Ninth International Symposium on Artificial Intelligence and Mathematics .
[4] Beerenwinkel, N., Eriksson, N. and Sturmfels, B. (2007). Conjunctive Bayesian networks., Bernoulli 13 893-909. · Zbl 1129.62100 · doi:10.3150/07-BEJ6133
[5] Bochnak, J., Coste, M. and Roy, M.-F. (1998)., Real Algebraic Geometry . Springer. · Zbl 0912.14023
[6] Buneman, P. (1974). A note on the metric properties of trees., J. Combinatorial Theory Ser. B 17 48-50. · Zbl 0286.05102 · doi:10.1016/0095-8956(74)90047-1
[7] Casanellas, M. and Fernández-Sánchez, J. (2007). Performance of a New Invariants Method on Homogeneous and Nonhomogeneous Quartet Trees., Molecular Biology and Evolution 24 288.
[8] Cavender, J. A. (1997). Letter to the editor., Molecular Phylogenetics and Evolution 8 443-444.
[9] Cavender, J. A. and Felsenstein, J. (1987). Invariants of phylogenies in a simple case with discrete states., Journal of Classification 4 57-71. · Zbl 0612.62142 · doi:10.1007/BF01890075
[10] Chang, J. T. (1996). Full reconstruction of Markov models on evolutionary trees: Identifiability and consistency., Mathematical Biosciences 137 51-73. · Zbl 1059.92504 · doi:10.1016/S0025-5564(96)00075-2
[11] Chernoff, H. (1954). On the distribution of the likelihood ratio., The Annals of Mathematical Statistics 25 573-578. · Zbl 0056.37102 · doi:10.1214/aoms/1177728725
[12] Chor, B., Hendy, M. D., Holland, B. R. and Penny, D. (2000). Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach., Molecular Biology and Evolution 17 1529-1541.
[13] Davis-Stober, C. P. (2009). Analysis of multinomial models under inequality constraints: Applications to measurement theory., Journal of Mathematical Psychology 53 1-13. · Zbl 1176.91140 · doi:10.1016/j.jmp.2008.08.003
[14] Drton, M. and Richardson, T. S. (2008). Binary models for marginal independence., Journal of the Royal Statistical Society: Series B (Statistical Methodology) 70 287-309. · Zbl 1148.62043 · doi:10.1111/j.1467-9868.2007.00636.x
[15] Drton, M. and Sullivant, S. (2007). Algebraic Statistical Models., Statistica Sinica 17 1273-1297. · Zbl 1132.62003
[16] Eriksson, N. (2007)., Using invariants for phylogenetic tree construction . The IMA Volumes in Mathematics and its Applications 149 89-108. Springer. · Zbl 1158.92033 · doi:10.1007/978-0-387-09686-5_4
[17] Eriksson, N., Ranestad, K., Sturmfels, B. and Sullivant, S. (2005). Phylogenetic algebraic geometry. In, Projective varieties with unexpected properties 237-255. Walter de Gruyter GmbH & Co. KG, Berlin. · Zbl 1106.14050
[18] Garcia, L. D., Stillman, M. and Sturmfels, B. (2005). Algebraic geometry of Bayesian networks., J. Symbolic Comput 39 331-355. · Zbl 1126.68102 · doi:10.1016/j.jsc.2004.11.007
[19] Gelfand, I. M., Kapranov, M. M. and Zelevinsky, A. V. (1994)., Discriminants, Resultants, and Multidimensional Determinants . Birkhäuser. · Zbl 0827.14036
[20] Gilula, Z. (1979). Singular value decomposition of probability matrices: Probabilistic aspects of latent dichotomous variables., Biometrika 66 339-344. · Zbl 0411.62003 · doi:10.1093/biomet/66.2.339
[21] Lake, J. A. (1987). A rate-independent technique for analysis of nucleic acid sequences: evolutionary parsimony., Molecular Biology and Evolution 4 167.
[22] Lauritzen, S. L. (1996)., Graphical models . Oxford Statistical Science Series 17 . The Clarendon Press Oxford University Press, New York. Oxford Science Publications. · Zbl 0907.62001
[23] Lazarsfeld, P. F. and Henry, N. W. (1968)., Latent structure analysis . Houghton, Mifflin, New York. · Zbl 0182.52201
[24] Matsen, F. A. (2009). Fourier Transform Inequalities for Phylogenetic Trees., Computational Biology and Bioinformatics, IEEE/ACM Transactions on 6 89-95.
[25] McCullagh, P. (1987)., Tensor methods in statistics . Monographs on Statistics and Applied Probability . Chapman & Hall, London. · Zbl 0732.62003
[26] Pearl, J. (1986). Fusion, propagation, and structuring in belief networks* 1., Artificial intelligence 29 241-288. · Zbl 0624.68081 · doi:10.1016/0004-3702(86)90072-X
[27] Pearl, J. and Tarsi, M. (1986). Structuring causal trees., J. Complexity 2 60-77. Complexity of approximately solved problems (Morningside Heights, N.Y., 1985). · Zbl 0589.68060 · doi:10.1016/0885-064X(86)90023-3
[28] Rusakov, D. and Geiger, D. (2005). Asymptotic model selection for naive Bayesian networks., J. Mach. Learn. Res. 6 1-35 (electronic). · Zbl 1222.68294
[29] Semple, C. and Steel, M. (2003)., Phylogenetics . Oxford Lecture Series in Mathematics and its Applications 24 . Oxford University Press, Oxford. · Zbl 1043.92026
[30] Settimi, R. and Smith, J. Q. (1998). On the Geometry of Bayesian Graphical Models with Hidden Variables. In, UAI ( G. F. Cooper and S. Moral, eds.) 472-479. Morgan Kaufmann.
[31] Settimi, R. and Smith, J. Q. (2000). Geometry, moments and conditional independence trees with hidden variables., Ann. Statist. 28 1179-1205. · Zbl 1105.62321 · doi:10.1214/aos/1015956712
[32] Smith, J. and Daneshkhah, A. (2010). On the robustness of Bayesian networks to learning from non-conjugate sampling., International Journal of Approximate Reasoning 51 558-572. · Zbl 1205.68317 · doi:10.1016/j.ijar.2010.01.013
[33] Smith, J. Q. and Rigat, F. (2008). Isoseparation and Robustness in Finitre Parameter Bayesian Inference., CRiSM Res Rep 07-22.
[34] Spirtes, P., Richardson, T. and Meek, C. Heuristic greedy search algorithms for latent variable models In, Proceedings of AI & STAT’97 481-488. Citeseer.
[35] Stanley, R. P. (2002)., Enumerative combinatorics. Volume I . Cambridge Studies in Advanced Mathematics 49. Cambridge University Press.
[36] Steel, M. and Faller, B. (2009). Markovian log-supermodularity, and its applications in phylogenetics., Applied Mathematics Letters . · Zbl 1179.92046 · doi:10.1016/j.aml.2008.10.005
[37] Sturmfels, B. and Sullivant, S. (2005). Toric Ideals of Phylogenetic Invariants., Journal of Computational Biology 12 204-228. · Zbl 1391.13058
[38] Zwiernik, P. An asymptotic approximation of the marginal likelihood for general Markov models. arXiv :1012.0753., submitted. · Zbl 1280.68225
[39] Zwiernik, P. (2010). L-cumulants, L-cumulant embeddings and algebraic statistics., · Zbl 1351.62069
[40] Zwiernik, P. and Smith, J. Q. (2010). Tree-cumulants and the geometry of binary tree models., to appear in Bernoulli . · Zbl 1235.62004 · doi:10.3150/10-BEJ338
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.