Algorithmic statistics

By P. Gács, John Tromp, Paul M. B. Vitányi. 2000

155 citations recorded by the source corpus.

While Kolmogorov (1965, 1983) complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data, for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. We develop the algorithmic theory of statistic, sufficient statistic, and minimal sufficient statistic. This theory is based on two-part codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the model-to-data code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. We distinguish implicit and explicit descriptions of the models. We give characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modes-in the explicit mode under some constraints. We also strengthen and elaborate on earlier results for the "Kolmogorov structure function" and "absolutely nonstochastic objects"-those objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves. We demonstrate a close relation between the probabilistic notions and the algorithmic ones: (i) in both cases there is an "information non-increase" law; (ii) it is shown that a function is a probabilistic sufficient statistic iff it is with high probability (in an appropriate sense) an algorithmic sufficient statistic.

Subfields: Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Causal Markov condition for submodular information measures (2010, background): “hortest program that computes s from the shortest compression of t. Note that deﬁning R(s) := K(s) implies that the conditional information reads R(s|t) = K(s|t∗) due to K(s,t) =+ K(t)+K(s|t∗), 8 see [12]. Then K(xi,pai,ni) =+ K(pa i,ni) is equivalent to K(xi|(pai,ni) ∗) = 0+ , which, in turn, is eq”
Causal Inference Using the Algorithmic Markov Condition (2008, background): “In this paper, observables will either be random variables (formalizing statistical quantities) or they will be strings (formalizing the description of objects).”
Distinguishing Cause and Effect via Second Order Exponential Models (2009, background): “The following terminology [26] will be crucial: Deﬁnition 1 (Algorithmic mutual information) For any two binary strings s, t , the diﬀerence is called the algorithmic mutual information between s and t .”
A tutorial introduction to the minimum description length principle (2004, background): “Solomonoff’s ideas were later extended by several authors, leading to an ‘idealized’ version of MDL [Solomonoff 1978; Li and Vitányi 1997; Gács, Tromp, and Vitányi 2001].”
Justifying Additive Noise Model-Based Causal Discovery via Algorithmic Information Theory (2009, methodology): “A data processing inequality (Corrolary II.8 in [4]) then implies We conclude with K (cid:15) ( p ) + ≤ K ( q ) due to ineq.”
Advances in Minimum Description (methodology): “For these ﬁ ’s we thus have ﬁ + h x ( ﬁ ) = K ( x ) + O (1); a model corresponding to such an ﬁ (witness for h x ( ﬁ )) is a su–cient statistic, and it is minimal for the least such ﬁ (see above and [1; 3]).”