NOTE-790: Vitányi — Meaningful Information

Contribution

Algorithmic statistics had defined the sufficient statistic of an individual string for finite-set models and for computable probability models. This paper does it for the most general class that still works, total recursive functions, and shows why that class is the limit: one step further, to partial recursive functions, and the minimal sufficient statistic is trivial for every string. It proves the definition is non-vacuous at both ends. Random strings have sophistication about 0, and for every length some string has sophistication close to its length. It also shows that the three model classes give the same answer to within logarithmic terms, and that sophistication is not computable.

Key insight

The shortest program for a string can always be cut into a model part and a data-to-model part. Where the cut falls is meaningful only if the model class has no universal member. A universal machine can take over any model and move all its information into the data part, so a class that contains one gives every string a zero-length model. Totality is what blocks this. Sophistication is therefore a property of a string relative to a model class, and the paper’s result is that the obvious classes, short of the universal one, agree.

Assumptions

• Prefix complexity on a fixed reference universal prefix machine U. All equalities and inequalities (=⁺, <⁺) hold to within an additive constant that depends on U, and some only to within O(log n).
• Finite binary strings. Data are individual strings x of length n, and nothing is assumed about a source distribution.
• Models. Finite sets S ∋ x; computable probability mass functions P; and total recursive functions f, with data-to-model length l_x(f) = min{l(d) : f(d) = x} (Example 4.2(iii)).
• A recursive distortion measure d(x, M) defines typicality in each class (§IV). The choice of distortion “is a selection of which aspects of the data are relevant, or meaningful” (Remark 4.1).
• Several results assume K(l_x(f) | f*) =⁺ 0, that the model’s shortest program also gives the length of the data part. Theorem 6.5(iv) drops this assumption and pays log n + 2 log log n for it.

Key results

• Two-part form of K (II.3). K(x) =⁺ min_T {K(T) + K(x | T)}.
• Sufficient statistic, total functions (Def. 5.4, V.3). f is sufficient for x if K(x) =⁺ K(f) + l_x(f). Then x is typical for f (Lemma 5.2), K(f | x*) =⁺ 0 (V.2), and each x has at most a constant number c of sufficient statistics (Lemma 6.6).
• Sophistication (Def. 6.1). soph(x) = min{K(f) : K(f) + l_x(f) =⁺ K(x)}, over total recursive f.
• Partial models trivialise it (Lemma 6.2). If partial recursive statistics are allowed, soph(x) =⁺ 0 for every x: U itself is a model, and U(u, ⟨T_f, d⟩) = U(T_f, d) = x.
• Upper bound (Lemma 6.4). soph(x) <⁺ K(x). Prefixing x* with a constant program that ignores its input makes it total.
• Range (Theorem 6.5).
  • (i) If K(l_x(f) | f*) =⁺ 0, then K(f) >⁺ K(K(x)) and l_x(f) <⁺ K(x) − K(K(x)).
  • (ii) liminf_{l(x)→∞} soph(x) =⁺ 0, witnessed by strings with K(x) =⁺ n + K(n) and the identity function.
  • (iii) For every n some x of length n has every such sufficient statistic with K(f) >⁺ n. The proof transfers Theorem IV.2 of Gács–Tromp–Vitányi from finite sets.
  • (iv) For every n some x of length n has soph(x) >⁺ n − log n − 2 log log n.
• The model classes correspond (§VII).
  • Lemma 7.1: a finite-set sufficient statistic S gives a computable distribution P with K(P) =⁺ K(S) and log 1/P(x) =⁺ log |S|. A distribution P gives a total function f with K(f) =⁺ K(P) and l_x(f) =⁺ log 1/P(x). Both directions are within a constant.
  • Lemma 7.2: a total-function sufficient statistic f gives a finite set S ∋ x with K(S) + log |S| = K(x) + O(log n), and K(S) <⁺ K(f) + K(l_x(f)). The return trip costs O(log n), and sufficiency itself is only recovered to within O(log n).
• Uncomputability (§VIII).
  • Theorem 8.1: soph is not recursive.
  • Theorem 8.3: an oracle that returns a sufficient statistic f* of x (with a constant correction c_x) computes K and the halting sequence.
  • Lemma 8.4: K(f | x, K(x)) =⁺ 0, nonuniformly; the constant program may depend on x.
  • Theorem 8.5: K(f* | x) =⁺ K(K(x) | x) =⁺ K(x* | x), which lies between log n − log log n and log n for some x (by Gács’s VIII.1).
  • Lemma 8.7: soph is not computable “to any significant precision” (proved in Vereshchagin–Vitányi, cited), and is computable from x and the first 2^{2l(x)} bits of the halting sequence.
• Structure function (§IX). soph(x) is where Kolmogorov’s structure function λ_x(α), the shortest two-part code with model complexity at most α, first drops to K(x), “everything up to a logarithmic addive term”. Its analysis is deferred to Vereshchagin–Vitányi.

