ON THE COMPLEXITY OF TEACHING

While most theoretical work in machine learning has focused on the com plexity of learning, recently there has been increasing interest in fo rmally studying the complexity of teaching. In this paper we study the complexity of teaching by considering a variant of the on-line learni ng model in which a helpful teacher selects the instances. We measure the complexity of teaching a concept from a given concept class by a c ombinatorial measure we call the teaching dimension, Informally, the t eaching dimension of a concept class is the minimum number of instance s a teacher must reveal to uniquely identify any target concept chosen from the class. (C) 1995 Academic Press, Inc.