Authors: V. Arvind and N.V. Vinodchandran
Email: arvind@imsc.ernet.in
Source: Theoretical Computer Science Vol. 241, No. 1-2, 2000, 51-81.
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).
©Copyright 2000 Elsevier Science