Telling Cause from Effect using MDL-based Local and Global Regression

About

We consider the fundamental problem of inferring the causal direction between two univariate numeric random variables $X$ and $Y$ from observational data. The two-variable case is especially difficult to solve since it is not possible to use standard conditional independence tests between the variables. To tackle this problem, we follow an information theoretic approach based on Kolmogorov complexity and use the Minimum Description Length (MDL) principle to provide a practical solution. In particular, we propose a compression scheme to encode local and global functional relations using MDL-based regression. We infer $X$ causes $Y$ in case it is shorter to describe $Y$ as a function of $X$ than the inverse direction. In addition, we introduce Slope, an efficient linear-time algorithm that through thorough empirical evaluation on both synthetic and real world data we show outperforms the state of the art by a wide margin.

Alexander Marx, Jilles Vreeken · 2017

Related benchmarks

Task	Dataset	Result
Causal Discovery	Tübingen	AUROC80.5	37
Causal Discovery	CE-Gauss	AUROC73.3	31
Bivariate Causal Discovery	CE Multi	AUROC96.9	21
Bivariate Causal Discovery	CE-Cha	AUROC59.3	21
Bivariate Causal Discovery	SIM-c	AUROC57.2	21
Bivariate Causal Discovery	CE-Net	AUROC67.1	21
Bivariate Causal Discovery	LS-s	AUROC11	21
Bivariate Causal Discovery	SIM	AUROC47.9	21
Bivariate Causal Discovery	MN-U	AUROC1.1	21
Bivariate Causal Discovery	SIM-G	AUROC45.1	21