Kolmogorov's structure functions and model selection

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 g...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2004-12, Vol.50 (12), p.3265-3290
Main Authors: Vereshchagin, N.K., Vitanyi, P.M.B.
Format: Article
Language:English
Subjects:
Computability
Computer science
constrained best fit model sel- ection
constrained maximum likelihood (ML)
constrained minimum description length (MDL)
Engineering profession
function prediction
Kolmogorov complexity
Kolmogorov structure function
Logic
lossy compression
Mathematics
minimal sufficient statistic
nonprobabilistic statistics
Predictive models
Region 8
Source coding
Statistical analysis
Statistics
Stochastic processes
sufficient statistic
Technological innovation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.".
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2004.838346