Graph Transformations in Data-Driven Dependency Parsing

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 257–264, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Graph Transformations in Data-Driven Dependency Parsing Jens Nilsson V¨axj¨o University jni@msi.vxu.se Joakim Nivre V¨axj¨o University and Uppsala University nivre@msi.vxu.se Johan Hall V¨axj¨o University jha@msi.vxu.se Abstract Transforming syntactic representations in order to improve parsing accuracy has been exploited successfully in statistical parsing systems using constituency-based representations. In this paper, we show that similar transformations can give sub- stantial improvements also in data-driven dependency parsing. Experiments on the Prague Dependency Treebank show that systematic transformations of coordinate structures and verb groups result in a 10% error reduction for a deterministic data-driven dependency parser. Combin- ing these transformations with previously proposed techniques for recovering non- projective dependencies leads to state-of- the-art accuracy for the given data set. 1 Introduction It has become increasingly clear that the choice of suitable internal representations can be a very important factor in data-driven approaches to syn- tactic parsing, and that accuracy can often be im- proved by internal transformations of a given kind of representation. This is well illustrated by the Collins parser (Collins, 1997; Collins, 1999), scru- tinized by Bikel (2004), where several transforma- tions are applied in order to improve the analy- sis of noun phrases, coordination and punctuation. Other examples can be found in the work of John- son (1998) and Klein and Manning (2003), which show that well-chosen transformations of syntac- tic representations can greatly improve the parsing accuracy obtained with probabilistic context-free grammars. In this paper, we apply essentially the same techniques to data-driven dependency parsing, specifically targeting the analysis of coordination and verb groups, two very common constructions that pose special problems for dependency-based approaches. The basic idea is that we can facili- tate learning by transforming the training data for the parser and that we can subsequently recover the original representations by applying an inverse transformation to the parser’s output. The data used in the experiments come from the Prague Dependency Treebank (PDT) (Hajiˇc, 1998; Hajiˇc et al., 2001), the largest avail- able dependency treebank, annotated according to the theory of Functional Generative Description (FGD) (Sgall et al., 1986). The parser used is MaltParser (Nivre and Hall, 2005; Nivre et al., 2006), a freely available system that combines a deterministic parsing strategy with discriminative classifiers for predicting the next parser action. The paper is structured as follows. Section 2 provides the necessary background, including a definition of dependency graphs, a discussion of different approaches to the analysis of coordina- tion and verb groups in dependency grammar, as well as brief descriptions of PDT, MaltParser and some related work. Section 3 introduces a set of dependency graph transformations, specifically defined to deal with the dependency annotation found in PDT, which are experimentally evaluated in section 4. While the experiments reported in section 4.1 deal with pure treebank transforma- tions, in order to establish an upper bound on what can be achieved in parsing, the experiments …

Content truncated to 500 words