AAAI Publications, Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Reasoning about Saturated Conditional Independence Under Uncertainty: Axioms, Algorithms, and Levesque's Situations to the Rescue
Sebastian Link

Last modified: 2013-06-30


The implication problem of probabilistic conditional independencies is investigated in the presence of missing data. Here, graph separation axioms fail to hold for saturated conditional independencies, unlike the known idealized case with no missing data. Several axiomatic, algorithmic, and logical characterizations of the implication problem for saturated conditional independencies are established. In particular, equivalences are shown to the implication problem of a propositional fragment under Levesque's situations, and that of Lien's class of multivalued database dependencies under null values.


Axiomatization; Algorithm; Conditional independence; Data dependency; Implication problem; Logic; Missing data; Saturation; Situation

Full Text: PDF