# Combinatorial characterization of exact learning with membership queries

Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I may not know it. Even a comment like "I work in the area, but I haven't seen a characterization like this" would be helpful!

Background:

There are several well-studied models of learning in learning theory (e.g., PAC learning, online learning, exact learning with membership/equivalence queries).

For example, in PAC learning, the sample complexity of a concept class has a nice combinatorial characterization in terms of the VC dimension of the class. So if we want to learn a class with constant accuracy and confidence, this can be done with $\Theta(d)$ samples, where $d$ is the VC dimension. (Note that we're talking about sample complexity, not time complexity.) There is also a more refined characterization in terms of the accuracy and confidence. Similarly, the mistake bound model of online learning has a nice combinatorial characterization.

Question:

I want to know if a similar result is known for the model of exact learning with membership queries. The model is defined as follows: We have access to a black box which on input $x$ gives you $f(x)$. We know $f$ comes from some concept class $C$. We want to determine $f$ with as few queries as possible.

Is there a combinatorial parameter of a concept class $C$ that characterizes the number of queries needed to learn a concept in the model of exact learning with membership queries?

What I know:

The best such characterization I have found is in this paper by Servedio and Gortler, using a parameter they attribute to Bshouty, Cleve, Gavaldà, Kannan and Tamon. They define a combinatorial parameter called $\gamma^C$, where $C$ is the concept class, which has the following properties. (Let $Q_C$ be the optimal number of queries needed to learn $C$ in this model.)

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

This characterization is almost tight. However, there could be a quadratic gap between the upper and lower bounds. For example if $1/\gamma^C = \log |C| = k$, then the lower bound is $\Omega(k)$, but the upper bound is $O(k^2)$. (I also think this gap is achievable, i.e., there exists a concept class for which the lower bounds are both $\Omega(k)$, but the upper bound is $O(k^2)$.)

-

To drive home the point of anonymous moose's example, consider the concept class that consists of functions that output 1 on only one point in {0,1}^n. The class is of size 2^n, and 2^n queries are needed in the worst-case. Take a look at worst-case Teaching Dimension (Goldman & Schapire) which provides something similar to what you're looking for.

-
Thanks! Searching for the Teaching Dimension led me to the Extended Teaching Dimension, which is similar to the combinatorial parameter I mentioned in the question, which then led me to many other interesting papers on the topic. –  Robin Kothari Dec 5 '12 at 22:31

I don't know of such a characterization. However, it's worthwhile to note that for almost any concept class, one needs to query all points. To see this, consider the concept class that consists of all n-dimensional boolean vectors with Hamming weight 1. This concept class obviously requires n queries to learn, which is equal to its cardinality. You can probably generalize this observation to get that almost any concept class also requires performing all queries.

I would suspect that given a concept class C as input, it is NP-hard to determine the complexity of exactly learning the concept class with membership queries, or even to approximate it up to say a constant. This would give some indication that a "good" combinatorial characterization does not exist. If you wish to prove such an NP-hardness result but try and fail feel free to post here and I'll see if I can figure it out (I have some ideas).

-
Thanks for the response. Even if it is true that almost all concept classes (under some reasonable distribution over classes) are hard to learn, some classes are easy to learn and it would be interesting to have a combinatorial parameter that characterizes this. I don't mind if the parameter is hard to compute. Even the VC dimension is not known to be efficiently computable. –  Robin Kothari Dec 5 '12 at 4:22