An efficient implementation of a new DOP model

An Efficient Implementation of a New POP Model Rens Bod ILLC, University of Amsterdam School of Computing, University of Leeds Nieuwe Achtergracht 166, NL-1018 WV Amsterdam rens@science.uva.n1 Abstract Two apparently opposing DOP models exist in the literature: one which computes the parse tree involving the most frequent subtrees from a treebank and one which computes the parse tree involving the fewest subtrees from a treebank. This paper proposes an integration of the two models which outperforms each of them separately. Together with a PCFG- reduction of DOP we obtain improved accuracy and efficiency on the Wall Street Journal treebank Our results show an 11% relative reduction in error rate over previous models, and an average processing time of 3.6 seconds per WSJ sentence. 1 Introduction: A Little History 1.1 DOP and its Doppelgangers 1 The distinctive feature of the DOP approach when it was proposed in 1992 was to model sentence structures on the basis of previously observed frequencies of sentence structure fragments, without imposing any constraints on the size of these fragments. Fragments include, for instance, subtrees of depth 1 (corresponding to context-free rules) as well as entire trees. To appreciate these innovations, it should be noted that the model was radically different from all other statistical parsing models at the time. Other models started off with a predefined grammar and used a corpus only for estimating the rule probabilities (as e.g. in Fujisaki et al. 1989; Black et al. 1992, 1993; Briscoe and I Thanks to Ivan Sag for this pun. Waegner 1992; Pereira and Schabes 1992). The DOP model, on the other hand, was the first model (to the best of our knowledge) that proposed not to train a predefined grammar on a corpus, but to directly use corpus fragments as a grammar. This approach has now gained wide usage, as exemplified by the work of Collins (1996, 1999), Charniak (1996, 1997), Johnson (1998), Chiang (2000), and many others. The other innovation of DOP was to take (in principle) all corpus fragments, of any size, rather than a small subset. This innovation has not become generally adopted yet: many approaches still work either with local trees, i.e. single level rules with limited means of information percolation, or with restricted fragments, as in Stochastic Tree-Adjoining Grammar (Schabes 1992; Chiang 2000) that do not include non- lexicalized fragments. However, during the last few years we can observe a shift towards using more and larger corpus fragments with fewer restrictions. While the models of Collins (1996) and Eisner (1996) restricted the fragments to the locality of head-words, later models showed the importance of including context from higher nodes in the tree (Charniak 1997; Johnson 1998a). The importance of including nonhead- words has become uncontroversial (e.g. Collins 1999; Charniak 2000; Goodman 1998). And Collins (2000) argues for "keeping track of counts of arbitrary fragments within parse trees", which has indeed been carried out in Collins and Duffy (2002) who use exactly the same set of (all) tree fragments as proposed in …

Content truncated to 500 words