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 GYSSENS, Marc 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. mniepert@cs.washington.edu; marc.gyssens@uhasselt.be; bassem.sayrafi@gmail.com; vgucht@cs.indiana.edu | Keywords: | Conditional independence; Probability and lattice theory | Document URI: | http://hdl.handle.net/1942/15841 | 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 | Size | Format | |
---|---|---|---|---|
niepert 1.pdf Restricted Access | Published version | 632.38 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
19
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
24
checked on Apr 23, 2024
Page view(s)
74
checked on Sep 7, 2022
Download(s)
54
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.