|
NeuroCOLT
Technical Report NC-TR-94-002
The Complexity
of Learning with Queries
by Ricard Gavalda, Department
of Software (LSI),
Universitat Politecnica de Catalunya,
Pau Gargallo 5, E-08028 Barcelona, Spain
Abstract
We survey recent research concerning
the qualitative complexity of Angluin's model of learning with queries.
In this model, there is a learner that tries to identify a target
concept by means of queries to a teacher. Thus, the process
can be naturally formulated as an oracle computation. Among the results
we review there are: characterizations of the power of different
learning protocols by complexity classes of oracle machines; relations
between the complexity of learning and the complexity of computing
advice functions for nonuniform classes; and combinatorial characterizations
of the concept classes that are learnable in specific protocols.
Download Compressed Postscript
|