CISPA
Browse
cispa_all_2907.pdf (1.2 MB)

Origo: Causal Inference by Compression

Download (1.2 MB)
journal contribution
posted on 2023-11-29, 18:07 authored by Kailash Budhathoki, Jilles VreekenJilles Vreeken
Causal inference from observational data is one of the most fundamental problems in science. In general, the task is to tell whether it is more likely that X caused Y, or vice versa, given only data over their joint distribution. In this paper we propose a general inference framework based on Kolmogorov complexity, as well as a practical and computable instantiation based on the Minimum Description Length (MDL) principle. Simply put, we propose causal inference by compression. That is, we infer that X is a likely cause of Y if we can better compress the data by first encoding X, and then encoding Y given X, than in the other direction. To show this works in practice, we propose Origo, an efficient method for inferring the causal direction from binary data. Origo employs the lossless Pack compressor (Tatti & Vreeken, 2008) and searches for that set of decision trees that encodes the data most succinctly. Importantly, it works directly on the data and does not require assumptions about neither distributions nor the type of causal relations. To evaluate Origo in practice, we provide extensive experiments on synthetic, benchmark, and real-world data, including three case studies. Altogether the experiments show that Origo reliably infers the correct causal direction on a wide range of settings.

History

Preferred Citation

Kailash Budhathoki and Jilles Vreeken. Origo: Causal Inference by Compression. In: Knowledge and Information Systems. 2018.

Primary Research Area

  • Trustworthy Information Processing

Legacy Posted Date

2019-06-07

Journal

Knowledge and Information Systems

Pages

285 - 307

Open Access Type

  • Unknown

Sub Type

  • Article

BibTeX

@article{cispa_all_2907, title = "Origo: Causal Inference by Compression", author = "Budhathoki, Kailash and Vreeken, Jilles", journal="{Knowledge and Information Systems}", year="2018", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC