Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 221–225, New York City, June 2006. c⃝2006 Association for Computational Linguistics Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines Joakim Nivre Johan Hall Jens Nilsson School of Mathematics and Systems Engineering V¨axj¨o University 35195 V¨axj¨o, Sweden {nivre,jha,jni}@msi.vxu.se G¨uls¸en Eryiˇgit Department of Computer Engineering Istanbul Technical University 34469 Istanbul, Turkey gulsen@cs.itu.edu.tr Svetoslav Marinov School of Humanities and Informatics University of Sk¨ovde Box 408 54128 Sk¨ovde, Sweden svetoslav.marinov@his.se Abstract We use SVM classifiers to predict the next action of a deterministic parser that builds labeled projective dependency graphs in an incremental fashion. Non-projective dependencies are captured indirectly by projectivizing the training data for the classifiers and applying an inverse trans- formation to the output of the parser. We present evaluation results and an error analysis focusing on Swedish and Turkish. 1 Introduction The CoNLL-X shared task consists in parsing texts in multiple languages using a single dependency parser that has the capacity to learn from treebank data. Our methodology for performing this task is based on four essential components: • A deterministic algorithm for building labeled projective dependency graphs (Nivre, 2006). • History-based feature models for predicting the next parser action (Black et al., 1992). • Support vector machines for mapping histories to parser actions (Kudo and Matsumoto, 2002). • Graph transformations for recovering non- projective structures (Nivre and Nilsson, 2005). All experiments have been performed using Malt- Parser (Nivre et al., 2006), version 0.4, which is made available together with the suite of programs used for pre- and post-processing.1 1www.msi.vxu.se/users/nivre/research/MaltParser.html 2 Parsing Methodology 2.1 Parsing Algorithm The parsing algorithm used for all languages is the deterministic algorithm first proposed for unlabeled dependency parsing by Nivre (2003) and extended to labeled dependency parsing by Nivre et al. (2004). The algorithm builds a labeled dependency graph in one left-to-right pass over the input, using a stack to store partially processed tokens and adding arcs using four elementary actions (where top is the token on top of the stack and next is the next token): • SHIFT: Push next onto the stack. • REDUCE: Pop the stack. • RIGHT-ARC(r): Add an arc labeled r from top to next; push next onto the stack. • LEFT-ARC(r): Add an arc labeled r from next to top; pop the stack. Although the parser only derives projective graphs, the fact that graphs are labeled allows non-projective dependencies to be captured using the pseudo- projective approach of Nivre and Nilsson (2005) . Another limitation of the parsing algorithm is that it does not assign dependency labels to roots, i.e., to tokens having HEAD=0. To overcome this problem, we have implemented a variant of the algorithm that starts by pushing an artificial root token with ID=0 onto the stack. Tokens having HEAD=0 can now be attached to the artificial root in a RIGHT-ARC(r) action, which means that they can be assigned any label. Since this variant of the algorithm increases the overall nondeterminism, it has only been used …

Content truncated to 500 words