6
$\begingroup$

Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31):

Following the work of Kearns and Valiant, we now know that many natural learning problems — as an example, inferring the rules of a regular or context-free language from random examples of grammatical and ungrammatical sentences — are computationally intractable.

My question is: Which factors make the problem of inferring the grammar difficult? Is the introducing random examples of ungrammatical sentences? If so, what would happen if the condition of "random examples of grammatical and ungrammatical sentences" is replace with "random examples of grammatical sentences with probability p>0 and random examples of ungrammatical sentences with probability 1-p"?

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ Have you read the work of Kearns and Valiant? Maybe that's a nice place to start. $\endgroup$
    – john_leo
    Commented Nov 7, 2014 at 15:47
  • $\begingroup$ this is probably the TCS equivalent of something like the Generalization error in machine learning. basically no algorithm can theoretically succeed in finding a generalization from finite examples (there are an infinite number of different models that agree with the data). practically, however, with "real world data", its an entirely different matter. the entire new field deep learning advances general research in this area. also note (re linguistics) human do this successfully at young age... $\endgroup$
    – vzn
    Commented Jan 8, 2015 at 21:59
  • $\begingroup$ @vzn what you are saying is inaccurate and very misleading. the generalization error can be bounded for many infinite concept classes using e.g. Rademacher complexity, and the bounds are "theoretical", i.e. they are theorems rather than empirical observations. the point is that the measure of complexity is not really size, even for finite concept classes where one looks at things like VC dimension. $\endgroup$
    – Sasho Nikolov
    Commented May 7, 2015 at 8:23
  • $\begingroup$ seems the classes for which generalization error can be theoretically bounded (not too familiar with them) are "contrived" and defn not "random" as requested... or it may be a different defn of the technical concept of "generalization" than used in (more empirical/ statistical) machine learning... its a comment/ lead, not an answer... maybe you can work your pov into an answer... dont think the strong criticism is justified... $\endgroup$
    – vzn
    Commented May 7, 2015 at 14:52
  • 1
    $\begingroup$ Let's stick to regular grammmars for concreteness. The problem is purely computational. IF you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc). $\endgroup$
    – Aryeh
    Commented May 7, 2015 at 15:43

2 Answers 2

Reset to default
3
$\begingroup$

Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The source of difficulty is purely computational; the statistical aspects are quite straightforward.

If you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). See Theorems 2 and 3 of Graepel et al. http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf for actual state-of-the-art bounds.

However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc): http://www.sciencedirect.com/science/article/pii/S0019995878906836 http://web.mit.edu/6.863/www/spring2010/readings/gold67limit.pdf http://dl.acm.org/citation.cfm?id=138042 [the latter even gives a hardness-of-approximation result].

But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in some representation (i.e., a mechanism for predicting the labels of test strings drawn from the same distribution as the training set). If such an algorithm were to exist, and succeeded against all distributions, then it would also break RSA and related cryptographic primitives: http://dl.acm.org/citation.cfm?id=697797

Improve this answer
$\endgroup$
1
  • $\begingroup$ For completeness, I should add that the "learning" above refers to the PAC model, which is not the only one -- just the most natural/popular one. But do look up Gold's "learning in the limit" and various "online" learning models. $\endgroup$
    – Aryeh
    Commented May 8, 2015 at 7:29
0
$\begingroup$

I have not read the paper, but I doubt strongly it is as simple as what you suggest. The first obvious remark is that whatever you provide with examples is finite, so it can be recognized precisely by a FSA. Hence you need some definition of the complexity of a grammar, and what you probably want is a grammar of some type that makes your sentences grammatical with a small (minimal?) complexity grammar. Adding probabilities may or may not help.

Then you may want to go further and try to identify sentences that may not fit the class of grammars you have chosen, though that is apparently not part of what you are considering. I am thinking for example of the work of linguists. Though they can express a good deal of natural language syntax with Context-Free grammars (well, for a basic grammatical skeleton), some languages do not fit that model, such as the cross-serial dependencies in Dutch or Swiss-German. This can be handled by another type of grammars: the Tree Adjoining Grammars (TAG), which include CF grammars (in the sense of strong equivalence of parse-trees).

Improve this answer
$\endgroup$

Your Answer

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

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