Paper Info
Title
Kolmogorov's structure functions and model selection
Abstract
In 1974, Kolmogorov proposed a nonprobabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The "structure function" of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best fitting model in the class irrespective of whether the "true" model is in the model class considered or not. In this setting, this happens with certainty, rather than with high probability as is in the classical case. We precisely quantify the goodness-of-fit of an individual model with respect to individual data. We show that-within the obvious constraints-every graph is realized by the structure function of some data. We determine the (un)computability properties of the various functions contemplated and of the "algorithmic minimal sufficient statistic.".
Year
DOI
Venue
2004
10.1109/TIT.2004.838346
IEEE Transactions on Information Theory
Keywords
Field
DocType
maximum likelihood,indexing terms,kolmogorov structure function,structure function,maximum likelihood estimation,data analysis,information theory,lossy compression,sufficient statistic,computational complexity,computability,probability,goodness of fit,model selection
Information theory,Discrete mathematics,Combinatorics,Finite set,Kolmogorov complexity,Lossy compression,Model selection,Computability,Kolmogorov structure function,Sufficient statistic,Mathematics
Journal
Volume
Issue
ISSN
50
12
0018-9448
Citations 
PageRank 
References 
36
2.81
11
Authors
2
Name
Order
Citations
PageRank
Nikolai K. Vereshchagin114215.89
Paul Vitányi22130287.76