<p>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. </p>

<p><em>If</em> 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.
<a href="http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf" rel="nofollow">http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf</a>
for actual state-of-the-art bounds. </p>

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

<p>But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in <em>some</em> 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 <em>all</em> distributions, then it would also break RSA and related cryptographic primitives:
<a href="http://dl.acm.org/citation.cfm?id=697797" rel="nofollow">http://dl.acm.org/citation.cfm?id=697797</a></p>

CC BY-SA 3.0
2015-05-08T07:29:27.780Z
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.
Aryeh
CC BY-SA 3.0
2015-05-08T07:08:03.833Z
2015-05-08T07:08:03.833Z
Aryeh
<p>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.</p>

<p>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 <a href="https://linguistics.stackexchange.com/questions/414/what-is-an-example-of-a-syntactic-structure-that-cant-be-represented-by-a-bnf-g">cross-serial dependencies in Dutch or Swiss-German</a>. 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).</p>

CC BY-SA 3.0
2014-11-07T15:25:35.467Z
2014-11-07T15:25:35.467Z
2017-04-13T12:54:12.010Z
babou
<p>Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see <a href="http://eccc.hpi-web.de/report/2011/108/" rel="nofollow">ECCC Report: TR11-108</a>, section 7, pp 25-31):</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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"?</p>

