ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING
Date
1994-04-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We show that the class of all circuits is exactly learnable in
(randomized) expected polynomial-time using subset and superset
queries. Subset and superset queries are a generalization of
equivalence queries, where an instance of a negative counterexample
is requested (for subset queries) or a positive counterexample is
requested (for superset queries).
Our result is a consequence of the following result which we
consider to be of independent interest: the class of all circuits
is exactly learnable in (randomized) expected polynomial-time with
equivalence queries and the aid of an NP-oracle. This improves the
previous result of Gavald\o'a\(ga' [G93] where a $SIGMA~pile {p above
3 }$-oracle and equivalence queries are required in place of the
NP-oracle and equvalence queries, and the learning algorithm is
deterministic.
The hypothesis class for both of the above learning algorithms is the
class of circuits of slightly larger (polynomially related) size. Also,
the algorithms can be adapted to learn the class of DNF formulas with
hypothesis class consisting of depth-3 $andsign - orsign - andsign$ formulas
(by the work of Angluin [A90], this is optimal in the sense that
the hypothesis class cannot be reduced to depth-2 DNF formulas).
We also found deterministic learning algorithms that use \fImembership\fR
queries and the NP-oracle for learning monotone boolean functions and
the class 0(log $n$)-DNF $cap$ 0(log $n$)-CNF. The running time of these
algorithms are polynomial in $n$, DNF size and CNF size of the target
formula. Finally with an NP-oracle and membership queries, there is a
randomized polynomial-time algorithm that learns any class that is
learnable from membership queries with unlimited computational power.
Description
Keywords
Computer Science