Abstract

In this note, we propose a new linear-algebraic method for the implication problem among conditional independence statements, which is inspired by the factorization characterization of conditional independence. First, we give a criterion in the case of a discrete strictly positive density and relate it to an earlier linear-algebraic approach. Then, we extend the method to the case of a discrete density that need not be strictly positive. Finally, we provide a computational result in the case of six variables.

AMS classification 90A99, 68T15

Keywords

conditional independence inference

automated theorem proving

semi-elementary imset

A pdf version of the published paper (424kB) is available.

The paper builds on results from the following publications:

• R. Bouckaert, R. Hemmecke, S. Lindner, M. Studeny: Efficient algorithms for conditional independence inference. Journal of Machine Learning Research 11 (2010), pp. 3453-3479.
• M. Studeny (2005). Probabilistic Conditional Independence Structures. London: Springer-Verlag.
• M. Baioletti, G. Busanello, B. Vantaggi: Conditional independence structure and its closure: Inferential rules and algorithms. International Journal of Approximate Reasoning 50 (2009), pp. 1097-1114.
• T. Kashimura, T. Sei, A. Takemura , K. Tanaka (2012) Cones of elementary imsets and supermodular functions: a review and some new results. In Proceedings of the Second CREST-SBM International Conference ``Harmony of Groebner Bases and the Modern Industrial Society, pages 117-152.