Computing the Stochastic Complexity of Simple Probabilistic Graphical Models

Abstract

Minimum Description Length (MDL) is an information-theoretic principle that can be used for model selection and other statistical inference tasks. There are various ways to use the principle in practice. One theoretically valid way is to use the normalized maximum likelihood (NML) criterion. Due to computational difficulties, this approach has not been used very often. This thesis presents efficient floating-point algorithms that make it possible to compute the NML for multinomial, Naive Bayes and Bayesian forest models. None of the presented algorithms rely on asymptotic analysis and with the first two model classes we also discuss how to compute exact rational number solutions.

Koneoppimisessa ollaan kiinnostuneita löytämään automaattisesti malleja, jotka sopivat yhteen mahdollisimman hyvin havaintojen kanssa. Nämä havainnot esitetään usein mittaustuloksina taulukkomuodossa. Tällaisen taulukon toivotaan sisältävän kaikki tarkasteltavan ilmiön kannalta oleelliset ominaisuudet. Ilmiötä on kuitenkin vaikea hahmottaa vain tarkastelemalla taulukkoa, mistä johtuen taulukon sisältämästä tiedosta rakennetaan usein malli. Koneoppimisessa annetaan tietokoneen etsiä tällainen malli automaattisesti ennalta määritellystä valtavan suuresta mallijoukosta. Hyvä malli on sellainen, joka ei pyri kuvaamaan esitettyä äärellistä aineistoa mahdollisimman tarkasti, vaan pystyy yleistämään ja kuvaamaan siten myös tulevaisuudessa kerättävät havainnot.

Koneoppimismenetelmät sisältävät useita erilaisia mittareita mallien hyvyyden määrittämiseksi. Hyvä mittari pystyy löytämään hyvän, ilmiötä kuvaavan mallin myös pienen havaintoaineiston perusteella. Nämä mittarit, joita kutsutaan mallinvalintakriteereiksi, ovat yleisiä mallijoukosta riippumattomia periaatteita, joskin ne joudutaan käytännössä usein sovittamaan tiettyyn mallijoukkoon soveltuviksi. Tällainen sovittaminen saattaa olla monesti hankalaa ja sovitettua menetelmää käytettäessä saatetaan tarvita paljon laskentatehoa.

Yksi mallinvalintamenetelmistä on informaatioteoriaan pohjautuva, erityisesti lyhimmän kuvauspituuden periaatteeseen ja stokastisen kompleksisuuden käsitteeseen pohjautuva normalisoidun suurimman uskottavuuden kriteeri. Tämä menetelmä on teoreettisesti hyvin perusteltu ja osoittautunut myös useissa testeissä hyvin toimivaksi. Kuitenkin monien tilastomallityyppien hyvyyden arvioiminen tällä menetelmällä on laskennallisesti erittäin työlästä, joten monissa sovelluksissa kyseisen menetelmän käyttö on ollut pitkälti mahdotonta.

Tässä väitöskirjassa esitetään tehokkaita normalisoidun suurimman uskottavuuden laskentamenetelmiä kolmelle yksinkertaiselle graafisiin malleihin kuuluvalle mallityypille. Lisäksi työssä selkiytetään kokonaiskuvaa aikaisempien laskentamenetelmien suhteen ja osoitetaan yhteyksiä muihin tutkimusongelmiin.