Testing Conditional Independence on Discrete Data using Stochastic\n Complexity

Testing for conditional independence is a core aspect of constraint-based\ncausal discovery. Although commonly used tests are perfect in theory, they\noften fail to reject independence in practice, especially when conditioning on\nmultiple variables.\n We focus on discrete data and propose a new test based on the notion of\nalgorithmic independence that we instantiate using stochastic complexity.\nAmongst others, we show that our proposed test, SCI, is an asymptotically\nunbiased as well as $L_2$ consistent estimator for conditional mutual\ninformation (CMI). Further, we show that SCI can be reformulated to find a\nsensible threshold for CMI that works well on limited samples. Empirical\nevaluation shows that SCI has a lower type II error than commonly used tests.\nAs a result, we obtain a higher recall when we use SCI in causal discovery\nalgorithms, without compromising the precision.\n