Tree Revision Learning for Dependency Parsing

Proceedings of NAACL HLT 2007, pages 388–395, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Tree Revision Learning for Dependency Parsing Giuseppe Attardi Dipartimento di Informatica Universit`a di Pisa Pisa, Italy attardi@di.unipi.it Massimiliano Ciaramita Yahoo! Research Barcelona Barcelona, Spain massi@yahoo-inc.com Abstract We present a revision learning model for improving the accuracy of a dependency parser. The revision stage corrects the out- put of the base parser by means of revi- sion rules learned from the mistakes of the base parser itself. Revision learning is performed with a discriminative classi- fier. The revision stage has linear com- plexity and preserves the efficiency of the base parser. We present empirical evalu- ations on the treebanks of two languages, which show effectiveness in relative error reduction and state of the art accuracy. 1 Introduction A dependency parse tree encodes useful semantic in- formation for several language processing tasks. De- pendency parsing is a simpler task than constituent parsing, since dependency trees do not have ex- tra non-terminal nodes and there is no need for a grammar to generate them. Approaches to depen- dency parsing either generate such trees by consid- ering all possible spanning trees (McDonald et al., 2005), or build a single tree on the fly by means of shift-reduce parsing actions (Yamada & Matsumoto, 2003). In particular, Nivre and Scholz (2004) and Attardi (2006) have developed deterministic depen- dency parsers with linear complexity, suitable for processing large amounts of text, as required, for ex- ample, in information retrieval applications. We investigate a novel revision approach to dependency parsing related to re-ranking and transformation-based methods (Brill, 1993; Brill, 1995; Collins, 2000; Charniak & Johnson, 2005; Collins & Koo, 2006). Similarly to re-ranking, the second stage attempts to improve the output of a base parser. Instead of re-ranking n-best candi- date parses, our method works by revising a sin- gle parse tree, either the first-best or the one con- structed by a deterministic shift-reduce parser, as in transformation-based learning. Parse trees are re- vised by applying rules which replace incorrect with correct dependencies. These rules are learned by comparing correct parse trees with incorrect trees produced by the base parser on a training corpus. We use the same training corpus on which the base parser was trained, but this need not be the case. Hence, we define a new learning task whose output space is a set of revision rules and whose input is a set of features extracted at each node in the parse trees produced by the parser on the training corpus. A statistical classifier is trained to solve this task. The approach is more suitable for dependency parsing since trees do not have non-terminal nodes, therefore revisions do not require adding/removing nodes. However, the method applies to any parser since it only analyzes output trees. An intuitive mo- tivation for this method is the observation that a dependency parser correctly identifies most of the dependencies in a tree, and only local corrections might be necessary to produce a correct …

Content truncated to 500 words