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.

Onttojen puiden lahopuukovakuoriaiset — kolmen pyydystyypin vertailu

Vanhat ja ontot puut ovat tärkeä elinympäristö monelle lahopuusta riippuvaiselle eliölajille. Onttoihin puihin on erikoistunut suuri määrä myös vaarantuneita ja harvinaisia hyönteislajeja, jotka elävät puun onkalon seinämillä tai onkalon pohjalle kerääntyvässä orgaanisessa aineksessa, ns. mulmissa. Tutkimuksen tavoitteena oli selvittää, mikä kolmesta pyydystyypistä (ikkuna-, vuoka- ja kuoppapyydys) soveltuu parhaiten onttojen puiden lahopuukovakuoriaisten pyyntiin. Lisäksi tavoitteena oli kartoittaa hyönteisnäytteiden ensimmäiseen laboratoriokäsittelyyn vaadittua aikaa. Tutkimuksessa oli mukana vanhoja rungostaan onttoutuneita lehmuksia, tammia ja vaahteroita pääkaupunkiseudun puisto- ja kartanoalueilta. Puiden onkaloiden sisään aseteltiin ikkuna-, vuoka- ja kuoppapyydyksiä, kaksi kutakin tyyppiä ja ne tyhjennettiin kolmen viikon välein touko-heinäkuussa 2006. Pyydyksiä oli siis yhteensä 90 per pyyntijakso. Kun näytteistä eroteltiin halutut hyönteislahkot (mukaanlukien kovakuoriaiset) niiden käsittelyyn käytetty aika kirjattiin ylös. Aineistosta tunnistettiin yhteensä 3825 kovakuoriaisyksilöä ja 212 lajia, joista lahopuusta riippuvaisia oli yhteensä 3398 yksilöä ja 121 lajia. Ikkunapyydyksissä esiintyi yhteensä 1639 yksilöä ja 140 lajia, vuokapyydyksissä 1506 yksilöä ja 134 lajia, kuoppapyydyksissä 680 yksilöä ja 111 lajia. Näytteiden käsittelyaikojen keskiarvot olivat 48,3 minuuttia ikkunapyydykselle, 65,5 minuuttia vuokapyydykselle ja 34,1 kuoppapyydykselle. Lajistokoostumuksen huomioiva ?-diversiteetti erosi huomattavasti pyydysten välillä, se oli 36,5 % ikkuna- ja vuokapyydysten välillä, 13,1 % ikkuna- ja kuoppapyydysten välillä ja 14,2 % vuoka- ja kuoppapyydysten välillä. Ikkuna- ja vuokapyydysten välillä ei havaittu tilastollisesti merkitsevää eroa saproksyylilajien (p<0,05), -yksilöiden (p<0,05) tai käsittelyaikojen (p<0,05) keskiarvoissa. Ikkuna- ja vuokapyydyksillä saatiin keskimäärin selvästi enemmän saproksyylilajeja ja –yksilöitä kuoppapyydykseen verrattuna. Kuoppapyydyksellä saatiin kokonaisyksilömäärään verrattuna suhteellisesti vähemmän saproksyylejä (59 %) kuin ikkuna- (69 %) ja vuokapyydyksillä (71 %). Ikkunapyydykset olivat tehokkain pyydystyyppi vertailtaessa pyydysten keräämää saproksyyliyksilömäärää suhteessa aineiston käsittelyn vaatimaan aikaan. Tehokkuus (yksilöä minuutissa) ikkunapyydykselle oli 0,74, vuokapyydykselle 0,43 ja kuoppapyydykselle 0,21. Ikkunapyydyksiä ei ole aikaisemmin käytetty puun onkalon sisällä hyönteisiä pyydettäessä vaan ne ovat aikaisemmissa tutkimuksissa roikkuneet onkalon ulkopuolella. Ikkunapyydykset kuitenkin toimivat erinomaisesti myös onkaloiden sisällä. Ikkuna- sekä vuokapyydys toimivatkin selkeästi paremmin lahopuukovakuoriaisten pyynnissä verrattuna kuoppapyydykseen, jonka poisjättäminen olisi kuitenkin tuottanut huomattavasti lajiköyhemmän aineiston. Mahdollisimman monimuotoisen onttojen puiden lahopuukovakuoriaislajiston keräämiseksi tulisi käyttää ikkuna- tai vuokapyydyksiä yhdessä kuoppapyydysten kanssa.