Abstract
The notion of effective learnability is analyzed by relating it to the proof-theoretic strength of an axiom system which is used to derive totality proofs for recursive functions. The main result, the generator-predictor theorem, states that an infinite sequence of bits is learnable if the axiom system proves the totality of a recursive function which dominates the time function of the bit sequence generating process.
This result establishes a tight connection between learnability and provability, thus reducing the question of what can be effectively learned to the foundational questions of mathematics with regard to set existence axioms. Results of reverse mathematics are used to illustrate the implications of the generator-predictor theorem by connecting a hierarchy of axiom systems with increasing logical strength to fast growing functions.
Our results are discussed in the context of the probabilistic universal induction framework pioneered by Solomonoff, showing how the integration of a proof system into the learning process leads to naturally defined effective instances of Solomonoff induction. Finally, we analyze the problem of effective learning in a framework where the time scales of the generator and the predictor are coupled, leading to a surprising conclusion.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge University Press (2009)
Friedman, H.: Some systems of second order arithmetic and their use. In: Proceedings of the International Congress of Mathematicians, Vancouver, B.C, vol. 1, pp. 235–242. Canad. Math. Congress, Montreal (1974)
Gold, E.M.: Language identification in the limit. Information and Control 10(5), 447–474 (1967)
Goodstein, R.: On the restricted ordinal theorem. Journal of Symbolic Logic 9, 33–41 (1944)
Huber, F., Schmidt-Petri, C. (eds.): Degrees of Belief. Springer (2009)
Hutter, M.: The fastest and shortest algorithm for all well-defined problems. International Journal of Foundations of Computer Science 13(3), 431–443 (2002)
Hutter, M.: Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability. Springer (2005)
Legg, S.: Is There an Elegant Universal Theory of Prediction? In: Balcázar, J.L., Long, P.M., Stephan, F. (eds.) ALT 2006. LNCS (LNAI), vol. 4264, pp. 274–287. Springer, Heidelberg (2006)
Li, M., Vitányi, P.M.B.: An introduction to Kolmogorov complexity and its applications, 3rd edn. Graduate Texts in Computer Science. Springer (2008)
Rathjen, M.: The art of ordinal analysis. In: Proceedings of the International Congress of Mathematicians, pp. 45–69. Eur. Math. Soc. (2006)
Simpson, S.G.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press (2009)
Solomonoff, R.: A formal theory of inductive inference, part I. Information and Control 7(1), 1–22 (1964)
Solomonoff, R.: A formal theory of inductive inference, part II. Information and Control 7(2), 224–254 (1964)
Weihrauch, K.: Computable analysis. Springer (2000)
Zimmermann, J., Cremers, A.B.: The Quest for Uncertainty. In: Calude, C.S., Rozenberg, G., Salomaa, A. (eds.) Maurer Festschrift. LNCS, vol. 6570, pp. 270–283. Springer, Heidelberg (2011)
Zimmermann, J., Cremers, A.B.: Proof-driven learning systems (2012) (preprint)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zimmermann, J., Cremers, A.B. (2012). Making Solomonoff Induction Effective. In: Cooper, S.B., Dawar, A., Löwe, B. (eds) How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30870-3_75
Download citation
DOI: https://doi.org/10.1007/978-3-642-30870-3_75
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30869-7
Online ISBN: 978-3-642-30870-3
eBook Packages: Computer ScienceComputer Science (R0)