Norbert Klasner, Hans Ulrich Simon:
In the exact learning model, a learner has to exactly identify a
hidden target concept by means of queries. The query complexity of a
concept class $\cC$ is the smallest number of queries which suffices
(in the worst case) to exactly identify an unknown target concept $C
\in {\cal C}$. Popular query types are equivalence and membership
queries, for instance. In this paper, we prove general lower bounds on
the query complexity of a concept class ${\cal C}$ in terms of
combinatorial complexity measures like the capacity function or the
VC-dimension of ${\cal C}$. These bounds are parameterized by an
additional parameter $k$, and are valid for all collections of query
types which include equivalence queries and (arbitrarily many) other
types of queries with at most $k$ possible answers. They are tight
(up to an asymptotically negligible additive term). Special cases of
the most general lower bound lead to improvements of previous bounds.
The methods, that we apply to derive the various lower bounds, allow
to compare the power of equivalence queries with the power of queries
with at most $k$ answers. It turns out that (for concept classes
whose query complexity asymptotically matches the lower bounds) in a
first phase queries with at most $k$ answers provide more information.
In a second phase equivalence queries become more effective. The last
two sections of the paper are devoted to a discussion of the
``breakpoint'', where the learner should switch from Phase 1 to Phase
2. Besides this intuitive insight into the power of different query
types, our proof method has a strong combinatorial flavor and the
auxiliary results may be interesting in their own right.
Last update: 11/17/98. Norbert Klasner,
klasner@lmi.ruhr-uni-bochum.de.
Return to list of my publications.