research-article

Identifiability of Cause and Effect using Regularized Regression

Authors:

Alexander Marx,

Jilles VreekenAuthors Info & Claims

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 852 - 861

https://doi.org/10.1145/3292500.3330854

Published: 25 July 2019 Publication History

Abstract

We consider the problem of telling apart cause from effect between two univariate continuous-valued random variables X and Y. In general, it is impossible to make definite statements about causality without making assumptions on the underlying model; one of the most important aspects of causal inference is hence to determine under which assumptions are we able to do so. In this paper we show under which general conditions we can identify cause from effect by simply choosing the direction with the best regression score. We define a general framework of identifiable regression-based scoring functions, and show how to instantiate it in practice using regression splines. Compared to existing methods that either give strong guarantees, but are hardly applicable in practice, or provide no guarantees, but do work well in practice, our instantiation combines the best of both worlds; it gives guarantees, while empirical evaluation on synthetic and real-world data shows that it performs at least as well as the state of the art.

References

[1]

Niels Henrik Abel. 1826. Démonstration de l'impossibilité de la résolution algébrique des équations générales qui passent le quatrieme degré. Journal für die reine und angewandte Mathematik, Vol. 1 ( 1826), 65--96.

[2]

Hirotugu Akaike. 1983. Information measures and model selection. Int Stat Inst, Vol. 44 (1983), 277--291.

[3]

Patrick Blöbaum, Dominik Janzing, Takashi Washio, Shohei Shimizu, and Bernhard Schö lkopf. 2018. Cause-Effect Inference by Comparing Regression Errors. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS). 900--909.

[4]

Peter Bühlmann, Jonas Peters, Jan Ernest, et al. 2014. CAM: Causal additive models, high-dimensional order search and penalized regression. The Annals of Statistics, Vol. 42, 6 (2014), 2526--2556.

[5]

David Deutsch. 1985. Quantum theory, the Church--Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, Vol. 400, 1818 (1985), 97--117.

[6]

Arthur Gretton, Kenji Fukumizu, Choon H Teo, Le Song, Bernhard Schölkopf, and Alex J Smola. 2008. A kernel statistical test of independence. 585--592.

Digital Library

[7]

Peter Grünwald. 2007. The Minimum Description Length Principle .MIT Press.

[8]

PO. Hoyer, D. Janzing, JM. Mooij, J. Peters, and B. Schölkopf. 2009. Nonlinear causal discovery with additive noise models. 689--696.

Digital Library

[9]

Shoubo Hu, Zhitang Chen, Vahid Partovi Nia, Laiwan CHAN, and Yanhui Geng. 2018. Causal Inference and Mechanism Clustering of A Mixture of Additive Noise Models. In Proceedings of the 32th Annual Conference on Neural Information Processing Systems (NeurIPS). 5212--5222.

Digital Library

[10]

Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniuvsis, Bastian Steudel, and Bernhard Schölkopf. 2012. Information-geometric approach to inferring causal directions., Vol. 182--183 (2012), 1--31.

Digital Library

[11]

D. Janzing and B. Schölkopf. 2010. Causal Inference Using the Algorithmic Markov Condition. IEEE Transactions on Information Technology, Vol. 56, 10 (2010), 5168--5194.

Digital Library

[12]

Niki Kilbertus, Giambattista Parascandolo, and Bernhard Schölkopf. 2018. Generalization in anti-causal learning. arXiv preprint arXiv:1812.00524 (2018).

[13]

A.N. Kolmogorov. 1965. Three Approaches to the Quantitative Definition of Information. Problemy Peredachi Informatsii, Vol. 1, 1 (1965), 3--11.

[14]

M. Li and P. Vitányi. 1993. An Introduction to Kolmogorov Complexity and its Applications .Springer.

Digital Library

[15]

Alexander Marx, Christina Backes, Eckart Meese, Hans-Peter Lenhof, and Andreas Keller. 2016. EDISON-WMW: Exact Dynamic Programming Solution of the Wilcoxon-Mann-Whitney Test. Genomics, Proteomics & Bioinformatics (2016).

[16]

Alexander Marx and Jilles Vreeken. 2017. Telling Cause from Effect using MDL-based Local and Global Regression. IEEE, 307--316.

[17]

Alexander Marx and Jilles Vreeken. 2018. Telling cause from effect by local and global regression. Knowledge and Information Systems (2018).

[18]

Joris M. Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Bernhard Schö lkopf. 2016. Distinguishing Cause from Effect Using Observational Data: Methods and Benchmarks. Journal of Machine Learning Research, Vol. 17, 32 (2016), 1--102.

Digital Library

[19]

Judea Pearl. 2009. Causality: Models, Reasoning and Inference 2nd ed.). Cambridge University Press, New York, NY, USA.

Digital Library

[20]

Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. 2017. Elements of Causal Inference: Foundations and Learning Algorithms .MIT Press.

Digital Library

[21]

J. Peters, JM. Mooij, D. Janzing, and B. Schölkopf. 2014. Causal Discovery with Continuous Additive Noise Models. Journal of Machine Learning Research, Vol. 15 (2014), 2009--2053.

Digital Library

[22]

Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. 2011. Identifiability of Causal Graphs Using Functional Models. In Proceedings of the 27nd International Conference on Uncertainty in Artificial Intelligence (UAI). AUAI Press, 589--598.

Digital Library

[23]

Gideon Schwarz. 1978. Estimating the dimension of a model. The Annals of Statistics, Vol. 6, 2 (1978), 461--464.

