FM Juho-Kustaa Kangas väittelee perjantaina 9.12.2016 klo 14 Helsingin yliopiston Exactum-rakennuksen auditoriossa CK112 (Gustaf Hällströmin katu 2b) aiheesta "Combinatorial Algorithms with Applications in Learning Graphical Models". Vastaväittäjänä toimii vanhempi lehtori James Cussens (Yorkin yliopisto, Iso-Britannia) ja kustoksena professori Petri Myllymäki (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi.

Kombinatorisia algoritmeja graafisten mallien oppimiseen

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.

Väitöskirjan saatavuus

Väitöskirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-2725-9.

Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: juho-kustaa.kangas@helsinki.fi.