article

Free access

Ultra-scalable and efficient methods for hybrid observational and experimental local causal pathway discovery

Authors:

Alexander Statnikov,

Efstratios Efstathiadis,

Eric R. Peskin,

Constantin F. AliferisAuthors Info & Claims

The Journal of Machine Learning Research, Volume 16, Issue 1

Pages 3219 - 3267

Published: 01 January 2015 Publication History

PDF eReader Publisher Site

Abstract

Discovery of causal relations from data is a fundamental objective of several scientific disciplines. Most causal discovery algorithms that use observational data can infer causality only up to a statistical equivalency class, thus leaving many causal relations undetermined. In general, complete identification of causal relations requires experimentation to augment discoveries from observational data. This has led to the recent development of several methods for active learning of causal networks that utilize both observational and experimental data in order to discover causal networks. In this work, we focus on the problem of discovering local causal pathways that contain only direct causes and direct effects of the target variable of interest and propose new discovery methods that aim to minimize the number of required experiments, relax common sufficient discovery assumptions in order to increase discovery accuracy, and scale to high-dimensional data with thousands of variables. We conduct a comprehensive evaluation of new and existing methods with data of dimensionality up to 1,000,000 variables. We use both artificially simulated networks and in-silico gene transcriptional networks that model the characteristics of real gene expression data.

References

[1]

Constantin F Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, and Xenofon D Koutsoukos. Local causal and markov blanket induction for causal discovery and feature selection for classification part i: Algorithms and empirical evaluation. The Journal of Machine Learning Research, 11:171-234, 2010a.

Digital Library

[2]

Constantin F Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, and Xenofon D Koutsoukos. Local causal and markov blanket induction for causal discovery and feature selection for classification part ii: Analysis and extensions. The Journal of Machine Learning Research, 11:235-284, 2010b.

Digital Library

[3]

Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series B (Methodological), pages 289-300, 1995.

[4]

Yoav Benjamini and Daniel Yekutieli. The control of the false discovery rate in multiple testing under dependency. Annals of Statistics, pages 1165-1188, 2001.

[5]

David Maxwell Chickering. Optimal structure identification with greedy search. The Journal of Machine Learning Research, 3:507-554, 2003.

Digital Library

[6]

Diego Colombo and Marloes H Maathuis. Order-independent constraint-based causal structure learning. The Journal of Machine Learning Research, 15(1):3741-3782, 2014.

Digital Library

[7]

Povilas Daniusis, Dominik Janzing, Joris Mooij, Jakob Zscheischler, Bastian Steudel, Kun Zhang, and Bernhard Schölkopf. Inferring deterministic causal relations. arXiv preprint arXiv:1203.3475, 2012.

[8]

Edward R Dougherty and Marcel Brun. On the number of close-to-optimal feature sets. Cancer Informatics, 2:189, 2006.

[9]

Frederick Eberhardt, Patrik O Hoyer, and Richard Scheines. Combining experiments to discover linear cyclic models with latent variables. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 185-192, 2010.

[10]

Clark N. Glymour and Gregory F. Cooper. Computation, Causation, and Discovery. AAAI Press ; MIT Press, Menlo Park, California, 1999.

[11]

Isabelle Guyon, Constantin F Aliferis, Gregory F Cooper, André Elisseeff, Jean-Philippe Pellet, Peter Spirtes, and Alexander R Statnikov. Design and analysis of the causation and prediction challenge. In WCCI Causation and Prediction Challenge, pages 1-33, 2008.

[12]

Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(11), 2008.

[13]

Patrik O Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, pages 689-696, 2009.

Digital Library

[14]

Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Causal discovery for linear cyclic models with latent variables. on Probabilistic Graphical Models, page 153, 2010.

[15]

Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Learning linear cyclic causal models with latent variables. The Journal of Machine Learning Research, 13(1):3387- 3439, 2012.

Digital Library

[16]

Dominik Janzing, Joris Mooij, Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis, Bastian Steudel, and Bernhard Schölkopf. Information-geometric approach to inferring causal directions. Artificial Intelligence, 182:1-31, 2012.

Digital Library

[17]

Jan Lemeire. Learning Causal Models of Multivariate Systems and the Value of it for the Performance Modeling of Computer Programs. PhD thesis, Vrije Universiteit Brussel, 2007.

[18]

Daniel Marbach, Thomas Schaffter, Claudio Mattiussi, and Dario Floreano. Generating realistic in silico gene networks for performance assessment of reverse engineering methods. Journal of Computational Biology, 16(2):229-239, 2009.

[19]

Stijn Meganck, Philippe Leray, and Bernard Manderick. Learning causal bayesian networks from observations and experiments: A decision theoretic approach. In Proceedings of the Third International Conference on Modeling Decisions for Artificial Intelligence, MDAI'06, pages 58-69, Berlin, Heidelberg, 2006. Springer-Verlag.

Digital Library

[20]

Joshua Menke and Tony R Martinez. Using permutations instead of student's t distribution for p-values in paired-difference algorithm comparisons. In Neural Networks, 2004. Proceedings. 2004 IEEE International Joint Conference on, volume 2, pages 1331-1335. IEEE, 2004.

[21]

Joris Mooij, Oliver Stegle, Dominik Janzing, Kun Zhang, and Bernhard Schölkopf. Probabilistic latent variable models for distinguishing between cause and effect. In Advances in Neural Information Processing Systems, pages 1687-1695, 2010.

[22]

Kevin P Murphy. Active learning of causal bayes net structure, 2001.

[23]

Richard E. Neapolitan. Learning Bayesian Networks. Prentice Hall, illustrated edition edition, April 2003. ISBN 0130125342.

Digital Library

