Causal Inference Using the Algorithmic Markov Condition
By Dominik Janzing, Bernhard Schölkopf. 2008
345 citations recorded by the source corpus.
Inferring the causal structure that links n observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why causal inference is also possible when the sample size is one. We develop a theory how to generate causal graphs explaining similarities between single objects. To this end, we replace the notion of conditional stochastic independence in the causal Markov condition with the vanishing of conditional algorithmic mutual information and describe the corresponding causal inference rules. We explain why a consistent reformulation of causal inference in terms of algorithmic complexity implies a new inference principle that takes into account also the complexity of conditional probability densities, making it possible to select among Markov equivalent causal graphs. This insight provides a theoretical foundation of a heuristic principle proposed in earlier work. We also sketch some ideas on how to replace Kolmogorov complexity with decidable complexity criteria. This can be seen as an algorithmic analog of replacing the empirically undecidable question of statistical independence with practical independence tests that are based on implicit or explicit assumptions on the underlying distribution.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Causal Inference & Discovery, Information Theory
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
- Bernhard Schölkopf
- Yoshua Bengio
- Dacheng Tao
- Sergey Levine
- Quoc V. Le
- David Lopez-Paz
- Jan Peters
- Mohit Bansal
In Computational Theory and Mathematics
- Bernhard Schölkopf
- Kun Zhang
- Dominik Janzing
- Jan Peters
- David Lopez-Paz
- Jilles Vreeken
- Dino Sejdinovic
- Biwei Huang
In Causal Inference & Discovery
- Bernhard Schölkopf
- Dominik Janzing
- Kun Zhang
- David Lopez-Paz
- Jan Peters
- Joris M. Mooij
- Jilles Vreeken
- Stefan Bauer
In Information Theory
- Bernhard Schölkopf
- Dominik Janzing
- David Lopez-Paz
- Kun Zhang
- Jilles Vreeken
- Jan Peters
- Joris M. Mooij
- Kailash Budhathoki
Citations in the corpus
- An Analysis of the Adaptation Speed of Causal Models (2020, background): “In general, SCMs model the distribution of observations with a directed graph where edges represent independent mechanisms (Janzing and Scholkopf, 2010).”
- Discovering Causal Signals in Images (2016, background): “This can be formalized either probabilistically [3] or in terms of algorithmic complexity [12].”
- Towards Causal Representation Learning (2021, methodology): “prove that they are implied by the structural causal model [120].”
- Algorithmic recourse under imperfect causal knowledge: a probabilistic approach (2020, methodology): “This can be shown by using the following argument from [14, Footnote 1] (adapted to our notation): “ let U r consist of (possibly uncountably many) real-valued random variables U r [ x pa ( r ) ] , one for each value x pa ( r ) of the parents X pa ( r ) .”
- A theory of independent mechanisms for extrapolation in generative models (2020, methodology): “Capturing the causal structure of this process allows the different mechanisms involved in generating the data to be intervened on independently, based on the principle of Independence of Mechanisms (IM) (Janzing and Sch¨olkopf 2010; Lemeire and Janzing 2012; Peters, Janzing, and Sch¨olkopf 2017).”
- Causality for Machine Learning (2019, methodology): “Similar to the statistical case, one can define a local causal Markov condition, a global one in terms of d-separation, and an additive decomposition of the joint Kolmogorov complexity in analogy to (2), and prove that they are implied by the structural causal model (Janzing and Schölkopf, 2010).”
- Semi-supervised learning, causality, and the conditional cluster assumption (2019, background): “This notion has been formalized in terms of Kolmogorov complexity (or Algorithmic Information) K(·) by Janzing and Schölkopf [21] who show that when X is a cause of Y , X → Y ,”
- Generalization in anti-causal learning (2018, background): “Janzing and Schölkopf (2010) argue that the causal direction has a shorter description in terms of Kolmogorov complexity 6 than the anti-causal one.”
- Domain Generalization via Conditional Invariant Representations (2018, neutral): “According to some recent results in causal learning (Sch ¨ olkopf et al. 2012; Janzing and Scholkopf 2010), P ( Y | X ) can be stable when P ( X ) changes in the situation where X is the cause for Y , i.e., the causal structure is X → Y .”
- Learning Independent Causal Mechanisms (2017, background): “In this section we briefly discuss the notion of independence of mechanisms as in Janzing & Sch¨olkopf (2010), where the independence principle is formalized in terms of algorithmic complexity (also known as Kolmogorov complexity).”
- Algorithmic independence of initial condition and dynamical law in thermodynamics and causal inference (2015, background): “If s is algorithmically independent of the pair (D, e) (which is true, for instance when K(e) is negligible and s and D are independent), independence of s and M follows because algorithmic independence of two strings a, b implies independence of a, c whenever c can be computed from b via a program ”
- Telling cause from effect in deterministic linear dynamical systems (2015, background): “Thus, these two objects should not contain any information about each other [12, 14, 21].”
- On causal and anticausal learning (2012, methodology): “2 This assumption has been used by Janzing & Sch¨olkopf (2010), inspired by Lemeire & Dirkx (2007).”
- Identifiability of Causal Graphs using Functional Models (2011, background): “…it can only happen if the cause distribution p(cause) and the conditional distribution of the effect given the cause p(effect | cause) are matched in a precise way, whereas one rather expects input and mechanism to be most often “independent” [Lemeire and Dirkx, 2006, Janzing and Schölkopf, 2010].”
- Inferring deterministic causal relations (2010, background): “While this postulate is informal in the sense that we do not specify what we mean by independence, we point out that Lemeire and Dirkx [2006] and Janzing and Schölkopf [2008] give a formalization in terms of algorithmic independence.”
- Causal Markov condition for submodular information measures (2010, background): “In [4] the probabilistic setting is generalized to the case where every observation is formalized by a binary string x j (without any statistical population).”