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

doi:10.1016/j.artint.2013.06.005

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

2013-09-01

24

OA

AI

DOI：10.1016/j.artint.2013.06.005

Original

Save

View PDF

Abstract

En 中文

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 (Cl) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with Cl 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 Cl statements. We also show that the general probabilistic Cl 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. (C) 2013 Elsevier B.V. All rights reserved.

Keywords:

Conditional independence

Probability and lattice theory

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

Abstract

AI Summary

Journal

Organization