We first define Algorithmic Probability, an extremely powerful method of inductive inference. We discuss its completeness, incomputability, diversity and subjectivity and show that its incomputability in no way inhibits its use for practical prediction. Applications to Bernoulli sequence prediction and grammar discovery are described. We conclude with a note on its employment in a very strong AI system for very general problem solving.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems of Information Transmission 1(1), 1–7 (1965)
Levin, L.A.: Universal search problems. Problemy Peredaci Informacii 9, 115–116 (1973); Translated in Problems of Information Transmission 9, 265–266
Rissanen, J.: Modeling by the shortest data description. Automatica 14, 465–471 (1978)
Rissanen, J.: Stochastical Complexity and Statistical Inquiry. World Scientific, Singapore (1989)
Solomonoff, R.J.: A preliminary report on a general theory of inductive inference. (Revision of Report V–131, Feb. 1960), Contract AF 49(639)–376, Report ZTB—138. Zator, Cambridge (Nov, 1960) (http://www.world.std.com/rjs/pubs.html)
Solomonoff, R.J.: A formal theory of inductive inference, Part I. Information and Control 7(1), 1–22 (1964)
Solomonoff, R.J.: A formal theory of inductive inference, Part II. Information and Control 7(2), 224–254 (1964)
Solomonoff, R.J.: Complexity-based induction systems: comparisons and convergence theorems. IEEE Transactions on Information Theory IT–24(4), 422–432 (1978)
Solomonoff, R.J.: A system for incremental learning based on algorithmic probability. In: Proceedings of the Sixth Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition 515–527 (Dec. 1989)
Solomonoff, R.J.: Three kinds of probabilistic induction: universal distributions and convergence theorems. Appears in Festschrift for Chris Wallace (2003)
Solomonoff, R.J.: Progress in incremental machine learning. TR IDSIA-16-03, revision 2.0. (2003)
Stolcke, A.: On learning context free grammars. PhD Thesis (1994)
Wallace, C.S and Boulton, D.M.: An information measure for classification. Computer Journal 11, 185–195 (1968)
Further Reading
Cover, T. and Thomas, J.: Elements of Information Theory. Wiley, New York (1991) — Good treatments of statistics, predictions, etc.
Li, M. and Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York (1993) (1997) — Starts with elementary treatment and development. Many sections very clear, very well written. Other sections difficult to understand. Occasional serious ambiguity of notation (e.g. definition of “enumerable”). Treatment of probability is better in 1997 than in 1993 edition.
Shan, Y., McKay, R.I., Baxter, R., et al.: Grammar Model-Based Program Evolution. (Dec. 2003) A recent review of work in this area, and what looks like a very good learning system. Discusses mechanics of fitting Grammar to Data, and how to use Grammars to guide Search Problems.
Solomonoff, R.J.: The following papers are all available at the website: world.std.com/ rjs/ pubs.html.
Stolcke, A., Omohundro, S.: Inducing Probabilistic Grammars by Bayesian Model Merging. ICSI, Berkeley (1994) This is largely a summary of Stolcke's: On Learning Context Free Grammars [12].
A Preliminary Report on a General Theory of Inductive Inference. (1960).
A Formal Theory of Inductive Inference. Information and Control, Part I. (1964).
A Formal Theory of Inductive Inference, Part II. (June 1964) — Discusses fitting of context free grammars to data. Most of the discussion is correct, but Sects. 4.2.4 and 4.3.4 are questionable and equations (49) and (50) are incorrect.
A Preliminary Report … and A Formal Theory … give some intuitive justification for the way ALP does induction.
The Discovery of Algorithmic Probability. (1997) — Gives heuristic background for discovery of ALP. Page 27 gives a time line of important publications related to development of ALP.
Progress in Incremental Machine Learning; Revision 2.0. (Oct. 30, 2003) — A more detailed description of the system I'm currently working on. There have been important developments since, however.
The Universal Distribution and Machine Learning. (2003) — Discussion of irrelevance of incom-putability to applications for prediction. Also discussion of subjectivity.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Solomonoff, R.J. (2009). Algorithmic Probability: Theory and Applications. In: Emmert-Streib, F., Dehmer, M. (eds) Information Theory and Statistical Learning. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-84816-7_1
Download citation
DOI: https://doi.org/10.1007/978-0-387-84816-7_1
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-84815-0
Online ISBN: 978-0-387-84816-7
eBook Packages: Computer ScienceComputer Science (R0)