Causal inference using the algorithmic Markov condition

Dominik Janzing, Bernhard Schölkopf

TL;DR

This paper introduces a novel framework for causal inference that moves beyond traditional statistical methods by leveraging algorithmic information theory. It proposes an "algorithmic Markov condition" that allows for causal discovery from individual observations, not just statistical ensembles, and offers new rules for statistical inference by identifying algorithmic dependencies between Markov kernels.

What Problem Does This Paper Address?

Traditional causal inference methods, like those based on the statistical causal Markov condition, rely heavily on detecting statistical independences in i.i.d. (independent and identically distributed) data. This approach faces limitations:

  1. Markov Equivalence: It often leads to multiple equally plausible causal graphs, making it difficult to pinpoint a unique causal structure.
  2. Dependence on i.i.d. Sampling: Real-world causal inference often deals with data that changes over time or involves single observations, where traditional statistical methods fall short.

The authors aim to address these limitations by developing a probability-free causal inference theory that can infer causal relationships from similarities between individual objects, rather than relying solely on statistical properties of large datasets. This opens up possibilities for causal discovery in scenarios where statistical independence tests are insufficient or impossible to apply.

Methods

The core of the paper is the introduction of the algorithmic Markov condition. This condition replaces the notion of statistical independence with algorithmic independence, measured using Kolmogorov complexity.

  • Kolmogorov Complexity (K(s)): The length of the shortest program that generates a string s.
  • Algorithmic Mutual Information (I(x:y)): Measures the information shared between two strings x and y in terms of their Kolmogorov complexities.
  • Algorithmic Markov Condition: Analogous to the statistical version, it states that a variable xj is algorithmically independent of its non-descendants given its parents. This is formulated using algorithmic mutual information.
  • Algorithmic Model of Causality: A formalization where causal mechanisms are represented by programs that compute outputs from inputs, with the assumption that these programs are mutually independent. This postulate is shown to imply the algorithmic Markov condition.
  • Algorithmic Independence of Markov Kernels: A key insight is that for a correct causal hypothesis, the Markov kernels (which describe conditional probabilities) should be algorithmically independent. This provides a new rule for statistical inference, suggesting that if Markov kernels are algorithmically dependent, the causal hypothesis is suspicious.
  • Decidable Modifications: Since Kolmogorov complexity is uncomputable, the paper explores ways to replace it with decidable criteria, such as using compression algorithms or symmetry constraints, to develop practical inference rules.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses illustrative examples rather than empirical datasets.

Key Insights and Ideas

  • Causality Beyond Statistics: The paper demonstrates that causal relationships can be inferred from algorithmic properties of data, not just statistical ones. This is particularly relevant for individual objects or non-i.i.d. data.
  • Algorithmic Markov Kernels as a New Inference Tool: The concept of algorithmic independence of Markov kernels offers a novel way to select among Markov-equivalent causal graphs. If the kernels are algorithmically dependent, it suggests a problem with the assumed causal structure.
  • Probability-Free Causal Inference: By using algorithmic complexity, the theory bypasses the need for computable probability distributions, making it applicable in more general settings.
  • Asymmetry of Cause and Effect: The framework naturally captures asymmetries between causes and effects, which is crucial for directional causal discovery. For instance, the complexity of describing a cause from an effect might differ from describing an effect from a cause.
  • The Importance of "Simplicity" in Causal Models: The paper formalizes the intuition that simpler causal explanations are preferred, not just in terms of graph structure but also in the algorithmic complexity of the underlying mechanisms.

Key Results

  • Equivalence of Algorithmic Markov Conditions: The paper establishes the equivalence of recursive, local, and global algorithmic Markov conditions, mirroring the statistical case.
  • Algorithmic Model Implies Markov Condition: A proposed algorithmic model of causality is shown to satisfy the algorithmic Markov condition.
  • New Statistical Inference Rules: The algorithmic independence of Markov kernels leads to new rules for statistical causal inference, suggesting that suspicious causal hypotheses can be identified if their corresponding Markov kernels are algorithmically dependent.
  • Theoretical Foundation for Simplicity Principles: The work provides a theoretical basis for heuristic principles that favor simpler causal models, connecting simplicity to algorithmic complexity.

Limitations and Future Work

  • Uncomputability of Kolmogorov Complexity: The primary limitation is that Kolmogorov complexity is uncomputable. The paper acknowledges this and proposes using decidable approximations and practical inference rules based on these approximations.
  • Approximation of Algorithmic Complexity: Developing practical inference rules that accurately approximate algorithmic complexity remains an active area of research.
  • Resource-Bounded Complexity: The paper briefly touches upon resource-bounded complexity as a more computationally tractable alternative, suggesting it could offer additional hints for causal structure.
  • Quantum Information: The authors note that quantum information might play a role in causal inference, a topic not fully explored in this work.
  • Practical Application: While the theory is developed, its direct application to real-world complex datasets would require robust implementations of algorithmic complexity estimators.

Summary updated

Abstract

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.
BibTeX
@article{janzing2010causal,
  author = {Dominik Janzing and Bernhard Schölkopf},
  title = {{Causal inference using the algorithmic Markov condition}},
  journal = {IEEE Trans. Information Theory},
  year = {2010},
  doi = {10.1109/tit.2010.2060095},
}
Figure