On Learning from Exercises

Abstract

This paper explores a new direction in the formal theory of learning - learning in the sense of improving computational efficiency as opposed to concept learning in the sense of Valiar'. Specifically, the paper concerns algorithms that learn to solve problems from sample instances ot the problems. We develop a general framework for such learning and study the framework over two distinct random sources of sample instances. The first source provides sample instances together with their solutions, while the second source provides unsolved instances or "exercises". We prove two theorems identifying conditions sufficient for learning over the two sources, our proofs being constructive in that they exhibit learning algorithms. To illustrate the scope of our results, we discuss their application to a program that learns to solve restricted classes of symbolic integrals.