More Web Proxy on the site http://driver.im/

research-article

Public Access

Generalized Score Functions for Causal Discovery

Authors:

Bernhard Schölkopf,

Clark GlymourAuthors Info & Claims

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

Pages 1551 - 1560

https://doi.org/10.1145/3219819.3220104

Published: 19 July 2018 Publication History

Abstract

Discovery of causal relationships from observational data is a fundamental problem. Roughly speaking, there are two types of methods for causal discovery, constraint-based ones and score-based ones. Score-based methods avoid the multiple testing problem and enjoy certain advantages compared to constraint-based ones. However, most of them need strong assumptions on the functional forms of causal mechanisms, as well as on data distributions, which limit their applicability. In practice the precise information of the underlying model class is usually unknown. If the above assumptions are violated, both spurious and missing edges may result. In this paper, we introduce generalized score functions for causal discovery based on the characterization of general (conditional) independence relationships between random variables, without assuming particular model classes. In particular, we exploit regression in RKHS to capture the dependence in a nonparametric way. The resulting causal discovery approach produces asymptotically correct results in rather general cases, which may have nonlinear causal mechanisms, a wide class of data distributions, mixed continuous and discrete data, and multidimensional variables. Experimental results on both synthetic and real-world data demonstrate the efficacy of our proposed approach.

Supplementary Material

MP4 File (huang_causal_discovery.mp4)

Download
407.99 MB

References

[1]

C. F. Aliferis, A. R. Statnikov, I. Tsamardinos, S. Mani, and X. D. Koutsoukos . 2010. Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation. Journal of Machine Learning Research Vol. 11 (2010), 171--234.

Digital Library

[2]

F. R. Bach and M. I. Jordan . 2002. Learning graphical models with Mercer kernels. Advances in Neural Information Processing Systems (2002), 1009--1016.

Digital Library

[3]

T. E. Bakken, A. M. Dale, and N. J. Schork . 2011. A Geographic Cline of Skull and Brain Morphology among Individuals of European Ancestry. Hum Hered Vol. 72(1) (2011), 35--44.

[4]

P Bühlmann, J. Peters, and J. Ernest . 2014. CAM: Causal Additive Models, high-dimensional order search and penalized regression. Annals of Statistics Vol. 42(6) (2014), 2526--2556.

[5]

W. Buntine . 1991. Theory refinment on Bayesian networks. Uncertainty in Artificial Intelligence (1991), 52--60.

Digital Library

[6]

A. Caponnetto and E. De Vito . 2006. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics (2006).

[7]

D. M. Chickering . 2003. Optimal Structure Identification With Greedy Search. Journal of Machine Learning Research Vol. 3 (2003), 507--554.

Digital Library

[8]

D. M. Chickering and D. Heckerman . 1997. Efficient approximations for the marginal likelihood of bayesian networks with hidden variables. Machine Learning Vol. 29 (1997), 181--212.

Digital Library

[9]

T. Claassen and T. Heskes . 2012. A Bayesian approach to constraint based causal inference. Uncertainty in Artificial Intelligence (2012), 207--216.

Digital Library

[10]

K. Fukumizu, F. R. Bach, and M. I. Jordan . 2004. Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. Journal of Machine Learning Research Vol. 5 (2004), 73--79.

Digital Library

[11]

K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf . 2007. Kernel measures of conditional dependence. NIPS Vol. 11 (2007), 489--496.

Digital Library

[12]

D. Geiger and D. Heckerman . 1994. Learning Gaussian networks. In Proceedings of Tenth Conference on Uncertainty in Artificial Intelligence (1994), 235 --243.

Digital Library

[13]

D. Heckerman, D. Geiger, and D.M. Chickering . 1995. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning Vol. 20 (1995), 197--243.

Digital Library

[14]

D. Heckerman, C. Meek, and G. Cooper . 2006. A Bayesian approach to causal discovery. Innovations in Machine Learning (2006), 1--28.

[15]

P. Hoyer, D. Janzing, J. Mooji, Peters J., and B. Schölkopf . 2009. Nonlinear causal discovery with additive noise models. NIPS (2009).

Digital Library

[16]

B. Huang, K. Zhang, J. Zhang, R. Sanchez-Romero, C. Glymour, and B. Schölkopf . 2017. Behind Distribution Shift: Mining Driving Forces of Changes and Causal Arrows. ICDM (2017), 913--918.

[17]

