Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach
Mathias Niepert, Dirk Van Gucht, Marc Gyssens
Abstract:
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.
Keywords:
Pages: 435-443
PS Link:
PDF Link: /papers/08/p435-niepert.pdf
BibTex:
@INPROCEEDINGS{Niepert08,
AUTHOR = "Mathias Niepert and Dirk Van Gucht and Marc Gyssens",
TITLE = "On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach",
BOOKTITLE = "Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2008",
PAGES = "435--443"
}


hosted by DSL   •   site info   •   help