General mathematical frameworks of language acquisition since Gold

Question

Gold's theorem on the unlearnability of certain sets of languages (among them context-free ones) made several assumptions in its modeling of learning a language:

1. At each time step the learner receives one sentence from our language, and for each sentence in our language there is some finite time by which the learner will have been exposed to the sentence. Apart from this, there are no restrictions on the ordering or frequency of occurrence of the sentences (in fact, the environment might pick sentences in an adversarial order to make learning hard).

2. There are absolutely no restrictions on the learner's learning strategy (in fact, it need not even be computable)

3. The languages in our sets of languages are named (equivalently: numbered). A learner has successfully learned a language L if for any environment consistent with (1) there is some finite time after which the learner always guesses that the environment's language is L. A set of languages is learnable if there exists a single learner that can learn every language in the set.

Back in the late 60s and 70s this theorem made a bit of a stir in the povery of the stimulus debate. However, the modeling is pretty simple, how has this model of language learning been refined by linguists in the years since?

---

Notes

• I am interested only in formal refinements of the above model. Thus, replacing rule (2) by "the learner's learning strategy must be a Turing Machine that takes as input the finite segment of sentences seen so far and outputs the name of a language" is fine, but a replacement like "the learner is an average child" is not of interest (unless the authors have a formal definition of average-child).

• Modifications that change the input (say to allow explicit negative instances) or impose a distribution on it are fine, but obviously rule (3) must be modified accordingly. I think this is how people show the learnability of stochastic context-free grammars.

• I am not interested in arguments that try to trivially undercut the whole approach, even if they have empirical validity. For instance, the whole approach can be derailed by asserting that human languages (and definitely individual humans) are not capable of creating sentences of arbitrary depth. Alternatively, a human learner has an upper bound on their life span and hence cannot wait an arbitrarily large (but finite) time to hear a sentence. These arguments are very important in the greater poverty of the stimulus debate, but make formal modeling a bit boring.

• I am vaguely familiar with some of the refinements of the above model used by theoretical computer scientists and would like to hear about models that are of interest to linguists, not just computer scientists.

Answer 1

I am not familiar with the literature on machine learning, but some possible starting points:

Work by Giorgio Magri, who works on computational models for the acquisition of OT grammars.

Also work by Alexander Clark, e.g.:

Clark, Alexander (2010). Efficient, correct, unsupervised learning of context-sensitive languages. Proceedings of the Fourteenth Conference on Computational Natural Language Learning, 28-37. Uppsala, Sweden: Association for Computational Linguistics. http://www.cs.rhul.ac.uk/home/alexc/papers/conll2010.pdf

Clark, Alexander, and Remi Eyraud (2007). Polynomial time identification in the limit of substitutable context-free languages. Journal of Machine Learning Research, 8, 1725–1745.

Hopefully someone else can offer a more complete set of references.

Answer 2

I was hoping @Mitch would expand on his comment about PAC-learning. For now, I will provide the only application of PAC-learning directly to linguistics that I know. It is in Ronald de Wolf's master's thesis: Philosophical Applications of Computational Learning Theory.

de Wolf argues for the Chomskian stance on poverty of the stimulus in much the same way as Gold. Except, instead of showing that the context-free languages are not learnable in the limit from positive instances (as Gold), he instead shows that context-free languages are not effeciently PAC-learnable from positive and negative instances.

Note that PAC-learning is much more reasonable model than Gold's since it allows errors of two kinds: (1) some very small fraction of children completely failing to learn the language, and (2) even the successful children making occasional (again small fraction of instances) mistakes on specific sentences, but getting the overwhelming majority of the language correct. These seem reasonable.

The two restrictions placed on the learners (different from Gold) are: (1) that the algorithm must be polynomial time (i.e. efficient), and (2) the analysis is over worst-case distributions over inputs. The first restriction is perfectly reasonable if we are of the brain as computers camp. The second restriction is unreasonable (children don't get arbitrary distributions, they get very specific ones sometimes involving things like motherese), but still more reasonable than Gold's restriction of a completely adversarial presentation of sentences (that just lists them only in the limit).

Unfortunately, I don't think de Wolf's thesis was unnoticed by lingusitics, since the only citations to it is from a recent non-linguistics paper by another theoretical computer scientist.

Answer 3

Starting in the early 1980's, with Dana Angluin and then later Leslie Valiant with PAC learning, the computational learning theory field has a subfield of language learning.

More accurately, the entire field of PAC learning is about learning of languages in the abstract TCS sense, but there is a sub-part that specifically addresses classes in the Chomsky hierarchy, regular, context-free, and context sensitive languages.

The principles and parameters model comes from the linguistics and psycholinguistics literature, was an attempt at addressing learnability, but is not a particularly mathematical framework.