I was reading Koller's book on Probabilistic Graphical Models and was wondering how to prove soundness and completeness of the d-separation ?
Let me explain what is d-separation and it's properties soundness and completeness which needs to be proved in order to prove d-separation.
d-separation has been based on intuitions regarding flow of influence in Bayesian Networks (BN). In other words there is no grantee that d-separation is "correct." Perhaps there is a distribution over the BN where X can influence Y despite the fact that all trails between them are blocked.
Hence, the first property we want to ensure for d-separation as a method for determining independence is soundness: if we find that two nodes X and Y are d-separated given some Z, then we are guaranteed that they are, in fact, conditionally independent given Z.
Theorem: If a distribution P factorizes according to G, then I(G) ⊆ I(P).
In other words, any independence reported by d-separation is satisfied by the underlying distribution.
A second desirable property is the complementary one — completeness: d-separation detects all possible independencies. More precisely, if we have that two variables X and Y are independent given Z, then they are d-separated. A careful examination of the completeness property reveals that it is ill defined, inasmuch as it does not specify the distribution in which X and Y are independent.
To formalize this property, we first define the following notion: A distribution P is faithful to G if, whenever (X ⊥ Y | Z) ∈ I(P), then d-sepG(X; Y | Z). In other words, any independence in P is reflected in the d-separation properties of the graph.
We can now provide one candidate formalization of the completeness property is as follows:
- For any distribution P that factorizes over G, we have that P is faithful to G; that is, if X and Y are not d-separated given Z in G, then X and Y are dependent in all distributions P that factorize over G.
Thank you.