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 SizeFormat 
ceyssens 2.pdf
  Restricted Access
published version356.26 kBAdobe PDFView/Open    Request a copy
Show full item record

SCOPUSTM   
Citations

18
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

14
checked on May 14, 2022

Page view(s)

86
checked on May 18, 2022

Download(s)

114
checked on May 18, 2022

Google ScholarTM

Check

Altmetric


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