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

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.