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.

Key words： 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. 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. New York: Springer-Verlag, 1999

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

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

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. http://www.singular.uni-kl.de, 2011

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

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

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. Oxford: Clarendon Press, 1996

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. Conditional independences in Gaussian vectors and rings of polynomials. In: Kern-Isberner G, Rodder W, Kulmann F, eds. Proceedings of WCII 2002, Lect Notes Artif Intell, 3301. Berlin, Heidelberg: Springer-Verlag, 2005, 152-161

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

22 Niepert M. Logical inference algorithms and matrix representations for probabilistic conditional independence. In: 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. In: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, 2008. 2008, 435-443

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

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

26 Studený M. Conditional independence relations have no finite complete characterization. In: Kubik S, Visek J A, eds. Information Theory, Statistical Decision Functions and Random Processes, Vol B. Dordrecht: Kluwer, 1992, 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. In: Proceedings of the Prague Stochastics ’ 98, Prague. 1998, 521-528

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

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

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

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