home | search | Algorithmic Information Theory | contact | up |
|
Andrei Kolmogorov The theory of probability ... can and should be developed from axioms ... Entities should not be multiplied unnecessarily William of Occam It seems to me that the most important discovery since Gödel was the discovery by Chaitin, Solomonoff, and Kolmogorov of a concept called Algorithmic Probability. ... This is a beautiful theory ... Everybody should learn all about that and spend the rest of their lives working on it. Marvin Minsky, 2010 |
Tutorials
- Introduction to Algorithmic Information Theory and Machine Learning (1 hour tutorial)
- Introduction to Algorithmic Information Theory and Applications (1.5 hour tutorial)
- Scholarpedia on Algorithmic Information Theory
- Wikipedia on Kolmogorov complexity
- Kolmogorov Complexity: Sources, Theory and Applications, by A.Gammerman and V.Vovk, The Computer Journal 42:4 (1999) 252-255
Courses
- Understanding Artificial Intelligence through Algorithmic Information Theory, EdX MOOC, by Jean-Louis Dessalles
- Topics in Kolmogorov Complexity, Seminar 236804, by Ran El-Yaniv
- Complexity of Algorithms, by Laszlo Lovasz
- Lecture notes on Kolmogorov complexity (in German) , by J. Schmidhuber, TUM, Munich, Germany, 1994.
Information
- Algorithmic Information Theory for scientists and non-Mathematicians, online book by Sean Devine
- Entropy in Information and Coding Theory, by Chris Hillman.
- Predictive Complexity at CLRC
- Minimum Description Length on the Web
- Minimum Message Length and Minimum Encoding Length Inference, list of links by David Dowe
- Complexity measures for complex systems and complex objects, by Pablo Funes.
Books
- An Introduction to Kolmogorov Complexity and Its Applications, Ming Li and Paul Vitanyi (2008)
- Information and Randomness: An Algorithmic Perspective, Cristian Calude (1994&2002)
- Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, Marcus Hutter (2005)
- Algorithmic Randomness and Complexity, Rod Downey and Denis Hirschfeldt (2010)
- Elements of Information Theory, Thomas Cover and Joy Thomas (1991)
- The Limits of Mathematics, Gregory Chaitin (1998&2003)
- Kolmogorov Complexity and Computational Complexity, Osamu Watanabe (1992)
Magazines
- Special Issue on Kolmogorov Complexity, The Computer Journal, Volume 42, Issue 4, 1999.
- Special Issue on Kolmogorov Complexity, Theoretical Computer Science, Volume 271, Issue 1-2, B. Durand, January 2002
- Special Issue on Kolmogorov Complexity, Theoretical Computer Science, vol 207, no 2, A.Semenov (1998)
Some Online Papers
- Franz&al. (2021) A theory of incremental compression
- Rathmanner&Hutter (2011) A Philosophical Treatise of Universal Induction
- Janzing&Schölkopf (2010) Causal Inference Using the Algorithmic Markov Condition
- M. Mueller, Stationary Algorithmic Probability, Theoretical Computer Science, 411(1):113--130, 2010
- M. Hutter, On Universal Prediction and Bayesian Confirmation, Theoretical Computer Science, 384(1) 33-48, 2007
- R. Cilibrasi and P.M.B. Vitanyi, Clustering by Compression, IEEE Trans. Information Theory, 51(4):1523--1545, 2005.
- J. Schmidhuber, The New AI: General & Sound & Relevant for Physics In Artificial General Intelligence and http://arxiv.org/abs/cs.AI/0302012, 2003.
- J. Lutz, The dimensions of individual strings and sequences, ACM Computing Research Repository, 31 pages, 2002.
- M. Hutter, The fastest and shortest algorithm for all well-defined problems, International Journal of Foundations of Computer Science, 13:3 (2002) 431-443
- P. Gacs, J. Tromp, P. Vitanyi, Algorithmic statistics, IEEE Trans. Inform. Theory, 47:6(2001), 2443-2463.
- H. Bannai, A Theory of Discovery and Its Applications in Discovery Science", Master Thesis, Department of Information Science, Graduate School of Science, University of Tokyo, January 2000.
- J. Schmidhuber. Algorithmic theories of everything. quant-ph/0011122, TR IDSIA-20-00, Version 1.0, IDSIA, Manno (Lugano), Switzerland, November 2000. http://arxiv.org/abs/quant-ph/0011122. HTML version .
- M. Hutter Towards a Universal Theory of Artificial Intelligence based on Algorithmic Probability and Sequential Decisions Proceedings of the 12th European Conference on Machine Learning (ECML-2001) 226-238
- Chris Hillman, Kolmogorov complexity of generalized computably enumerable sets, preprint, also available in PDF.
- H. Bannai and S. Miyano, A Definition of Discovery In Terms of Generalized Descriptional Complexity, Discovery Science 1999: 316-318
- S. Hochreiter and J. Schmidhuber. Feature extraction through LOCOCODE. Neural Computation 11(3): 679-714, 1999
- Martin Schmidt, Time-Bounded Kolmogorov Complexity May Help in Search for Extra Terrestrial Intelligence (SETI)
- C. Wallace and D. Dowe, Minimum Message Length and Kolmogorov complexity, Comp. J., Vol 42, No. 4 (1999), pp270-283
- John Tromp, A CL-based definition of Kolmogorov Complexity
- Vladik Kreinovich and Luc Longpré, Human Visual Perception and Kolmogorov Complexity: Revisited
- Vladik Kreinovich, Luc Longpre, and Misha Koshelev, Kolmogorov Complexity, Statistical Regularization of Inverse Problems, and Birkhoff's Formalization of Beauty
- Sanjeev Subbaramu, Ann Q. Gates and Vladik Kreinovich, Applications of Kolmogorov Complexity to Image Compression,
- Arthur De Vany, How Much Information is there in an Economic Organization and Why Can't Large Ones be Optimal?
- Andrei Muchnik, Andrei Romashchenko, Alexander Shen and Nikolai Vereshchagin, Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Abstract
- M. Conte, et al. Genetic Programming Estimates of Kolmogorov Complexity. Proc. 7th Int. Conf. on GA, 743-750, 1997.
- S. Hochreiter and J. Schmidhuber. Flat Minima. Neural Computation, 9(1):1-42, 1997.
- J. Schmidhuber. Low-complexity art. Leonardo, Journal of the International Society for the Arts, Sciences, and Technology, 30(2):97-103, 1997.
- Yongge Wang, Randomness and Complexity, PhD thesis, 1996
Research field abbreviations:
Algorithmic Information Theory (AIT),
Kolmogorov Complexity (KC),
Algorithmic Probability (AP),
Algorithmic Randomness (AR),
Universal Levin Search (US),
Artificial Intelligence (AI),
Machine Learning (ML),
Minimum Description Length (MDL),
Minimum Message Length (MML),
Computational Complexity (CC).
Eric Allender Rutgers University, New Jersey, USA (AR) Klaus Ambos-Spies Universität Heidelberg, Germany (AR) Eugene Asarin Université Joseph Fourier, Grenoble, France Luis Antunes University of Porto, Portugal (AIT) Maxim Babenko Moscow State University, Russia (KC) Janis Barzdins University of Latvia (AIT) Verónica Becher University of Buenos Aires, Argentina (AR,KC) Harry Buhrman CWI and University of Amsterdam, The Netherlands (AR,KC) Cristian S. Calude University of Auckland, New Zealand (AR) Gregory J. Chaitin IBM Research, Yorktown Heights, NY, USA (AR,AI) Alexey Chernov Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (KC,CC) Thomas Cover Stanford University, CA, USA (AIT,other) David Dowe Monash University, Melbourne, Australia (MML) Rodney G. Downey Victoria University, New Zealand (AR) Bruno Durand Université de Provence, Marseille, France Allan Erskine University College London, UK (ML,KC) Santiago Figueira University of Buenos Aires, Argentina (AR,KC) Lance Fortnow University of Chicago, USA (CC) Péter Gács Boston University, USA (AIT) Alex Gammerman Royal Holloway University, London, UK (AIT,ML) Murray Gell-Mann Santa Fe Institute, USA (AIT,other) Peter Grünwald CWI and Eindhoven University of Technology, The Netherlands (MDL) Denis R. Hirschfeldt University of Chicago, USA (AR) John Hitchcock University of Wyoming, Laramie, WY, USA (AIT,CC) Achim Hoffmann University of New South Wales, Australia (KC,Occam) Günther Hotz Universität Saarbrücken, Germany (AIT,CC) Marcus Hutter Australian National University, Australia (AIT,AP,AI,ML) Yuri Kalnishkan Royal Holloway University of London, UK (AIT,ML) Bjorn Kjos-Hanssen University of Connecticut, Storrs, CT, USA (AR) Andrei Kolmogorov Moscow, Russia (AIT) Kevin Korb Monash University, Melbourne, Australia (MDL) Sophie Laplante Université Paris-Sud, France (CC,KC,AR) Tor Lattimore Australian National University, Australia (AIT,AP,ML) Troy Lee CWI Amsterdam, The Netherlands (CC,KC) Leonid A. Levin Boston University, USA (AIT) Ming Li University of Waterloo, Canada (AIT) Luc Longpré University of Texas at El Paso, USA (KC,CC) Jack Lutz Iowa State University, USA (AR) Jean-Yves Marion LORIA Université Nancy, France (CC,KC) Per Martin-Löf University of Stockholm, Sweden (AR) Elvira Mayordomo University of Zaragossa, Spain (AR) Wolfgang Merkle Universität Heidelberg, Germany (AR) Nenad Mihailovic Universität Heidelberg, Germany (AR) Joseph Miller University of Wisconsin—Madison, USA (CC,KC,AR) Philippe Moser Iowa State University, USA (AR) Andrej Muchnik Institute of New Technologies, Moscow, Russia (AIT) Andre Nies University of Auckland, New Zealand (AR) Jan Poland Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano (AIT,ML) Jan Reimann Universität Heidelberg, Germany (KC,AR) Jorma Rissanen Almaden Research Center, San Jose, CA, USA (MDL) Andrei Romashchenko Institute of Problems of Information Transmission, Moscow, Russia (KC) Boris Ryabko Siberian State University of Telecommunication and Computer Science, Siberia (AR,KC) Jürgen Schmidhuber Istituto Dalle Molle di Studi Sull'Intelligenza Artificiale (IDSIA), Lugano, Switzerland (US,AIT,ML) Claus-Peter Schnorr Goethe-Universität Frankfurt, Germany (AR) Robert Solovay University of California, Berkeley, USA (AIT) Alexander Kh. Shen Institute of Problems of Information Transmission, Moscow, Russia (CC,AIT) Theodor A. Slaman University of California, Berkeley, USA (AR,CC) Ray J. Solomonoff Oxbridge Research, Cambridge, MA, USA (AP,ML,AI) Ludwig Staiger Universität Halle, Germany (AR) Frank Stephan Universität Heidelberg, Germany (AR) Sebastiaan A. Terwijn Technical University of Vienna, Austria (AR) Leen Torenvliet University of Amsterdam, The Netherlands Boris A. Trakhtenbrot Tel Aviv University, Israel John Tromp Formerly at the Dutch Centre for Math&CS and CWI, The Netherlands (CC,KC) Maxim Ushakov Moscow State University, Russia Vladimir Uspensky Moscow State University, Russia Vladimir V'yugin Institute of Problems of Information Transmission, Moscow, Russia (KC) Michael Vyugin Royal Holloway University, London, UK (KC,ML) Nikolai Vereshchagin Moscow State University, Russia (KC,CC) Paul M. B. Vitanyi CWI, Amsterdam, The Netherlands (KC,ML) Volodya Vovk Royal Holloway University, London, UK (KC,ML) Chris Wallace Monash University, Australia (MML) Yongge Wang University Heidelberg, Germany (CC,AR) Osamu Watanabe Tokyo Institute of Technology, Tokyo, Japan (CC,KC)
Ray Solomonoff ... Algorithmic Probability can serve as a kind of 'Gold Standard' for induction systems Only math nerds would call 2500 finite Leonid Levin |
© 2000 by ... | home | search | science | calculators | personal | contact | up | ... Marcus Hutter |