Learning from a Consistently Ignorant Teacher

摘要

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-learn- ability results are presented.