|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-01-090
2001-090
A
New Abstract Combinatorial Dimension for Exact Learning via Queries
JL Balcazar, J Castro,
D Guijarro
ABSTRACT
We introduce an abstract model of exact learning via queries that
can be instantiated to all the query learning models currently in
use, while being closer to them than previous unifying attempts. We
present a characterization of those Boolean function classes learnable
in this abstract model, in terms of a new combinatorial notion that
we introduce, the abstract identification dimension. Then we prove
that the particularization of our notion to specific known protocols
such as equivalence, membership, and membership and equivalence queries
results in exactly the same combinatorial notions currently known
to characterize learning in these models, such as strong consistency
dimension, extended teaching dimension, and certificate size. Our
theory thus fully unifies all these characterizations. For models
enjoying a specific property that we identify, the notion can be simplified
while keeping the same characterizations of all those other models
for query learning proposed in the literature. We can also obtain
the first polynominal-query learning algorithms for specific interesting
problems such as learning DNF with proper subset and superset queries.
Download
Postscript
|