Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/10986
Title: | Logical and algorithmic properties of stable conditional independence | Authors: | Niepert, Mathias Van Gucht, Dirk GYSSENS, Marc |
Issue Date: | 2010 | Publisher: | ELSEVIER SCIENCE INC | Source: | INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 51(5). p. 531-543 | Abstract: | The logical and algorithmic properties of stable conditional independence (Cl) as an alternative structural representation of conditional independence information are investigated. We utilize recent results concerning a complete axiomatization of stable conditional independence relative to discrete probability measures to derive perfect model properties of stable conditional independence structures. We show that stable CI can be interpreted as a generalization of Markov networks and establish a connection between sets of stable CI statements and propositional formulas in conjunctive normal form. Consequently, we derive that the implication problem for stable CI is coNP-complete. Finally, we show that Boolean satisfiability (SAT) solvers can be employed to efficiently decide the implication problem and to compute concise, non-redundant representations of stable Cl, even for instances involving hundreds of random variables. (C) 2010 Elsevier Inc. All rights reserved. | Notes: | [Niepert, Mathias] Univ Mannheim, Dept Comp Sci, KR & KM Res Grp, D-68159 Mannheim, Germany. [Van Gucht, Dirk] Indiana Univ, Dept Comp Sci, Bloomington, IN 47405 USA. [Gyssens, Marc] Hasselt Univ, Dept WNI, B-3590 Diepenbeek, Belgium. [Gyssens, Marc] Transnat Univ Limburg, B-3590 Diepenbeek, Belgium. mathias@informatik.uni-mannheim.de; vgucht@cs.indiana.edu; marc.gyssens@uhasselt.be | Keywords: | Conditional independence; Graphical models; Stable conditional independence; Computational complexity; Concise representation | Document URI: | http://hdl.handle.net/1942/10986 | ISSN: | 0888-613X | e-ISSN: | 1873-4731 | DOI: | 10.1016/j.ijar.2010.01.011 | ISI #: | 000278692300006 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2011 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ceyssens 2.pdf Restricted Access | Published version | 356.26 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
18
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
17
checked on Sep 12, 2024
Page view(s)
100
checked on Sep 7, 2022
Download(s)
118
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.