×

A computational algebraic-geometry method for conditional-independence inference. (English) Zbl 1276.13023

Let \(N\) be a non-empty finite set, like a set of random variables. Let \(A,B,C \subset N\) be pairwise independent subsets. The symbol \(A\perp B | C\) is an abstract conditional independence symbol. In the case of random variables, it represents the set of all joint distribution under which the variables in \(A\) are conditionally independent of those in \(B\) given those in \(C\). For actual probability distributions, one can show that four implications, the so called semi-graphoid axioms hold. Abstractly, one can take these four implications as axioms and consider the closure operation which adds to a given set of CI statements all those that follow according to the axioms. Finding this closure ist the conditional independence implication problem. According to an observation of R. Hemmecke et al. [Comb. Probab. Comput. 17, No. 2, 239–257 (2008; Zbl 1211.62197)], this can be translated into a problem of commutative algebra.
The present paper describes this approach and details how to use Hilbert’s Nullstellensatz to actually do conditional independence inference.

MSC:

13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
60A05 Axioms; other general questions in probability

Citations:

Zbl 1211.62197

Software:

SINGULAR; Separoids; 4ti2; MIM
PDFBibTeX XMLCite
Full Text: DOI

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 · Zbl 1185.62009 · doi:10.1016/j.ijar.2009.05.002
[3] Bouckaert R R, Hemmecke R, Lindner S, Studený M. Efficient algorithms for conditional independence inference. J Mach Learn Res, 2010, 11: 3453–3479 · Zbl 1242.62129
[4] Bouckaert R R, Studený M. Racing algorithms for conditional independence inference. Int J Approx Reason, 2007, 45: 386–401 · Zbl 1122.68130 · doi:10.1016/j.ijar.2006.06.018
[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 · Zbl 1273.13052 · doi:10.1080/10586458.2011.544574
[6] Chickering D M. Optimal structure identification with greedy search. J Mach Learn Res, 2002, 3: 507–554 · Zbl 1084.68519
[7] Cowell R G, Dawid A P, Lauritzen S L, Spiegelhalter D G. Probabilistic Network and Expert System. New York: Springer-Verlag, 1999 · Zbl 0937.68121
[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 · Zbl 0880.62124
[10] Dawid A P. Conditional independence in statistical theory. J Roy Statist Soc Ser B, 1979, 41: 1–31 · Zbl 0408.62004
[11] Dawid A P. Separoids: a mathematical framework for conditional independence and irrelevance. Ann Math Artif Intell, 2001, 32: 335–372 · Zbl 1314.68308 · doi:10.1023/A:1016734104787
[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 · Zbl 0952.62003
[15] Hemmecke R, Morton J, Shiu A, Sturmfels B, Wienand O. Three counterexamples on semigraphoids. Combin Probab Comput, 2008, 17: 239–257 · Zbl 1211.62197
[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 · Zbl 0941.60004 · doi:10.1017/S0963548399003740
[18] Matúš F. Lengths of semigraphoid inferences. Ann Math Artif Intell, 2002, 35: 287–294 · Zbl 0991.05039 · doi:10.1023/A:1014525817725
[19] Matúš F. Towards classification of semi-graphoids. Discrete Math, 2004, 277: 115–145 · Zbl 1059.68082 · doi:10.1016/S0012-365X(03)00155-9
[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 · Zbl 1111.68685
[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 · Zbl 1329.68250
[24] Pearl J. Probabilistic Reasoning in Intelligent Systems. Burlington: Morgan Kaufmann, 1988 · Zbl 0649.68104
[25] Shenoy P P. Conditional independence in valuation-based systems. Int J Approx Reason, 1994, 10: 203–234 · Zbl 0821.68114 · doi:10.1016/0888-613X(94)90001-9
[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 · Zbl 0764.60004
[27] Studený M. Semigraphoids and structures of probabilistic conditional independence. Ann Math Artif Intell, 1997, 21: 71–98 · Zbl 0888.68112 · doi:10.1023/A:1018905100242
[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 · Zbl 1070.62001
[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 · Zbl 0732.62056
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.