11
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Artem Kaznatcheev ♦
    Apr 3, 2012 at 18:57
  • $\begingroup$ No problem! And feel free to post to the linked CS.SE question. $\endgroup$
    – Lev Reyzin ♦
    Apr 3, 2012 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$
    – Artem Kaznatcheev ♦
    Apr 4, 2012 at 3:11
  • $\begingroup$ Cool. I'd upvote it if I had a CS.SE account :) $\endgroup$
    – Lev Reyzin ♦
    Apr 5, 2012 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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