Source-linked AI summary
Algorithmic information theory
Peter D. Grunwald, Paul M. B. Vitanyi
TL;DR
The paper asks how information in observations can be measured without relying on potentially unavailable probability distributions, and introduces Kolmogorov complexity as a program-based answer. It develops this framework, relates it to Shannon information and compression, and shows how structure functions separate meaningful from random information for inductive inference. The paper concludes that algorithmic information connects compression, MDL, and philosophical accounts of information while retaining a close relationship to Shannon entropy for probabilistically generated data.
Problem
Information measures based on probability distributions may be unsuitable when the generating distribution is unknown or nonexistent.
Method
The paper develops Kolmogorov complexity using shortest programs, universal machines, mutual information, structure functions, and compression-based inference.
Results
Algorithmic information closely tracks Shannon entropy when data are generated by a probabilistic process.
Takeaways & Limitations
The theory separates meaningful information from noise without probabilistic assumptions and connects this separation to inductive inference.
Takeaways & Limitations
Kolmogorov complexity is not computable in general, and the theory can make meaningful statements primarily in asymptotic terms.
Abstract
from arXiv · showhide
We introduce algorithmic information theory, also known as the theory of Kolmogorov complexity. We explain the main concepts of this quantitative approach to defining `information'. We discuss the extent to which Kolmogorov's and Shannon's information theory have a common purpose, and where they are fundamentally different. We indicate how recent developments within the theory allow one to formally distinguish between `structural' (meaningful) and `random' information as measured by the Kolmogorov structure function, which leads to a mathematical formalization of Occam's razor in inductive inference. We end by discussing some of the philosophical implications of the theory.
1 Introduction
Algorithmic information theory measures information through the shortest program that produces an observation, without requiring a probability distribution. Its complexity measure is language-invariant up to an additive constant and distinguishes regular from random strings.
- Kolmogorov complexity measures an object’s information as the length of the shortest terminating program that computes it.
- A long sequence of identical bits has little information because a short program can generate it.
- The apparently random digits of π also have low complexity because a short program can generate them indefinitely.
- Reasonable programming languages yield complexities differing only by an additive constant.
- The chapter surveys Kolmogorov complexity, its relation to Shannon information, and its applications to meaningful information and inductive inference.
2 Kolmogorov Complexity: Essentials
Kolmogorov complexity is defined through shortest programs and characterizes strings by how compressible they are. Regular strings have sublinear complexity, random strings have complexity near their length, and stochastic data grow according to entropy-related rates.
- Definition: K(x) is approximated as the length of the shortest computer program that prints x and halts.
- Definition: The formal definition permits programs to receive bit-string input, supporting later extensions such as conditional Kolmogorov complexity.
- Key properties: Regular objects, including prefixes of π or repeated 1s, have K(x) = O(log n), where n is their length.
- Key properties: The theory distinguishes simple, random, and stochastic objects using complexity growth patterns.
- Key properties: Most length-n strings have K(x) about n, because only a small fraction can be described substantially more briefly.
- Key properties: For nondegenerate stochastic data, complexity grows linearly with n, with a rate below 1 for compressible biased or dependent sources.
2. Invariance
Kolmogorov complexity is robust to the choice of universal programming language, but only asymptotically: language changes alter values by a constant independent of the object and its length.
- For any two universal languages, their complexity measures differ by at most a constant depending on the languages, not on x or its length.
- Because complexity is defined only up to an additive constant, meaningful claims concern asymptotic growth rather than exact values for individual objects.
- A compiler translating programs between universal languages establishes the additive-constant invariance result.
- Kolmogorov complexity is not computable in general, although it is upper semicomputable through successively improving approximations.
3. Uncomputability
Although exact Kolmogorov complexity is uncomputable, practical compressors provide computable approximations. These ideas underpin universal coding, MDL, and normalized compression distance.
- Existing compressors such as gzip approximate K(x) by the number of bits used to encode x.
- For many compressors, compressed lengths are close to K(x) for most strings in the relevant set.
- Universal coding and the Minimum Description Length Principle use related compression-based ideas.
- Normalized compression distance approximates an ideal but uncomputable Kolmogorov-complexity-based method for data similarity analysis.
3 Overview and Summary
The chapter compares Shannon and Kolmogorov information theories, then develops structural accounts of meaningful information and their philosophical implications.
- 5 Shannon vs. Kolmogorov: Kolmogorov complexity and Shannon entropy both concern information through description or compression, but they apply to different objects and pursue different aims.Their relation is close for computable data distributions, where entropy is roughly expected Kolmogorov complexity.
- 5 Shannon vs. Kolmogorov: Mutual information is defined in both theories as information that one object gives about another.The theories provide distinct notions of mutual information for random variables and individual sequences, respectively.
- 5 Shannon vs. Kolmogorov: Lossy description extends compression-based theories toward formalizing meaningful and useful information.Lossless descriptions require complete reconstruction of the original message; lossy extensions support richer notions of information.
- 6 Meaningful Information, Structure Function and Learning: The Kolmogorov structure function separates a string into structural and random parts, with the structural part representing its meaningful information.The structural component defines a model, and meaningful information is summarized by the simplest model yielding an appropriate two-part description.
- 7 Philosophical Implications: Kolmogorov complexity supports distinctions among forms of randomness and provides a formal justification for Occam’s Razor in statistics.The chapter also discusses implications for the foundations of mathematics, probability, statistics, and philosophy of information.
4 Kolmogorov Complexity: Details
This section motivates Kolmogorov complexity through effective description methods and coding theory, establishes its invariance properties, and develops consequences for formal mathematical reasoning.
- 4.1 Motivation: Descriptional complexity is the length of an object’s shortest description under an effective specification method.The framework restricts descriptions to computable functions so they can, in principle, be executed by humans or machines.
- 4.1 Motivation: An optimal universal description method minimizes description length relative to every other effective method up to an additive constant.This optimality motivates treating complexity as an intrinsic attribute rather than a property of a particular formalization.
- 4.2 Coding Preliminaries: Prefix-free codes enable unambiguous decoding because no codeword is a proper prefix of another.The chapter uses prefix-free coding as the basis for its version of Kolmogorov complexity and standard natural-number encodings.
- 4.3 Formal Definition of Kolmogorov Complexity: A universal prefix machine simulates every enumerated prefix machine, allowing complexity to be defined through the shortest input that produces an output.The resulting definition uses the length of the shortest input sequence y such that the machine produces x and halts.
- 4.3 Formal Definition of Kolmogorov Complexity: Sound formal systems cannot prove the randomness of all but finitely many random strings, because such proofs would yield short procedures for producing long random strings.Related incompleteness results show that many parameterized Diophantine statements are logically independent of sound and consistent arithmetic theories.
- 4.3 Formal Definition of Kolmogorov Complexity: The uncomputable halting probability Ω encodes information about program termination and mathematical truth.Its first n bits suffice to decide whether the universal machine halts on inputs of length at most n.
5 Shannon and Kolmogorov
Shannon and Kolmogorov information theory both measure description length, but they optimize for different objects: distributions and expected transmission versus individual messages and reconstruction. The chapter develops connections between them, including entropy as expected Kolmogorov complexity and Shannon mutual information as averaged algorithmic mutual information.
- 5 Shannon and Kolmogorov: Shannon theory encodes outcomes according to a known random source, whereas Kolmogorov complexity encodes individual objects using programs that generate them.Shannon minimizes expected transmission length; Kolmogorov minimizes the bits needed to reconstruct a particular message.
- 5.3 Entropy and Expected Kolmogorov Complexity: Entropy is approximately the expected Kolmogorov complexity, linking Shannon’s distribution-level measure to algorithmic descriptions of individual outcomes.For computable coin-toss distributions, complexity of the distribution can grow as O(log n), while entropy grows linearly with n.
- 5.1 Codes and distributions: For a known computable distribution P, the Shannon-Fano code uses lengths ⌈−log P(x)⌉ and is essentially optimal in expectation under P.The discussion restricts the comparison to computable distributions, while noting that uncomputable extensions exist elsewhere.
- 5 Shannon and Kolmogorov: Shannon information can be problematic when the generating distribution is unknown or does not exist, motivating an object-centered account of information.The issue arises because Shannon information is determined by the distribution rather than an individual message’s meaning, structure, or content.
- 5.4 Mutual Information: Kolmogorov complexity satisfies an additivity relation for individual objects, with shortest prefix programs supplying the required conditional information.The analogous entropy equality averages over distributions, whereas the complexity result applies directly to individual objects.
- 5.4 Mutual Information: Algorithmic mutual information replaces entropy with Kolmogorov complexity and random variables with individual sequences or generating programs.The chapter states that expected algorithmic mutual information is close to probabilistic mutual information.
6 Meaningful Information
The paper separates an object’s meaningful structure from its residual randomness by representing it with a model and an index, then refines this decomposition through sufficient statistics and the Kolmogorov structure function. These tools connect algorithmic information to statistical learning, MDL, Occam’s razor, and distinctions between positive and negative randomness.
- Meaningful Information: Kolmogorov complexity measures an object’s information as the length of its shortest binary program, but this shortest description need not be meaningful.Random strings typically encode mostly noise, whereas observational data can combine meaningful laws and parameters with measurement errors.
- Meaningful Information: A two-part code represents x with a model describing its regular aspects and a program describing the remaining irregular aspects.The model supplies the structural or valuable information, while the residual program captures random or useless information.
- Sufficient Statistics: Typicality and optimality alone do not guarantee meaningful structure, because the singleton set {x} can remain an optimal model without summarizing all meaningful information.Thus, optimality requires refinement before it can capture the intended notion of meaningful information.
- Sufficient Statistics: The algorithmic minimal sufficient statistic separates x into a relevant structure S and residual randomness given by x’s index in S.For strings with a fixed number of 1s, the set of length-n strings having that count is an optimal model, and its shortest program is an algorithmic sufficient statistic.
- The Kolmogorov Structure Function: The Kolmogorov structure function varies the allowed model complexity α and records the smallest residual description log |S| for a model containing x.It is nonincreasing, reaches zero near α = K(x), and remains within a constant of the diagonal sufficiency bound.
- The Kolmogorov Structure Function: The structure-function framework distinguishes positive, stochastic randomness from negative, non-stochastic randomness by whether low-complexity models provide satisfactory explanations.A small diagonal-intersection bound indicates stochasticity, whereas a high bound indicates negative randomness.
- Learning and MDL: MDL encodes a theory followed by data described through that theory, balancing model complexity against fit and formalizing Occam’s razor.This trade-off is intended to protect against modeling random fluctuations when models of arbitrary complexity are allowed.
- Learning and MDL: Although every AMSS minimizes the two-part code length up to O(1), some optimal sets selected by MDL are not minimal sufficient statistics.Such sets may fail to summarize all structure in x, distinguishing two-part optimality from the stronger AMSS criterion.
7 Philosophical Implications and Conclusion
The chapter draws philosophical lessons from algorithmic information theory: it distinguishes meaningful from random information, connects information to compression and inference, and clarifies tensions around objectivity and “aboutness.”
- Randomness and mathematical implications: The philosophical discussion situates algorithmic randomness within mathematics and probability, emphasizing that individual sequences can be analyzed for randomness rather than only ensembles.The chapter also relates algorithmic complexity to incompleteness and epistemological Occam’s razor.
- Inference and Occam’s razor: Algorithmic inference focuses on individual data sequences without requiring that data arise from a distribution, unlike the classical statistical assumption of an underlying distribution P.This perspective is connected to MDL and algorithmic sufficient statistics, while simple models are crucial to MDL convergence.
- Aboutness and philosophy of information: The chapter examines whether algorithmic information captures “aboutness,” since identifying information with K(x) does not automatically specify an external state of the world.The authors present this as partly a definitional question while arguing that “information” can still be the intuitively appropriate term in some situations.
- Limits and practical measures: Absolute inherent information is generally uncomputable and only asymptotically well-defined, so practical measures become relative to restricted description methods.Universal coding and practical MDL retain meaningfulness for individual sequences but cannot claim objectivity or absoluteness.
- Meaningful information: Algorithmic information theory formalizes “meaningful information” by separating it from noise without probabilistic assumptions, linking this distinction to inductive inference.Learning is characterized as an attempt to find meaningful information in data.
- Compression and Shannon theory: The theory reconnects information measurement with data compression and approaches Shannon information when data are generated by a probabilistic process.Under such a process, algorithmic information behaves similarly to the process’s Shannon entropy.