A. Hyttinen, F. Eberhardt, and M. J"arvisalo . 2014. Constraint-based causal discovery: Conflict resolution with answer set programming. Uncertainty in Artificial Intelligence (2014), 340--349.

Digital Library

[18]

A. Hyv"arinen and S.n M. Smith . 2013. Pairwise likelihood ratios for estimation of non-Gaussian structural equation models. Journal of Machine Learning Research Vol. 14 (2013), 111--152.

Digital Library

[19]

S. Imoto, T. Goto, and S. Miyano . 2002. Estimation of genetic networks and functional structures between genes by using Bayesian networks and nonparametric regression. Pacific Symposium on Biocomputing (2002), 175--186.

[20]

M. V. D. Laan, S. Dudoit, and S. Keles . 2004. Asymptotic optimality of likelihood-based cross-validation. Statistical Applications in Genetics and Molecular Biology Vol. 3(1) (2004), 1--23.

[21]

S. Meiri and T. Dayan . 2003. On the validity of Bergmann's rule. Journal of Biogeography Vol. 30(3) (2003), 331--351.

[22]

J. Pearl . 2000. Causality: Models, Reasoning, and Inference. Cambridge University Press New York.

Digital Library

[23]

A. N.V. Ruigrok, G. S. Khorshidi, M. Lai, S. B. Cohen, M. V. Lombardo, R. J. Tait, and J. Suckling . 2014. A meta-analysis of sex differences in human brain structure. Neuroscience and Biobehavioral Reviews Vol. 39 (2014), 34--50.

[24]

B. Schölkopf and A. J. Smola . 2002. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA.

Digital Library

[25]

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

[26]

E. Sokolova, P. Groot, T. Claassen, and T. Heskes . 2014. Causal discovery from databases with discrete and continuous variables. Workshop on Probabilistic Graphical Models (2014), 442--457.

[27]

P. Spirtes . 2010. Introduction to Causal Inference. Journal of Machine Learning Research Vol. 11 (2010), 1643--1662.

Digital Library

[28]

P. Spirtes, C. Glymour, and R. Scheines . 1993. Causation, Prediction, and Search. Spring-Verlag Lectures in Statistics.

[29]

P. Spirtes and K. Zhang . 2016. Causal discovery and inference: Concepts and recent methodological advances. Applied Informatics Vol. 3(3) (2016).

[30]

M. Springmann, D. Mason-DCroz, S. Robinson, P. Ballon, T. Garnett, and C. Godfray . 2016. The global and regional health impacts of future food production under climate change. The Lancet Vol. 387 (10031) (2016), 1937--1946.

[31]

I. Tsamardinos, L. E. Brown, and C. F. Aliferis . 2006. The max-min hill-climbing Bayesian network structure learning algorithm. Machine learning Vol. 65(1) (2006), 31--78.

Digital Library

[32]

K. Zhang, B. Huang, J. Zhang, C. Glymour, and B. Schölkopf . 2017. Causal discovery from nonstationary/heterogeneous data: Skeleton estimation and orientation determination. IJCAI (2017).

Digital Library

[33]

K Zhang and A. Hyv"arinen . 2009 a. Causality discovery with additive disturbances: An information-theoretical perspective. Machine learning and knowledge discovery in databases (2009), 570--585.

[34]

K. Zhang and A. Hyv"arinen . 2009 b. On the identifiability of the post-nonlinear causal model. UAI (2009), 647--655.

Digital Library

[35]

K. Zhang, J. Peters, D. Janzing, and B. Schölkopf . 2011. Kernel-based conditional independence test and application in causal discovery. Uncertainty in Artificial Intelligence (2011), 804--813.

Digital Library

[36]

K. Zhang, B. Schölkopf, P. Spirtes, and C. Glymour . 2018. Learning causality and causality-related learning: some recent progress. National Science Review Vol. 5(1) (2018), 26--29.

Cited By

Jung CJang Y(2024)Small dataset augmentation with radial basis function approximation for causal discovery using constraint‐based methodETRI Journal10.4218/etrij.2023-0397Online publication date: 2-Apr-2024
https://doi.org/10.4218/etrij.2023-0397
Gong KChen YSong XFu ZDing X(2024)Causal Inference for Hypertension Prediction (Preprint)JMIR Cardio10.2196/60238Online publication date: 6-May-2024
https://doi.org/10.2196/60238
Wang ZKrishnakumari PAnupam Kvan Lint HErkens S(2024)A causal discovery approach to study key mixed traffic‐related factors and age of highway affecting ravelingComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1322239:19(2861-2880)Online publication date: May-2024
https://doi.org/10.1111/mice.13222
Show More Cited By

