Alternative approaches for Generating Bodies of Grammar Rules

Alternative Approaches for Generating Bodies of Grammar Rules Gabriel Infante-Lopez and Maarten de Rijke Informatics Institute, University of Amsterdam {infante,mdr}@science.uva.nl Abstract We compare two approaches for describing and gen- erating bodies of rules used for natural language parsing. In today’s parsers rule bodies do not ex- ist a priori but are generated on the fly, usually with methods based on n-grams, which are one particu- lar way of inducing probabilistic regular languages. We compare two approaches for inducing such lan- guages. One is based on n-grams, the other on min- imization of the Kullback-Leibler divergence. The inferred regular languages are used for generating bodies of rules inside a parsing procedure. We com- pare the two approaches along two dimensions: the quality of the probabilistic regular language they produce, and the performance of the parser they were used to build. The second approach outper- forms the first one along both dimensions. 1 Introduction N-grams have had a big impact on the state of the art in natural language parsing. They are central to many parsing models (Charniak, 1997; Collins, 1997, 2000; Eisner, 1996), and despite their sim- plicity n-gram models have been very successful. Modeling with n-grams is an induction task (Gold, 1967). Given a sample set of strings, the task is to guess the grammar that produced that sample. Usu- ally, the grammar is not be chosen from an arbitrary set of possible grammars, but from a given class. Hence, grammar induction consists of two parts: choosing the class of languages amongst which to search and designing the procedure for performing the search. By using n-grams for grammar induc- tion one addresses the two parts in one go. In par- ticular, the use of n-grams implies that the solu- tion will be searched for in the class of probabilis- tic regular languages, since n-grams induce prob- abilistic automata and, consequently, probabilistic regular languages. However, the class of probabilis- tic regular languages induced using n-grams is a proper subclass of the class of all probabilistic reg- ular languages; n-grams are incapable of capturing long-distance relations between words. At the tech- nical level the restricted nature of n-grams is wit- nessed by the special structure of the automata in- duced from them, as we will see in Section 4.2. N-grams are not the only way to induce regular languages, and not the most powerful way to do so. There is a variety of general methods capable of in- ducing all regular languages (Denis, 2001; Carrasco and Oncina, 1994; Thollard et al., 2000). What is their relevance for natural language parsing? Re- call that regular languages are used for describing the bodies of rules in a grammar. Consequently, the quality and expressive power of the resulting gram- mar is tied to the quality and expressive power of the regular languages used to describe them. And the quality and expressive power of the latter, in turn, are influenced directly by the method used to induce them. These observations give rise to a natural ques- …

Content truncated to 500 words