Kolmogorov complexity
In plain wordsHow briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself.
A measure of the information in a single object: the number of bits in the briefest program that makes a fixed universal Turing machineTuring machine, n.: An imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all. print the object (say, a string) and halt. By the invariance theorem, changing the universal machine changes it by at most an additive constant, so it is an essentially machine-independent measure of the information content of an individual object — unlike Shannon entropyentropy, n.: A measure of unpredictability. A fair coin toss has more entropy than a rigged one; an AI that is unsure of its next word has high entropy., which describes probability distributions. A string is algorithmically random if no program much shorter than the string produces it. Kolmogorov complexity is uncomputable: no algorithm can calculate it for every string, a consequence of the undecidability of the halting problem, though real compressors give upper bounds. It grounds formal accounts of simplicity: Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next. weights hypotheses by two to the minus their program length, minimum description lengthminimum description length, n.: The principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress. offers a computable relative, and AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal. builds on it. It is also invoked in arguments that neural networks are biased toward simple functions and that prediction and compression are two faces of intelligence.
The digits of π look random but have low Kolmogorov complexity, because a short program generates them.
Origin
Defined independently by Ray Solomonoff (1960, 1964) as part of his theory of inductive inference, by Andrey Kolmogorov in 'Three Approaches to the Quantitative Definition of Information' (1965), and by Gregory Chaitin (1966, 1969). Leonid Levin and others developed the theory in the 1970s; Ming Li and Paul Vitányi's textbook (1993) is the standard reference.
Usage note
Not to be confused with computational complexity, which measures the time or memory an algorithm needs (see big O notationbig O notation, n.: Shorthand for how the cost of a computation grows as the problem gets bigger. Saying attention costs 'O(n²)' means doubling the length of the text roughly quadruples the work.).
Related
- Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.
- minimum description lengthminimum description length, n.: The principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress.
- Turing machineTuring machine, n.: An imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all.
- Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise.
- information theoryinformation theory, n.: A branch of mathematics that treats information as surprise — the less predictable a message, the more it tells you — and works out how far data can be compressed and how reliably it can be sent.
- AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal.
Sources
- Kolmogorov, A. N. (1965). Three Approaches to the Quantitative Definition of Information. Problems of Information Transmission, 1(1).
- Li, M. & Vitányi, P. (1993; 4th ed. 2019). An Introduction to Kolmogorov Complexity and Its Applications. Springer.
Mentioned in
information theoryinformation theory, n.: A branch of mathematics that treats information as surprise — the less predictable a message, the more it tells you — and works out how far data can be compressed and how reliably it can be sent., Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., Turing machineTuring machine, n.: An imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all., AIXIAIXI, prop. n.: A mathematical description of a perfect learning agent that weighs every possible explanation of its experience and acts to get the most future reward. It cannot actually be built, but it defines an ideal., Marcus HutterMarcus Hutter, prop. n.: A German computer scientist who defined AIXI, a mathematical ideal of a perfectly intelligent agent, and who argues that compressing data well is a measure of intelligence., minimum description lengthminimum description length, n.: The principle that the best explanation of some data is the one that lets you write the data down most briefly, counting both the rule and its exceptions. Good theories compress., Ray SolomonoffRay Solomonoff, prop. n.: An American mathematician who worked out an ideal mathematical recipe for predicting what comes next from past data, and who attended the 1956 meeting that launched AI., Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next., universal intelligenceuniversal intelligence, n.: A mathematical definition of intelligence as an agent's average ability to achieve goals across every possible environment, with simpler environments counting more.