Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 2110–2120 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1193 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 2110–2120 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1193 Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs Junjie Cao∗, Sheng Huang∗, Weiwei Sun and Xiaojun Wan Institute of Computer Science and Technology, Peking University The MOE Key Laboratory of Computational Linguistics, Peking University {junjie.cao,huangsheng,ws,wanxiaojun}@pku.edu.cn Abstract We study the Maximum Subgraph prob- lem in deep dependency parsing. We con- sider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2. Our main contribution is an exact algorithm that obtains maximum subgraphs satisfying both restrictions si- multaneously in time O(n5). Moreover, ignoring one linguistically-rare structure descreases the complexity to O(n4). We also extend our quartic-time algorithm into a practical parser with a discriminative dis- ambiguation model and evaluate its perfor- mance on four linguistic data sets used in semantic dependency parsing. 1 Introduction Dependency parsing has long been studied as a central issue in developing syntactic or seman- tic analysis. Recently, some linguistic projects grounded on deep grammar formalisms, including CCG, LFG, and HPSG, draw attentions to rich syn- tactic and semantic dependency annotations that are not limited to trees (Hockenmaier and Steed- man, 2007; Sun et al., 2014; Ivanova et al., 2012). Parsing for these deep dependency representations can be viewed as the search for Maximum Sub- graphs (Kuhlmann and Jonsson, 2015). This is a natural extension of the Maximum Spanning Tree (MST) perspective (McDonald et al., 2005) for de- pendency tree parisng. One main challenge of the Maximum Subgraph perspective is to design tracTable algorithms for certain graph classes that have good empirical cov- erage for linguistic annotations. Unfortunately, no previously defined class simultaneously has high ∗The first two authors contribute equally. coverage and low-degree polynomial parsing al- gorithms. For example, noncrossing dependency graphs can be found in time O(n3), but cover only 48.23% of sentences in CCGBank (Kuhlmann and Jonsson, 2015). We study two well-motivated restrictions to deep dependency graphs: (a) 1-endpoint-crossing (1EC hereafter; Pitler et al., 2013) and (b) pa- genumber is less than or equal to 2 (P2 hereafter; Kuhlmann and Jonsson, 2015). We will show that if the output dependency graphs are restricted to satisfy both restrictions, the Maximum Subgraph problem can be solved using dynamic program- ming in time O(n5). Moreover, if we ignore one linguistically-rare sub-problem, we can reduce the time complexity to O(n4). Though this new algo- rithm is a degenerated one, it has the same empiri- cal coverage for various deep dependency annota- tions. We evaluate the coverage of our algorithms on four linguistic data sets: CCGBank, DeepBank, Enju HPSGBank and Prague Dependency Tree- Bank. They cover 95.68%, 97.67%, 97.28% and 97.53% of dependency graphs in the four corpora. The relatively satisfactory coverage makes it pos- sible to parse with high accuracy. Based on the quartic-time algorithm, …

Content truncated to 500 words