Causal Markov condition for submodular information measures

By Bastian Steudel, Dominik Janzing, Bernhard Schölkopf. 2010

36 citations recorded by the source corpus.

The causal Markov condition (CMC) is a postulate that links observations to causality. It describes the conditional independences among the observations that are entailed by a causal hypothesis in terms of a directed acyclic graph. In the conventional setting, the observations are random variables and the independence is a statistical one, i.e., the information content of observations is measured in terms of Shannon entropy. We formulate a generalized CMC for any kind of observations on which independence is defined via an arbitrary submodular information measure. Recently, this has been discussed for observations in terms of binary strings where information is understood in the sense of Kolmogorov complexity. Our approach enables us to find computable alternatives to Kolmogorov complexity, e.g., the length of a text after applying existing data compression schemes. We show that our CMC is justified if one restricts the attention to a class of causal mechanisms that is adapted to the respective information measure. Our justification is similar to deriving the statistical CMC from functional models of causality, where every variable is a deterministic function of its observed causes and an unobserved noise term. Our experiments on real data demonstrate the performance of compression based causal inference.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Molecular Biology, 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

1. Bernhard Schölkopf
2. Yoshua Bengio
3. Anirudh Goyal
4. Stefan Bauer
5. Nan Rosemary Ke
6. Francesco Locatello
7. Kyunghyun Cho
8. Quoc V. Le

In Computational Theory and Mathematics

1. Bernhard Schölkopf
2. Jilles Vreeken
3. Kailash Budhathoki
4. Yoshua Bengio
5. Stefan Bauer
6. Anirudh Goyal
7. Nan Rosemary Ke
8. Francesco Locatello

In Molecular Biology

1. Nal Kalchbrenner
2. Bernhard Schölkopf
3. Stefan Bauer
4. Yoshua Bengio
5. Anirudh Goyal
6. Nan Rosemary Ke
7. Francesco Locatello
8. Stefano Ermon

In Causal Inference & Discovery

1. Yoshua Bengio
2. Anirudh Goyal
3. Stefan Bauer
4. Francesco Locatello
5. Nan Rosemary Ke
6. Jilles Vreeken
7. Kailash Budhathoki
8. Nal Kalchbrenner

In Information Theory

1. Jilles Vreeken
2. Kailash Budhathoki
3. Yoshua Bengio
4. Francesco Locatello
5. Nan Rosemary Ke
6. Stefan Bauer
7. Anirudh Goyal
8. Nal Kalchbrenner

Citations in the corpus

• Toward Causal Representation Learning (2021, background): “The notion of invariant, autonomous, and independent mechanisms has appeared in various guises throughout the history of causality research [72], [100], [111], [124], [183], [188], [240].”
• Towards Causal Representation Learning (2021, background): “The notion of invariant, autonomous, and independent mechanisms has appeared in various guises throughout the history of causality research [99, 71, 111, 183, 120, 240, 188].”
• Causality for Machine Learning (2019, background): “…the history of causality research.7 Our contribution may be in unifying these notions with the idea of informational independence, and in showing that one can use rather general independence measures (Steudel et al., 2010), a special case of which (algorithmic information) will be described below.”
• Origo: causal inference by compression (2016, background): “Definition 1 (Information measure [35]) A function R : Ω → R is an information measure if it satisfies the following axioms:”