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.

[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

Gon g KChen YSong XFu ZDing X(2025)Causal Inference for Hypertension Prediction With Wearable E lectrocardiogram and P hotoplethysmogram Signals: Feasibility StudyJMIR Cardio10.2196/602389(e60238-e60238)Online publication date: 23-Jan-2025
https://doi.org/10.2196/60238
Qiu CYang K(2025)Interventional Causal Structure Discovery Over Graphical Models With Convergence and Optimality GuaranteesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.348730112:1(156-172)Online publication date: Jan-2025
https://doi.org/10.1109/TNSE.2024.3487301
Tao ZChi MChen LBan TTu QGao FWang W(2025)Clinical causal analysis via iterative active structure learningMemetic Computing10.1007/s12293-025-00439-517:1Online publication date: 22-Feb-2025
https://doi.org/10.1007/s12293-025-00439-5
Show More Cited By

Recommendations

D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery
Causal reasoning is a crucial part of science and human intelligence. In order to discover causal relationships from data, we need structure discovery methods. We provide a review of background theory and a survey of methods for structure discovery. We ...
A Survey on Causal Inference

Causal inference is a critical research topic across many domains, such as statistics, computer science, education, public policy, and economics, for decades. Nowadays, estimating causal effect from observational data has become an appealing research ...
A Survey of Learning Causality with Data: Problems and Methods

This work considers the question of how convenient access to copious data impacts our ability to learn causal effects and relations. In what ways is learning causality in the era of big data different from—or the same as—the traditional one? To answer ...

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

51
Total Citations
View Citations
5,652
Total Downloads

Downloads (Last 12 months)1,071
Downloads (Last 6 weeks)141

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gon g KChen YSong XFu ZDing X(2025)Causal Inference for Hypertension Prediction With Wearable E lectrocardiogram and P hotoplethysmogram Signals: Feasibility StudyJMIR Cardio10.2196/602389(e60238-e60238)Online publication date: 23-Jan-2025
https://doi.org/10.2196/60238
Qiu CYang K(2025)Interventional Causal Structure Discovery Over Graphical Models With Convergence and Optimality GuaranteesIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.348730112:1(156-172)Online publication date: Jan-2025
https://doi.org/10.1109/TNSE.2024.3487301
Tao ZChi MChen LBan TTu QGao FWang W(2025)Clinical causal analysis via iterative active structure learningMemetic Computing10.1007/s12293-025-00439-517:1Online publication date: 22-Feb-2025
https://doi.org/10.1007/s12293-025-00439-5
Zhang WLi YYang BLu ZSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Tackling non-stationarity in reinforcement learning via causal-origin representationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694518(59264-59288)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694518
Wang WHuang BLiu FYou XLiu TZhang KGong MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Optimal kernel choice for score function-based causal discoveryProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694143(50650-50668)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694143
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
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
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

Figures

Tables

Media

View Table of Conten