Paper Info
Title
Exact learning via teaching assistants
Abstract
In this paper we introduce and study a new model of exact learning called the teaching assistant model. The new ingredient in this model, as compared to Angluin's model, is that apart from the learner and teacher there is a third agent called teaching assistant. We compare the teaching assistant model with Angluin's model and show that in this model we can do a fine classification of concept classes with respect to the complexity of exact learning. In particular, we consider two algebraic concept classes, namely, permutation groups and linear spaces over finite fields. These concept classes can be seen as special subclasses of the concept class of circuits. In Angluin's exact-learning model these concept classes are, just as the concept class 3-CNF, learnable with equivalence queries but not learnable with membership queries. However, we show that in the teaching assistant model permutation groups are exactly learnable with an LWPP-assistant, and linear spaces over finite fields are exactly learnable with an SPP-assistant. As a negative result, we show that if 3-CNFs are exactly learnable with an LWPP-assistant (SPP-assistant), then NP ⊆ LWPP (respectively, NP ⊆ SPP ).
Year
DOI
Venue
2000
10.1016/S0304-3975(99)00266-2
Theoretical Computer Science - Special issue on algorithmic learning theory
Keywords
DocType
Volume
exact learning,teaching assistant
Journal
241
Issue
ISSN
Citations 
1-2
0304-3975
0
PageRank 
References 
Authors
0.34
10
2
Name
Order
Citations
PageRank
V. Arvind112212.03
N. V. Vinodchandran229430.56