PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal inference using the algorithmic Markov condition

Dominik Janzing, Bernhard Schoelkopf

arXiv:0804.3678v1math.STcs.ITstat.ML

TL;DR

The paper addresses how to infer causal structure from similarities between single observations rather than statistical samples. It replaces conditional stochastic independence with vanishing conditional algorithmic mutual information and derives corresponding causal rules, including a principle involving conditional-density complexity for distinguishing Markov-equivalent graphs. It concludes that practical, decidable complexity criteria are needed because Kolmogorov-complexity-based dependence is not empirically decidable.

  • Problem

    Causal inference methods based on statistical independence do not directly cover causal relations among single objects, motivating a probability-free framework for their similarities.

  • Method

    The paper replaces conditional stochastic independence in the causal Markov condition with vanishing conditional algorithmic mutual information and compares shortest descriptions of objects, joints, and conditional distributions.

  • Results

    The algorithmic causal Markov condition links algorithmic dependencies between single observations to causal structure and yields inference rules that can use algorithmic dependence of Markov kernels.

  • Takeaways & Limitations

    Causal relations among individual objects can be inferred when their shortest descriptions are sufficiently complex, while the framework also motivates new statistical inference rules.

  • Takeaways & Limitations

    Kolmogorov complexity provides no decidable criterion for proving either algorithmic dependence or independence, so practical compression-based approximations remain a subject for further research.

Abstract

from arXiv · show

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 only single observations are present. 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 discuss 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.

1 Introduction to causal inference from statistical data

Statistical causal inference uses independence constraints and graph simplicity to propose causal structures. The paper connects these ideas to algorithmic causal inference, where single-object similarities are represented by strings and algorithmic information.

  • Motivation: Causal inference methods use statistical independence tests to generate hypotheses about causal directions from observed random variables.The causal Markov condition links direct causes and non-effects to informational relevance.
  • Statistical causal Markov condition: A causal hypothesis is acceptable when the joint distribution satisfies the Markov condition relative to its directed acyclic graph.The local condition states that each variable is conditionally independent of its non-descendants given its parents.
  • Graphical implications: D-separation determines which conditional independences are implied by a graph's local Markov condition.A set blocks every path between two node sets when it d-separates them.
  • Functional models: Functional models with jointly independent noise variables generate distributions satisfying both local and global Markov conditions.Each variable is represented as a function of its parents and a noise variable.
  • Algorithmic extension: The paper develops probability-free causal inference by comparing shortest individual and joint descriptions, while also deriving new statistical inference rules.The algorithmic formulation is intended to address causal relations among single objects and to distinguish some Markov-equivalent graphs.

2 Inferring causal relations among individual objects

The paper extends causal inference to similarities between single objects by representing objects as strings and measuring shared algorithmic information. It also identifies limits of simple similarity-based causal tests.

  • Motivation: Human causal learning often concerns causal relations among single objects, including deterministic relations that statistical inference rules do not directly address.The paper formalizes such objects as strings and seeks causal graphs explaining their similarities.
  • Limits of simple tests: Simple statistical tests can infer spurious causal links when shared parts are too straightforward to construct, while cryptographic causal similarities may evade efficient statistical analysis.These examples motivate algorithmic rather than purely statistical criteria for single-object inference.
  • Algorithmic representation: Kolmogorov complexity measures the shortest binary description of an object and provides the basis for algorithmic information comparisons.Strings over other alphabets can be converted into binary strings.
  • Algorithmic mutual information: Algorithmic mutual information measures how many description bits of one string can be saved when the shortest description of the other is known.Using the shortest description ensures a symmetric formulation up to a constant term.
  • Inference principle: Non-vanishing mutual information is used as an indicator of causal relations, while conditional mutual information provides more detailed causal-structure information.This differs from information-distance approaches that focus on the relative amount of shared information.

Definition 3 (conditional algorithmic mutual information information)

