Logical and algorithmic properties of stable conditional independence
Logical and algorithmic properties of stable conditional independence
复制标题
稳定条件独立的逻辑和算法特性
DOI：
10.1016/j.ijar.2010.01.011
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Gyssens
中科院分区：
文献类型：
--
作者：
Mathias Niepert;D. V. Gucht;M. Gyssens
研究了稳定条件独立（CI）作为条件独立信息的另一种结构表示的逻辑和算法性质。我们利用最近关于相对于离散概率测度的稳定条件独立的完全公理化的结果，推导了稳定条件独立结构的完美模型性质。我们证明了稳定CI可以被解释为马尔可夫网络的一种推广，并建立了稳定CI语句集与合取范式的命题公式之间的联系。因此，我们得到了稳定CI的隐含问题是conp完全的。最后，我们证明了布尔可满足性（SAT）解算器可以有效地决定隐含问题，并计算稳定CI的简洁，非冗余表示，甚至涉及数百个随机变量的实例。
The logical and algorithmic properties of stable conditional independence (CI) 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 CI, even for instances involving hundreds of random variables.