Learning Auxiliary Fronting with Grammatical Inference

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 125–132, New York City, June 2006. c⃝2006 Association for Computational Linguistics Learning Auxiliary Fronting with Grammatical Inference Alexander Clark Department of Computer Science Royal Holloway University of London Egham, Surrey TW20 0EX alexc@cs.rhul.ac.uk R´emi Eyraud EURISE 23, rue du Docteur Paul Michelon 42023 Saint-´Etienne Cedex 2 France remi.eyraud@univ-st-etienne.fr Abstract We present a simple context-free gram- matical inference algorithm, and prove that it is capable of learning an inter- esting subclass of context-free languages. We also demonstrate that an implementa- tion of this algorithm is capable of learn- ing auxiliary fronting in polar interroga- tives (AFIPI) in English. This has been one of the most important test cases in language acquisition over the last few decades. We demonstrate that learning can proceed even in the complete absence of examples of particular constructions, and thus that debates about the frequency of occurrence of such constructions are ir- relevant. We discuss the implications of this on the type of innate learning biases that must be hypothesized to explain first language acquisition. 1 Introduction For some years, a particular set of examples has been used to provide support for nativist theories of first language acquisition (FLA). These exam- ples, which hinge around auxiliary inversion in the formation of questions in English, have been con- sidered to provide a strong argument in favour of the nativist claim: that FLA proceeds primarily through innately specified domain specific mecha- nisms or knowledge, rather than through the oper- ation of general-purpose cognitive mechanisms. A key point of empirical debate is the frequency of oc- currence of the forms in question. If these are van- ishingly rare, or non-existent in the primary linguis- tic data, and yet children acquire the construction in question, then the hypothesis that they have innate knowledge would be supported. But this rests on the assumption that examples of that specific construc- tion are necessary for learning to proceed. In this paper we show that this assumption is false: that this particular construction can be learned without the learner being exposed to any examples of that par- ticular type. Our demonstration is primarily mathe- matical/computational: we present a simple experi- ment that demonstrates the applicability of this ap- proach to this particular problem neatly, but the data we use is not intended to be a realistic representation of the primary linguistic data, nor is the particular algorithm we use suitable for large scale grammar induction. We present a general purpose context-free gram- matical algorithm that is provably correct under a certain learning criterion. This algorithm incorpo- rates no domain specific knowledge: it has no spe- cific information about language; no knowledge of X-bar schemas, no hidden sources of information to reveal the structure. It operates purely on unanno- tated strings of raw text. Obviously, as all learn- ing algorithms do, it has an implicit learning bias. This very simple algorithm has a particularly clear bias, with a simple mathematical description, that al- lows …

Content truncated to 500 words