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

Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan


Abstract
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.
Anthology ID:
P17-1193
Volume:
Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Month:
July
Year:
2017
Address:
Vancouver, Canada
Editors:
Regina Barzilay, Min-Yen Kan
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
2110–2120
Language:
URL:
https://aclanthology.org/P17-1193
DOI:
10.18653/v1/P17-1193
Bibkey:
Cite (ACL):
Junjie Cao, Sheng Huang, Weiwei Sun, and Xiaojun Wan. 2017. Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2110–2120, Vancouver, Canada. Association for Computational Linguistics.
Cite (Informal):
Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs (Cao et al., ACL 2017)
Copy Citation:
PDF:
https://aclanthology.org/P17-1193.pdf
Note:
 P17-1193.Notes.pdf
Software:
 P17-1193.Software.tgz