In 1973, Andrey Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let each datum be a finite binary string and a model be a finite set of binary strings. Consider model classes consisting of models of given maximal Kolmogorov complexity. The Kolmogorov structure function of an individual data string 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. The structure function determines all stochastic properties of the individual data string: 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 the classical case we talk about a set of data with a probability distribution, and the properties are those of the expectations. In contrast, here we deal with individual data strings and the properties of the individual string focused on. In this setting, a property holds with certainty rather than with high probability as in the classical case. The Kolmogorov structure function precisely quantifies the goodness-of-fit of an individual model with respect to individual data.

The Kolmogorov structure function is used in the algorithmic information theory, also known as the theory of Kolmogorov complexity, for describing the structure of a string by use of modelss of increasing complexity.

Kolmogorov's definition

The structure function was originally proposed by Kolmogorov in 1973 at a Soviet Information Theory symposium in Tallinn, but these results were not published p.182. But the results were announced in in 1974, the only written record by Kolmogorov himself. One of his last scientific statements is (translated from the original Russian by L.A. Levin):

Contemporary definition

It is discussed in Cover and Thomas. It is extensively studied in Vereshchagin and Vitányi is the Kolmogorov complexity is the Kolmogorov complexity.

The algorithmic sufficient statistic

bits is therefore an algorithmic sufficient statistic. We write `algorithmic' for `Kolmogorov complexity' by convention. The main properties of an algorithmic sufficient statistic bits.) Therefore, the randomness deficiency and therefore by the Kolmogorov complexity symmetry of information is called the algorithmic minimal sufficient statistic.

is the best-fitting model for x. For more details see and especially and.

Selection of properties

additive term in argument and value) is realized by the structure function of some data x and vice versa. Where the graph hits the diagonal first the argument (complexity) is that of the minimum sufficient statistic. It is incomputable to determine this place. See.

Main property

with certainty, not with great probability.

The MDL variant

The Minimum description length, is given by the MDL function or constrained MDL estimator:

is the total length of two-part code of x with help of model S.

Main property

with certainty, not with great probability.

Application in statistics

The mathematics developed above were taken as the foundation of MDL by its inventor Jorma Rissanen.

Probability models

it can be proved is the Kolmogorov complexity is the Kolmogorov complexity version of the maximum likelihood (ML).

Main property

with certainty, not with great probability.

The MDL variant and probability models

, is given by the MDL function or constrained MDL estimator:

is the total length of two-part code of x with help of model P.

Main property

of complexity the MDL function allows us to select the best model for the individual string with certainty, not with great probability.

Extension to rate distortion and denoising

It turns out that the approach can be extended to a theory of rate distortion of individual finite sequences and denoising of individual finite sequences using Kolmogorov complexity. Experiments using real compressor programs have been carried out with success. Here the assumption is that for natural data the Kolmogorov complexity is not far from the length of a compressed version using a good compressor.

References

Literature

• , Especially pp.401–431 about the Kolmogorov structure function, and pp.613–629 about rate distortion and denoising of individual sequences.