Kolmogorov structure function
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
- Comment
- enIn 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
- Depiction
- Has abstract
- enIn 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 models of increasing complexity.
- Is primary topic of
- Kolmogorov structure function
- Label
- enKolmogorov structure function
- Link from a Wikipage to an external page
- www.mathnet.ru/php/archive.phtml%3Fwshow=paper&jrnid=tvp&paperid=1451&option_lang=eng%7Cdoi=10.1137/1132071
- epubs.siam.org/tvp/resource/1/tprbau/v32/i3/p389_s1
- Link from a Wikipage to another Wikipage
- Algorithmic information theory
- Andrey Kolmogorov
- Category:Algorithmic information theory
- Denoising
- File:Estimator.jpg
- File:Kolm complexity lect.jpg
- Jorma Rissanen
- Kolmogorov
- Kolmogorov complexity
- Mathematical model
- Maximum likelihood
- Minimal sufficient statistic
- Minimum description length
- Paul Vitányi
- Rate distortion
- Stochastic
- String (computer science)
- Sufficient statistic
- SameAs
- 4mort
- m.047t3gq
- Q5805968
- Sign
- Kolmogorov
- Source
- enannouncement cited above
- Subject
- Category:Algorithmic information theory
- Text
- enTo 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. But it is positively "probabilistically random" only when function having taken the value at a relatively small , then changes approximately as .
- Thumbnail
- WasDerivedFrom
- Kolmogorov structure function?oldid=1065352866&ns=0
- WikiPageLength
- 16844
- Wikipage page ID
- 18010343
- Wikipage revision ID
- 1065352866
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal
- Template:Quote
- Template:Reflist
