Automatic Grammar Induction and Parsing Free Text: A Transformation-Based Approach

Automatic Grammar Induction and Parsing Free Text: A Transformation-Based Approach Eric Brill* Department of Computer and Information Science University of Pennsylvania brill@unagi.cis.upenn.edu Abstract In this paper we describe a new technique for parsing free text: a transformational grammar I is automatically learned that is capable of accu- rately parsing text into binary-branching syntac- tic trees with nonterminals unlabelled. The algo- rithm works by beginning in a very naive state of knowledge about phrase structure. By repeatedly comparing the results of bracketing in the current state to proper bracketing provided in the training corpus, the system learns a set of simple structural transformations that can be applied to reduce er- ror. After describing the algorithm, we present results and compare these results to other recent results in automatic grammar induction. INTRODUCTION There has been a great deal of interest of late in the automatic induction of natural language gram- mar. Given the difficulty inherent in manually building a robust parser, along with the availabil- ity of large amounts of training material, auto- matic grammar induction seems like a path worth pursuing. A number of systems have been built that can be trained automatically to bracket text into syntactic constituents. In (MM90) mutual in- formation statistics are extracted from a corpus of text and this information is then used to parse new text. (Sam86) defines a function to score the quality of parse trees, and then uses simulated an- nealing to heuristically explore the entire space of possible parses for a given sentence. In (BM92a), distributional analysis techniques are applied to a large corpus to learn a context-free grammar. The most promising results to date have been *The author would like to thank Mark Liberman, Melting Lu, David Magerman, Mitch Marcus, Rich Pito, Giorgio Satta, Yves Schabes and Tom Veatch. This work was supported by DARPA and AFOSR jointly under grant No. AFOSR-90-0066, and by ARO grant No. DAAL 03-89-C0031 PRI. 1 Not in the traditional sense of the term. based on the inside-outside algorithm, which can be used to train stochastic context-free grammars. The inside-outside algorithm is an extension of the finite-state based Hidden Markov Model (by (Bak79)), which has been applied successfully in many areas, including speech recognition and part of speech tagging. A number of recent papers have explored the potential of using the inside- outside algorithm to automatically learn a gram- mar (LY90, SJM90, PS92, BW92, CC92, SRO93). Below, we describe a new technique for gram- mar induction. The algorithm works by beginning in a very naive state of knowledge about phrase structure. By repeatedly comparing the results of parsing in the current state to the proper phrase structure for each sentence in the training corpus, the system learns a set of ordered transformations which can be applied to reduce parsing error. We believe this technique has advantages over other methods of phrase structure induction. Some of the advantages include: the system is very simple, it requires only a very small set of transforma- tions, a high degree …

Content truncated to 500 words