Combinatorial characterization of exact learning with membership queries

Question

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)$.)

Answer 1

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.

Answer 2

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).

Answer 3

Although others have pointed out the answer. I thought I may make it self-contained and show why teaching dimension is the answer.

Consider a concept class $C$ over input space $X$. A set of elements $S\subseteq X$ is called a teaching set for a concept $f$ if $f$ is the only concept in $C$ consistent with $S$.

Let $\mathcal{T}(f)$ be the set of all teaching sets for $f$ and define TD$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$ to be the teaching dimension of $f$. i.e., the cardinality of the smallest teaching set TS$_{min}(f)$ in $\mathcal{T}(f)$. Similarly, consider TD$(C)=$max$_{f\in C}$TD$(f,C)$ to be the teaching dimension of $C$.

The minimum number of queries needed to identify $f$ is TD$(f,C)$. This happens when the query strategy uses the sequence TS$_{min}(f)$. As for any fewer queries we have at least two concepts consistent with it. And TD$(C)$ is the minimum for any $f$.