Applications of Common Entropy for Causal Inference

Murat Kocaoglu, Sanjay Shakkottai, Alexandros G. Dimakis, Constantine Caramanis, Sriram Vishwanath

Introduction

Distinguishing between "correlation" and "causation" remains the fundamental challenge of causal inference. Standard constraint-based methods, such as the widely used PC algorithm, rely on conditional independence (CI) tests to map out causal structures. However, these methods face two major hurdles. First, CI tests are notoriously unreliable when data is scarce, leading to "early errors" that cascade and result in completely incorrect causal graphs. Second, without interventions, it is often impossible to distinguish a direct causal link from a spurious correlation caused by a hidden confounder.

To tackle these challenges, researchers ask a fundamental question: What is the simplest possible hidden variable that could explain the observed correlation? By leveraging the concept of common entropy—the minimum complexity required for a latent variable to explain the correlation between two observed variables—this paper introduces an information-theoretic framework that significantly improves causal discovery in data-starved scenarios.

The Core Concept: Common Entropy

The paper centers on Rényi Common Entropy. If two variables $X$ and $Y$ are correlated, their common entropy is the minimum entropy a third variable $Z$ must have to make $X$ and $Y$ independent when conditioned on $Z$.

A core assumption of this approach is the "Simplicity of Nature": latent confounders in real-world systems are often relatively simple (low entropy) compared to the variables they influence. Conversely, causal mediators (variables in a chain $X \to M \to Y$) tend to be complex. Common entropy provides a physical lower bound. If a statistical test suggests that a low-entropy variable $S$ explains away the correlation between $X$ and $Y$, but the common entropy of $(X,Y)$ is higher than the entropy of $S$, the statistical test is likely a false positive caused by noise.

Four fundamental causal structures analyzed in the paper: (a) Latent Graph representing pure confounding, (b) Triangle Graph showing both confounding and causation, (c) Direct Graph for pure causation, and (d) Mediator Graph.

Methodology: LatentSearch and EntropicPC

To operationalize this concept, the authors introduce two key technical contributions:

  1. LatentSearch Algorithm: An iterative, multiplicative update algorithm designed to find the minimal latent variable $Z$. It optimizes a loss function that balances the residual dependency between $X$ and $Y$ against the complexity (entropy) of $Z$.
  2. EntropicPC: A modified version of the standard PC algorithm that uses common entropy as an information-theoretic "sanity check." Before the algorithm accepts that a set of variables $S$ makes $X$ and $Y$ independent, it checks if the entropy of $S$ is at least as large as the common entropy of $X$ and $Y$. If $S$ is too "simple" to explain the correlation, the independence claim is rejected.

Furthermore, the authors prove that if a hidden confounder is simple (low entropy), they can theoretically distinguish a purely confounded graph from one with a direct causal link, aiding in causal identification.

Experimental Validation and Key Results

The authors validated their approach using a mix of synthetic and real-world data, including 100 Erdös-Rényi random graphs, the Tuebingen Cause-Effect Pairs benchmark, and the ADULT census dataset.

  • Superior Performance in Small Samples: On synthetic data with only 1,000 samples, EntropicPC showed significant improvements in identifying the correct "skeleton" (the presence of edges) of the causal graph compared to the standard PC algorithm. The F1 score for EntropicPC was consistently higher when data was limited, demonstrating its robustness to noise and early errors.
  • Real-World Success: In the ADULT dataset, the standard PC algorithm failed to find any causes for "Salary," treating it as an isolated node. EntropicPC, however, correctly identified that "Education" and "Occupation" are causal drivers of "Salary."
  • Mediator Validation: Using the Tuebingen dataset, the authors confirmed their hypothesis that causal mediators generally have high entropy, supporting the use of common entropy as a reliable tool for distinguishing causal structure.

Limitations and Future Work

While highly effective, the framework has limitations. The assumption that confounders are "simpler" than their effects may not hold in every domain, such as highly complex biological systems. Additionally, the LatentSearch algorithm is iterative, and scaling it to graphs with hundreds or thousands of variables will require further optimization. Finally, the current work focuses on discrete variables; extending these information-theoretic bounds to continuous variables using differential entropy remains a promising but challenging future direction.

Summary updated

Abstract

We study the problem of discovering the simplest latent variable that can make two observed discrete variables conditionally independent. The minimum entropy required for such a latent is known as common entropy in information theory. We extend this notion to Renyi common entropy by minimizing the Renyi entropy of the latent variable. To efficiently compute common entropy, we propose an iterative algorithm that can be used to discover the trade-off between the entropy of the latent variable and the conditional mutual information of the observed variables. We show two applications of common entropy in causal inference: First, under the assumption that there are no low-entropy mediators, it can be used to distinguish direct causation from spurious correlation among almost all joint distributions on simple causal graphs with two observed variables. Second, common entropy can be used to improve constraint-based methods such as PC or FCI algorithms in the small-sample regime, where these methods are known to struggle. We propose a modification to these constraint-based methods to assess if a separating set found by these algorithms are valid using common entropy. We finally evaluate our algorithms on synthetic and real data to establish their performance.
BibTeX
@inproceedings{kocaoglu2020applications,
  author = {Murat Kocaoglu and Sanjay Shakkottai and Alexandros G. Dimakis and Constantine Caramanis and Sriram Vishwanath},
  title = {{Applications of Common Entropy for Causal Inference}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=KGtJ8g8D-SN},
}
Figure