Conditional algorithmic mutual information defines independence for strings by asking whether one string provides additional compressive information about another once a third string is known.

  • Definition: Conditional algorithmic mutual information is defined for three strings x, y, and z.It is the conditional analogue of algorithmic mutual information.
  • Symmetry: The conditional mutual information is symmetric in x and y up to a constant term.This preserves the symmetric character of mutual information in the conditional setting.
  • Conditional independence: Conditional independence is defined when I(x : y|z) is approximately zero.The threshold symbol is intentionally context-dependent for fixed real-life objects.
  • Interpretation: Given z, conditional independence means that additional knowledge of y does not enable stronger compression of x.The interpretation also conditions on the Kolmogorov complexity of y given z.

Theorem 1 (entropy and Kolmogorov complexity)

The paper relates statistical and algorithmic mutual information through entropy and Kolmogorov complexity, then shows that algorithmic dependence can arise even when the underlying distribution is statistically independent.

  • Entropy and complexity: For an i.i.d. string, Kolmogorov complexity is approximately related to the entropy of its generating probability distribution.The theorem is stated for symbols drawn from a distribution over a finite alphabet.
  • Mutual-information correspondence: For i.i.d. pairs, nE(I(x : y)) = I(X; Y).The relation follows by expressing statistical mutual information through marginal and joint entropies.
  • General relationship: When statistical mutual information is large relative to K(P), expected algorithmic mutual information is dominated by statistical mutual information.If K(P) is not small, statistical dependence need not provide useful compression because describing the dependence may cost more than it saves.
  • Algorithmic dependence under product measures: Knowledge of one string can enable compression of another even under a product measure, so algorithmic dependence need not imply statistical dependence.A point-mass example with x = y illustrates this possibility, and the construction generalizes it using product distributions labeled by strings.

2.2 Markov condition for algorithmic dependences among individual objects

The algorithmic causal Markov condition links causal structure among individual objects to conditional algorithmic mutual information. Its formulation conditions on an optimal joint compression of parent strings, yielding equivalence results analogous to statistical Markov conditions.

  • The postulate links algorithmic mutual dependences among individual objects with their causal structure.
  • For each object string, the formulation considers its parents and its non-descendants excluding itself.The parents and non-descendants are represented through concatenated strings.
  • The causal graph is rejected when the relevant conditional algorithmic mutual information is significantly greater than zero.The appropriate rejection cut-off rate is left unspecified.
  • Conditioning on the optimal joint compression of parent strings supports equivalence statements among different Markov-condition formulations.Differences from conditioning directly on the parent strings can be logarithmic in string lengths.
  • Applying the postulate to two unconnected nodes yields a causal principle for algorithmic mutual information.

Lemma 5 (causal principle for algorithmic information)

Significant algorithmic mutual information between two objects indicates a common past, interpreted broadly as direct influence in either direction or influence by a shared cause. Examples show why raw shared-pattern length is insufficient for judging meaningful similarity.

  • If I(x : y) is significantly greater than zero, the two objects have some kind of common past.
  • A common past includes influence from x to y, influence from y to x, or a third object influencing both.
  • Similarities between objects can motivate causal explanations involving common history, such as evolutionary relatedness between animal genomes.
  • Two people independently producing the binary representation of π may share a simple rule rather than a causal connection.
  • The length of a pattern shared by two observations is not by itself a reasonable criterion for significant similarity.

Theorem 3 (equivalence of algorithmic Markov conditions)

Theorem 3 establishes equivalence among recursive, local, and global formulations of the algorithmic Markov condition for strings and directed acyclic graphs. The result supports treating these formulations interchangeably.

  • Theorem 3 states that several conditions for strings and a directed acyclic graph are equivalent.
  • Recursive form: The recursive form expresses joint complexity as the sum of each node’s complexity given the optimal compression of its parents.
  • Local Markov condition: The local Markov condition makes every node independent of its non-descendants given the optimal compression of its parents.
  • Global Markov condition: The global Markov condition applies when one node set d-separates two others.
  • The shortest description of all strings is interpreted as describing how each string is generated from its direct causes.The paper describes this as a modularity of descriptions that also appears for joint probability distributions.
  • A lemma used in the proof provides an algorithmic analogue of the fact that applying a measurable function cannot increase statistical mutual information.It considers a string derived from x* by a simple rule.

Lemma 6 (monotonicity of algorithmic information)