Claims

id	claim	strength	support
C1	A model class containing a universal model gives every string sophistication 0, so no split into structure and noise	strong	Lemma 6.2, a two-line proof
C2	With total recursive models, sophistication is non-trivial: about 0 for random strings, and above n − log n − 2 log log n for some string of every length	strong	Theorem 6.5(ii), (iv), proved
C3	Finite-set, computable-distribution and total-function sufficient statistics correspond, so the amount of meaningful information does not depend on the class to within O(log n)	moderate	Lemmas 7.1–7.2; the reverse step keeps sufficiency only to within O(log n)
C4	Sophistication is not computable, and knowing a sufficient statistic is as hard as knowing K	strong	Theorems 8.1 and 8.3
C5	Sophistication is the point where the structure function reaches K(x)	weak	§IX, stated without proof, deferred to Vereshchagin–Vitányi

Concepts

• Model (statistic). A function from data to an element of a model class. Here mainly a total recursive function f, with x = f(d) for some data-to-model code d.
• Sufficient statistic. A model whose two-part code is as short as the shortest one-part code: K(f) + l_x(f) =⁺ K(x). The paper writes the probabilistic version as K(P) + log 1/P(x) =⁺ 0 (Example 5.3), a slip for =⁺ K(x).
• Sophistication. The complexity of a minimal sufficient statistic in the total-function class. It is the paper’s measure of “meaningful information”.
• Absolutely non-stochastic. Kolmogorov’s term, for strings with sophistication near their length: all information is meaningful and there is almost no accidental part.
• Randomness in the positive and negative sense (§I-B). High complexity as a typical outcome of a simple process (sophistication about 0), against high complexity because the process itself is complex (sophistication high).
• Randomness deficiency. δ(x | M) = log |B_M(d(x, M))| − K(x | M, d(x, M)). x is typical for M when it is =⁺ 0.

Connections

The paper extends Gács, Tromp and Vitányi’s Algorithmic statistics (2001), which treats finite-set and probability models. It borrows the word “sophistication” from Koppel (1987, 1988), whose setting is monotone machines on infinite sequences. The paper calls that treatment “technically sufficiently vague so as to have no issue for the present work” and does not compare the two definitions. Logical depth and coarse sophistication are not discussed. The paper names Vereshchagin–Vitányi’s structure-function paper as its sequel. It is probably the record’s LIT-239, which another reader has on the same day, and it holds the finite-set results this paper transfers.

Bearing on the record

• THEORY-036 (Dennett’s real patterns). This reading gives that account a sharper contrast than it has. Dennett calls a pattern real when a description beats the bit map. Vitányi’s two extremes come apart from that criterion in both directions. A maximally random string has no shorter description and also no meaningful information, so there they agree. An absolutely non-stochastic string is nearly incompressible: K(x) is close to n, so Dennett’s criterion finds no pattern. Yet by Theorem 6.5(iv) almost all of its information is structure. The paper does not discuss Dennett. The step is mine, and THEORY-036 does not cite the paper.
• NOTE-241 groups this paper with MDL works in which “the model’s description length is the code length of the hypothesis at a precision chosen jointly with the data’s code length”. That is fair for the two-part code here. The model part is a shortest program for a total function, which is uncomputable, not a code at a chosen precision.
• NOTE-300 pairs rate–distortion with Kolmogorov’s structure function. This paper uses individual-data distortion only to define typicality (§IV, after Vereshchagin–Vitányi). It does not prove the pairing.
• The Sefidgaran papers (LIT-233, LIT-236), filed under the same heading, share none of this machinery. Their compression is Shannon block coding of the learning algorithm’s output, read in the same batch.
• No instruction for machine-learning practice; nothing for the anthology.

Limitations

• Everything holds to within additive constants that depend on the reference machine, and some results only to within O(log n). For a string of a few thousand bits the slack is not small.
• Sophistication is uncomputable and not approximable to useful precision (Lemma 8.7, by citation), so it cannot be estimated for any real object, a learned model included.
• The equivalence of model classes is asymmetric. Going from a total function to a finite set costs O(log n), and the set obtained is sufficient only to that precision.
• The proof of Theorem 6.5(ii) writes K(x) =⁺ K(ι) + l(x*) for the identity function ι. The data part must be self-delimited for the equality to hold to within a constant, and the paper does not say how.
• Two results rest on cited work not read here: Theorem 6.5(iii) and Lemma 8.7(i).
• The structure-function claim of §IX is stated, not proved.

Open questions

• How does this sophistication relate to Koppel’s original notion, to coarse sophistication and to logical depth? The paper does not say.
• The choice of distortion function in §IV fixes “which aspects of the data are relevant”. What constrains that choice is left open, and it carries the same weight as the choice of model class.
• Is there a computable or resource-bounded version of sophistication that keeps the non-triviality of Theorem 6.5? The paper does not consider resource bounds.