Reversible Automata and Induction of the English Auxiliary System

REVERSIBLE AUTOMATA AND INDUCTION OF THE ENGLISH AUXILIARY SYSTEM Samuel F. Pilato Robert C. Berwick MIT Artificial Intelligence Laboratory 545 Technology Square Cambridge, MA 02139, USA ABSTRACT In this paper we apply some recent work of Angluin (1982) to the induction of the English auxiliary verb system. In general, the induction of finite automata is computation- ally intractable. However, Angluin shows that restricted finite automata, the It-reversible automata, can be learned by el~cient (polynomial time) algorithms. We present an ex- plicit computer model demonstrating that the English aux- iliary verb system can in fact be learned as a I-reversible automaton, and hence in a computationally feasible amount of time. The entire system can be acquired by looking at only half the possible auxiliary verb sequences, and the pat- tern of generalization seems compatible with what is known about human acquisition of auxiliaries. We conclude that certain linguistic subsystems may well be learnable by in- ductive inference methods of this kind, and suggest an ex- tension to context-free languages. INTRODUCTION Formal inductive inference methods have rarely been ap- plied to actual natural language systems. Linguists gener- ally suppose that languages axe easy to learn because grarn- mars axe highly constrained; no ~gener,d purpose" inductive inference methods are required. This assumption has gener- ally led to fruitful insights on the nature of grammars. Yet it remains to determine whether ~ll of a language is learned in a granHnar-specilic manner. In this paper we show how to successfully apply one computationally emcient inductive inference algorithm to the acquisition of a domain of English sy'nca.x. Our results suggest that particular language subsys- tems can be learned by general induction procedures, given certain general constraints. The problem is that these methods are in general com- pntationally intractablc. Even for regular languages induc- tion can be exponentially diiTicult (Gold, 1978). This sug- gests that there may be general constraints on the design of ce~ain linguistic subsystems to make them easy to learn by general inductive inference methods. We propose the constraint of k-reversibilit V as one such restriction. This constraint guarantees polynomial time inference (Angluin, 1982). In the remainder of this paper, we also show, by an explicit computer model, that the English auxiliary verb system meets this constraint, and so is easily inferred from a corpus. The theory gives one precise characterization of just whcre we may expect general inductive inference methods to be of v,~,lue in language acquisition. LEARNING K-REVERSIBLE LANGUAGES FROM EXAMPLES The question we address is, If a learner presumes that a natural language domain is systematic in some way, can the learner intelligently infer the complete system from only --- subset of sample sentences? Let us develop a:i exaauple to formally describe what we mean by "systematic in some way," and how such a systematic domain allows the infer- ence of a complete system front examples. If you were told that Mar~ bakes cakes, John bakes cakes, and Mar V eat~ pies are legal strings m some language, you might guess …

Content truncated to 500 words