RESEARCH ARTICLE

A computational algebraic-geometry method for conditional-independence inference

  • Benchong LI ,
  • Shoufeng CAI ,
  • Jianhua GUO
Expand
  • Key Laboratory for Applied Statistics of MOE and School of Mathematics and Statistics, Northeast Normal University, Changchun 130024, China

Received date: 05 Sep 2012

Accepted date: 10 Feb 2013

Published date: 01 Jun 2013

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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.

Cite this article

Benchong LI , Shoufeng CAI , Jianhua GUO . A computational algebraic-geometry method for conditional-independence inference[J]. Frontiers of Mathematics in China, 0 , 8(3) : 567 -582 . DOI: 10.1007/s11464-013-0295-9

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

Options
Outlines

/