Lemma 6 provides a monotonicity result for algorithmic information involving a string derived from another by a simple rule. It is presented as a special case of an earlier theorem.

  • The lemma considers strings x, y, and a string z derived from x* by a simple rule.
  • Its inequality bounds the conditional complexity of z in relation to the algorithmic mutual information between x and y.
  • The result is identified as a special case of Theorem II.7 in reference.

Lemma 7 (monotonicity of conditional information)

The lemma establishes a monotonicity relation for conditional algorithmic information, using properties of conditional Kolmogorov complexity. Its proof relies on handling the joint star operation on x and y.

  • Lemma 7 is non-trivial because the star operation is applied jointly to x and y.
  • The proof derives the result by computing x from the pair (x, y) with an O(1)-length program.
  • The argument rewrites the relevant expression using I(z : (x, y)) and then subtracts K(z), reversing the sign.

Lemma 8 (generalized data processing inequality)

The section relates conditional algorithmic complexities to conditional probabilities and uses this relation to establish algorithmic independence under d-separation. It thereby connects the algorithmic and statistical Markov arguments.

  • Lemma 8 (generalized data processing inequality): Conditional complexities of subsets are represented by the corresponding conditional probabilities through a logarithmic relation.The construction derives subset complexities from marginal probabilities and then obtains conditional complexities from conditional probabilities.
  • Lemma 8 (generalized data processing inequality): If R d-separates S and T, the recursion defining P gives S ⊥⊥ T |R.The probability function P is constructed to satisfy the graph recursion, so d-separation yields conditional stochastic independence.
  • Lemma 8 (generalized data processing inequality): The resulting conditional complexity identity proves algorithmic independence of S and T given R∗, establishing implication I ⇒III.The passage explicitly states that this proves algorithmic independence and the implication.

Theorem 4 (algorithmic model implies Markov)

Theorem 4 shows that the algorithmic model of independent causal mechanisms implies the algorithmic Markov condition. The proof extends the graph with independent inputs and transfers global Markovness back to the original variables.

  • Theorem 4 (algorithmic model implies Markov): Theorem 4 concludes that variables generated by Postulate 6 satisfy the algorithmic Markov condition with respect to G.The proof uses d-separation by the parents in the extended graph and then derives the local condition for G.
  • Theorem 4 (algorithmic model implies Markov): Independent mechanism inputs nj make each input independent of its non-descendants in the extended causal graph.Non-descendants can be computed from the other inputs by an O(1) program, supporting the local Markov condition for the extended graph.
  • Theorem 4 (algorithmic model implies Markov): Mutually dependent programs can violate the causal Markov condition, so independence of mechanisms is essential to the model.The paper gives a two-node edgeless graph as an example where dependent generating programs yield I(x1 : x2) > 0.

2.3 Relative causality

Causal dependence is defined relative to specified background information rather than unconditional similarity. Conditional algorithmic mutual information can reveal similarities that exceed shared properties such as membership in the same species.

  • 2.3 Relative causality: Human genetic sequences from unrelated people can have high unconditional similarity because both are human.The paper uses this example to motivate conditioning on background information.
  • 2.3 Relative causality: Given a human-genome code h, residual conditional mutual information indicates a relation beyond the shared human background.The paper contrasts expected unconditional information I(s1 : s2) ≥K(h) with conditional information given h.
  • 2.3 Relative causality: Background information can screen off common properties, allowing additional gene similarities to serve as indicators of causal relations.The supported scope is relations beyond the common evolutionary background.
  • 2.3 Relative causality: The framework assumes that relevant background information has been specified and real objects have been translated into binary strings.This requirement defines the representation and conditioning context for subsequent causal analysis.

3 Novel statistical inference rules from the algorithmic Markov condition

