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
Heavy-Duty Engines 2025 | 18. + 19. November 2025

Nutzfahrzeuge | Land- und Baumaschinen | Marine

Nehmen Sie als Referent an der 20. Internationalen MTZ-Fachtagung für Erfahrungsaustausch zu Industrie- und Nfz-Motoren teil. Reichen Sie online einen Themenvorschlag ein!
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2021 | OriginalPaper | Buchkapitel

Recent Advances in Counting and Sampling Markov Equivalent DAGs

verfasst von : Marcel Wienöbst, Max Bannach, 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

Counting and sampling directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we discuss recently proposed polynomial-time algorithms for these tasks. The presented result solves a long-standing open problem in graphical modelling. Experiments show that the proposed algorithms are implementable and effective in practice. Our paper is an extended abstract of the work [24], honored as an AAAI-21 Distinguished Paper at the 35th AAAI Conference on Artificial Intelligence.

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 Demystifying Artificial Intelligence for End-Users: Findings from a Participatory Machine Learning Show
Nächstes Kapitel An Approach to Reduce the Number of Conditional Independence Tests in the PC Algorithm
Literatur
1.
AhmadiTeshnizi, A., Salehkaleybar, S., Kiyavash, N.: Lazyiter: a fast algorithm for counting Markov equivalent DAGs and designing experiments. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020 (2020)
2.
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
3.
Chickering, D.M.: Learning equivalence classes of Bayesian-network structures. J. Mach. Learn. Res. 2, 445–498 (2002)MathSciNetMATH
4.
Chickering, D.M.: Optimal structure identification with greedy search. J. Mach. Learn. Res. 3, 507–554 (2002)MathSciNetMATH
5.
Ganian, R., Hamm, T., Talvitie, T.: An efficient algorithm for counting Markov equivalent dags. In: Proccedings of the 34th Conference on Artificial Intelligence, AAAI 2020, pp. 10136–10143 (2020)
6.
Ghassami, A., Salehkaleybar, S., Kiyavash, N., Bareinboim, E.: Budgeted experiment design for causal structure learning. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, pp. 1719–1728 (2018)
7.
Ghassami, A., Salehkaleybar, S., Kiyavash, N., Zhang, K.: Counting and sampling from Markovv equivalent dags using clique trees. In: Proceedings of the 33th Conference on Artificial Intelligence, AAAI 2019, pp. 3664–3671 (2019)
8.
Hauser, A., Bühlmann, P.: Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. J. Mach. Learn. Res. 13, 2409–2464 (2012)MathSciNetMATH
9.
He, Y.B., Geng, Z.: Active learning of causal networks with intervention experiments and optimal designs. J. Mach. Learn. Res. 9(Nov), 2523–2547 (2008)
10.
He, Y., Jia, J., Yu, B.: Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs. J. Mach. Learn. Res. 16(79), 2589–2609 (2015)MathSciNetMATH
11.
Heckerman, D., Geiger, D., Chickering, D.M.: Learning Bayesian networks: the combination of knowledge and statistical data. Mach. Learn. 20(3), 197–243 (1995)MATH
12.
Koller, D., Friedman, N.: Probabilistic Graphical Models - Principles and Techniques. MIT Press, Cambridge (2009)
13.
Maathuis, M.H., Kalisch, M., Bühlmann, P.: Estimating high-dimensional intervention effects from observational data. Ann. Stat. 37(6A), 3133–3164 (2009)MathSciNetCrossRef
14.
Madigan, D., Andersson, S.A., Perlman, M.D., Volinsky, C.T.: Bayesian model averaging and model selection for Markov equivalence classes of acyclic digraphs. Commun. Stat. Theory Methods 25(11), 2493–2519 (1996)CrossRef
15.
Meek, C.: Causal inference and causal explanation with background knowledge. In: Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, UAI 1995, pp. 403–410 (1995)
16.
Meek, C.: Graphical Models: Selecting Causal and Statistical Models. Ph.D. thesis, Carnegie Mellon University (1997)
17.
Pearl, J.: Causality. Cambridge University Press, Cambridge (2009)
18.
Perković, E., Textor, J., Kalisch, M., Maathuis, M.H.: Complete graphical characterization and construction of adjustment sets in Markov equivalence classes of ancestral graphs. J. Mach. Learn. Res. 18, 220:1–220:62 (2017)
19.
Shanmugam, K., Kocaoglu, M., Dimakis, A.G., Vishwanath, S.: Learning causal graphs with small interventions. In: Processing of the 28th Annual Conference on Neural Information Processing Systems, NIPS 2015, pp. 3195–3203 (2015)
20.
Spirtes, P., Glymour, C., Scheines, R.: Causation, Prediction, and Search, Second Edition. MIT Press, Cambridge (2000)
21.
Talvitie, T., Koivisto, M.: Counting and sampling Markov equivalent directed acyclic graphs. In: Proceedings of the 33th Conference on Artificial Intelligence, AAAI 2019, pp. 7984–7991 (2019)
22.
Verma, T., Pearl, J.: Equivalence and synthesis of causal models. In: Proceedings of the 6th Annual Conference on Uncertainty in Artificial Intelligence, UAI 1990, pp. 255–270 (1990)
23.
Verma, T., Pearl, J.: An algorithm for deciding if a set of observed independencies has a causal explanation. In: Proceedings of the 8th Annual Conference on Uncertainty in Artificial Intelligence, UAI 1992, pp. 323–330 (1992)
24.
Wienöbst, M., Bannach, M., Liśkiewicz, M.: Polynomial-time algorithms for counting and sampling Markov equivalent dags. In: Proccedings of the 35th Conference on Artificial Intelligence, AAAI 2021 (2021, in press)
25.
van der Zander, B., Liśkiewicz, M.: Separators and adjustment sets in Markov equivalent dags. In: Proceedings of the 30th Conference on Artificial Intelligence, AAAI 2016, pp. 3315–3321 (2016)
Metadaten
Titel
Recent Advances in Counting and Sampling Markov Equivalent DAGs
verfasst von
Marcel Wienöbst
Max Bannach
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_20

Premium Partner

    Bildnachweise