[24]

Eleni Sgouritsa, Dominik Janzing, Philipp Hennig, and Bernhard Schölkopf. 2015. Inference of Cause and Effect with Unsupervised Inverse Regression., Vol. 38 (2015), 847--855.

[25]

Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvarinen, and Antti Kerminen. 2006. A Linear Non-Gaussian Acyclic Model for Causal Discovery. Journal of Machine Learning Research, Vol. 7 (2006), 2003--2030.

Digital Library

[26]

Peter Spirtes, Clark N Glymour, Richard Scheines, David Heckerman, Christopher Meek, Gregory Cooper, and Thomas Richardson. 2000. Causation, prediction, and search .MIT press.

[27]

Oliver Stegle, Dominik Janzing, Kun Zhang, Joris M Mooij, and Bernhard Schölkopf. 2010. Probabilistic latent variable models for distinguishing between cause and effect. Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS) 26 (2010), 1687--1695.

Digital Library

[28]

Natasa Tagasovska, Thibault Vatter, and Valérie Chavez-Demoulin. 2018. Nonparametric Quantile-Based Causal Discovery. Technical Report 1801.10579. arXiv.

[29]

N.K. Vereshchagin and P.M.B. Vitányi. 2004. Kolmogorov's Structure functions and model selection. IEEE Transactions on Information Technology, Vol. 50, 12 (2004), 3265-- 3290.

Digital Library

[30]

Thomas Verma and Judea Pearl. 1991. Equivalence and Synthesis of Causal Models. 255--270.

Digital Library

[31]

Kun Zhang and Aapo Hyvarinen. 2009. On the Identifiability of the Post-nonlinear Causal Model. AUAU Press, 647--655.

Cited By

Zeng YHao ZCai RXie FHuang LShimizu S(2023)Nonlinear Causal Discovery for High-Dimensional Deterministic DataIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.310611134:5(2234-2245)Online publication date: May-2023
https://doi.org/10.1109/TNNLS.2021.3106111
Hao SLiu YWang YWang YZhe WZhang ARangwala H(2022)Three-Stage Root Cause Analysis for Logistics Time Efficiency via Explainable Machine LearningProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539024(2987-2996)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539024
Yang SWang HYu KCao FWu X(2021)Towards Efficient Local Causal Structure LearningIEEE Transactions on Big Data10.1109/TBDATA.2021.3062937(1-1)Online publication date: 2021
https://doi.org/10.1109/TBDATA.2021.3062937
Show More Cited By

Index Terms

Identifiability of Cause and Effect using Regularized Regression
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic representations
      1. Causal networks
    2. Statistical paradigms
      1. Regression analysis
        Robust regression

Recommendations

Using locally weighted learning to improve SMOreg for regression
PRICAI'06: Proceedings of the 9th Pacific Rim international conference on Artificial intelligence

Shevade et al.[1] are successful in extending some improved ideas to Smola and Scholkopf's SMO algorithm[2] for solving regression problems, simply named SMOreg. In this paper, we use SMOreg in exactly the same way as linear regression(LR) is used in ...
Telling cause from effect by local and global regression
Abstract
We consider the problem of inferring the causal direction between two univariate numeric random variables X and Y from observational data. This case is especially challenging as the graph X causes Y is Markov equivalent to the graph Y causes X, ...
Causal Effect Estimation Using Variational Information Bottleneck
Web Information Systems and Applications
Abstract
Causal inference is to estimate the causal effect in a causalrelationship when intervention is applied. Precisely, in a causal model with binary interventions, i.e., control and treatment, the causal effect is simply the difference between the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2019

3305 pages

ISBN:9781450362016

DOI:10.1145/3292500

General Chairs:
Ankur Teredesai
KenSci
,
Vipin Kumar
University of Minnesota
,
Program Chairs:
Ying Li
EV Analysis Corporation
,
Rómer Rosales
LinkedIn
,
Evimaria Terzi
Boston University
,
George Karypis
University of Minnesota

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '19

Sponsor:

KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 4 - 8, 2019

AK, Anchorage, USA

Acceptance Rates

KDD '19 Paper Acceptance Rate 110 of 1,200 submissions, 9%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
616
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zeng YHao ZCai RXie FHuang LShimizu S(2023)Nonlinear Causal Discovery for High-Dimensional Deterministic DataIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.310611134:5(2234-2245)Online publication date: May-2023
https://doi.org/10.1109/TNNLS.2021.3106111
Hao SLiu YWang YWang YZhe WZhang ARangwala H(2022)Three-Stage Root Cause Analysis for Logistics Time Efficiency via Explainable Machine LearningProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539024(2987-2996)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539024
Yang SWang HYu KCao FWu X(2021)Towards Efficient Local Causal Structure LearningIEEE Transactions on Big Data10.1109/TBDATA.2021.3062937(1-1)Online publication date: 2021
https://doi.org/10.1109/TBDATA.2021.3062937
Du XSun LDuivesteijn WNikolaev APechenizkiy M(2021)Adversarial balancing-based representation learning for causal effect inference with observational dataData Mining and Knowledge Discovery10.1007/s10618-021-00759-3Online publication date: 17-May-2021
https://doi.org/10.1007/s10618-021-00759-3
Tagasovska NChavez-Demoulin VVatter TDaumé HSingh A(2020)Distinguishing cause from effect using quantilesProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525801(9311-9323)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525801

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents