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

Junjie Cao, Sheng Huang, Weiwei Sun, Xiaojun Wan


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 noncrossing edges and crossing edges; (2) in a single construction step, whether to create a new arc is deterministic. These two characteristics make our algorithm relatively easy to be extended to incorporiate crossing-sensitive second-order features. We then introduce a new algorithm for quasi-second-order parsing. Experiments demonstrate that second-order features are helpful for Maximum Subgraph parsing.
Anthology ID:
D17-1003
Volume:
Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing
Month:
September
Year:
2017
Address:
Copenhagen, Denmark
Venue:
EMNLP
SIG:
SIGDAT
Publisher:
Association for Computational Linguistics
Note:
Pages:
24–34
Language:
URL:
https://www.aclweb.org/anthology/D17-1003
DOI:
10.18653/v1/D17-1003
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/D17-1003.pdf
Attachment:
 D17-1003.Attachment.pdf
Video:
 https://vimeo.com/238235370