tailieunhanh - Báo cáo khoa học: "Concise Integer Linear Programming Formulations for Dependency Parsing"

Dency parsing. We believe that our formulations can pave the way for efficient exploitation of global features and constraints in parsing applications, leading to more powerful models. Riedel and Clarke (2006) cast dependency parsing as an ILP, but efficient formulations remain an open problem. | Concise Integer Linear Programming Formulations for Dependency Parsing Andre F. T. Martins Noah A. Smith Eric P. Xing School of Computer Science Carnegie Mellon University Pittsburgh PA 15213 USA Institute de Telecomunicacoes Instituto Superior Tecnico Lisboa Portugal afm nasmith epxing @ Abstract We formulate the problem of non-projective dependency parsing as a polynomial-sized integer linear program. 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 constraints 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 integer linear programming ILP formulations of NLP problems with interesting results in applications like semantic role labeling Roth and Yih 2005 Punyakanok et al. 2004 dependency parsing 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 incorporate non-local features or global constraints which are often difficult to handle with traditional algorithms. ILP formulations focus more on the modeling 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 formulations for projective and non-projective depen dency parsing. We believe that