Header logo is

Causal Markov condition for submodular information measures


Conference Paper


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.

Author(s): Steudel, B. and Janzing, D. and Schölkopf, B.
Book Title: Proceedings of the 23rd Annual Conference on Learning Theory
Journal: COLT 2010: The 23rd Annual Conference on Learning Theory
Pages: 464-476
Year: 2010
Month: June
Day: 0
Editors: AT Kalai and M Mohri
Publisher: OmniPress

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: COLT 2010
Event Place: Haifa, Israel

Address: Madison, WI, USA
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Causal Markov condition for submodular information measures},
  author = {Steudel, B. and Janzing, D. and Sch{\"o}lkopf, B.},
  journal = {COLT 2010: The 23rd Annual Conference on Learning Theory},
  booktitle = {Proceedings of the 23rd Annual Conference on Learning Theory},
  pages = {464-476},
  editors = {AT Kalai and M Mohri},
  publisher = {OmniPress},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Madison, WI, USA},
  month = jun,
  year = {2010},
  month_numeric = {6}