Concise Integer Linear Programming Formulations for Dependency Parsing

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 342–350, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Concise Integer Linear Programming Formulations for Dependency Parsing Andr´e F. T. Martins∗† Noah A. Smith∗ Eric P. Xing∗ ∗School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, Lisboa, Portugal {afm,nasmith,epxing}@cs.cmu.edu Abstract We formulate the problem of non- projective dependency parsing as a polynomial-sized integer linear pro- gram. Our formulation is able to handle non-local output features in an efficient manner; not only is it compatible with prior knowledge encoded as hard con- straints, it can also learn soft constraints from data. In particular, our model is able to learn correlations among neighboring arcs (siblings and grandparents), word valency, and tendencies toward nearly- projective parses. The model parameters are learned in a max-margin framework by employing a linear programming relaxation. We evaluate the performance of our parser on data in several natural languages, achieving improvements over existing state-of-the-art methods. 1 Introduction Much attention has recently been devoted to in- teger linear programming (ILP) formulations of NLP problems, with interesting results in appli- cations like semantic role labeling (Roth and Yih, 2005; Punyakanok et al., 2004), dependency pars- ing (Riedel and Clarke, 2006), word alignment for machine translation (Lacoste-Julien et al., 2006), summarization (Clarke and Lapata, 2008), and coreference resolution (Denis and Baldridge, 2007), among others. In general, the rationale for the development of ILP formulations is to incorpo- rate non-local features or global constraints, which are often difficult to handle with traditional algo- rithms. ILP formulations focus more on the mod- eling of problems, rather than algorithm design. While solving an ILP is NP-hard in general, fast solvers are available today that make it a practical solution for many NLP problems. This paper presents new, concise ILP formu- lations for projective and non-projective depen- dency parsing. We believe that our formula- tions can pave the way for efficient exploitation of global features and constraints in parsing applica- tions, leading to more powerful models. Riedel and Clarke (2006) cast dependency parsing as an ILP, but efficient formulations remain an open problem. Our formulations offer the following comparative advantages: • The numbers of variables and constraints are polynomial in the sentence length, as opposed to requiring exponentially many constraints, elim- inating the need for incremental procedures like the cutting-plane algorithm; • LP relaxations permit fast online discriminative training of the constrained model; • Soft constraints may be automatically learned from data. In particular, our formulations han- dle higher-order arc interactions (like siblings and grandparents), model word valency, and can learn to favor nearly-projective parses. We evaluate the performance of the new parsers on standard parsing tasks in seven languages. The techniques that we present are also compatible with scenarios where expert knowledge is avail- able, for example in the form of hard or soft first- order logic constraints (Richardson and Domin- gos, 2006; Chang et al., 2008). 2 …

Content truncated to 500 words