What is the Minimal Set of Fragments that Achieves Maximal Parse Accuracy?

What is the Minimal Set of Fragments that Achieves Maximal Parse Accuracy? Rens Bod School of Computing University of Leeds, Leeds LS2 9JT, & Institute for Logic, Language and Computation University of Amsterdam, Spuistraat 134, 1012 VB Amsterdam rens@comp.leeds.ac.uk Abstract We aim at finding the minimal set of fragments which achieves maximal parse accuracy in Data Oriented Parsing. Expe- riments with the Penn Wall Street Journal treebank show that counts of almost arbitrary fragments within parse trees are important, leading to improved parse accuracy over previous models tested on this treebank (a precis - ion of 90.8% and a recall of 90.6%). We isolate some dependency relations which previous models neglect but which contribute to higher parse accuracy. 1 Introduction One of the goals in statistical natural language parsing is to find the minimal set of statistical dependencies (between words and syntactic structures) that achieves maximal parse accuracy. Many stochastic parsing models use linguistic intuitions to find this minimal set, for example by restricting the statistical dependencies to the locality of headwords of constituents (Collins 1997, 1999; Eisner 1997), leaving it as an open question whether there exist important statistical dependencies that go beyond linguistically motivated dependencies. The Data Oriented Parsing (DOP) model, on the other hand, takes a rather extreme view on this issue: given an annotated corpus, all fragments (i.e. subtrees) seen in that corpus, regardless of size and lexicalization, are in principle taken to form a grammar (see Bod 1993, 1998; Goodman 1998; Sima'an 1999). The set of subtrees that is used is thus very large and extremely redundant. Both from a theoretical and from a computational perspective we may wonder whether it is possible to impose constraints on the subtrees that are used, in such a way that the accuracy of the model does not deteriorate or perhaps even improves. That is the main question addressed in this paper. We report on experiments carried out with the Penn Wall Street Journal (WSJ) treebank to investigate several strategies for constraining the set of subtrees. We found that the only constraints that do not decrease the parse accuracy consist in an upper bound of the number of words in the subtree frontiers and an upper bound on the depth of unlexicalized subtrees. We also found that counts of subtrees with several nonheadwords are important, resulting in improved parse accuracy over previous parsers tested on the WSJ. 2 The DOP1 Model To-date, the Data Oriented Parsing model has mainly been applied to corpora of trees whose labels consist of primitive symbols (but see Bod & Kaplan 1998; Bod 2000c, 2001). Let us illus- trate the original DOP model presented in Bod (1993), called DOP1, with a simple example. Assume a corpus consisting of only two trees: NP VP S NP Mary V likes John NP VP S NP V Peter hates Susan Figure 1. A corpus of two trees New sentences may be derived by combining fragments, i.e. subtrees, from this corpus, by means of a node-substitution operation indicated …

Content truncated to 500 words