Projective Dependency Parsing with Perceptron

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 181–185, New York City, June 2006. c⃝2006 Association for Computational Linguistics Projective Dependency Parsing with Perceptron Xavier Carreras, Mihai Surdeanu and Llu´ıs M`arquez TALP Research Centre – Software Department (LSI) Technical University of Catalonia (UPC) Campus Nord - Edifici Omega, Jordi Girona Salgado 1–3, E-08034 Barcelona {carreras,surdeanu,lluism}@lsi.upc.edu Abstract We describe an online learning depen- dency parser for the CoNLL-X Shared Task, based on the bottom-up projective algorithm of Eisner (2000). We experi- ment with a large feature set that mod- els: the tokens involved in dependencies and their immediate context, the surface- text distance between tokens, and the syn- tactic context dominated by each depen- dency. In experiments, the treatment of multilingual information was totally blind. 1 Introduction We describe a learning system for the CoNLL-X Shared Task on multilingual dependency parsing (Buchholz et al., 2006), for 13 different languages. Our system is a bottom-up projective dependency parser, based on the cubic-time algorithm by Eisner (1996; 2000). The parser uses a learning function that scores all possible labeled dependencies. This function is trained globally with online Perceptron, by parsing training sentences and correcting its pa- rameters based on the parsing mistakes. The features used to score, while based on the previous work in dependency parsing (McDonald et al., 2005), intro- duce some novel concepts such as better codification of context and surface distances, and runtime infor- mation from dependencies previously parsed. Regarding experimentation, the treatment of mul- tilingual data has been totally blind, with no spe- cial processing or features that depend on the lan- guage. Considering its simplicity, our system achieves moderate but encouraging results, with an overall labeled attachment accuracy of 74.72% on the CoNLL-X test set. 2 Parsing and Learning Algorithms This section describes the three main components of the dependency parsing: the parsing model, the pars- ing algorithm, and the learning algorithm. 2.1 Model Let 1, . . . , L be the dependency labels, defined be- forehand. Let x be a sentence of n words, x1 . . . xn. Finally, let Y(x) be the space of well-formed depen- dency trees for x. A dependency tree y ∈ Y(x) is a set of n dependencies of the form [h, m, l], where h is the index of the head word (0 ≤ h ≤ n, where 0 means root), m is the index of the modi- fier word (1 ≤ m ≤ n), and l is the dependency label (1 ≤ l ≤ L). Each word of x participates as a modifier in exactly one dependency of y. Our dependency parser, dp, returns the maximum scored dependency tree for a sentence x: dp(x, w) = arg max y∈Y(x) � [h,m,l]∈y sco([h, m, l], x, y, w) In the formula, w is the weight vector of the parser, that is, the set of parameters used to score de- pendencies during the parsing process. It is formed by a concatenation of L weight vectors, one …

Content truncated to 500 words