The paper derives causal inference rules by applying the algorithmic Markov condition to statistical properties, individual observations, and finite-sample density estimators. These rules reject causal hypotheses when the relevant mechanisms or estimators exhibit algorithmic dependence, while supporting inference with very small samples and computable features.

  • Postulate 7 (algorithmic independence of statistical properties): A causal hypothesis is acceptable only when the joint density has a shortest description formed by concatenating the shortest descriptions of its Markov kernels.This formulation makes the conditional probability densities part of causal model selection.
  • Postulate 7 (algorithmic independence of statistical properties): Postulate 7 rejects causal hypotheses whose total model complexity is not minimal, extending algorithmic independence beyond known causal inference rules.The total complexity sums the complexities of the Markov kernels, and minimizing it can also be interpreted through Bayesian priors.
  • Resolving statistical ensembles into individual observations: Algorithmic causal inference detects links even when statistical dependence is absent, because equal strings require an explanation through dependence between the generating mechanisms.For i.i.d. data the link is between corresponding observations; for whole strings it can occur between P(X) and P(Y|X).
  • Analysis of the required sample size: The required sample size grows only logarithmically in n for estimating the distribution and distinguishing conditionals under the stated product-distribution assumption.The error probability decreases exponentially with the number of copies, yielding a logarithmic sample requirement.
  • Resolving statistical ensembles into individual observations: The resolved graph distinguishes causes from effects through asymmetric d-separation: x2 d-separates x1 and y2, whereas y2 does not d-separate y1 and x2.This asymmetry supports rejecting the reverse causal hypothesis without needing to test the alternative direction.
  • Conditional density estimation on subsamples: For conditional density estimation, a selected subsample is chosen to blur information about the full x-distribution before estimating P(Y|X).If dependence remains between the full-sample estimator and the conditional estimator, the hypothesis X →Y is rejected.
  • Conditional density estimation on subsamples: The estimator strategy remains applicable to uncomputable distributions by detecting algorithmic dependence between their computable features.The paper demonstrates this using strings characterizing uncomputable distributions and stochastic maps.

4 Decidable modifications of the inference rule

The paper develops practical causal-inference rules by replacing Kolmogorov-complexity minimization with decidable simplicity criteria and symmetry constraints. Examples show that smoothing and information loss can favor one causal direction, while algorithmic dependence remains undecidable in general.

  • Decidable inference rules: Practical applications replace Kolmogorov-complexity minimization with decidable simplicity criteria for causal inference.The paper presents empirically decidable rules while acknowledging that their relation to Kolmogorov complexity is indirect.
  • Symmetry constraints: A time-series graph has no independence constraint that distinguishes forward from reversed time, so statistical Markov structure alone cannot identify its direction.The graph’s skeleton is symmetric under time inversion and contains no unshielded collider.
  • Symmetry constraints: Comparing marginals can favor X →Y when a simple conditional produces P(Y ) from P(X), whereas no simple reverse conditional exists.The paper also notes that causal directions are often easier to identify for probabilistic than deterministic relations.
  • Average complexity of stochastic maps: For distributions with sharp peaks that are broadened by a stochastic map, reversing the map generally requires a more complex description encoding the peak locations.The forward map is a repeated doubly stochastic random walk, while reverse maps must account for information lost during smoothing.
  • Average complexity of stochastic maps: The average complexity of reverse maps is bounded below by the entropy difference created by the doubly stochastic random walk.The argument uses families of distributions and shows that sufficiently different stochastic matrices are required to recover the sharper distributions.
  • Symmetry constraints: Translation-covariant processes cannot increase translation non-invariance, and Gaussian convolution decreases Fisher information, preventing a translation-invariant reverse process.A related symmetry argument states that backward maps would need to encode information destroyed by the forward process.
  • Limitations and practical criteria: Algorithmic dependence has no decidable test: finding a short program relating two objects does not rule out an undiscovered short independent description.The paper therefore discusses compression and resource-bounded complexity as possible practical substitutes, leaving their causal-inference evaluation for future research.

5 Conclusions

The algorithmic Markov condition extends causal inference to single observations and yields new statistical inference rules, while decidable criteria provide practical approximations to an uncomputable idealization.

  • The algorithmic Markov condition links algorithmic dependences between single observations to the underlying causal structure.
  • Conventional causal inference can drop the assumption that observations were independently sampled from a constant joint distribution of random variables.
  • Algorithmic information theory replaces statistical causal inference with a probability-free formulation.
  • Causal relations among individual objects can be inferred when their shortest descriptions are sufficiently complex.
  • Causal hypotheses are suspicious when their corresponding Markov kernels are algorithmically dependent, yielding new statistical causal inference rules.
  • Because algorithmic mutual information and Kolmogorov complexity are uncomputable, the paper presents decidable inference rules motivated by the uncomputable idealization.
Loading 0804.3678v1…