Efficient Algorithms for Parsing the DOP Model

Efficient Algorithms for Parsing the DOP Model * Joshua Goodman Harvard University 33 Oxford St. Cambridge, MA 02138 goodman@das.harvard.edu Abstract Excellent results have been reported for Data- Oriented Parsing (DOP) of natural language texts (Bod, 1993c). Unfortunately, existing algorithms are both computationally intensive and difficult to implement. Previous algorithms are expen- sive due to two factors: the exponential number of rules that must be generated and the use of a Monte Carlo parsing algorithm. In this paper we solve the first problem by a novel reduction of the DOP model to:a small, equivalent probabilistic context-free grammar. We solve the second prob- lem by a novel deterministic parsing strategy that maximizes the expected number of correct con- stituents, rather than the probability of a correct parse tree. Using ithe optimizations, experiments yield a 97% crossing brackets rate and 88% zero crossing brackets rate. This differs significantly from the results reported by Bod, and is compara- ble to results from a duplication of Pereira and Schabes's (1992) experiment on the same data. We show that Bod's results are at least partially due to an extremely fortuitous choice of test data, and partially due to using cleaner data than other researchers. Introduction The Data-Oriented Parsing (DOP) model has a short, interesting, and controversial history. It was introduced by Remko Scha (1990), and was then studied by Rens Bod. Unfortunately, Bod (1993c, 1992) was not able to find an efficient exact * I would like to acknowledge support from Na- tional Science Foundation Grant IRI-9350192 and a National Science Foundation Graduate Student Fel- lowship. I would also like to thank Rens Bod, Stan Chen, Andrew Kehler, David Magerman, Wheeler Rural, Stuart Shieber, and Khalil Sima'an for help- ful discussions, and comments on earlier drafts, and the comments of the anonymous reviewers. algorithm for parsing using the model; however he did discover and implement Monte Carlo approxi- mations. He tested these algorithms on a cleaned up version of the ATIS corpus, and achieved some very exciting results, reportedly getting 96% of his test set exactly correct, a huge improvement over previous results. For instance, Bod (1993b) com- pares these results to Schabes (1993), in which, for short sentences, 30% of the sentences have no crossing brackets (a much easier measure than ex- act match). Thus, Bod achieves an extraordinary &fold error rate reduction. Not surprisingly, other researchers attempted to duplicate these results, but due to a lack of de- tails of the parsing algorithm in his publications, these other researchers were not able to confirm the results (Magerman, Lalferty, personal commu- nication). Even Bod's thesis (Bod, 1995a) does not contain enough information to replicate his re- sults. Parsing using the DOP model is especially dif- ficult. The model can be summarized as a spe- cial kind of Stochastic Tree Substitution Grammar (STSG): given a bracketed, labelled training cor- pus, let every subtree of that corpus be an elemen- tary tree, with a probability proportional to the number of occurrences of that subtree in the train- …

Content truncated to 500 words