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 Valiant. Specifically, the paper concerns algorithms that learn to solve problems from sample instances of 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.
Cite
Text
Natarajan. "On Learning from Exercises." Annual Conference on Computational Learning Theory, 1989. doi:10.1016/B978-0-08-094829-4.50008-8Markdown
[Natarajan. "On Learning from Exercises." Annual Conference on Computational Learning Theory, 1989.](https://mlanthology.org/colt/1989/natarajan1989colt-learning/) doi:10.1016/B978-0-08-094829-4.50008-8BibTeX
@inproceedings{natarajan1989colt-learning,
title = {{On Learning from Exercises}},
author = {Natarajan, B. K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1989},
pages = {72-87},
doi = {10.1016/B978-0-08-094829-4.50008-8},
url = {https://mlanthology.org/colt/1989/natarajan1989colt-learning/}
}