Measuring Conditional Independence by Independent Residuals: Theoretical Results and Application in Causal Discovery

2018-02-08

Proceedings of the AAAI Conference on Artificial Intelligence, 32

Volume

Thirty-Second AAAI Conference on Artificial Intelligence 2018

AAAI Technical Track: Knowledge Representation and Reasoning

We investigate the relationship between conditional independence (CI) x ⊥ y|Z and the independence of two residuals x – E(x|Z) ⊥ –E(y|Z), where x and y are two random variables, and Z is a set of random variables. We show that if x, y and Z are generated by following linear structural equation model and all external influences follow Gaussian distributions, then x ⊥ y|Z if and only if x – E(x|Z) ⊥ y – E(y|Z). That is, the test of x ⊥ y|Z can be relaxed to a simpler unconditional independence test of x – E(x|Z) ⊥ y – E(y|Z). Furthermore, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⊥ y|Z ⇔ x – E(x|Z) ⊥ y – E(y|Z). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V-structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in linear non-Gaussian context, x – E(x|Z) ⊥ y – E(y|Z) ⇒ x – E(x|Z) ⊥ z or y – E(y|Z ⊥ z (∀z ∈ Z) if Z is a minimal d-separator, which implies z causes x (or y) if z directly connects to x (or y). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, compared with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is experimentally validated.

10.1609/aaai.v32i1.11555