Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence

Mathias Niepert
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:436-443, 2009.

Abstract

Logical inference algorithms for conditional independence (CI) statements have important applications from testing consistency during knowledge elicitation to constraintbased structure learning of graphical models. We prove that the implication problem for CI statements is decidable, given that the size of the domains of the random variables is known and fixed. We will present an approximate logical inference algorithm which combines a falsification and a novel validation algorithm. The validation algorithm represents each set of CI statements as a sparse 0-1 matrix A and validates instances of the implication problem by solving specific linear programs with constraint matrix A. We will show experimentally that the algorithm is both effective and efficient in validating and falsifying instances of the probabilistic CI implication problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-niepert09a, title = {Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence}, author = {Niepert, Mathias}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {436--443}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/niepert09a/niepert09a.pdf}, url = {https://proceedings.mlr.press/r7/niepert09a.html}, abstract = {Logical inference algorithms for conditional independence (CI) statements have important applications from testing consistency during knowledge elicitation to constraintbased structure learning of graphical models. We prove that the implication problem for CI statements is decidable, given that the size of the domains of the random variables is known and fixed. We will present an approximate logical inference algorithm which combines a falsification and a novel validation algorithm. The validation algorithm represents each set of CI statements as a sparse 0-1 matrix A and validates instances of the implication problem by solving specific linear programs with constraint matrix A. We will show experimentally that the algorithm is both effective and efficient in validating and falsifying instances of the probabilistic CI implication problem.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence %A Mathias Niepert %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-niepert09a %I PMLR %P 436--443 %U https://proceedings.mlr.press/r7/niepert09a.html %V R7 %X Logical inference algorithms for conditional independence (CI) statements have important applications from testing consistency during knowledge elicitation to constraintbased structure learning of graphical models. We prove that the implication problem for CI statements is decidable, given that the size of the domains of the random variables is known and fixed. We will present an approximate logical inference algorithm which combines a falsification and a novel validation algorithm. The validation algorithm represents each set of CI statements as a sparse 0-1 matrix A and validates instances of the implication problem by solving specific linear programs with constraint matrix A. We will show experimentally that the algorithm is both effective and efficient in validating and falsifying instances of the probabilistic CI implication problem. %Z Reissued by PMLR on 04 October 2026.
APA
Niepert, M.. (2009). Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:436-443 Available from https://proceedings.mlr.press/r7/niepert09a.html. Reissued by PMLR on 04 October 2026.

Related Material