Dependency Parsing with Bounded Block Degree and Well-nestedness via Lagrangian Relaxation and Branch-and-Bound

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 355–366, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Dependency Parsing with Bounded Block Degree and Well-nestedness via Lagrangian Relaxation and Branch-and-Bound Caio Corro Joseph Le Roux Mathieu Lacroix Antoine Rozenknop Roberto Wolfler Calvo Laboratoire d’Informatique de Paris Nord, Universit´e Paris 13 – SPC, CNRS UMR 7030, F-93430, Villetaneuse, France {corro,leroux,lacroix,rozenknop,wolfler}@lipn.fr Abstract We present a novel dependency pars- ing method which enforces two structural properties on dependency trees: bounded block degree and well-nestedness. These properties are useful to better represent the set of admissible dependency structures in treebanks and connect dependency pars- ing to context-sensitive grammatical for- malisms. We cast this problem as an Inte- ger Linear Program that we solve with La- grangian Relaxation from which we derive a heuristic and an exact method based on a Branch-and-Bound search. Experimen- tally, we see that these methods are effi- cient and competitive compared to a base- line unconstrained parser, while enforcing structural properties in all cases. 1 Introduction We address the problem of enforcing two struc- tural properties on dependency trees, namely bounded block degree and well-nestedness, with- out sacrificing algorithmic efficiency. Intuitively, bounded block degree constraints force each sub- tree to have a yield decomposable into a lim- ited number of blocks of contiguous words, while well-nestedness asserts that every two distinct sub- trees must not interleave: either the yield of one subtree is entirely inside some gap of the other or they are completely separated. These two types of constraints generalize the notion of projectiv- ity: projective trees actually have a block degree bounded to one and are well-nested. Our first motivation is the fact that most de- pendency trees in NLP treebanks are well-nested and have a low block degree which depends on the language and the linguistic representation, as shown in (Pitler et al., 2012). Unfortunately, al- though polynomial algorithms exist for this class of trees (G´omez-Rodr´ıguez et al., 2009), they are not efficient enough to be of practical use in ap- plications requiring syntactic structures. In ad- dition, if either property is dropped, but not the other, then the underlying decision problem be- comes harder. That is why practical parsing algo- rithms are either completely unconstrained (Mc- Donald et al., 2005) or enforce strict projectivity (Koo and Collins, 2010). This work is, to the best of our knowledge, the first attempt to build a discriminative dependency parser that enforces well-nestedness and/or bounded block degree and to use it on treebank data. We base our method on the following obser- vation: a non-projective dependency parser, thus not requiring neither well-nestedness nor bounded block degree, returns dependency trees satisfying these constraints in the vast majority of sentences. This would tend to indicate that the heavy machin- ery involved to parse with these constraints is only needed in very few cases. We consider arc-factored dependency parsing with well-nestedness and bounded block degree constraints. We formulate this problem as an In- teger Linear Program …

Content truncated to 500 words