An Introduction to Kolmogorov Complexity and Its Applications, Third Edition

By Ming Li, Paul M. B. Vitányi. 1997

How researchers see this paper

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

Citations in the corpus

Deep learning in neural networks: An overview (2014, neutral): “Given some programming language, the principle of Minimum Description Length (MDL) can be used to measure the complexity of a solution candidate by the length of the shortest program that computes it (e.g., Solomonoff, 1964; Kolmogorov, 1965b; Chaitin, 1966; Wallace and Boulton, 1968; Levin, 1973a; ”
PowerPlay: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem (2011, methodology): “The compression drive tends to improve generalization performance, according to the principles of Occam’s Razorand Minimum Description Length(MDL) and Minimum Message Length(MML) [50, 16, 57, 58, 51, 26, 18, 14].”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “Given some RL problem, according to the AIT argument (Sec.”
The Description Length of Deep Learning models (2018, methodology): “…ultimately rooted in Solomonoff’s general theory of inference (Solomonoff, 1964) (see also, e.g., (Hutter, 2007; Schmidhuber, 1997)), whose principle is to favor models that correspond to the “shortest program” to produce the training data, based on its Kolmogorov complexity (Li and Vitányi, 2008).”
One Big Net For Everything (2018, methodology): “As discussed in earlier work [77], according to the Theory of Algorithmic Information (AIT) or Kolmogorov Complexity [84, 31, 6, 34, 85, 36], given some universal computer, U , whose programs are encoded as bit strings, the mutual information between two programs p and q is expressed as K ( q | p )…”
Self-Delimiting Neural Networks (2012, background): “In fact, SLIM programs are essential for making the theory of algorithmic probability elegant, e.g., [43].”
A Century of Gestalt Psychology in Visual Perception II. Conceptual and Theoretical Foundations (2012, methodology): “…1978), which connects the maximization of the Bayesian posterior to the minimization of the data encoding, and the theory of Kolmogorov complexity (see Li & Vitányi, 1997), which connects the inherent complexity of models to their probability via a universal prior (Solomonoff, 1964a, 1964b).”
Learning Deep Architectures for AI (2007, background): “According to learning theory (Vapnik, 1995; Li & Vitanyi, 1997), to obtain good generalization it is enough that the total number of bits needed to encode thewhole training setbe small, compared to the size of the training set.”
Measuring universal intelligence: Towards an anytime intelligence test (2010, background): “The relation between intuitive complexity and K ( ) is one of the recurrent issues in Kolmogorov complexity , and this has motivated the development of variants ( such as logical depth , see [ Li and Vitányi 2008 ] for details ) .”
Driven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise, Interestingness, Attention, Curiosity, Creativity, Art, Science, Music, Jokes (2008, methodology): “The ultimate limit for C l ( p, h ( ≤ t )) would be K ( h ( ≤ t )) , a variant of the Kolmogorov complexity of h ( ≤ t ) , namely, the length of the shortest program (for the given hardware) that computes an output starting with h ( ≤ t ) [106, 34, 37, 73].”
The missing link between the theory and empirics of path dependence: Conceptual clarification, testability issue, and methodological implications (2010, methodology): “We recur to an intuitive approach of randomness derived from the works of mathematicians (Chaitin, 1975; Li and Vitanyi, 1997; Solomonoff, 1960), according to which a series of events appears more random than others when more information is necessary to generate it (Chaitin, 1975).”
Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution (2021, background): “[7, 19] for a much broader discussion of the rate of introduction of new phenotypes in the evolutionary literature, and [20] for an important discussion of bias in the introduction of new variation.”
Reinforcement Learning Upside Down: Don't Predict Rewards - Just Map Them to Actions (2019, background): “From an algorithmic point of view [60, 25, 26, 49], however, randomness simply reﬂects a separate, unobservable oracle injecting extra bits of information into the observations.”
Evolving neural networks in compressed weight space (2010, background): “the one with the lowest Kolmogorov complexity [8].”