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

2017-07-01 · ACL 2017 7 · Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan

We study the Maximum Subgraph problem in deep dependency parsing. We consider 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 simultaneously 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 disambiguation model and evaluate its performance on four linguistic data sets used in semantic dependency parsing.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Dependency Parsing Semantic Dependency Parsing

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

2017-09-01 · EMNLP 2017 9 · Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan

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 noncrossing edges and crossing…

ARC Dependency Parsing

Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs

2017-09-01 · WS 2017 9 · Robin Kurtz, Marco Kuhlmann

Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint…

Dependency Parsing Sentence

Parsing to Noncrossing Dependency Graphs

2015-01-01 · TACL 2015 1 · Marco Kuhlmann, Peter Jonsson

We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restricti…

ARC Dependency Parsing Semantic Dependency Parsing

Neural Maximum Subgraph Parsing for Cross-Domain Semantic Dependency Analysis

2018-10-01 · CONLL 2018 10 · Yufei Chen, Sheng Huang, Fang Wang, Junjie Cao 외

We present experiments for cross-domain semantic dependency analysis with a neural Maximum Subgraph parser. Our parser targets 1-endpoint-crossing, pagenumber-2 graphs which are a good fit to semantic dependency graphs, …

Dependency Parsing Semantic Parsing

Finding Optimal 1-Endpoint-Crossing Trees

2013-01-01 · TACL 2013 1 · Emily Pitler, Sampath Kannan, Mitchell Marcus

Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8{-…

Dependency Parsing Machine Translation Question Answering