Learning with a Helpful Teacher

Abstract

Recent work in theoretical mac,hine learning has produced many important results, primarily using the PAC-learning model. These results show algorithms to be capable of learning a concept within a certain error tolerance f: with a polynomial number of examples. Experimental machine learning, on the other hand, has produced impressive results using far fewer examples than would be required by PAClearning models. In this paper, we propose a new theoretical model in which the teacher knows the learning algorithm and chooses examples in the best way possible. We call this the Helpful Teacher model, and note that it often requires a very small number of examples to learn a concept. The model applies to both exact learning and approximate learning. We prove some lower and upper bounds for a variety of concept classes, and we observe that some of these bounds correspond closely to recent experimental results. We also note that strategies discovered using this model provide insights into the design of practical machine learning algorithms.