Complexity of Teaching by a Restricted Number of Examples

Abstract

Teaching is inextricably linked to learning, and there are many studies on the complexity of teaching as well as learning in computational learning theory. In this paper, we study the complexity of teaching in the situation that the number of examples is restricted, especially less than its teaching dimension. We formulate a model of teaching by a restricted number of examples, where the complexity is measured by the maximum error to a target concept. We call a concept class is optimally incrementally teachable if the teacher can optimally teach it to the learner whenever teaching is terminated. We study the complexity of the three concept classes of monotone monomials, monomials without the empty concept, and monomials in our model. We show that the boundary of optimally incremental teachability is different from that of polynomial teachability in the classical model. We also show that inconsistent examples help to reduce the maximum error in our model.