A Constraint Satisfaction Approach to Dependency Parsing

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1124–1128, Prague, June 2007. c⃝2007 Association for Computational Linguistics A Constraint Satisfaction Approach to Dependency Parsing Sander Canisius ILK / Communication and Information Science Tilburg University, P.O. Box 90153, NL-5000 LE Tilburg, The Netherlands S.V.M.Canisius@uvt.nl Erik Tjong Kim Sang ISLA, University of Amsterdam, Kruislaan 403, NL-1098 SJ Amsterdam, The Netherlands erikt@science.uva.nl Abstract We present an adaptation of constraint satis- faction inference (Canisius et al., 2006b) for predicting dependency trees. Three differ- ent classifiers are trained to predict weighted soft-constraints on parts of the complex out- put. From these constraints, a standard weighted constraint satisfaction problem can be formed, the solution to which is a valid dependency tree. 1 Introduction Like the CoNLL-2006 shared task, the 2007 shared task focuses on dependency parsing and aims at comparing state-of-the-art machine learning algo- rithms applied to this task (Nivre et al., 2007). For our official submission, we used the dependency parser described by Canisius et al. (2006a). In this paper, we present a novel approach to dependency parsing based on constraint satisfaction. The method is an adaptation of earlier work using constraint sat- isfaction techniques for predicting sequential out- puts (Canisius et al., 2006b). We evaluated our ap- proach on all ten data sets of the 2007 shared task1. In the remainder of this paper, we will present the new constraint satisfaction method for dependency parsing in Section 2. The method is evaluated in Section 3, in which we will also present a brief error 1Hajiˇc et al. (2004), Aduriz et al. (2003), Mart´ı et al. (2007), Chen et al. (2003), B¨ohmov´a et al. (2003), Marcus et al. (1993), Johansson and Nugues (2007), Prokopidis et al. (2005), Csendes et al. (2005), Montemagni et al. (2003), Oflazer et al. (2003) analysis. Finally, Section 4 presents our main con- clusions. 2 Constraint Satisfaction Inference for Dependency Trees The parsing algorithm we used is an adaptation for dependency trees of the constraint satisfaction in- ference method for sequential output structures pro- posed by Canisius et al. (2006b). The technique uses standard classifiers to predict a weighted con- straint satisfaction problem, the solution to which is the complete dependency tree. Constraints that are predicted each cover a small part of the complete tree, and overlap between them ensures that global output structure is taken into account, even though the classifiers only make local predictions in isola- tion of each other. A weighted constraint satisfaction problem (W- CSP) is a tuple (X, D, C, W). Here, X {x1, x2, . . . , xn} is a finite set of variables. D(x)= is a function that maps each variable to its domain, and C is a set of constraints on the values assigned to the variables. For a traditional (non-weighted) constraint satisfaction problem, a valid solution is an assignment of values to the variables that (1) are a member of the corresponding variable’s domain, and (2) satisfy all constraints in the set C. Weighted constraint satisfaction, however, relaxes …

Content truncated to 500 words