Algorithmic information theory

By Marcus Hutter. Scholarpedia, 2007

357 citations recorded by the source corpus.

This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.

Subfields: Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ab5c79e7ccc16dc7e08824c859734d2e75c29eb9

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 Inference by Stochastic Complexity (2017, background): “Kolmogorov complexity of a probability distribution P , K ( P ) , is the length of the shortest program that outputs P ( x ) to precision q on input (cid:104) x , q (cid:105) [4].”
Towards a theory of semantic communication (2011, background): “Another related area of research is Algorithmic Information Theory (AIT) [11] and Kolmogorov Complexity [38].”
Prediction (2010, neutral): “This is due to the organization of the spatio-temporal dynamics in so-called “coherent structures”, corresponding to coherent vortices in hydrodynamic flows [8].”
The Measure of Intelligence (2019, neutral): “For an extensive introduction, see [15, 14, 30, 55].”
An information-theoretic primer on complexity, self-organization, and emergence (2009, methodology): “The original formulation can be traced back to Solomonoﬀ, Kolmogorov and Chaitin, who developed independently what is today known as Kolmogorov-Chaitin or algorithmic complexity [39, 12].”
Adaptive weighing of context models for lossless data compression (2005, background): “The algorithmic, or Kolmogorov, complexity of a string, defined as the length of the shortest program that outputs it, is not computable (Chaitin 1977).”
Rule Extraction from Recurrent Neural Networks: ATaxonomy and Review (2005, background): “Previous studies seem to show promising results (Crutchfield & Young, 1990; Blair & Pollack, 1997; Bakker & Jong, 2000) with regard to complexity estimations that go beyond Shannon entropy (Cover & Thomas, 1990) and minimum algorithmic description length complexity (Chaitin, 1987) (a.”
Between order and chaos (2011, neutral): “For almost all infinite sequences produced by a stationary process the growth rate of the Kolmogorov– Chaitin complexity is the Shannon entropy rate 23 : As a measure—that is, a number used to quantify a system property—Kolmogorov–Chaitin complexity is uncomputable 24,25 .”
Causal Inference via Kernel Deviance Measures (2018, methodology): “In particular, we reason about it in terms of algorithmic complexity, i.e. Kolmogorov complexity [Gr¨unwald and Vit´anyi, 2008] which is the description length of the shortest program that implements the sampling process of the distribution.”