A computational algebraic-geometry method for conditional-independence inference
Received date: 05 Sep 2012
Accepted date: 10 Feb 2013
Published date: 01 Jun 2013
Copyright
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.
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
|
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
|
/
〈 | 〉 |