Causal Inference by Stochastic Complexity
By Kailash Budhathoki, Jilles Vreeken. 2017
9 citations recorded by the source corpus.
The algorithmic Markov condition states that the most likely causal direction between two random variables X and Y can be identified as that direction with the lowest Kolmogorov complexity. Due to the halting problem, however, this notion is not computable. We hence propose to do causal inference by stochastic complexity. That is, we propose to approximate Kolmogorov complexity via the Minimum Description Length (MDL) principle, using a score that is mini-max optimal with regard to the model class under consideration. This means that even in an adversarial setting, such as when the true distribution is not in this class, we still obtain the optimal encoding for the data relative to the class. We instantiate this framework, which we call CISC, for pairs of univariate discrete variables, using the class of multinomial distributions. Experiments show that CISC is highly accurate on synthetic, benchmark, as well as real-world data, outperforming the state of the art by a margin, and scales extremely well with regard to sample and domain sizes.
Subfields: Artificial Intelligence, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Anirudh Goyal
- C. Pal
- Nan Rosemary Ke
- Sergey Levine
- Ruslan Salakhutdinov
- Bernhard Schölkopf
- Kyunghyun Cho
In Statistics and Probability
- Anirudh Goyal
- Dino Sejdinovic
- Yee Whye Teh
- Jovana Mitrovi'c
- Nan Rosemary Ke
- Stefan Bauer
- Yoshua Bengio
- Hugo Larochelle
Citations in the corpus
- Learning Neural Causal Models from Unknown Interventions (2019, methodology): “…based on observational data (Chickering, 2002; Tsamardinos et al., 2006; Goudet et al., 2017; Hauser & Bühlmann, 2012; Spirtes et al., 2000; Sun et al., 2007; Zhang et al., 2012; Shimizu et al., 2006; Hoyer et al., 2009; Daniusis et al., 2012; Budhathoki & Vreeken, 2017; Kalainathan et al., 2018).”
- Causal Inference via Kernel Deviance Measures (2018, methodology): “In [Da-niusis et al., 2012], instead of computing the intractable Kolmogorov complexity, the correlation between the input and the conditional distribution is measured, whereas [Budhathoki and Vreeken, 2017] use the minimum description length principle.”