Semantic Dependency Parsing via Book Embedding

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 828–838 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1077 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 828–838 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1077 Semantic Dependency Parsing via Book Embedding Weiwei Sun, Junjie Cao and Xiaojun Wan Institute of Computer Science and Technology, Peking University The MOE Key Laboratory of Computational Linguistics, Peking University {ws,junjie.cao,wanxiaojun}@pku.edu.cn Abstract We model a dependency graph as a book, a particular kind of topological space, for semantic dependency parsing. The spine of the book is made up of a sequence of words, and each page contains a subset of noncrossing arcs. To build a semantic graph for a given sentence, we design new Maximum Subgraph algorithms to gener- ate noncrossing graphs on each page, and a Lagrangian Relaxation-based algorithm to combine pages into a book. Experi- ments demonstrate the effectiveness of the book embedding framework across a wide range of conditions. Our parser obtains comparable results with a state-of-the-art transition-based parser. 1 Introduction Dependency analysis provides a lightweight and effective way to encode syntactic and semantic information of natural language sentences. One of its branches, syntactic dependency parsing (K¨ubler et al., 2009) has been an extremely ac- tive research area, with high-performance parsers being built and applied for practical use of NLP. Semantic dependency parsing, however, has only been addressed in the literature recently (Oepen et al., 2014, 2015; Du et al., 2015; Zhang et al., 2016; Cao et al., 2017). Semantic dependency parsing employs a graph- structured semantic representation. On the one hand, it is flexible enough to provide analysis for various semantic phenomena (Ivanova et al., 2012). This very flexibility, on the other hand, brings along new challenges for designing pars- ing algorithms. For graph-based parsing, no previ- ously defined Maximum Subgraph algorithm has simultaneously a high coverage and a polynomial complexity to low degrees. For transition-based parsing, no principled decoding algorithms, e.g. dynamic programming (DP), has been developed for existing transition systems. In this paper, we borrow the idea of book em- bedding from graph theory, and propose a novel framework to build parsers for flexible depen- dency representations. In graph theory, a book is a kind of topological space that consists of a spine and a collection of one or more half-planes. In our “book model” of semantic dependency graph, the spine is made up of a sequence of words, and each half-plane contains a subset of dependency arcs. In particular, the arcs on each page com- pose a noncrossing dependency graph, a.k.a. pla- nar graph. Though a dependency graph in general is very flexible, its subgraph on each page is rather regular. Under the new perspective, semantic de- pendency parsing can be cast as a two-step task: Each page is first analyzed separately, and then all the pages are bound coherently. Our work is motivated by the extant …

Content truncated to 500 words