Search, Structure or Statistics? A Comparative Study of Memoryless Heuristics for Syntax Acquisition

Search, Structure or Statistics? A Comparative Study of Memoryless Heuristics for Syntax Acquisition William Gregory Sakas (sakas@hunter.cuny.edu) Department of Computer Science, Hunter College, CUNY Ph.D. Programs in Linguistics and Computer Science, The Graduate Center, CUNY 695 Park Avenue, New York, NY 10021 USA Eiji N ishimoto (enishimoto@gc.cuny.edu) Ph.D. Program in Linguistics, The Graduate Center, CUNY 365 Fifth Avenue, New York, NY 10016 USA Abstract Although several studies propose computational models of tlie process by which children acquire the syntax of their native language, most focus on a single algorithm applied in a single domain. Typically, the focus is learnability — under what conditions an algorithm can or cannot acquire the grammar of the target (native) language. Here, we present a comparative study of 12 algorithmic heuristics that are run in a domain that consists of 16 abstract languages each generated by a dijferent grammar specified in Chomsky’s principles and parameters fiamework. The heuristics consist of botl1 those used in previously established models and new variations that we introduce. In contrast to a leamability study, our focus is feasibility — how much time and/or eifort is required to achieve the target grammar. We find that the best heuristics make use of structural information obtained by parsing input sentences during the course of learning, that the performance of statistically- based heuristics are next in line, and finally, that heuristics that make use of hill-climbing search and a simple can-parse/can’t- parse outcome from the parsing mechanism perform least well. Background Principles and Parameters Chomsky (1981 and elsewhere) has proposed that all natural languages share the same innate universal principles (Universal Grammar - UG) and differ only with respect to the settings of a finite number of (binary) parameters. For example, all languages have a subject of some sort, but whether a language's grammar dictates that the subject must be overt is determined by the setting of the null subject parameter. The null subject parameter is set ofl ir1 English and on m Spanish. The syntactic component of a grammar m the principles and parameters (PP Briscoe, 2000; Clark, 1992; Fodor, 1998a; Gibson & Wexler, 1994; Yang, 2000; among others), and although it has proved linguistically fiuitfiil to construct parametric analyses, it turns out to be surprisingly difficult to construct a workable model of parametric syntax acquisition. Parametric Ambiguity and the Need for Heuristics A sentence is parametrically ambiguous if it is licensed by two or more distinct combinations of parameter values. Parametric ambiguity is rampant ir1 natural language. For example, a sequence of the form Subject-Verb-Object (SVO) is parametrically ambiguous between underlying SVO order as in English, and verb second (V2) order as m German.1 Although SVO sentences can be parsed by either grammar, the derivations will be different due to the different parameter settings. By contrast, a VOS sentence is not parametrically ambiguous with respect to the V2 parameter. It can be licensed only by the -V2 value (since the second token is not a verb or auxiliary). Ambiguity is a natural enemy of efficient language acquisition. The key problem is that, due to ambiguity, there does not exist a one-to-one correspondence between the linear left-to- right word order of an input sequence and the correct parameter values for the target grammar (as described above for an SVO sentence with respect to + or -V2). So, even if the learner hypothesizes parameter values which license the single, current input sentence, those values may ultimately be incorrect for Gag. In the face of parametric ambiguity, efficient search heuristics must be employed to guide the learner towards the target grammar as sentences are progressively consumed by the learner. The remainder of the paper presents a comparative study of 12 search heuristics that are incorporated into current parameter- setting models of language acquisition. Overview A Measure of Feasibility As a simple example of a learning heuristic and of our simulation approach, consider a domain of 4 parameters and a memoryless 1 See Appendix for the linguistic details of how we implement the V2 parameter.