jmlr jmlr2010 jmlr2010-32 jmlr2010-32-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Remco Bouckaert, Raymond Hemmecke, Silvia Lindner, Milan Studený
Abstract: The topic of the paper is computer testing of (probabilistic) conditional independence (CI) implications by an algebraic method of structural imsets. The basic idea is to transform (sets of) CI statements into certain integral vectors and to verify by a computer the corresponding algebraic relation between the vectors, called the independence implication. We interpret the previous methods for computer testing of this implication from the point of view of polyhedral geometry. However, the main contribution of the paper is a new method, based on linear programming (LP). The new method overcomes the limitation of former methods to the number of involved variables. We recall/describe the theoretical basis for all four methods involved in our computational experiments, whose aim was to compare the efficiency of the algorithms. The experiments show that the LP method is clearly the fastest one. As an example of possible application of such algorithms we show that testing inclusion of Bayesian network structures or whether a CI statement is encoded in an acyclic directed graph can be done by the algebraic method. Keywords: conditional independence inference, linear programming approach
Remco R. Bouckaert and Milan Studen´ . Racing algorithms for conditional independence inference. y International Journal of Approximate Reasoning, 45(2):386–401, 2007. Winfried Bruns, Bogdan Ichim, and Christof S¨ ger. N ORMALIZ, a tool for computations in affine o monoids, vector configurations, lattice polytopes and rational cones. Available electronicly at http://www.math.uos.de/normaliz/, 2009. Winfried Bruns, Raymond Hemmecke, Bogdan Ichim, Matthias K¨ ppe, and Christof S¨ ger. Chalo o lenging computations of Hilbert bases of cones associated with algebraic statistics. To appear in Experimental Mathematics, e-print available at arxiv.org/abs/1001.4145v1, 2010. 3477 ´ B OUCKAERT, H EMMECKE , L INDNER AND S TUDEN Y David M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(2):507–554, 2002. Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen, and David J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer Verlag, 1999. A. Philip Dawid. Conditional independence in statistical theory. Journal of the Royal Statistical Society B, 41(1):1–31, 1979. Matthias Franz. C ONVEX, a Maple package for convex geometry. Available electronicly at www. math.uwo.ca/˜mfranz/convex/, 2009. Komei Fukuda. C DD and CDD +, an implementation of the double description method. Available electronicly at www.ifor.math.ethz.ch/˜fukuda/cdd_home/cdd.html, 2008. Dan Geiger, Tom Verma, and Judea Pearl. D-separation: from theorems to algorithms. In Proceedings of the 5th Conference on Uncertainty in Artificial Intelligence, pages 118–125, Elsevier, 1989. Raymond Hemmecke, Jason Morton, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Three counter-examples on semi-graphoids. Combinatorics, Probability and Computing, 17(2):239– 257, 2008. IBM Ilog team. CPLEX, a mathematical programming optimizer. Available electronicly at www-01.ibm.com/software/integration/optimization/cplex/, 2009. Finn V. Jensen. Bayesian Networks and Decision Graphs. Springer Verlag, 2001. Steffen L. Lauritzen. Graphical Models. Clarendon Press, 1996. Richard E. Neapolitan. Learning Bayesian Networks. Pearson Prentice Hall, 2004. Mathias Niepert, Dirk van Gucht, and Marc Gyssens. On the conditional independence implication problem, a lattice theoretic approach. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, pages 435–443, AUAI Press, 2008. Mathias Niepert. Logical inference algorithms and matrix representations for probabilistic conditional independence. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages 428–435, AUAI Press, 2009. Mathias Niepert, Dirk van Gucht, and Marc Gyssens. Logical and algorithmic properties of stable conditional independence. International Journal of Approximate Reasoning, 51(5):531–543, 2010. Judea Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988. Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986. ˇ Petr Simeˇ ek. Independence models (in Czech). PhD thesis, Charles University, Prague, 2007. c Milan Studen´ . Multiinformation and the problem of characterization of conditional independence y relations. Problems of Control and Information Theory, 18(1):3–16, 1989. 3478 E FFICIENT A LGORITHMS FOR C ONDITIONAL I NDEPENDENCE I NFERENCE Milan Studen´ . Convex set functions I and II. Research reports n. 1733 and 1734, Institute of Infory mation Theory and Automation, Prague, November 1991. Milan Studen´ . Conditional independence relations have no finite complete characterization. In y Information Theory, Statistical Decision Functions and Random Processes, Transactions of the ´ ıˇ 11th Prague Conference, vol. B (S. Kub´k, J. A. V´sek eds.), pages 377–396, Kluwer, 1992. ı Milan Studen´ . Convex cones in finite-dimensional real vector spaces. Kybernetika, 29(2):180–200, y 1993. Milan Studen´ , Remco R. Bouckaert, and Tom´ s Koˇ ka. Extreme supermodular set functions over y aˇ c five variables. Research report n. 1977, Institute of Information Theory and Automation, Prague, January 2000. Milan Studen´ . Structural imsets, an algebraic method for describing conditional independence y structures. In Proceedings of IPMU 2004 (B. Bouchon-Meunier, G. Coletti, R. R. Yager eds.), pages 1323–1330, 2004. Milan Studen´ . Probabilistic Conditional Independence Structures. Springer Verlag, 2005. y Milan Studen´ , Jiˇ´ Vomlel, and Raymond Hemmecke. A geometric view on learning Bayesian y rı network structures. International Journal of Approximate Reasoning, 51(5):573–586, 2010. Milan Studen´ and Jiˇ´ Vomlel. On open questions in the geometric approach to structural learning y rı Bayesian nets. Accepted in International Journal of Approximate Reasoning, to appear in 2011. 4ti2 team. 4 TI 2, a software package for algebraic, geometric and combinatorial problems on linear spaces. Available electronicly at www.4ti2.de, 2008. 3479