Teaching a smart learner
Sally A. Goldman, H. David Mathias · 1993
We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible.Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner.We prove that any class that can be exactly identified by a polynomial-time algorithm with access to a very rich set of examplebased queries is teachable by a computationally unbounded teacher and a polynomial-time learner.In addition, we present other general results relating this model of teaching to various previous results.We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of decision lists and Horn sentences.