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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.