Discovering Fully Oriented Causal Networks

Authors

  • Osman A Mian CISPA Helmholtz Center for Information Security
  • Alexander Marx CISPA Helmholtz Center for Information Security
  • Jilles Vreeken CISPA Helmholtz Center for Information Security

Keywords:

Causal Learning

Abstract

We study the problem of inferring causal graphs from observational data. We are particularly interested in discovering graphs where all edges are oriented, as opposed to the partially directed graph that the state of the art discover. To this end, we base our approach on the algorithmic Markov condition. Unlike the statistical Markov condition, it uniquely identifies the true causal network as the one that provides the simplest— as measured in Kolmogorov complexity—factorization of the joint distribution. Although Kolmogorov complexity is not computable, we can approximate it from above via the Minimum Description Length principle, which allows us to define a consistent and computable score based on non-parametric multivariate regression. To efficiently discover causal networks in practice, we introduce the GLOBE algorithm, which greedily adds, removes, and orients edges such that it minimizes the overall cost. Through an extensive set of experiments, we show GLOBE performs very well in practice, beating the state of the art by a margin.

Downloads

Published

2021-05-18

How to Cite

Mian, O. A., Marx, A., & Vreeken, J. (2021). Discovering Fully Oriented Causal Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10), 8975-8982. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17085

Issue

Section

AAAI Technical Track on Machine Learning III