Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten sv
dc.contributor University of Helsinki, Faculty of Science, Department of Computer Science en
dc.contributor Tietojenkäsittelytieteen tohtoriohjelma fi
dc.contributor Doktorandprogrammet i datavetenskap sv
dc.contributor Doctoral Programme in Computer Science en
dc.contributor.author Talvitie, Topi
dc.date.accessioned 2019-11-07T07:48:23Z
dc.date.available 2019-11-11
dc.date.available 2019-11-07T07:48:23Z
dc.date.issued 2019-11-21
dc.identifier.uri URN:ISBN:978-951-51-5610-5
dc.identifier.uri http://hdl.handle.net/10138/306782
dc.description.abstract Bayesian networks are probabilistic models that represent dependencies between random variables via directed acyclic graphs (DAGs). They provide a succinct representation for the joint distribution in cases where the dependency structure is sparse. Specifying the network by hand is often unfeasible, and thus it would be desirable to learn the model from observed data over the variables. In this thesis, we study computational problems encountered in different approaches to learning Bayesian networks. All of the problems involve counting or sampling DAGs under various constraints. One important computational problem in the fully Bayesian approach to structure learning is the problem of sampling DAGs from the posterior distribution over all the possible structures for the Bayesian network. From the typical modeling assumptions it follows that the distribution is modular, which means that the probability of each DAG factorizes into per-node weights, each of which depends only on the parent set of the node. For this problem, we give the first exact algorithm with a time complexity bound exponential in the number of nodes, and thus polynomial in the size of the input, which consists of all the possible per-node weights. We also adapt the algorithm such that it outperforms the previous methods in the special case of sampling DAGs from the uniform distribution. We also study the problem of counting the linear extensions of a given partial order, which appears as a subroutine in some importance sampling methods for modular distributions. This problem is a classic example of a #P-complete problem that can be approximately solved in polynomial time by reduction to sampling linear extensions uniformly at random. We present two new randomized approximation algorithms for the problem. The first algorithm extends the applicable range of an exact dynamic programming algorithm by using sampling to reduce the given instance into an easier instance. The second algorithm is obtained by combining a novel, Markov chain-based exact sampler with the Tootsie Pop algorithm, a recent generic scheme for reducing counting into sampling. Together, these two algorithms speed up approximate linear extension counting by multiple orders of magnitude in practice. Finally, we investigate the problem of counting and sampling DAGs that are Markov equivalent to a given DAG. This problem is important in learning causal Bayesian networks, because distinct Markov equivalent DAGs cannot be distinguished only based on observational data, yet they are different from the causal viewpoint. We speed up the state-of-the-art recursive algorithm for the problem by using dynamic programming. We also present a new, tree decomposition-based algorithm, which runs in linear time if the size of the maximum clique is bounded. en
dc.description.abstract Bayes-verkot mallintavat satunnaismuuttujien välisiä tilastollisia suhteita suunnattuina syklittöminä verkkoina, joissa solmut vastaavat satunnaismuuttujia ja kaaret niiden välisiä riippuvuuksia. Verkkorakenne havainnollistaa muuttujien kuvaaman ilmiön rakennetta ja mahdollistaa muuttujien yhteisjakauman esittämisen tiiviissä muodossa. Vaikka Bayes-verkko voidaan periaatteessa rakentaa käsin, se on epäkäytännöllistä, mikäli muuttujia on paljon tai mallinnettavaa ilmiötä ei ymmärretä täydellisesti. Tämän takia on hyödyllistä oppia verkon rakenne ilmiöstä kerätyn datan perusteella. Väitöskirjassa tutkitaan laskennallisia ongelmia, jotka liittyvät Bayes-verkon rakenteen oppimiseen. Kaikki nämä ongelmat koskevat suunnattujen syklittömien verkkojen laskemista tai satunnaisotantaa erilaisilla rajoitteilla. Yksi keskeinen ongelma Bayes-verkon rakenteen oppimisessa on rakenteen poiminta posteriorisatunnaisjakaumasta, joka painottaa parhaiten dataa vastaavia rakenteita. Väitöskirjassa esitellään tähän ongelmaan ensimmäinen eksakti algoritmi, joka hyödyntämällä posteriorijakauman erityisominaisuuksia saavuttaa polynomisen aikavaativuuden suhteessa jakauman määrittelevän tietorakenteen kokoon. Algoritmi tarjoaa myös aiempia algoritmeja tehokkaamman tavan suunnattujen syklittömien verkkojen poimintaan tasajakaumasta. Toinen väitöskirjassa tutkittu ongelma on osittaisjärjestyksen lineaariekstensioiden laskenta. Tämä ongelma tiedetään kuuluvaksi vaikeiden laskentaongelmien #P-luokkaan, mutta se voidaan silti ratkaista likimäärisesti polynomisessa ajassa palauttamalla se vastaavaan satunnaisotantaongelmaan. Väitöskirja esittelee kaksi uutta likimääräistä satunnaisalgoritmia lineaariekstensioiden laskentaan. Ensimmäinen algoritmi muuttaa tunnetun eksaktin laskenta-algoritmin likimääräiseksi yhdistämällä siihen satunnaisotokseen perustuvaa arviointia. Toinen algoritmi palauttaa laskentaongelman uuteen Markovin ketjuihin perustuvan satunnaisotantamenetelmään. Yhdessä nämä kaksi algoritmia nopeuttavat käytännön tapauksissa likimääräistä lineaariekstensioiden laskentaa usealla kertaluokalla. Työn loppuosassa tutkitaan tietyssä Markov-ekvivalenssiluokassa olevien suunnattujen syklittömien verkkojen laskenta- ja satunnaisotantaongelmia. Ongelma on tärkeä Bayes-verkkojen käytössä kausaalisten riippuvuuksien mallintamiseen, koska Markov-ekvivalentteja rakenteita ei voi erottaa pelkästään havaintodatan perusteella, vaikka ne ovat kausaalisesta näkökulmasta erilaisia. Työssä esitellään tapa nopeuttaa parasta tunnettua algoritmia dynaamisen ohjelmoinnin avulla. Tämän lisäksi väitöskirja esittelee uuden verkon puuhajotelmaan perustuvan menetelmän, jonka aikavaativuus on lineaarinen, mikäli verkon suurimman klikin koko on rajoitettu. fi
dc.format.mimetype application/pdf
dc.language.iso en
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-951-51-5609-9
dc.relation.isformatof Helsinki: University of Helsinki, 2019, Department of Computer Science, Series of Publications A. 1238-8645
dc.relation.ispartof Department of Computer Science, Series of Publications A
dc.relation.ispartof URN:ISSN:1238-8645
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject computer science
dc.title Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Doktorsavhandling (sammanläggning) sv
dc.ths Koivisto, Mikko
dc.ths Polishchuk, Valentin
dc.opn Meel, Kuldeep
dc.type.dcmitype Text

Files in this item

Total number of downloads: Loading...

Files Size Format View
Counting.pdf 828.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record