Foundational Papers in Complexity Science pp. 793–822
DOI: 10.37911/9781947864535.25
A General System for Machine Learning
Author: Paul M. B. Vitányi, CWI and University of Amsterdam
Excerpt
Ray J. Solomonoff (1926–2009), founding father of algorithmic information theory, was born in Cleveland, Ohio in the United States. Algorithmic information theory (Li and Vitányi 2019) deals with the shortest effective description length of objects and is commonly designated by the term “Kolmogorov complexity.”
The latter notion was a side product of his approach to induction. His crucial results concerning prediction, in 1960 and later, partially resolve the old philosophical problem of how to obtain a valid prior distribution in Bayes’s rule by showing that a single “universal” distribution can be used instead of any computable prior with almost the same resulting predictions. This may be viewed as a central problem of artificial intelligence, machine learning, and statistical inference—with the caveat that the universal distribution is incomputable. Solomonoff’s theory has led to feasible induction and prediction procedures (Fine 1973). His contributions to science together with biographical remarks are outlined in Gács and Vitányi (2011) and Li and Vitányi (2019), while his scientific autobiography up to 1997 can be found in Solomonoff (1997).
Bibliography
Carnap, R. 1950. Logical Foundations of Probability. Chicago, IL: University of Chicago Press.
Cover, T. M. 1974. Universal Gambling Schemes and the Complexity Measures of Kolmogorov and Chaitin. Technical report 12. Stanford University Department of Statistics.
Fine, T. L. 1973. Theories of Probability: An Examination of Foundations. New York, NY: Academic Press.
Gács, P., and P. M. B. Vitányi. 2011. “Raymond J. Solomonoff 1926–2009.” IEEE Information Theory Society Newsletter 61 (1): 11–16. https://www.itsoc.org/sites/default/files/2021-03/nits-NL_0311-Web.pdf.
Grünwald, P. D. 2007. The Minimum Description Length Principle. Cambridge, MA: MIT Press.
Hutter, M. 2005. Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Berlin, Germany: Springer-Verlag.
Li, M., and P. M. B. Vitányi. 2019. Introduction to Kolmogorov Complexity and Its Applications. 4th. New York, NY: Springer.
Rissanen, J. J. 1983. “A Universal Prior for Integers and Estimation by Minimal Description Length.” Annals of Statistics 11 (2): 416–431. https://doi.org/10.1214/aos/1176346150.
—. 1989. Stochastic Complexity in Statistical Inquiry. London, UK: World Scientific Publishing.
—. 2007. Information and Complexity in Statistical Modeling. New York, NY: Springer.
Solomonoff, R. J. 1960. A Preliminary Report on a General Theory of Inductive Inference. Technical report V-131. Zator Company, Cambridge, MA.
—. 1964. “A Formal Theory of Inductive Inference, Part I.” Information and Control 7 (1): 1–22. https://doi.org/10.1016/S0019-9958(64)90223-2.
—. 1997. “The Discovery of Algorithmic Probability.” Journal of Computer and System Sciences 55 (1): 73–88. https://doi.org/10.1006/jcss.1997.1500.
Vovk, V. G. 1989. “Prediction of Stochastic Sequences.” Problems of Information Transmission 25 (4): 285–296.
Zvonkin, A. K., and L. A. Levin. 1970. “The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms.” Russian Mathematical Surveys 25 (6): 83–124. https://doi.org/10.1070/RM1970v025n06ABEH001269.