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
- 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)
- PDF:
- https://preview.aclanthology.org/teach-a-man-to-fish/Q15-1040.pdf