Top

Published in:

2021 | OriginalPaper | Chapter

An Approach to Reduce the Number of Conditional Independence Tests in the PC Algorithm

Authors : Marcel Wienöbst, Maciej Liśkiewicz

Published in: KI 2021: Advances in Artificial Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The PC algorithm is one of the most prominent constraint-based methods for learning causal structures from observational data. The algorithm relies on conditional independence (CI) tests to infer the structure and its time consumption heavily depends on the number of performed CI tests. We present a modification, called ED-PC, such that – in the oracle model – both ED-PC and the original PC algorithm infer the same structure. However, by using a new idea allowing the detection of a v-structure without explicit knowledge of a separating set, our method reduces the number of needed CI tests significantly. This is made possible by detecting nonadjacencies considerably earlier.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Recent Advances in Counting and Sampling Markov Equivalent DAGs

next chapter Unsupervised Anomaly Detection for Financial Auditing with Model-Agnostic Explanations

For exact definitions of the notions used in the algorithm, see Sect. 2.

We use iff as shorthand for “if and only if”.

Andersson, S.A., Madigan, D., Perlman, M.D.: A characterization of Markov equivalence classes for acyclic digraphs. Ann. Stat. 25(2), 505–541 (1997)MathSciNetMATH

Baba, K., Shibata, R., Sibuya, M.: Partial correlation and conditional correlation as measures of conditional independence. Aust. N. Z. J. Stat. 46(4), 657–664 (2004)MathSciNetCrossRef

Bergsma, W.P.: Testing conditional independence for continuous random variables. Eurandom (2004)

Colombo, D., Maathuis, M.H., Kalisch, M., Richardson, T.S.: Learning high-dimensional directed acyclic graphs with latent and selection variables. Ann. Stat. 40, 294–321 (2012)MathSciNetCrossRef

Doran, G., Muandet, K., Zhang, K., Schölkopf, B.: A permutation-based kernel conditional independence test. In: UAI, pp. 132–141 (2014)

Harris, N., Drton, M.: PC algorithm for nonparanormal graphical models. J. Mach. Learn. Res. 14(1), 3365–3383 (2013)MathSciNetMATH

Kalisch, M., Bühlmann, P.: Estimating high-dimensional directed acyclic graphs with the PC-Algorithm. J. Mach. Learn. Res. 8, 613–636 (2007)MATH

Meek, C.: Causal inference and causal explanation with background knowledge. In: Proceedings of UAI 1995, pp. 403–410. MK Publishers Inc. (1995)

Pearl, J.: Causality: Models, Reasoning and Inference, 2nd edn. Cambridge University Press, Cambridge (2009)CrossRef

10.

Scutari, M.: Learning Bayesian networks with the bnlearn R package. J. Stat. Softw. 35(3), 1–22 (2010)

11.

Sondhi, A., Shojaie, A.: The reduced PC-algorithm: improved causal structure learning in large random networks. J. Mach. Learn. Res. 20(164), 1–31 (2019)MathSciNetMATH

12.

Spirtes, P., Glymour, C., Scheines, R.: Causation, Prediction, and Search, 2nd edn. MIT Press, Cambridge (2000)MATH

13.

Talvitie, T., Parviainen, P.: Learning Bayesian networks with cops and robbers. In: The 10th International Conference on Probabilistic Graphical Models (2020)

14.

Verma, T., Pearl, J.: Equivalence and synthesis of causal models. In: Proceedings of UAI 1990, pp. 255–270. Elsevier (1990)

15.

Wienöbst, M., Liśkiewicz, M.: Recovering causal structures from low-order conditional independencies. In: 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 10302–10309 (2020)

16.

Zhang, H., Zhou, S., Zhang, K., Guan, J.: Causal discovery using regression-based conditional independence tests. In: Thirty-First AAAI Conference on Artificial Intelligence (2017)

17.

Zhang, K., Peters, J., Janzing, D., Schölkopf, B.: Kernel-based conditional independence test and application in causal discovery. In: 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), pp. 804–813. AUAI Press (2011)

Title: An Approach to Reduce the Number of Conditional Independence Tests in the PC Algorithm
Authors: Marcel Wienöbst
Maciej Liśkiewicz
Publisher: Springer International Publishing
Book: KI 2021: Advances in Artificial Intelligence
Print ISBN: 978-3-030-87625-8

Electronic ISBN: 978-3-030-87626-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-87626-5_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"