Multi-lingual Dependency Parsing with Incremental Integer Linear Programming

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 226–230, New York City, June 2006. c⃝2006 Association for Computational Linguistics Multi-lingual Dependency Parsing with Incremental Integer Linear Programming Sebastian Riedel and Ruket C¸ akıcı and Ivan Meza-Ruiz ICCS School of Informatics University of Edinburgh Edinburgh, EH8 9LW, UK S.R.Riedel,R.Cakici,I.V.Meza-Ruiz@sms.ed.ac.uk Abstract Our approach to dependency parsing is based on the linear model of McDonald et al.(McDonald et al., 2005b). Instead of solving the linear model using the Max- imum Spanning Tree algorithm we pro- pose an incremental Integer Linear Pro- gramming formulation of the problem that allows us to enforce linguistic constraints. Our results show only marginal improve- ments over the non-constrained parser. In addition to the fact that many parses did not violate any constraints in the first place this can be attributed to three reasons: 1) the next best solution that fulfils the con- straints yields equal or less accuracy, 2) noisy POS tags and 3) occasionally our inference algorithm was too slow and de- coding timed out. 1 Introduction This paper presents our submission for the CoNLL 2006 shared task of multilingual dependency pars- ing. Our parser is inspired by McDonald et al.(2005a) which treats the task as the search for the highest scoring Maximum Spanning Tree (MST) in a graph. This framework is efficient for both pro- jective and non-projective parsing and provides an online learning algorithm which combined with a rich feature set creates state-of-the-art performance across multiple languages (McDonald and Pereira, 2006). However, McDonald and Pereira (2006) mention the restrictive nature of this parsing algorithm. In their original framework, features are only defined over single attachment decisions. This leads to cases where basic linguistic constraints are not satisfied (e.g. verbs with two subjects). In this paper we present a novel way to implement the parsing al- gorithms for projective and non-projective parsing based on a more generic incremental Integer Linear Programming (ILP) approach. This allows us to in- clude additional global constraints that can be used to impose linguistic information. The rest of the paper is organised in the following way. First we give an overview of the Integer Linear Programming model and how we trained its param- eters. We then describe our feature and constraint sets for the 12 different languages of the task (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 Torruella and Mart´ı Anton´ın, 2002; Nilsson et al., 2005; Oflazer et al., 2003; Atalay et al., 2003). Finally, our results are discussed and error analyses for Chinese and Turk- ish are presented. 2 Model Our model is based on the linear model presented in McDonald et al. (2005a), s (x, y) = � (i,j)∈y s (i, j) = � w · f (i, j) (1) where x is a sentence, y a parse and s a score func- tion over …

Content truncated to 500 words