LOGICAL AND ALGORITHMIC PROPERTIES OF CONDITIONAL-INDEPENDENCE AND GRAPHICAL MODELS

This article develops an axiomatic basis for the relationship between conditional independence and graphical models in statistical analysis. In particular, the following relationships are established: (1) every axiom for conditional independence is an axiom for graph separation, (2) every graph represents a consistent set of independence and depend ence constraints, (3) all binary factorizations of strictly positive p robability models can be encoded and determined in polynomial time usi ng their correspondence to graph separation, (4) binary factorizations of non-strictly positive probability models can also be derived in po lynomial time albeit less efficiently and (5) unconditional independen ce relative to normal models can be axiomatized with a finite set of a xioms.