Paper: Incremental Integer Linear Programming For Non-Projective Dependency Parsing

ACL ID W06-1616
Title Incremental Integer Linear Programming For Non-Projective Dependency Parsing
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2006
Authors

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 signi cant improvement over state- of-the-art.