Parsing to Noncrossing Dependency Graphs

Parsing to Noncrossing Dependency Graphs Marco Kuhlmann and Peter Jonsson Department of Computer and Information Science Linköping University, Sweden marco.kuhlmann@liu.se and peter.jonsson@liu.se Abstract We study the generalization of maximum span- ning tree dependency parsing to maximum acyclic subgraphs. Because the underlying op- timization problem is intractable even under an arc-factored model, we consider the restric- tion to noncrossing dependency graphs. Our main contribution is a cubic-time exact infer- ence algorithm for this class. We extend this al- gorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most k and show that the resulting optimization prob- lem is NP-hard for k � 2. 1 Introduction Dependency parsers provide lightweight represen- tations for the syntactic and the semantic structure of natural language. Syntactic dependency parsing (Kübler et al., 2009) has been an extremely active research area for the last decade or so, resulting in accurate and efficient parsers for a wide range of languages. Semantic dependency parsing has only recently been addressed in the literature (Oepen et al., 2014; Oepen et al., 2015; Du et al., 2015a). Syntactic dependency parsing has been formal- ized as the search for maximum spanning trees in weighted digraphs (McDonald et al., 2005b). For semantic dependency parsing, where target represen- tations are not necessarily tree-shaped, it is natural to generalize this view to maximum acyclic subgraphs, with or without the additional requirement of weak connectivity (Schluter, 2014). While a maximum spanning tree of a weighted digraph can be found in polynomial time (Tarjan, 1977), computing a maximum acyclic subgraph is intractable, and even good approximate solutions are hard to find (Guruswami et al., 2011). In this pa- per we therefore address maximum acyclic subgraph parsing under the restriction that the subgraph should be noncrossing, which informally means that its arcs can be drawn on the half-plane above the sentence in such a way that no two arcs cross (and without chang- ing the order of the words). The main contribution of this paper is an algorithm that finds a maximum noncrossing acyclic subgraph of a (vertex-ordered) weighted digraph on n vertices in time O.n3/. After giving some background (Section 2) we in- troduce the noncrossing condition, compare it to other structural constraints from the literature, and study its empirical coverage (Section 3). We then present our parsing algorithm (Section 4). To turn this algorithm into a practical parser, we combine it with an off-the-shelf feature model and online train- ing (Section 5); the source code of our system is re- leased with this paper.1 We evaluate the performance of our parser on four linguistic data sets: those used in the recent SemEval task on semantic dependency parsing (Oepen et al., 2015), and the dependency graphs extracted from CCGbank (Hockenmaier and Steedman, 2007). Finally, we explore the limits of our approach by showing that finding the maximum acyclic subgraph under a natural generalization …

Content truncated to 500 words