[24]

Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, 1 edition, September 1997. ISBN 9781558604797.

[25]

Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2009. ISBN 052189560X, 9780521895606.

Digital Library

[26]

Dana Pe'er, Aviv Regev, Gal Elidan, and Nir Friedman. Inferring subnetworks from perturbed expression profiles. Bioinformatics, 17, 2001.

[27]

Jose M Peña, Roland Nilsson, Johan Björkegren, and Jesper Tegnér. Towards scalable and data efficient learning of markov boundaries. International Journal of Approximate Reasoning, 45(2):211-232, 2007.

Digital Library

[28]

Joseph Ramsey, Jiji Zhang, and Peter L Spirtes. Adjacency-faithfulness and conservative causal inference. In Proceedings of the 22nd Annual Conference on Uncertainty in Artificial Intelligence (UAI-2006), pages 401-408, 2006.

[29]

Thomas Richardson. A discovery algorithm for directed cyclic graphs. In Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence, pages 454-461. Morgan Kaufmann Publishers Inc., 1996.

Digital Library

[30]

Thomas Richardson and Peter Spirtes. Automated Discovery of Linear Feedback Models, chapter 7, pages 254-302. MIT Press, 1999.

[31]

Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721):523-529, 2005.

[32]

Thomas Schaffter, Daniel Marbach, and Dario Floreano. Genenetweaver: in silico benchmark generation and performance profiling of network inference methods. Bioinformatics, 27(16):2263-2270, 2011.

Digital Library

[33]

Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. The Journal of Machine Learning Research, 7:2003-2030, 2006.

Digital Library

[34]

Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, Prediction, and Search, volume 81. MIT press, 2000.

[35]

Alexander Statnikov and Constantin F Aliferis. Analysis and computational dissection of molecular signature multiplicity. PLoS Computational Biology, 6(5):e1000790, 2010.

[36]

Alexander Statnikov, Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. Causal explorer: A matlab library of algorithms for causal discovery and variable selection for classification, volume 2, page 267. Microtome Publishing, 2010.

[37]

Alexander Statnikov, Mikael Henaff, Nikita I Lytkin, and Constantin F Aliferis. New methods for separating causes from effects in genomics data. BMC Genomics, 13, 2012.

[38]

Alexander Statnikov, Jan Lemeir, and Constantin F Aliferis. Algorithms for discovery of multiple markov boundaries. The Journal of Machine Learning Research, 14(1):499-566, 2013.

Digital Library

[39]

Simon Tong and Daphne Koller. Active learning for structure in bayesian networks. In Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 2, IJCAI'01, pages 863-869, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.

Digital Library

[40]

Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, 2006a.

Digital Library

[41]

Ioannis Tsamardinos, Alexander R Statnikov, Laura E Brown, and Constantin F Aliferis. Generating realistic large bayesian networks by tiling. In FLAIRS Conference, pages 592-597, 2006b.

[42]

Jianxin Yin, You Zhou, Changzhang Wang, Ping He, Cheng Zheng, and Zhi Geng. Partial orientation and local structural learning of causal networks for prediction. In WCCI Causation and Prediction Challenge, pages 93-105, 2008.

[43]

Kun Zhang and Aapo Hyvärinen. Distinguishing causes from effects using nonlinear acyclic causal models. In Journal of Machine Learning Research, Workshop and Conference Proceedings (NIPS 2008 causality workshop), volume 6, pages 157-164, 2008.

Cited By

Mian OMameche SVreeken JBaeza-Yates RBonchi F(2024)Learning Causal Networks from Episodic DataProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671999(2224-2235)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671999
Mian OKamp MVreeken JWilliams BChen YNeville J(2023)Information-theoretic causal discovery and intervention detection over multiple environmentsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i8.26100(9171-9179)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i8.26100
Yu KGuo XLiu LLi JWang HLing ZWu X(2020)Causality-based Feature SelectionACM Computing Surveys10.1145/340938253:5(1-36)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3409382

Ultra-scalable and efficient methods for hybrid observational and experimental local causal pathway discovery
1. Computing methodologies

Recommendations

A Simple Constraint-Based Algorithm for Efficiently Mining Observational Databases for Causal Relationships

This paper presents a simple, efficient computer-based method for discovering causal relationships from databases that contain observational data. Observational data is passively observed, as contrasted with experimental data. Most of the databases ...
Experiment selection for causal discovery

Randomized controlled experiments are often described as the most reliable tool available to scientists for discovering causal relationships among quantities of interest. However, it is often unclear how many and which different experiments are needed to ...
Disentangling causality: assumptions in causal discovery and inference
Abstract
Causality has been a burgeoning field of research leading to the point where the literature abounds with different components addressing distinct parts of causality. For researchers, it has been increasingly difficult to discern the assumptions ...

Comments

Information & Contributors

Information

Published In

The Journal of Machine Learning Research Volume 16, Issue 1

January 2015

3855 pages

ISSN:1532-4435

EISSN:1533-7928

Editors:
Kevin Murphy
Google
,
Bernhard Schölkopf
MPI for Intelligent Systems

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Revised: 01 April 2015

Published: 01 January 2015

Published in JMLR Volume 16, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)16

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mian OMameche SVreeken JBaeza-Yates RBonchi F(2024)Learning Causal Networks from Episodic DataProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671999(2224-2235)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671999
Mian OKamp MVreeken JWilliams BChen YNeville J(2023)Information-theoretic causal discovery and intervention detection over multiple environmentsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i8.26100(9171-9179)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i8.26100
Yu KGuo XLiu LLi JWang HLing ZWu X(2020)Causality-based Feature SelectionACM Computing Surveys10.1145/340938253:5(1-36)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3409382

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents