Kolmogorov structure function
In 1973, Andrey Kolmogorov proposed a non-probabilistic approach to statistics and model selection.
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.
In the classical case we talk about a set of data with a probability distribution, and the properties are those of the expectations.
In this setting, a property holds with certainty rather than with high probability as in the classical case.
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 models of increasing complexity.
The structure function was originally proposed by Kolmogorov in 1973 at a Soviet Information Theory symposium in Tallinn, but these results were not published[1] p. 182.
But the results were announced in[2] 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): To each constructive object corresponds a function
of a natural number k—the log of minimal cardinality of x-containing sets that allow definitions of complexity at most k. If the element x itself allows a simple definition, then the function
drops to 0 even for small k. Lacking such definition, the element is "random" in a negative sense.
[1] It is extensively studied in Vereshchagin and Vitányi[3] where also the main properties are resolved.
never decreases more than a fixed independent constant below the diagonal called sufficiency line L defined by It is approached to within a constant distance by the graph of
The main properties of an algorithmic sufficient statistic are the following: If
This can be easily seen as follows: using straightforward inequalities and the sufficiency property, we find that
With respect to the picture: The MDL structure function
[4] Within the constraints that the graph goes down at an angle of at least 45 degrees, that it starts at n and ends approximately at
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.
[3] The Minimum description length (MDL) function: The length of the minimal two-part code for x consisting of the model cost K(S) and the length of the index of x in S, in the model class of sets of given maximal Kolmogorov complexity
is the total length of two-part code of x with help of model S. It is proved that at each level
of complexity the structure function allows us to select the best model S for the individual string x within a strip of
[3] The mathematics developed above were taken as the foundation of MDL by its inventor Jorma Rissanen.
Kolmogorov's structure function becomes where x is a binary string of length n with
is the Kolmogorov complexity version of the maximum likelihood (ML).
, in the model class of computable probability mass functions of given maximal Kolmogorov complexity
is the total length of two-part code of x with help of model P. It is proved that at each level
of complexity the MDL function allows us to select the best model P for the individual string x within a strip of
[3] 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[7] using Kolmogorov complexity.
Experiments using real compressor programs have been carried out with success.
[8] 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.
