On the conditional independence implication problem: A lattice-theoretic approach Original Research Article

Conditional independence is a crucial notion in the development of probabilistic systems which are successfully employed in areas such as computer vision, computational biology, and natural language processing. We introduce a lattice-theoretic framework 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 inferring general from saturated CI statements and (2) complete for inferring general from general CI statements. We also show that the general probabilistic CI implication problem can be reduced to that for elementary CI statements. The completeness of the inference system together with its lattice-theoretic characterization yields a criterion we can use to falsify instances of the probabilistic CI implication problem as well as several heuristics that approximate this falsification criterion in polynomial time. We also propose a validation criterion based on representing constraints and sets of constraints as sparse 0–1 vectors which encode their semi-lattices. The validation algorithm works by finding solutions to a linear programming problem involving these vectors and matrices. We provide experimental results for this algorithm and show that it is more efficient than related approaches.