Exact learning via teaching assistants

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).