Incremental Integer Linear Programming for Non-projective Dependency Parsing

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 129–137, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Incremental Integer Linear Programming for Non-projective Dependency Parsing Sebastian Riedel and James Clarke School of Informatics, University of Edinburgh 2 Bucclecuch Place, Edinburgh EH8 9LW, UK s.r.riedel@sms.ed.ac.uk, jclarke@ed.ac.uk Abstract Integer Linear Programming has recently been used for decoding in a number of probabilistic models in order to enforce global constraints. However, in certain ap- plications, such as non-projective depen- dency parsing and machine translation, the complete formulation of the decod- ing problem as an integer linear program renders solving intractable. We present an approach which solves the problem in- crementally, thus we avoid creating in- tractable integer linear programs. This ap- proach is applied to Dutch dependency parsing and we show how the addition of linguistically motivated constraints can yield a significant improvement over state- of-the-art. 1 Introduction Many inference algorithms require models to make strong assumptions of conditional indepen- dence between variables. For example, the Viterbi algorithm used for decoding in conditional ran- dom fields requires the model to be Markovian. Strong assumptions are also made in the case of McDonald et al.’s (2005b) non-projective depen- dency parsing model. Here attachment decisions are made independently of one another1. However, often such assumptions can not be justified. For example in dependency parsing, if a subject has already been identified for a given verb, then the probability of attaching a second subject to the verb is zero. Similarly, if we find that one coor- dination argument is a noun, then the other argu- 1If we ignore the constraint that dependency trees must be cycle-free (see sections 2 and 3 for details). ment cannot be a verb. Thus decisions are often co-dependent. Integer Linear Programming (ILP) has recently been applied to inference in sequential condi- tional random fields (Roth and Yih, 2004), this has allowed the use of truly global constraints during inference. However, it is not possible to use this approach directly for a complex task like non-projective dependency parsing due to the ex- ponential number of constraints required to pre- vent cycles occurring in the dependency graph. To model all these constraints explicitly would re- sult in an ILP formulation too large to solve effi- ciently (Williams, 2002). A similar problem also occurs in an ILP formulation for machine transla- tion which treats decoding as the Travelling Sales- man Problem (Germann et al., 2001). In this paper we present a method which extends the applicability of ILP to a more complex set of problems. Instead of adding all the constraints we wish to capture to the formulation, we first solve the program with a fraction of the constraints. The solution is then examined and, if required, addi- tional constraints are added. This procedure is re- peated until all constraints are satisfied. We apply this dependency parsing approach to Dutch due to the language’s non-projective nature, and take the parser of McDonald et al. (2005b) as a …

Content truncated to 500 words