Logical and algorithmic properties of independence and their application to Bayesian networks

This paper establishes a partial axiomatic characterization of the predicateI(X, Z, Y), to read “X is conditionally independent ofY, givenZ”. The main aim of such a characterization is to facilitate a solution of theimplication problem namely, deciding whether an arbitrary independence statementI(X, Z, Y) logically follows from a given setS of such statements. In this paper, we provide acomplete axiomatization and efficient algorithms for deciding implications in the case whereS is limited to one of four types of independencies:marginal independencies,fixed context independencies, arecursive set of independencies or afunctional set of independencies. The recursive and functional sets of independencies are the basic building blocks used in the construction ofBayesian networks. For these models, we show that the implication algorithm can be used to efficiently identify which propositions are relevant to a task at hand at any given state of knowledge. We also show that conditional independence is anArmstrong relation [10], i.e., checkingconsistency of a mixed set of independencies and dependencies can be reduced to a sequence of implication problems. This property also implies a strong correspondence between conditional independence and graphical representations: for every undirected graphG there exists a probability distributionP that exhibits all the dependencies and independencies embodied inG.