General lower bounds on the query complexity within the exact learning model Original Research Article

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 C is the smallest number of queries which suffices (in the worst case) to exactly identify an unknown target concept C∈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 C in terms of combinatorial complexity measures like the capacity function or the VC-dimension of 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, 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.