Please use this identifier to cite or link to this item:
Title: On the conditional independence implication problem: A lattice-theoretic approach
Authors: Niepert, Mathias
Sayrafi, Bassem
Van Gucht, Dirk
Issue Date: 2013
Source: ARTIFICIAL INTELLIGENCE, 202, p. 29-51
Abstract: 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– 1vectors which encode their semi-lattices. The validation algorithm works by finding solutions to a linear programming problem involving these vectors an dmatrices. We provide experimental results for this algorithm and show that it is more efficient than related approaches.
Notes: Niepert, M (reprint author), Univ Washington, 185 Stevens Way, Seattle, WA 98195 USA.;;;
Keywords: Conditional independence; Probability and lattice theory
Document URI:
ISSN: 0004-3702
e-ISSN: 1872-7921
DOI: 10.1016/j.artint.2013.06.005
ISI #: 000324354700002
Category: A1
Type: Journal Contribution
Validations: ecoom 2014
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
niepert 1.pdf
  Restricted Access
published version632.38 kBAdobe PDFView/Open    Request a copy
Show full item record


checked on Sep 3, 2020


checked on May 21, 2022

Page view(s)

checked on May 25, 2022


checked on May 25, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.