Entropic Latent Variable Discovery

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 Rényi common entropy by minimizing the Rényi 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.

Introduction

A fundamental challenge in data science is distinguishing between "causation" and "spurious correlation." According to Reichenbach’s common cause principle, if two variables $X$ and $Y$ are correlated, either one causes the other, or they share a hidden common cause (a latent confounder $Z$).

Standard constraint-based algorithms, such as PC or FCI, rely on conditional independence tests to map these relationships. However, these methods face two major hurdles: they generally cannot distinguish $X \to Y$ from $X \leftarrow Z \to Y$ using only observational data, and they are notorious for failing in the small-sample regime where early errors in independence testing propagate through the graph-building process. This paper addresses these gaps by asking: What is the simplest possible hidden variable that could explain this correlation?

The Entropic Approach

The paper centers on the concept of Common Entropy. In information theory, the common entropy $G(X, Y)$ is the minimum Shannon entropy of a latent variable $Z$ such that $X$ and $Y$ become independent when conditioned on $Z$ ($X \perp Y | Z$).

Simple causal structures: (a) Latent Graph, (b) Triangle Graph, (c) Direct Graph, and (d) Mediator Graph.

Key Innovations

  • Rényi Common Entropy: The authors generalize common entropy to Rényi entropy, providing a broader framework for measuring latent complexity.
  • LatentSearch Algorithm: Since calculating common entropy is computationally difficult, the authors propose a multiplicative update algorithm. It optimizes a trade-off between the complexity of the latent variable $H(Z)$ and the residual dependency $I(X; Y | Z)$.
  • EntropicPC: This is a modified version of the classic PC algorithm. It uses common entropy as an "information-theoretic filter." If the algorithm finds a potential "separating set" (a group of variables that should make $X$ and $Y$ independent) but that set has less entropy than the calculated common entropy of $X$ and $Y$, the set is rejected as invalid.

Evaluation and Insights

The authors validate their approach using synthetic graphs (Erdös-Rényi, line, and collider graphs) and real-world benchmarks like the Tuebingen Cause-Effect Pairs and the ADULT census dataset.

Key Results

  • Small-Sample Performance: In synthetic tests with 1,000 to 5,000 samples, EntropicPC dramatically outperformed the standard PC algorithm in skeleton discovery (identifying connections regardless of direction).
  • Real-World Recovery: On the ADULT dataset, standard PC failed to find any causes for "Salary." EntropicPC correctly identified "Education," "Occupation," and "Workclass" as causal factors.
  • Efficiency: LatentSearch demonstrated a staggering speedup over gradient descent—converging in 0.01 seconds compared to 27.3 seconds for a 5-state system.

Simplicity as a Causal Signal

The core insight is that if the simplest latent variable required to explain a correlation is very complex (high entropy), it is statistically more likely that the variables are directly causally linked rather than confounded by a simple hidden cause. The paper proves that common entropy provides a fundamental lower bound on the entropy of any valid separating set, providing a rigorous "sanity check" for causal discovery.

Limitations and Future Work

The method relies on the assumption that latent confounders in nature tend to have relatively low entropy. If a system is confounded by an extremely high-entropy hidden variable, this method might misidentify the relationship as direct causation. Additionally, while LatentSearch is efficient for pairs, scaling it to massive graphs with thousands of nodes remains a challenge. Finally, the authors propose a conjecture regarding how common entropy scales with observed variables, which remains an open mathematical challenge.

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{kocaoglu2020entropic,
  author = {Murat Kocaoglu and Sanjay Shakkottai and Alexandros G. Dimakis and Constantine Caramanis and Sriram Vishwanath},
  title = {{Entropic Latent Variable Discovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=KGtJ8g8D-SN},
}
Figure