One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. In particular, we consider learning from a teacher who labels examples +'' (a positive instance of the concept being learned), &'' (a negative instance of the concept being learned), and ?'' (an instance with unknown classification), in such a way that knowledge of the concept class and all the positive and negative examples is not sufficient to determine the labelling of any of the examples labelled with ?''. The goal of the learner is not to compensate for the ignorance of the teacher by attempting to infer +'' or &'' labels for the examples labelled with ``?'', but is rather to learn (an approximation to) the ternary labelling presented by the teacher. Thus, the goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We present general results describing when known learning algorithms can be used to obtain algorithms that learn from a consistently ignorant teacher. We investigate the learnability of a variety of concept classes in this model, including monomials, monotone DNF formulas, Horn sentences, decision trees, DFAs, and axis-parallel boxes in Euclidean space, among others. Both learnability and non-learnability results are presented. ] 1996 Academic Press, Inc.
Consistency requires you to be as ignorant today as you were a year ago. '' Bernard Berenson (1865 1959) Variations of the basic theoretical models of concept learning allow for the possibility that the information given to the learning algorithm does not come from an omniscient'' teacher, but instead may be inaccurate. Nonetheless, in most of these variations, it is assumed that underlying the inaccurate information is some ``correct'' classification of article no.