On the conditional independence implication problem: a lattice-theoretic approach

Mathias Niepert, Dirk Van Gucht, Marc Gyssens
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:435-443, 2008.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-niepert08a, title = {On the conditional independence implication problem: a lattice-theoretic approach}, author = {Niepert, Mathias and Van Gucht, Dirk and Gyssens, Marc}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {435--443}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/niepert08a/niepert08a.pdf}, url = {https://proceedings.mlr.press/r6/niepert08a.html}, 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.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T On the conditional independence implication problem: a lattice-theoretic approach %A Mathias Niepert %A Dirk Van Gucht %A Marc Gyssens %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-niepert08a %I PMLR %P 435--443 %U https://proceedings.mlr.press/r6/niepert08a.html %V R6 %X 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. %Z Reissued by PMLR on 09 October 2024.
APA
Niepert, M., Van Gucht, D. & Gyssens, M.. (2008). On the conditional independence implication problem: a lattice-theoretic approach. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:435-443 Available from https://proceedings.mlr.press/r6/niepert08a.html. Reissued by PMLR on 09 October 2024.

Related Material