A computational algebraic-geometry method for conditional-independence inference

Abstract

We consider the problems of semi-graphoid inference and of independence implication from a set of conditional-independence statements. Based on ideas from R. Hemmecke et al. [Combin. Probab. Comput., 2008, 17: 239–257], we present algebraic-geometry characterizations of these two problems, and propose two corresponding algorithms. These algorithms can be realized with any computer algebra system when the number of variables is small.

Keywords

Conditional independence / independence implication / radical membership / semi-graphoid inference / structural imset

References

[1] 4ti2 team: 4ti2—A software package for algebraic, geometric and combinatorial problems on linear spaces. www.4ti2.de.

[2] Baioletti M, Busanello G, Vantaggi B. Conditional independence structure and its closure: Inference rules and algorithms. Int J Approx Reason, 2009, 50: 1097-1114

[3] Bouckaert R R, Hemmecke R, Lindner S, Studený M. Efficient algorithms for conditional independence inference. J Mach Learn Res, 2010, 11: 3453-3479

[4] Bouckaert R R, Studený M. Racing algorithms for conditional independence inference. Int J Approx Reason, 2007, 45: 386-401

[5] Bruns W, Hemmecke R, Ichim B, Köppe M, Söger C C. Challenging computations of Hilbert bases of cones associated with algebraic statistics. Experiment Math, 2011, 20: 25-33

[6] Chickering D M. Optimal structure identification with greedy search. J Mach Learn Res, 2002, 3: 507-554

[7] Cowell R G, Dawid A P, Lauritzen S L, Spiegelhalter D G. Probabilistic Network and Expert System, 1999, New York: Springer-Verlag

[8] Cox D, Little J, O’Shea D. Ideals, Varieties, and Algorithms, 2007 3rd ed New York: Springer

[9] Cox D R, Wermuth N. Multivariate Dependencies: Models Analysis and Interpretation, 1993, London: Chapman & Hall

[10] Dawid A P. Conditional independence in statistical theory. J Roy Statist Soc Ser B, 1979, 41: 1-31

[11] Dawid A P. Separoids: a mathematical framework for conditional independence and irrelevance. Ann Math Artif Intell, 2001, 32: 335-372

[12] Decker W, Greuel G M, Pfister G, Schönemann H. Singular 3-1-1-A computer algebra system for polynomial computations, 2011

[13] Drton M, Sturmdels B, Sullivant S. Lectures on Algebraic Statistics. Oberwolfach Seminars, Vol 39, 2009, Berlin: Springer

[14] Edwards D. Introduction to Graphical Modelling, 2000 2nd ed Berlin: Springer-Verlag

[15] Hemmecke R, Morton J, Shiu A, Sturmfels B, Wienand O. Three counterexamples on semigraphoids. Combin Probab Comput, 2008, 17: 239-257

[16] Lauritzen S L. Graphical Models, 1996, Oxford: Clarendon Press

[17] Matúš F. Conditional independences among four random variables III: Final conclusion. Combin Probab Comput, 1999, 8: 269-276

[18] Matúš F. Lengths of semigraphoid inferences. Ann Math Artif Intell, 2002, 35: 287-294

[19] Matúš F. Towards classification of semi-graphoids. Discrete Math, 2004, 277: 115-145

[20] Matúš F. Kern-Isberner G, Rodder W, Kulmann F. Conditional independences in Gaussian vectors and rings of polynomials. Proceedings of WCII 2002, 2005, Berlin, Heidelberg: Springer-Verlag 152 161

[21] Neapolitan R E. Learning Bayesian Networks, 2004, Upper Saddle River: Pearson Prentice Hall

[22] Niepert M. Logical inference algorithms and matrix representations for probabilistic conditional independence. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, 2009, 2009 428 435

[23] Niepert M, Gucht D V, Gyssens M. On the conditional independence implication problem: a lattice-theoretic approach. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, 2008, 2008 435 443

[24] Pearl J. Probabilistic Reasoning in Intelligent Systems, 1988, Burlington: Morgan Kaufmann

[25] Shenoy P P. Conditional independence in valuation-based systems. Int J Approx Reason, 1994, 10: 203-234

[26] Studený M. Kubik S, Visek J A. Conditional independence relations have no finite complete characterization. Information Theory, Statistical Decision Functions and Random Processes, Vol B, 1992, Dordrecht: Kluwer 377 396

[27] Studený M. Semigraphoids and structures of probabilistic conditional independence. Ann Math Artif Intell, 1997, 21: 71-98

[28] Studený M. Complexity of structural models. Proceedings of the Prague Stochastics’ 98, Prague, 1998 521 528

[29] Studený M. Probabilistic Conditional Independence Structures, 2005, Berlin: Springer-Verlag

[30] Studený M, Bouckaert R R, Kocka T. Extreme Supermodular Set Functions Over Five Variables, 2000, Prague: Institute of Information Theory and Automation

[31] Verma T, Pearl J. Shachter R D, Lewitt T S, Kanal L N, Lemmer J F. Causal networks, semantics and expressiveness. Uncertainty in Artificial Intelligence, 4, 1990, Amsterdam: North-Holland 69 76

[32] Whittaker J. Graphical Models in Applied Multivariate Statistics, 1990, New York: Wiley