Kolmogorov Structure Function
In 1973 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let each data be a finite binary string and models be finite sets 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 focussed on. In this setting, a property holds with certainty rather than with high probability as in the classical case. The Kolmogorov structure function precisely quantify 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 models of increasing complexity.
Read more about Kolmogorov Structure Function: Kolmogorov's Definition, Contemporary Definition, The MDL Variant, Probability Models and The Kolmogorov Structure Function, The MDL Variant and Probability Models, Extension To Rate Distortion and Denoising
Famous quotes containing the words structure and/or function:
“The philosopher believes that the value of his philosophy lies in its totality, in its structure: posterity discovers it in the stones with which he built and with which other structures are subsequently built that are frequently betterand so, in the fact that that structure can be demolished and yet still possess value as material.”
—Friedrich Nietzsche (18441900)
“The function of muscle is to pull and not to push, except in the case of the genitals and the tongue.”
—Leonardo Da Vinci (14251519)