Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.

We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.

Are there any known lower bounds on the number of queries in the membership and counterexample model?

I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.

If there are no lower-bounds: Are there known bariers to proving query lower bounds in this model?

Related questions

Are there improvements on Dana Angluin's algorithm for learning regular sets


Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time. There is a whole paper developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.

One easy way to get lower bounds is information-theory. You can figure out how many distinct targets there are and how many bits a query gives you, etc. These upper bounds come close but aren't there. There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner. A well-chosen counterexample can give away quite a lot of information.

Update to the discussion above: Angluin and Dohrn address the question learning with random counterexamples in a recent paper.

  • $\begingroup$ Thanks for the answer! Do you mind if I give your answer to my linked question on the linked question (with links back here)? Or do you plan to make a CS.SE account? I totally agree with paragraph 3, I was fooling around with demanding that the tutor give a minimal counterexample and learning seems to become much easier. $\endgroup$ Apr 3 '12 at 18:57
  • $\begingroup$ No problem! And feel free to post to the linked CS.SE question. $\endgroup$
    – Lev Reyzin
    Apr 3 '12 at 21:05
  • $\begingroup$ I read through the relevant part of Schapire's thesis (section 5.4.5) and summarized the improvement, hopefully I got the gist right. I will look more closely at the lower-bounds paper you cite later in the week :D. $\endgroup$ Apr 4 '12 at 3:11
  • $\begingroup$ Cool. I'd upvote it if I had a CS.SE account :) $\endgroup$
    – Lev Reyzin
    Apr 5 '12 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.