Sound Approximate Reasoning about Saturated Conditional Probabilistic Independence under Controlled Uncertainty

Abstract

Knowledge about complex events is usually incomplete in practice. Zeros can be utilized to capture such events within probability models. In this article, Geiger and Pearl’s conditional probabilistic independence statements are investigated in the presence of zeros. Random variables can be specified to be zero-free, i.e., to disallow zeros in their domains. Zero-free random variables provide an effective mechanism to control the degree of uncertainty caused by permitting zeros. A finite axiomatization for the implication problem of saturated conditional independence statements is established under controlled uncertainty, relative to discrete probability measures. The completeness proof utilizes special probability models where two events have probability one half. The special probability models enable us to establish an equivalence between the implication problem and that of a propositional fragment in Cadoli and Schaerf’s S-3 logic. Here, the propositional variables in S correspond to the random variables specified to be zero-free. The duality leads to an almost linear time algorithm to decide implication. It is shown that this duality cannot be extended to cover general conditional independence statements. All results subsume classical reasoning about saturated conditional independence statements as the idealized special case where every random variable is zero-free. In the presence of controlled uncertainty, zero-free random variables allow us to soundly approximate classical reasoning about saturated conditional independence statements.