PAC Learning of Causal Trees with Latent Variables

Prasad Tadepalli, Stuart J. Russell

Abstract

Learning the structure and parameters of causal models with latent variables is a fundamental challenge in machine learning. This work presents the first polynomial-time algorithm for PAC learning tree-structured Structural Causal Models (SCMs) where internal nodes are hidden. By leveraging a combination of observational data and targeted interventions at the leaf nodes, the proposed approach overcomes traditional barriers like Markov equivalence and computational hardness.

Introduction

In artificial intelligence, distinguishing between correlation and causation is critical. Structural Causal Models (SCMs) provide a robust framework for representing these relationships, but discovering them from data is notoriously difficult, particularly when some variables are "latent" (unobserved).

Most existing causal discovery methods face two primary hurdles: the "Markov Equivalence" problem, where observational data cannot distinguish between different causal directions, and "Computational Hardness," which makes learning even simple Boolean circuits cryptographically difficult as model size increases. This paper addresses these challenges for Causal Trees, where causality flows from multiple input "leaves" through hidden internal layers to a single "root" target. The challenge lies in reconstructing these hidden connections without direct access to the latent nodes.

Methods

The authors frame the problem as Probably Approximately Correct (PAC) learning. The methodology rests on two theoretical pillars:

  1. Control Normal Form (CNF): Any causal tree can be mathematically transformed into a "normal form" where internal hidden nodes can be deterministically controlled by specific combinations of input values. This effectively makes hidden nodes observable through their effects.
  2. Chain Rule of Causal Effects: The causal effect of an input on the root is decomposed into a product of effects along the path, providing a scoring mechanism for potential subtrees.

The core algorithm, BuildTree, operates bottom-up. It initializes each input as a tree, iteratively groups them under new hidden parent nodes, and validates these groupings using a specialized scoring function. Once the structure is established, the FillCPT procedure uses experimental queries (interventions) to estimate the Conditional Probability Tables (CPTs).

Causal tree structure and parameter estimation process.

Experimental Evaluation and Results

The algorithm was evaluated using synthetic datasets consisting of full binary trees with 16 leaf nodes and a depth of 4. CPTs were filled with random values biased toward extreme probabilities to increase learning difficulty.

The results demonstrate that the algorithm is provably efficient, running in polynomial time relative to the number of nodes and desired accuracy. Empirically, the algorithm reconstructed target models with near-zero test error. A key finding is that while learning the structure is significantly more complex than learning parameters alone—requiring roughly 10 times more unique queries—it remains computationally feasible and highly accurate.

Comparison of performance metrics when the tree structure is given versus learned.

Discussion and Limitations

This work highlights that active interventions are essential to breaking the computational barriers of learning hidden causal structures. By restricting the model to a tree structure, the authors bypass the cryptographic hardness associated with general causal graphs, making the problem solvable in polynomial time.

However, several limitations remain. The current framework is restricted to tree structures and binary variables, excluding "collider" structures or continuous data common in fields like biology or economics. Furthermore, the proof assumes an "exact" experimental oracle; future work must address the noise inherent in real-world experimental data to generalize these findings to approximate oracles.

Summary updated

Abstract

Learning causal models with latent variables from observational and experimental data is an important problem. In this paper we present a polynomial-time algorithm that PAC learns the structure and parameters of a rooted tree-structured causal network of bounded degree where the internal nodes of the tree cannot be observed or manipulated. Our algorithm is the first of its kind to provably learn the structure and parameters of tree-structured causal models with latent internal variables from random examples and active experiments.
BibTeX
@inproceedings{tadepalli2021pac,
  author = {Prasad Tadepalli and Stuart J. Russell},
  title = {{PAC Learning of Causal Trees with Latent Variables}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i11.17175},
}
Figure