FM Topi Talvitie\u00a0defends v\u00e4ittelee torstaina 21.11.2019 klo 12 Helsingin yliopiston Exactum-rakennuksen auditoriossa CK112 (Pietari Kalmin katu 5, pohjakerros) aiheesta\u00a0Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks. Vastav\u00e4itt\u00e4j\u00e4n\u00e4 toimii\u00a0apulaisprofessori Kuldeep Meel (National University of Singapore, Singapore)\u00a0ja kustoksena\u00a0professori Mikko Koivisto (Helsingin yliopisto). V\u00e4it\u00f6stilaisuus pidet\u00e4\u00e4n englanniksi.<\/p>\n
Topi Talvitien\u00a0v\u00e4it\u00f6skirjaty\u00f6 on osa Helsingin yliopiston tietojenk\u00e4sittelytieteen osastolla ja Sums of Products -ryhm\u00e4ss\u00e4 teht\u00e4v\u00e4\u00e4 tutkimusta.\u00a0V\u00e4it\u00f6skirjaty\u00f6n\u00a0ohjaajina ovat toimineet professori Mikko Koivisto (Helsingin yliopisto) ja apulaisprofessori\u00a0Valentin Polishchuk (Link\u00f6pings Universitet, Ruotsi).<\/p>\n
Suunnattujen syklitt\u00f6mien verkkojen laskenta ja satunnaisotanta Bayes-verkkojen oppimiseen<\/p>\n
Bayes-verkot mallintavat satunnaismuuttujien v\u00e4lisi\u00e4 tilastollisia suhteita suunnattuina syklitt\u00f6min\u00e4 verkkoina, joissa solmut vastaavat satunnaismuuttujia ja kaaret niiden v\u00e4lisi\u00e4 riippuvuuksia. Verkkorakenne havainnollistaa muuttujien kuvaaman ilmi\u00f6n rakennetta ja mahdollistaa muuttujien yhteisjakauman esitt\u00e4misen tiiviiss\u00e4 muodossa. Vaikka Bayes-verkko voidaan periaatteessa rakentaa k\u00e4sin, se on ep\u00e4k\u00e4yt\u00e4nn\u00f6llist\u00e4, mik\u00e4li muuttujia on paljon tai mallinnettavaa ilmi\u00f6t\u00e4 ei ymm\u00e4rret\u00e4 t\u00e4ydellisesti. T\u00e4m\u00e4n takia on hy\u00f6dyllist\u00e4 oppia verkon rakenne ilmi\u00f6st\u00e4 ker\u00e4tyn datan perusteella. V\u00e4it\u00f6skirjassa tutkitaan laskennallisia ongelmia, jotka liittyv\u00e4t Bayes-verkon rakenteen oppimiseen. Kaikki n\u00e4m\u00e4 ongelmat koskevat suunnattujen syklitt\u00f6mien verkkojen laskemista tai satunnaisotantaa erilaisilla rajoitteilla.<\/p>\n
Yksi keskeinen ongelma Bayes-verkon rakenteen oppimisessa on rakenteen poiminta posteriorisatunnaisjakaumasta, joka painottaa parhaiten dataa vastaavia rakenteita. V\u00e4it\u00f6skirjassa esitell\u00e4\u00e4n t\u00e4h\u00e4n ongelmaan ensimm\u00e4inen eksakti algoritmi, joka hy\u00f6dynt\u00e4m\u00e4ll\u00e4 posteriorijakauman erityisominaisuuksia saavuttaa polynomisen aikavaativuuden suhteessa jakauman m\u00e4\u00e4rittelev\u00e4n tietorakenteen kokoon. Algoritmi tarjoaa my\u00f6s aiempia algoritmeja tehokkaamman tavan suunnattujen syklitt\u00f6mien verkkojen poimintaan tasajakaumasta.<\/p>\n
Toinen v\u00e4it\u00f6skirjassa tutkittu ongelma on osittaisj\u00e4rjestyksen lineaariekstensioiden laskenta. T\u00e4m\u00e4 ongelma tiedet\u00e4\u00e4n kuuluvaksi vaikeiden laskentaongelmien #P-luokkaan, mutta se voidaan silti ratkaista likim\u00e4\u00e4risesti polynomisessa ajassa palauttamalla se vastaavaan satunnaisotantaongelmaan. V\u00e4it\u00f6skirja esittelee kaksi uutta likim\u00e4\u00e4r\u00e4ist\u00e4 satunnaisalgoritmia lineaariekstensioiden laskentaan. Ensimm\u00e4inen algoritmi muuttaa tunnetun eksaktin laskenta-algoritmin likim\u00e4\u00e4r\u00e4iseksi yhdist\u00e4m\u00e4ll\u00e4 siihen satunnaisotokseen perustuvaa arviointia. Toinen algoritmi palauttaa laskentaongelman uuteen Markovin ketjuihin perustuvan satunnaisotantamenetelm\u00e4\u00e4n. Yhdess\u00e4 n\u00e4m\u00e4 kaksi algoritmia nopeuttavat k\u00e4yt\u00e4nn\u00f6n tapauksissa likim\u00e4\u00e4r\u00e4ist\u00e4 lineaariekstensioiden laskentaa usealla kertaluokalla.<\/p>\n
Ty\u00f6n loppuosassa tutkitaan tietyss\u00e4 Markov-ekvivalenssiluokassa olevien suunnattujen syklitt\u00f6mien verkkojen laskenta- ja satunnaisotantaongelmia. Ongelma on t\u00e4rke\u00e4 Bayes-verkkojen k\u00e4yt\u00f6ss\u00e4 kausaalisten riippuvuuksien mallintamiseen, koska Markov-ekvivalentteja rakenteita ei voi erottaa pelk\u00e4st\u00e4\u00e4n havaintodatan perusteella, vaikka ne ovat kausaalisesta n\u00e4k\u00f6kulmasta erilaisia. Ty\u00f6ss\u00e4 esitell\u00e4\u00e4n tapa nopeuttaa parasta tunnettua algoritmia dynaamisen ohjelmoinnin avulla. T\u00e4m\u00e4n lis\u00e4ksi v\u00e4it\u00f6skirja esittelee uuden verkon puuhajotelmaan perustuvan menetelm\u00e4n, jonka aikavaativuus on lineaarinen, mik\u00e4li verkon suurimman klikin koko on rajoitettu.<\/p>\n
V\u00e4it\u00f6skirjan saatavuus<\/p>\n
V\u00e4it\u00f6skirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa\u00a0http:\/\/urn.fi\/URN:ISBN:978-951-51-5610-5<\/a>.<\/p>\n