Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15841

Title: On the conditional independence implication problem: A lattice-theoretic approach
Authors: Niepert, Mathias
Sayrafi, Bassem
Van Gucht, Dirk
Issue Date: 2013
Citation: 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. mniepert@cs.washington.edu; marc.gyssens@uhasselt.be; bassem.sayrafi@gmail.com; vgucht@cs.indiana.edu
URI: http://hdl.handle.net/1942/15841
DOI: 10.1016/j.artint.2013.06.005
ISI #: 000324354700002
ISSN: 0004-3702
Category: A1
Type: Journal Contribution
Validation: ecoom, 2014
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version632.38 kBAdobe PDF

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