The Recovery of Causal Poly-Trees from Statistical Data

George Rebane, Judea PearlUAI 1987

TL;DR

This paper introduces a method to infer the structure and causal direction of "poly-trees" – complex causal networks with multiple causes – directly from observed statistical data. By extending the Chow-Liu algorithm, it can recover these structures with minimal reliance on external domain knowledge, offering a powerful tool for understanding intricate causal relationships.

What Problem Does This Paper Address?

Understanding causal relationships is fundamental in many scientific fields. Bayesian Networks (BNs) provide a powerful framework for representing these relationships using directed acyclic graphs (DAGs). However, many real-world phenomena involve variables with multiple causes, which are not fully captured by simple tree structures. Poly-trees, a type of singly connected causal network that allows for multiple causes, offer a more expressive model. The challenge addressed here is how to automatically infer the structure and, crucially, the direction of causality in these poly-trees solely from observed joint probability distributions of variables, without needing extensive prior knowledge or manual intervention.

Methods

The paper builds upon the Chow-Liu algorithm, which uses the Maximum Weight Spanning Tree (MWST) approach to recover the undirected skeleton (topology) of a dependency tree from a joint probability distribution. The authors prove that this same MWST algorithm can also recover the undirected skeleton of a poly-tree.

The novel contribution lies in the subsequent step: recovering the causal directionality of the branches. This is achieved by analyzing conditional independencies and mutual information between triplets of variables. Specifically, they introduce a "partially directed triplet test" that leverages the properties of poly-trees, particularly "causal basins" (a node and its direct parents/descendants), to infer the direction of influence. The algorithm systematically searches for multi-parent nodes and uses these tests to orient branches, working inwards from the outermost layers of the inferred skeleton.

Datasets

Not discussed in the paper. The methods are presented as general algorithms applicable to any discrete joint probability distribution derived from empirical observations.

Key Insights and Ideas

  • MWST for Poly-tree Skeletons: The surprising finding is that the Chow-Liu MWST algorithm, designed for simple trees, also works for recovering the undirected structure of more complex poly-trees. This significantly simplifies the initial step of structure discovery.
  • Directionality from Statistical Properties: The core innovation is demonstrating that causal directionality can be inferred from statistical properties (mutual information, conditional independence) of the data itself, rather than relying solely on external semantic information.
  • Causal Basins as Inference Units: The concept of "causal basins" is crucial. These localized structures within the poly-tree provide the necessary statistical information (especially from multi-parent clusters) to resolve branch directionality.
  • Minimizing External Semantics: The algorithm aims to determine directionality "up to the maximum extent possible" from the data, explicitly identifying where external knowledge is required for complete inference.

Key Results

The paper theoretically demonstrates that:

  • The MWST algorithm can unambiguously recover the undirected topology of any non-degenerate poly-tree.
  • The directionality of a branch can be recovered if and only if it is contained within a causal basin of the poly-tree.
  • For simple trees (no multi-parent clusters), causal direction cannot be assigned without external semantics, as Type-1 and Type-2 triplets are statistically indistinguishable.
  • The algorithm can handle "degenerate cases" where multiple poly-tree structures might fit the data, though it may produce any one of them. In such cases, higher-order statistics might be needed for orienting causal basins.

Limitations and Future Work

  • Degenerate Cases: In degenerate cases, where multiple skeletons have equal maximum weights, the MWST algorithm might produce any one of them. Resolving directionality in these cases might require higher-order statistics than just pairwise mutual information.
  • Simple Trees: For simple trees without multi-parent clusters, the algorithm cannot infer directionality without external semantics.
  • Maximum Extent of Recovery: The paper acknowledges that total directionality may not always be recoverable from the JPDF alone, depending on the specific structure and statistical properties of the data.
  • Future Work: The paper implicitly suggests exploring how to best integrate external semantics when the data is insufficient for full directionality recovery. Further investigation into handling degenerate cases with more advanced statistical tests is also implied.

Summary updated

BibTeX
@inproceedings{rebane1987recovery,
  author = {George Rebane and Judea Pearl},
  title = {{The Recovery of Causal Poly-Trees from Statistical Data}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1987},
}
Figure