Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1995-01-01

Filename

WUCS-95-16.PDF

DOI:

10.7936/K70C4T1X

Technical Report Number

WUCS-95-16

Abstract

Previous teaching models in the learning theory community have been batch models. That is, in these models the teacher has generated a single set of helpful examples to present to the learner. In this paper we present an interactive model in which the learner has the ability to ask queries as in the query learning model of Angluin [1]. We show that this model is at least as powerful as previous teaching models. We also show that anything learnable with queries, even by a randomized learner, is teachable in our model. In all previous teaching models, all classes shown to be teachable are known to be efficiently learnable. An important concept class that is not known to be learnable is DNF formulas. We demonstrate the power of our approach by providing a determinstic teacher and learner for the class of DNF formulas. The learner makes only equivalence queries and all hypotheses are also DNF formulas.

Comments

Permanent URL: http://dx.doi.org/10.7936/K70C4T1X

Download

Share

COinS