Index Terms

Generalized Score Functions for Causal Discovery
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic representations
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Kernel methods

Recommendations

Generalised Partial Association in Causal Rules Discovery
Progress in Artificial Intelligence
Abstract
One of the most significant challenges for machine learning nowadays is the discovery of causal relationships from data. This causal discovery is commonly performed using Bayesian like algorithms. However, more recently, more and more causal ...
The Generalized Causal-Effect Score in Data Management (short paper)
GUIDE-AI '24: Proceedings of the Conference on Governance, Understanding and Integration of Data for Effective and Responsible AI

The Causal Effect is a numerical measure used to uncover and analyze causal relationships between variables. In particular, it deals with interventions on variables and their effects in the broad areas of observational studies and structural causality. ...
Causal Discovery via Causal Star Graphs
Discovering causal relationships among observed variables is an important research focus in data mining. Existing causal discovery approaches are mainly based on constraint-based methods and functional causal models (FCMs). However, the constraint-based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

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

July 2018

2925 pages

ISBN:9781450355520

DOI:10.1145/3219819

General Chairs:
Yike Guo
Imperial College London
,
Faisal Farooq
IBM

Copyright © 2018 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 ACM 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: 19 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

National Institutes of Health
United States Air Force

Conference

KDD '18

Sponsor:

KDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 19 - 23, 2018

London, United Kingdom

Acceptance Rates

KDD '18 Paper Acceptance Rate 107 of 983 submissions, 11%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
5,385
Total Downloads

Downloads (Last 12 months)1,033
Downloads (Last 6 weeks)133

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jung CJang Y(2024)Small dataset augmentation with radial basis function approximation for causal discovery using constraint‐based methodETRI Journal10.4218/etrij.2023-0397Online publication date: 2-Apr-2024
https://doi.org/10.4218/etrij.2023-0397
Gong KChen YSong XFu ZDing X(2024)Causal Inference for Hypertension Prediction (Preprint)JMIR Cardio10.2196/60238Online publication date: 6-May-2024
https://doi.org/10.2196/60238
Wang ZKrishnakumari PAnupam Kvan Lint HErkens S(2024)A causal discovery approach to study key mixed traffic‐related factors and age of highway affecting ravelingComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1322239:19(2861-2880)Online publication date: May-2024
https://doi.org/10.1111/mice.13222
Liu JHan LJi J(2024)MCAN: Multimodal Causal Adversarial Networks for Dynamic Effective Connectivity Learning From fMRI and EEG DataIEEE Transactions on Medical Imaging10.1109/TMI.2024.338167043:8(2913-2923)Online publication date: Aug-2024
https://doi.org/10.1109/TMI.2024.3381670
Guo XYu KLiu LLi JLiang JCao FWu X(2024)Progressive Skeleton Learning for Effective Local-to-Global Causal Structure LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.346183236:12(9065-9079)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3461832
Ji JHan LWang FLiu J(2024)Dynamic Effective Connectivity Learning Based on Nonparametric State Estimation and GANIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2023.333674873(1-12)Online publication date: 2024
https://doi.org/10.1109/TIM.2023.3336748
Li WZhang WZhang QZhang XWang X(2024)Weakly Supervised Causal Discovery Based on Fuzzy Knowledge and Complex Data ComplementarityIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2024.347118732:12(7002-7014)Online publication date: Dec-2024
https://doi.org/10.1109/TFUZZ.2024.3471187
Liu WHe YGuan JZhou S(2024)Multivariate Time Series Forecasting with Causal-Temporal Attention NetworkICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10448031(5735-5739)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10448031
Li YScheel-Sailer ARiener RPaez-Granados D(2024)Mixed-variable graphical modeling framework towards risk prediction of hospital-acquired pressure injury in spinal cord injury individualsScientific Reports10.1038/s41598-024-75691-914:1Online publication date: 23-Oct-2024
https://doi.org/10.1038/s41598-024-75691-9
Wu XZhong YLing ZYang JLi LSheng WJiang B(2024)Nonlinear learning method for local causal structuresInformation Sciences10.1016/j.ins.2023.119789654(119789)Online publication date: Jan-2024
https://doi.org/10.1016/j.ins.2023.119789
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents