Algorithms for Exact Structure Discovery in Bayesian Networks

Bayesian networks are compact, flexible, and interpretable representations of a joint distribution. When the network structure is unknown but there are observational data at hand, one can try to learn the network structure. This is called structure discovery. This thesis contributes to two areas of structure discovery in Bayesian networks: space--time tradeoffs and learning ancestor relations. The fastest exact algorithms for structure discovery in Bayesian networks are based on dynamic programming and use excessive amounts of space. Motivated by the space usage, several schemes for trading space against time are presented. These schemes are presented in a general setting for a class of computational problems called permutation problems; structure discovery in Bayesian networks is seen as a challenging variant of the permutation problems. The main contribution in the area of the space--time tradeoffs is the partial order approach, in which the standard dynamic programming algorithm is extended to run over partial orders. In particular, a certain family of partial orders called parallel bucket orders is considered. A partial order scheme that provably yields an optimal space--time tradeoff within parallel bucket orders is presented. Also practical issues concerning parallel bucket orders are discussed. Learning ancestor relations, that is, directed paths between nodes, is motivated by the need for robust summaries of the network structures when there are unobserved nodes at work. Ancestor relations are nonmodular features and hence learning them is more difficult than modular features. A dynamic programming algorithm is presented for computing posterior probabilities of ancestor relations exactly. Empirical tests suggest that ancestor relations can be learned from observational data almost as accurately as arcs even in the presence of unobserved nodes.

Algoritmeja Bayes-verkkojen rakenteen tarkkaan oppimiseen Bayes-verkot ovat todennäköisyysmalleja, joiden avulla voidaan kuvata muuttujien välisiä suhteita. Bayes-verkko koostuu kahdesta osasta: rakenteesta ja kuhunkin muuttujaan liittyvästä ehdollisesta todennäköisyysjakaumasta. Rakenteen puolestaan muodostaa muuttujien välisiä riippuvuuksia kuvaava suunnattu syklitön verkko. Kun tarkasteltavaa ilmiötä hyvin kuvaavaa Bayes-verkkoa ei tunneta ennalta, mutta ilmiöön liittyvistä muuttujista on kerätty havaintoaineistoa, voidaan sopivia algoritmeja käyttäen yrittää löytää verkkorakenne, joka sovittuu aineistoon mahdollisimman hyvin. Nopeimmat tarkat rakenteenoppimisalgoritmit perustuvat niin kutsuttuun dynaamiseen ohjelmointiin, eli ne pitävät välituloksia muistissa ja näin välttävät suorittamasta samoja laskuja useaan kertaan. Vaikka tällaiset menetelmät ovat suhteellisen nopeita, niiden haittapuolena on suuri muistinkäyttö, joka estää suurten verkkojen rakenteen oppimisen. Väitöskirjan alkuosa käsittelee rakenteenoppimisalgoritmeja, jotka tasapainottelevat ajan- ja muistinkäytön välillä. Kirjassa esitellään menetelmiä, joilla verkon rakenne voidaan oppia tehokkaasti käyttäen hyväksi kaikki käytössä oleva tila. Uusi menetelmä mahdollistaa entistä suurempien verkkojen rakenteen oppimisen. Edellä mainittu menetelmä yleistetään ratkaisemaan Bayes-verkkojen rakenteenoppimisen lisäksi myös niin kutsuttuja permutaatio-ongelmia, joista tunnetuin lienee kauppamatkustajan ongelma. Väitöskirjan loppuosa käsittelee muuttujien välisien esi-isäsuhteiden oppimista. Kyseiset suhteet ovat kiinnostavia, sillä ne antavat lisätietoa muuttujien sekä suorista että epäsuorista syy-seuraussuhteista. Väitöskirjassa esitetään algoritmi esi-isäsuhteiden todennäköisyyksien laskemiseen. Algoritmin toimintaa tutkitaan käytännössä ja todetaan, että esi-isäsuhteita pystytään oppimaan melko hyvin jopa silloin, kun useat havaitsemattomat muuttujat vaikuttavat aineiston muuttujiin.