Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Elektrische Antriebe und Energiesysteme 2025 | 26 + 27 März 2025

19. Internationaler MTZ-Fachkongress Zukunftsantriebe

Seien Sie bei der Konferenz dabei! Dort treffen Experten aus der Automobilindustrie, Energieerzeugung und Stromnetzbetrieb auf Vertreter aus Politik und Wissenschaft. Diskutiert werden wichtige Themen der Branche.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2021 | OriginalPaper | Buchkapitel

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

verfasst von : Marcel Wienöbst, Maciej Liśkiewicz

Erschienen in: KI 2021: Advances in Artificial Intelligence

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Recent Advances in Counting and Sampling Markov Equivalent DAGs
Nächstes Kapitel Unsupervised Anomaly Detection for Financial Auditing with Model-Agnostic Explanations
Fußnoten
1
For exact definitions of the notions used in the algorithm, see Sect. 2.
 
2
We use iff as shorthand for “if and only if”.
 
Literatur
1.
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
2.
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
3.
Bergsma, W.P.: Testing conditional independence for continuous random variables. Eurandom (2004)
4.
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
5.
Doran, G., Muandet, K., Zhang, K., Schölkopf, B.: A permutation-based kernel conditional independence test. In: UAI, pp. 132–141 (2014)
6.
Harris, N., Drton, M.: PC algorithm for nonparanormal graphical models. J. Mach. Learn. Res. 14(1), 3365–3383 (2013)MathSciNetMATH
7.
Kalisch, M., Bühlmann, P.: Estimating high-dimensional directed acyclic graphs with the PC-Algorithm. J. Mach. Learn. Res. 8, 613–636 (2007)MATH
8.
Meek, C.: Causal inference and causal explanation with background knowledge. In: Proceedings of UAI 1995, pp. 403–410. MK Publishers Inc. (1995)
9.
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)
Metadaten
Titel
An Approach to Reduce the Number of Conditional Independence Tests in the PC Algorithm
verfasst von
Marcel Wienöbst
Maciej Liśkiewicz
Copyright-Jahr
2021
Buch
KI 2021: Advances in Artificial Intelligence

Print ISBN: 978-3-030-87625-8

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

Copyright-Jahr: 2021

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

Premium Partner

    Bildnachweise