|
NeuroCOLT
Technical Report NC-TR-97-015
Exact
Learning of subclasses of CDNF formulas with membership queries
Carlos
Domingo
Universitat Politècnica de Catalunya
Spain
Abstract
We consider the exact learnability of subclasses of Boolean
formulas from membership queries alone. We show how to combine known
learning algorithms that use membership and equivalence queries to
obtain new learning results only with memberships. In particular we
show the exact learnability of read-$k$ monotone CDNF formulas, Sat-$k$
${\cal O}(\log n)$-CDNF, and ${\cal O}(\sqrt{\log n})\mbox{-size CDNF}$
from membership queries only.
Download Compressed Postscript
|