Counting and Sampling Markov Equivalent Directed Acyclic Graphs

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/306070

Lähdeviite

Talvitie , T & Koivisto , M 2019 , Counting and Sampling Markov Equivalent Directed Acyclic Graphs . in THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE . AAAI Press , Palo Alto, CA , pp. 7984-7991 , 33rd AAAI Conference on Artificial Intelligence , Honolulu , Hawaii , United States , 27/01/2019 . < https://aaai.org/ojs/index.php/AAAI/article/view/4799/4677 >

Julkaisun nimi: Counting and Sampling Markov Equivalent Directed Acyclic Graphs
Tekijä: Talvitie, Topi; Koivisto, Mikko
Tekijän organisaatio: Department of Computer Science
Julkaisija: AAAI Press
Päiväys: 2019
Kieli: eng
Sivumäärä: 8
Kuuluu julkaisusarjaan: THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
ISBN: 978-1-57735-809-1
URI: http://hdl.handle.net/10138/306070
Tiivistelmä: Exploring directed acyclic graphs (DAGs) in a Markov equivalence class is pivotal to infer causal effects or to discover the causal DAG via appropriate interventional data. We consider counting and uniform sampling of DAGs that are Markov equivalent to a given DAG. These problems efficiently reduce to counting the moral acyclic orientations of a given undirected connected chordal graph on n vertices, for which we give two algorithms. Our first algorithm requires O(2(n)n(4)) arithmetic operations, improving a previous super-exponential upper bound. The second requires O (k! 2(k) k(2)n) operations, where k is the size of the largest clique in the graph; for bounded-degree graphs this bound is linear in n. After a single run, both algorithms enable uniform sampling from the equivalence class at a computational cost linear in the graph size. Empirical results indicate that our algorithms are superior to previously presented algorithms over a range of inputs; graphs with hundreds of vertices and thousands of edges are processed in a second on a desktop computer.
Avainsanat: ENUMERATION
NUMBER
113 Computer and information sciences
Vertaisarvioitu: Kyllä
Tekijänoikeustiedot: unspecified
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: publishedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
4799_Article_Text_7838_1_10_20190708.pdf 804.2KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot