Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1745–1755 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1160 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1745–1755 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1160 Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing Anssi Yli-Jyr¨a University of Helsinki, Finland anssi.yli-jyra@helsinki.fi Carlos G´omez-Rodr´ıguez Universidade da Coru˜na, Spain carlos.gomez@udc.es Abstract We present a simple encoding for unla- beled noncrossing graphs and show how its latent counterpart helps us to repre- sent several families of directed and undi- rected graphs used in syntactic and seman- tic parsing of natural language as context- free languages. The families are separated purely on the basis of forbidden patterns in latent encoding, eliminating the need to differentiate the families of non-crossing graphs in inference algorithms: one algo- rithm works for all when the search space can be controlled in parser input. 1 Introduction Dependency parsing has received wide attention in recent years, as accurate and efficient dependency parsers have appeared that are applicable to many languages. Traditionally, dependency parsers have produced syntactic analyses in tree form, includ- ing exact inference algorithms that search for max- imum projective trees (Eisner and Satta, 1999) and maximum spanning trees (McDonald et al., 2005) in weighted digraphs, as well as greedy and beam- search approaches that forgo exact search for extra efficiency (Zhang and Nivre, 2011). Recently, there has been growing interest in pro- viding a richer analysis of natural language by go- ing beyond trees. In semantic dependency parsing (Oepen et al., 2015; Kuhlmann and Oepen, 2016), the desired syntactic representations can have in- degree greater than 1 (re-entrancy), suggesting the search for maximum acyclic subgraphs (Schluter, 2014, 2015). As this inference task is intractable (Guruswami et al., 2011), noncrossing digraphs have been studied instead, e.g. by Kuhlmann and Johnsson (2015) who provide a O(n3) parser for maximum noncrossing acyclic subgraphs. Yli-Jyr¨a (2005) studied how to axiomatize de- pendency trees as a special case of noncrossing di- graphs. This gave rise to a new homomorphic rep- resentation of context-free languages that proves the classical Chomsky and Sch¨utzenberger theo- rem using a quite different internal language. In this language, the brackets indicate arcs in a de- pendency tree in a way that is reminiscent to en- coding schemes used earlier by Greibach (1973) and Oflazer (2003). Cubic-time parsing algo- rithms that are incidentally or intentionally appli- cable to this kind of homomorphic representations have been considered, e.g., by Nederhof and Satta (2003), Hulden (2011), and Yli-Jyr¨a (2012). Extending these insights to arbitrary noncross- ing digraphs, or to relevant families of them, is far from obvious. In this paper, we develop (1) a lin- ear encoding supporting general noncrossing di- graphs, and (2) show that the encoded noncrossing digraphs form a context-free language. We then give it (3) two homomorphic, nonderivative repre- sentations and use the latent local features …

Content truncated to 500 words