Maximum Spanning Tree Algorithm for Non-projective Labeled Dependency Parsing

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 236–240, New York City, June 2006. c⃝2006 Association for Computational Linguistics Maximum Spanning Tree Algorithm for Non-projective Labeled Dependency Parsing Nobuyuki Shimizu Dept. of Computer Science State University of New York at Albany Albany, NY, 12222, USA shimizu@cs.albany.edu Abstract Following (McDonald et al., 2005), we present an application of a maximum spanning tree algorithm for a directed graph to non-projective labeled depen- dency parsing. Using a variant of the voted perceptron (Collins, 2002; Collins and Roark, 2004; Crammer and Singer, 2003), we discriminatively trained our parser in an on-line fashion. After just one epoch of training, we were generally able to attain average results in the CoNLL 2006 Shared Task. 1 Introduction Recently, we have seen dependency parsing grow more popular. It is not rare to see dependency re- lations used as features, in tasks such as relation ex- traction (Bunescu and Mooney, 2005) and machine translation (Ding and Palmer, 2005). Although En- glish dependency relations are mostly projective, in other languages with more flexible word order, such as Czech, non-projective dependencies are more fre- quent. There are generally two methods for learn- ing non-projective dependencies. You could map a non-projective dependency tree to a projective one, learn and predict the tree, then bring it back to the non-projective dependency tree (Nivre and Nilsson, 2005). Non-projective dependency parsing can also be represented as search for a maximum spanning tree in a directed graph, and this technique has been shown to perform well in Czech (McDonald et al., 2005). In this paper, we investigate the effective- ness of (McDonald et al., 2005) in the various lan- guages given by the CoNLL 2006 shared task for non-projective labeled dependency parsing. The paper is structured as follows: in section 2 and 3, we review the decoding and learning aspects of (McDonald et al., 2005), and in section 4, we de- scribe the extension of the algorithm and the features needed for the CoNLL 2006 shared task. 2 Non-Projective Dependency Parsing 2.1 Dependency Structure Let us define x to be a generic sequence of input to- kens together with their POS tags and other morpho- logical features, and y to be a generic dependency structure, that is, a set of edges for x. We use the terminology in (Taskar et al., 2004) for a generic structured output prediction, and define a part. A part represents an edge together with its label. A part is a tuple ⟨DEPREL, i, j⟩ where i is the start point of the edge, j is the end point, and DEPREL is the label of the edge. The token at i is the head of the token at j. Table 1 shows our formulation of building a non- projective dependency tree as a prediction problem. The task is to predict y, the set of parts (column 3, Table 1), given x, the input tokens and their features (column 1 and 2, Table 1). In this paper we use …

Content truncated to 500 words