Dependency Parsing as a Classication Problem

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 246–250, New York City, June 2006. c⃝2006 Association for Computational Linguistics Dependency Parsing as a Classification Problem Deniz Yuret Koc¸ University Istanbul, Turkey dyuret@ku.edu.tr Abstract This paper presents an approach to depen- dency parsing which can utilize any stan- dard machine learning (classification) al- gorithm. A decision list learner was used in this work. The training data provided in the form of a treebank is converted to a format in which each instance represents information about one word pair, and the classification indicates the existence, di- rection, and type of the link between the words of the pair. Several distinct mod- els are built to identify the links between word pairs at different distances. These models are applied sequentially to give the dependency parse of a sentence, favoring shorter links. An analysis of the errors, attribute selection, and comparison of dif- ferent languages is presented. 1 Introduction This paper presents an approach to supervised learn- ing of dependency relations in a language using stan- dard machine learning techniques. The treebanks (Hajiˇc et al., 2004; Chen et al., 2003; B¨ohmov´a et al., 2003; Kromann, 2003; van der Beek et al., 2002; Brants et al., 2002; Kawata and Bartels, 2000; Afonso et al., 2002; Dˇzeroski et al., 2006; Civit Tor- ruella and Mart´ı Anton´ın, 2002; Nilsson et al., 2005; Oflazer et al., 2003; Atalay et al., 2003) provided for the CoNLL shared task(Buchholz et al., 2006) were converted to a set of instances each of which con- sists of the attributes of a candidate word pair with a classification that indicates the existence, direction and type of the dependency link between the pair. An initial model is built to identify dependency relations between adjacent word pairs using a deci- sion list learning algorithm. To identify longer dis- tance relations, the adjacent modifiers are dropped from the sentence and a second order model is built based on the word pairs that come into contact. A total of three models were built using this technique successively and used for parsing. All given attributes are considered as candidates in an attribute selection process before building each model. In addition, attributes indicating suffixes of various lengths and character type information were constructed and used. To parse a given sentence, the models are applied sequentially, each one considering candidate word pairs and adding new links without deleting the ex- isting links or creating conflicts (cycles or crossings) with them. Thus, the algorithm can be considered a bottom-up, multi-pass, deterministic parser. Given a candidate word pair, the models may output “no link”, or give a link with a specified direction and type. Thus labeling is an integrated step. Word pair candidates that may form cycles or crossings are never considered, so the parser will only gen- erate projective structures. Section 2 gives the details of the learning algo- rithm. Section 3 describes the first pass model of links between adjacent words. Section 4 details the approach …

Content truncated to 500 words