Making Solomonoff Induction Effective Or: You Can Learn What You Can Bound

摘要

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.