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

• "Haystack dimension" characterizes the query complexity of optimizing a function: cis.upenn.edu/~mkearns/papers/haystack.pdf , This is different than what you want, but you might enjoy the related work which discusses what is known about characterizing the query complexity of exact learning. – Aaron Roth Dec 1 '15 at 19:38

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

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

• I don't understand why the teaching dimension upper bounds the query complexity of learning $f$. What does the algorithm look like? The function $f$ in unknown to the algorithm when we start, so it cannot simply query the teaching set for $f$. – Robin Kothari Nov 27 '15 at 22:46
• @RobinKothari TD lower bounds the minimum number of queries in any MQ-algorithm. In practice, there may be no algorithm that blindly achieves this bound without cheating or code tricks. In Angluin's "Queries Revisited" paper, she discussed a parameter called MQ that represent the number of queries needed by the best MQ-algorithm in the worst case. I don't recall its details but certainly TD<=MQ. – seteropere Nov 28 '15 at 0:32
• What I was interested in (when I asked this question) was a parameter that characterizes exact learning with membership queries. It should be both an upper and lower bound. I provided an example of a parameter that achieves this (up to a log |C| factor) in the question. My question was whether something better is known. – Robin Kothari Nov 28 '15 at 3:11