General Lower Bounds on the Query Complexity within the Exact

Abstract.  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 cC. 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 cC in terms of combinatorial complexity measures like the capacity function or the VC-dimension of cC. 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, allows us 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.