Automatic Grammar Acquisition

AUTOMATIC GRAMMAR ACQUISITION Scott Miller Heidi J. Fox College of Computer Science Northeastern University Boston, MA 02115 BBN Systems and Technologies 70 Fawcett St., Cambridge, MA 02138 ABSTRACT We describe a series of three experiments in which supervised learning techniques were used to acquire three different types of grammars for English news stories. The acquired grammar types were: 1) context-free, 2) context-dependent, and 3) probabilistic context-free. Training data were derived from University of Pennsylvania Treebank parses of 50 Wall Street Journal articles. In each case, the system started with essentially no grammatical knowledge, and learned a set of grammar rules exclusively from the training data. Performance for each gr~rnar type was then evaluated on an independent set of test sentences using Parseval, a standard measure of parsing accuracy. These experimental results yield a direct qtmntitative comparison between each of the three methods. 1. INTRODUCTION Designing and refining a natural language grammar is a difficult and time-intensive task, often consuming months or even years of skilled effort. The resulting grammar is usually not completely satisfactory, failing to cover a significant fraction of the sentences in the intended domain. Conversely, the grammar is likely to overgenerate, leading to multiple interpretations for a single sentence, many of which are incorrect. With the increasing availability of large, machine-readable, parsed corpora such as the University of Pennsylvania Treebank [Santorini, 90], it has become worthwhile to consider automatic grammar acquisition through the application of machine learning techniques. By learning a grammar that completely covers a training set for some domain, it is hoped that coverage will also be increased for new sentences in that domain. Additionally, machine learning techniques may be useful in reducing overgeneration through a variety of techniques that have been suggested in recent literature. One suggestion is to introduce local contextual information into a grammar [Simmons and Yu, 92], based on the premise that local context provides useful information for selecting among competing grammar rules. A second suggestion is to introduce probabilities in the form of a probabilistic context-free grammar [Chitaro and Gfishman, 9% based on the premise that a combination of local probability measures provides a useful estimate of the probability of an entire parse. J In this work, we Investigate both of these suggestions and compare them with a simple, automatically learned, context-free grammar. In each case, the grammar is acquired from a subset of parsed Wall Street Journal articles taken from the University of Pennsylvania Treebank. We then apply the acquired grammar to the problem of producing a single unambiguous parse for each sentence of an independent test set derived from the same SOUrce. 2. LEARNING A CONTEXT-FREE GRAMMAR A context-free grammar is acquired from a parsed Treebank corpus by straightforward memorization of the grammar rules used in each training example. Figure 1 shows a typical parse tree from our training corpus; Table 1 shows the grammar rules used. SMAJ NN NN NN VBD CD NN TO $ CD CD [ I [ I I I [[I I Government construction …

Content truncated to 500 words