Computationally Efficient Methods for MDL-Optimal Density Estimation and Data Clustering


Autoria(s): Kontkanen, Petri
Contribuinte(s)

Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, tietojenkäsittelytieteen laitos

Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, institutionen för datavetenskap

University of Helsinki, Faculty of Science, Department of Computer Science

Hong Kong University of Science and Technology

Data(s)

30/11/2009

Resumo

The Minimum Description Length (MDL) principle is a general, well-founded theoretical formalization of statistical modeling. The most important notion of MDL is the stochastic complexity, which can be interpreted as the shortest description length of a given sample of data relative to a model class. The exact definition of the stochastic complexity has gone through several evolutionary steps. The latest instantation is based on the so-called Normalized Maximum Likelihood (NML) distribution which has been shown to possess several important theoretical properties. However, the applications of this modern version of the MDL have been quite rare because of computational complexity problems, i.e., for discrete data, the definition of NML involves an exponential sum, and in the case of continuous data, a multi-dimensional integral usually infeasible to evaluate or even approximate accurately. In this doctoral dissertation, we present mathematical techniques for computing NML efficiently for some model families involving discrete data. We also show how these techniques can be used to apply MDL in two practical applications: histogram density estimation and clustering of multi-dimensional data.

Yksi laskennallisen mallinnuksen keskeisistä ongelmista on mallinvalinta, jossa tehtävänä on valita joukosta kilpailevia matemaattisia malleja se, joka selittää annetun aineistojoukon parhaiten. Lyhimmän kuvauspituuden (MDL) periaate on yleinen, teoreettisesti ja intuitiivisesti mielekäs lähestymistapa tähän ongelmaan. Modernein formaali versio MDL-periaatteesta perustuu normalisoidun suurimman uskottavuuden (NML) jakaumaan, jonka laskeminen on matemaattisesti haastava ongelma. Väitöskirjassa esitetään tehokkaita laskentatapoja NML-jakaumalle kahden tärkeän malliperheen tapauksessa. Näiden laskennallisten tulosten käyttökelpoisuus osoitetaan soveltamalla menetelmiä kahteen käytännölliseen ongelmaan: histogrammi-muotoisten tiheysfunktioiden estimointiin ja kasauma-analyysiin.

Identificador

URN:ISBN:978-952-10-5901-8

http://hdl.handle.net/10138/21372

Idioma(s)

en

Publicador

Helsingin yliopisto

Helsingfors universitet

University of Helsinki

Relação

URN:ISBN:978-952-10-5900-1

1238-8645

Direitos

Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden.

Palavras-Chave #tietojenkäsittelytiede
Tipo

Väitöskirja (artikkeli)

Doctoral dissertation (article-based)

Doktorsavhandling (sammanläggning)

Text