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

Show full item record

Permalink

http://urn.fi/URN:ISBN:978-952-10-5901-8
Title: Computationally Efficient Methods for MDL-Optimal Density Estimation and Data Clustering
Author: Kontkanen, Petri
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Hong Kong University of Science and Technology
Thesis level: Doctoral dissertation (article-based)
Abstract: 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.
URI: URN:ISBN:978-952-10-5901-8
http://hdl.handle.net/10138/21372
Date: 2009-11-30
Subject: tietojenkäsittelytiede
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
computat.pdf 427.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record