Top

Published in:

2021 | OriginalPaper | Chapter

Recent Advances in Counting and Sampling Markov Equivalent DAGs

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

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.

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 Demystifying Artificial Intelligence for End-Users: Findings from a Participatory Machine Learning Show

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

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)

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

Chickering, D.M.: Learning equivalence classes of Bayesian-network structures. J. Mach. Learn. Res. 2, 445–498 (2002)MathSciNetMATH

Chickering, D.M.: Optimal structure identification with greedy search. J. Mach. Learn. Res. 3, 507–554 (2002)MathSciNetMATH

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)

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)

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)

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

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)

Title: Recent Advances in Counting and Sampling Markov Equivalent DAGs
Authors: Marcel Wienöbst
Max Bannach
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_20

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"