Combinatorial Algorithms with Applications in Learning Graphical Models

Graphical models are a framework for representing joint distributions over random variables. By capturing the structure of conditional independencies between the variables, a graphical model can express the distribution in a concise factored form that is often efficient to store and reason about. As constructing graphical models by hand is often infeasible, a lot of work has been devoted to learning them automatically from observational data. Of particular interest is the so-called structure learning problem, of finding a graph that encodes the structure of probabilistic dependencies. Once the learner has decided what constitutes a good fit to the data, the task of finding optimal structures typically involves solving an NP-hard problem of combinatorial optimization. While first algorithms for structure learning thus resorted to local search, there has been a growing interest in solving the problem to a global optimum. Indeed, during the past decade multiple exact algorithms have been proposed that are guaranteed to find optimal structures for the family of Bayesian networks, while first steps have been taken for the family of decomposable graphical models. This thesis presents combinatorial algorithms and analytical results with applications in the structure learning problem. For decomposable models, we present exact algorithms for the so-called full Bayesian approach, which involves not only finding individual structures of good fit but also computing posterior expectations of graph features, either by exact computation or via Monte Carlo methods. For Bayesian networks, we study the empirical hardness of the structure learning problem, with the aim of being able to predict the running time of various structure learning algorithms on a given problem instance. As a result, we obtain a hybrid algorithm that effectively combines the best-case performance of multiple existing techniques. Lastly, we study two combinatorial problems of wider interest with relevance in structure learning. First, we present algorithms for counting linear extensions of partially ordered sets, which is required to correct bias in MCMC methods for sampling Bayesian network structures. Second, we give results in the extremal combinatorics of connected vertex sets, whose number bounds the running time of certain algorithms for structure learning and various other problems.Graafiset mallit ovat todennäköisyysmalleja, jotka esittävät muuttujien välisiä tilastollisia suhteita verkkona. Verkon jokainen solmu vastaa yhtä muuttujaa, ja solmujen väliset kaaret kuvaavat muuttujien välisiä riippuvuuksia. Graafinen esitystapa auttaa havainnollistamaan muuttujien kuvaamaa ilmiötä sekä usein mahdollistaa niiden yhteisjakauman esittämisen tiiviissä ja tehokkaasti käsiteltävässä muodossa. Graafisten mallien rakentaminen käsin on kuitenkin usein kohtuuttoman työlästä, mistä syystä niitä on pyritty oppimaan koneellisesti sovittamalla saatavilla olevaan havaintoaineistoon. Erityisesti verkon rakenteen oppiminen on haastava kombinatorinen ongelma, jota on ratkottu pitkälti likimääräisin menetelmin mutta erityisesti viime aikoina myös eksaktisti. Väitöskirjassa esitellään kombinatorisia algoritmeja rakenneoppimisongelman ratkaisemiseksi sekä kokeellisia ja analyyttisiä tuloksia ongelman vaativuudesta. Niin kutsutuille hajoaville graafisille malleille esitellään eksakti algoritmi, joka mahdollistaa sekä yhden optimaalisen verkon löytämisen että niin kutsutun bayesiläisen lähestymistavan, jossa opitaan jakauma kaikkien mahdollisten verkkojen yli. Jakaumasta voidaan joko poimia verkkoja satunnaisotannalla tai se voidaan tiivistää esimerkiksi verkon jokaisen kaaren marginaalitodennäköisyytenä. Bayes-verkot ovat toinen graafisten mallien perhe, joiden oppimiseen on viime aikoina esitetty useita eksakteja algoritmeja. Yksikään tällä hetkellä tunnettu algoritmi ei ole yksiselitteisesti muita nopeampi, vaan eri algoritmit toimivat nopeasti erityyppisillä syötteillä ja niiden ajoajan tarkka arviointi on osoittautunut vaikeaksi. Työn toisessa vaiheessa tutkitaan kokeellisesti, kuinka tällaisten algoritmien ajoaika riippuu annetusta syötteestä, sekä pyritään ennustamaan ajoaikaa koneoppimismenetelmin nopeimman algoritmin valitsemiseksi. Työn loppuosassa tutkitaan kahta kombinatorista ongelmaa, jotka ovat paitsi yleisesti kiinnostavia myös merkittäviä erityisesti Bayes-verkkojen oppimisessa. Ensimmäinen ongelma käsittelee osittaisjärjestysten lineaaristen laajennusten lukumäärän laskemista, jonka avulla korjataan vääristymiä satunnaisotantaan perustuvassa rakenneoppimisessa. Toinen kysymys koskee niin kutsuttujen yhtenäisten solmujoukkojen suurinta mahdollista lukumäärää, joka antaa ylärajan eräiden rakenneoppimisalgoritmien aikavaativuudelle. Suurimmalle lukumäärälle esitetään ylä- ja alarajoja verkoissa, joissa kunkin solmun naapurien lukumäärä on rajoitettu