On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach

Autor:	Niepert, Mathias, Van Gucht, Dirk, Gyssens, Marc
Rok vydání:	2014
Předmět:	Computer Science - Artificial Intelligence Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	A lattice-theoretic framework is introduced that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for saturated CI statements, (2) complete for general CI statements, and (3) sound and complete for stable CI statements. These results yield a criterion that can be used to falsify instances of the implication problem and several heuristics are derived that approximate this "lattice-exclusion" criterion in polynomial time. Finally, we provide experimental results that relate our work to results obtained from other existing inference algorithms. Comment: Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1408.2030 Zobrazit plný text záznamu View this record from Arxiv