Quasi-Second-Order Parsing for 1-Endpoint-Crossing, Pagenumber-2 Graphs

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 24–34 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Quasi-Second-Order Parsing for 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 propose a new Maximum Subgraph algorithm for first-order parsing to 1- endpoint-crossing, pagenumber-2 graphs. Our algorithm has two characteristics: (1) it separates the construction for noncross- ing edges and crossing edges; (2) in a single construction step, whether to cre- ate a new arc is deterministic. These two characteristics make our algorithm rela- tively easy to be extended to incorpo- riate crossing-sensitive second-order fea- tures. We then introduce a new algorithm for quasi-second-order parsing. Experi- ments demonstrate that second-order fea- tures are helpful for Maximum Subgraph parsing. 1 Introduction Previous work showed that treating semantic de- pendency parsing as the search for Maximum Sub- graphs is not only elegant in theory but also ef- fective in practice (Kuhlmann and Jonsson, 2015; Cao et al., 2017). In particular, our previous work showed that 1-endpoint-crossing, pagenumber-2 (1EC/P2) graphs are an appropriate graph class for modelling semantic dependency structures (Cao et al., 2017). On the one hand, it is highly expres- sive to cover a majority of semantic analysis. On the other hand, the corresponding Maximum Sub- graph problem with an arc-factored disambigua- tion model can be solved in low-degree polyno- mial time. Defining disambiguation models on wider con- texts than individual bi-lexical dependencies im- proves various syntactic parsers in different ar- chitectures. This paper studies exact algorithms for second-order parsing for 1EC/P2 graphs. The existing algorithm, viz. our previous algorithm (GCHSW, hereafter), has two properties that make it hard to incorporate higher-order features in a principled way. First, GCHSW does not explicitly consider the construction of noncrossing arcs. We will show that incorporiating higher-order factors containing crossing arcs without increasing time and space complexity is extremely hard. An effec- tive strategy is to only include higher-order factors containing only noncrossing arcs (Pitler, 2014). But this crossing-sensitive strategy is incompat- ible with GCHSW. Second, all existing higher- order parsing algorithms for projective trees, in- cluding (McDonald and Pereira, 2006; Carreras, 2007; Koo and Collins, 2010), require that which arcs are created in a construction step be deter- ministic. This design is also incompatible with GCHSW. In summary, it is not convenient to ex- tend GCHSW to incorporate higher-order features while keeping the same time complexity. In this paper, we introduce an alternative Max- imum Subgraph algorithm for first-order parsing to 1EC/P2 graphs. while keeping the same time and space complexity to GCHSW, our new algo- rithm has two characteristics that make it rela- tively easy to be extended to incorporate crossing- sensitive, second-order features: (1) it separates the construction for noncrossing edges and pos- sible crossing edges; (2) whether an edge is cre- ated is deterministic in each construction rule. We then introduce a …

Content truncated to 500 words