Parsing to Noncrossing Dependency Graphs

Marco Kuhlmann, Peter Jonsson


Abstract
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 restriction to noncrossing dependency graphs. Our main contribution is a cubic-time exact inference algorithm for this class. We extend this algorithm into a practical parser and evaluate its performance on four linguistic data sets used in semantic dependency parsing. We also explore a generalization of our parsing framework to dependency graphs with pagenumber at most k and show that the resulting optimization problem is NP-hard for k ≥ 2.
Anthology ID:
Q15-1040
Volume:
Transactions of the Association for Computational Linguistics, Volume 3
Month:
Year:
2015
Address:
Cambridge, MA
Editors:
Michael Collins, Lillian Lee
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
559–570
Language:
URL:
https://aclanthology.org/Q15-1040
DOI:
10.1162/tacl_a_00158
Bibkey:
Cite (ACL):
Marco Kuhlmann and Peter Jonsson. 2015. Parsing to Noncrossing Dependency Graphs. Transactions of the Association for Computational Linguistics, 3:559–570.
Cite (Informal):
Parsing to Noncrossing Dependency Graphs (Kuhlmann & Jonsson, TACL 2015)
Copy Citation:
PDF:
https://aclanthology.org/Q15-1040.pdf