Learning from a consistently ignorant teacher

Michael Frazier, Sally Goldman, Nina Mishra, Leonard Pitt

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)471-492
Number of pages22
JournalJournal of Computer and System Sciences
Volume52
Issue number3
DOIs
StatePublished - Jun 1996
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Learning from a consistently ignorant teacher'. Together they form a unique fingerprint.

Cite this