Logical Inference Algorithms and Matrix Representations for Probabilistic Conditional Independence
This work addresses a foundational problem in probabilistic graphical models and knowledge representation, with applications in structure learning and consistency testing, though it is incremental in improving algorithmic efficiency for a known bottleneck.
The paper tackles the problem of deciding logical implications among probabilistic conditional independence statements, proving decidability when variable domain sizes are fixed and presenting an approximate inference algorithm that combines falsification and a novel validation approach using sparse matrix representations and linear programming. The algorithm is shown to be effective and efficient in experiments for validating and falsifying instances.
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.