Applications of Common Entropy for Causal Inference

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

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 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 is valid using common entropy. We finally evaluate our algorithms on synthetic and real data to establish their performance.

1. Introduction

A fundamental challenge in data science is distinguishing between causation (where $X$ causes $Y$) and spurious correlation (where a hidden variable $Z$ causes both $X$ and $Y$). Standard statistical tests often find these scenarios indistinguishable without experimental interventions. Furthermore, "constraint-based" causal discovery algorithms, such as the famous PC algorithm, rely on Conditional Independence (CI) tests that are notoriously unreliable in small-sample regimes. If a CI test makes an early mistake, the entire predicted causal graph can collapse. This paper proposes an information-theoretic framework using common entropy to validate causal relationships and improve discovery accuracy when data is scarce.

2. Methodology

The core concept is Rényi Common Entropy. If $X$ and $Y$ are correlated, the common entropy is the minimum Shannon entropy a latent variable $Z$ must have to render $X$ and $Y$ independent when controlling for $Z$.

Four fundamental causal structures analyzed: Latent, Triangle, Direct, and Mediator graphs.

2.1 The LatentSearch Algorithm

Calculating common entropy is computationally difficult in the general case. The authors developed LatentSearch, a multiplicative update algorithm that explores the trade-off between the complexity of the latent variable ($H(Z)$) and how well it explains the dependency ($I(X;Y|Z)$). Inspired by techniques in topic modeling and non-negative matrix factorization, LatentSearch converges in hundreds of iterations rather than the hundreds of thousands required by standard gradient descent.

2.2 EntropicPC

The authors introduce EntropicPC, a modification to the standard PC algorithm. Before the algorithm removes an edge between two variables based on a "separating set," EntropicPC checks if that set's entropy is at least as large as the common entropy of the two variables. This acts as an information-theoretic "sanity check"; if the entropy is too low, the separation is rejected as a statistical fluke.

3. Experimental Evaluation

The approach was evaluated using synthetic graphs and real-world benchmarks, including the Tuebingen Cause-Effect Pairs and the UCI ADULT census dataset.

  • Small-Sample Superiority: In simulations with limited samples (100–500), EntropicPC significantly outperformed the standard PC algorithm in terms of F1 score and Structural Hamming Distance.
  • Real-World Discovery: On the ADULT dataset, the standard PC algorithm failed to identify any causal drivers for "Salary," treating it as an isolated node. EntropicPC correctly identified Education, Occupation, and Relationship status as causal drivers.
  • Efficiency: LatentSearch proved to be orders of magnitude faster than gradient descent, reaching better local minima in a fraction of the time.

4. Discussion and Limitations

The method relies on the Mediator Assumption: it assumes that mediators (variables in a chain $X \to M \to Y$) are not extremely low-entropy. While empirical evidence suggests this usually holds, a very simple mediator could potentially lead the algorithm to misidentify a direct causal link as a hidden confounder. Additionally, while LatentSearch is efficient for pairs, scaling the approach to graphs with thousands of variables remains a challenge for future research.

In conclusion, by applying the principle of Occam’s Razor to latent variables, common entropy provides a powerful framework for distinguishing true causation from spurious correlation, particularly in data-constrained environments.

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 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 is 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