Ambiguity and the Computational Feasibility of Syntax Acquisition
Ph.D. Dissertation, City University of New York
William Gregory Sakas

The thesis presents a framework that can be used for empirical and formal analysis of parameter setting models of language acquisition.  Such models attempt to mirror computationally the process by which children acquire the grammar of their native language.  Research into formal language learning theory standardly focuses on issues of learnability – Under what conditions is learning possible?  The thesis contributes to the important, but under-investigated question of feasibility – Is acquisition possible within a reasonable amount of time and/or with a reasonable amount of work?

The proposed framework formalizes existing notions such as the rate of parametric ambiguity and parametric expression within a generally defined parameter space, so that different types of learning algorithms and grammar spaces can be explored.  Two influential learning algorithms are examined in detail: The Triggering Learning Algorithm (Gibson and Wexler, 1994) and The Structural Triggers Learner (Fodor, 1998).  Empirical results indicate that the Triggering Learning Algorithm's simple hill-climbing search heuristics are sufficient to acquire the target grammar without the learner's consumption of an unreasonable number of input sentences when the learning space contains a strong correlation between the similarity of languages and the grammars that generate them.

The results also indicate that the Structural Triggers Learner's use of structural information lying beneath the surface word order of an input sentence allows for feasible learning when the rate of parametric expression varies across the input sentences encountered by the learner.  Notably, however, both models are acutely sensitive to changes in the amount and type of ambiguity present in the domain.  A small change in just one of the factors that contributes to the distribution of ambiguity has a large impact on learning efficiency.