CC BY-SA 3.0
2014-11-07T15:47:00.607Z
Have you read the work of Kearns and Valiant? Maybe that's a nice place to start.
john_leo
CC BY-SA 3.0
2015-01-08T21:59:02.103Z
this is probably the TCS equivalent of something like the [Generalization error](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Deep_learning) advances general research in this area. also note (re linguistics) human do this successfully at young age...
vzn
CC BY-SA 3.0
2015-05-07T08:23:26.640Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2015-05-07T14:52:51.813Z
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...
vzn
CC BY-SA 3.0
2015-05-07T15:43:31.273Z
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).
Aryeh
CC BY-SA 3.0
2015-05-07T17:20:05.407Z
@vzn I do think the strong criticism is justified, and you continue to make uninformed remarks. The concept of generalization is the same. Generalization bounds can be proved for very practical things like SVMs. See Chapter 26 of Shalev-Schwartz and Ben-David's "Understanding Machine Learning".
Sasho Nikolov
CC BY-SA 3.0
2015-05-07T23:37:31.683Z
wrt Aryeh comments, think there may be different concepts of _generalization_ being thrown around & this could be sorted out. had linked to the one intended (concede it is more _applied_), think the statements are accurate wrt it & SN is _overreacting._ suggest [chat] for further _civil/ constructive_ analysis if actually possible, & think this is starting to verge on [Sayrian](http://en.wikipedia.org/wiki/Sayre%27s_law)
vzn
CC BY-SA 3.0
2015-05-08T04:40:29.640Z
@vzn I do not wish to waste time on chat, I just suggest you stop making misleading and poorly researched comments when they do not add value. Once again, the concept of generalization is the same, it's not true that there are different notions of generalization "thrown around". Aryeh's comment is perfectly accurate: the only issue is computational, otherwise Occam's razor takes care of generalization.
Sasho Nikolov
CC BY-SA 3.0
2015-05-08T04:59:23.740Z
_sigh @#$&_ the original comment _hedged_ and said only _probably._ from the 1st page of the wikipedia article cited: **The generalization error of a machine learning model is a function that measures how well a learning machine generalizes to unseen data.** that is _beyond_ an undecidable problem, it is an _impossible_ problem in general/ theory. for every finite set of data, there is a "model" _(function/ algorithm)_ that _perfectly_ fits it and is _wrong_ on _all_ elements of the unseen data, based on a simple halting-problem like proof....! & isnt this basic stuff taught to undergraduates?
vzn
CC BY-SA 3.0
2015-05-08T05:15:38.213Z
see also [bias variance tradeoff](http://en.wikipedia.org/wiki/Bias%E2%80%93variance_tradeoff) _"The bias–variance tradeoff is a central problem in supervised learning. Ideally, one wants to choose a model that both accurately captures the regularities in its training data, but also **generalizes** well to **unseen data**. Unfortunately, **it is typically impossible to do both simultaneously**."_
vzn
CC BY-SA 3.0
2015-05-08T05:34:35.637Z
@vzn yes, that's why you restrict the concept class. that's done in theory and practice. and is absolutely basic stuff. generalization error is always with respect to a concept class and things like Rademacher complexity and VC dimension measure the capacity of the concept class.
Sasho Nikolov
CC BY-SA 3.0
2015-05-08T05:38:01.030Z
@Aryeh maybe you can make your comment into an answer?
Sasho Nikolov
CC BY-SA 3.0
2015-05-08T07:35:05.320Z
@vzn seems to be saying: there are too many grammars out there, so even if you find one consistent with the data, how do you know it will generalize well on new data? Answer: if you choose the "smallest" or "simplest" consistent grammar, you are guaranteed a generalization bound that decays roughly as [hypothesis grammar description size]/[sample size].
Aryeh
CC BY-SA 3.0
2015-05-08T15:01:22.417Z
there is more than one way to define _generalization_ & the theoretical literature defns apparently do not exactly match that from applied ML. seems there are simplified/ "restricted"/ "near-_toy_" problems from theory for which one can say may have "optimal generalizations" in narrow senses as A/SN seem to be asserting (eg "simple(r)" language classes such as DFAs/ CFLs etc). lets find a way to agree eh? :) ... note the original question referred to randomness and did _not_ restrict the grammars... note recursively enumerable languages are also _grammars_... note also kolmogorov complexity!
vzn
<cc.complexity-theory><lg.learning><grammars><philosophy>
Which factors make the problem of inferring the grammar difficult?
Pigmann
# Which factors make the problem of inferring the grammar difficult?

(Asked by: username_0 on 2014-11-05)

Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see [ECCC Report: TR11-108](http://eccc.hpi-web.de/report/2011/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"?

**Tags:** cc.complexity-theory, lg.learning, grammars, philosophy

> **Comments:**
> **username_1**: Have you read the work of Kearns and Valiant? Maybe that's a nice place to start.  
> **username_2**: this is probably the TCS equivalent of something like the [Generalization error](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Deep_learning) advances general research in this area. also note (re linguistics) human do this successfully at young age...  
> **username_3**: @username_2 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.  
> **username_2**: 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...  
> **username_4**: 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).  
> **username_3**: @username_2 I do think the strong criticism is justified, and you continue to make uninformed remarks. The concept of generalization is the same. Generalization bounds can be proved for very practical things like SVMs. See Chapter 26 of Shalev-Schwartz and Ben-David's "Understanding Machine Learning".  
> **username_2**: wrt username_4 comments, think there may be different concepts of _generalization_ being thrown around & this could be sorted out. had linked to the one intended (concede it is more _applied_), think the statements are accurate wrt it & SN is _overreacting._ suggest [chat] for further _civil/ constructive_ analysis if actually possible, & think this is starting to verge on [Sayrian](http://en.wikipedia.org/wiki/Sayre%27s_law)  
> **username_3**: @username_2 I do not wish to waste time on chat, I just suggest you stop making misleading and poorly researched comments when they do not add value. Once again, the concept of generalization is the same, it's not true that there are different notions of generalization "thrown around". username_4's comment is perfectly accurate: the only issue is computational, otherwise Occam's razor takes care of generalization.  
> **username_2**: _sigh @#$&_ the original comment _hedged_ and said only _probably._ from the 1st page of the wikipedia article cited: **The generalization error of a machine learning model is a function that measures how well a learning machine generalizes to unseen data.** that is _beyond_ an undecidable problem, it is an _impossible_ problem in general/ theory. for every finite set of data, there is a "model" _(function/ algorithm)_ that _perfectly_ fits it and is _wrong_ on _all_ elements of the unseen data, based on a simple halting-problem like proof....! & isnt this basic stuff taught to undergraduates?  
> **username_2**: see also [bias variance tradeoff](http://en.wikipedia.org/wiki/Bias%E2%80%93variance_tradeoff) _"The bias–variance tradeoff is a central problem in supervised learning. Ideally, one wants to choose a model that both accurately captures the regularities in its training data, but also **generalizes** well to **unseen data**. Unfortunately, **it is typically impossible to do both simultaneously**."_  
> **username_3**: @username_2 yes, that's why you restrict the concept class. that's done in theory and practice. and is absolutely basic stuff. generalization error is always with respect to a concept class and things like Rademacher complexity and VC dimension measure the capacity of the concept class.  
> **username_3**: @username_4 maybe you can make your comment into an answer?  
> **username_4**: @username_2 seems to be saying: there are too many grammars out there, so even if you find one consistent with the data, how do you know it will generalize well on new data? Answer: if you choose the "smallest" or "simplest" consistent grammar, you are guaranteed a generalization bound that decays roughly as [hypothesis grammar description size]/[sample size].  
> **username_2**: there is more than one way to define _generalization_ & the theoretical literature defns apparently do not exactly match that from applied ML. seems there are simplified/ "restricted"/ "near-_toy_" problems from theory for which one can say may have "optimal generalizations" in narrow senses as A/SN seem to be asserting (eg "simple(r)" language classes such as DFAs/ CFLs etc). lets find a way to agree eh? :) ... note the original question referred to randomness and did _not_ restrict the grammars... note recursively enumerable languages are also _grammars_... note also kolmogorov complexity!  

---

## 2 answers

### Answer by username_4 on 2015-05-08. Score: 3

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>

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_5 on 2014-11-07. Score: 0

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](https://linguistics.stackexchange.com/questions/414/what-is-an-example-of-a-syntactic-structure-that-cant-be-represented-by-a-bnf-g). 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).


---

