Abstract
We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as dynamic oracle. Unlike existing algorithms, it is applicable if the training corpus contains non-projective structures. We then show that for a projective training corpus, the time complexity can be improved from cubic to linear.- Anthology ID:
- Q19-1018
- Volume:
- Transactions of the Association for Computational Linguistics, Volume 7
- Month:
- Year:
- 2019
- Address:
- Cambridge, MA
- Venue:
- TACL
- SIG:
- Publisher:
- MIT Press
- Note:
- Pages:
- 283–296
- Language:
- URL:
- https://aclanthology.org/Q19-1018
- DOI:
- 10.1162/tacl_a_00268
- Cite (ACL):
- Mark-Jan Nederhof. 2019. Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time. Transactions of the Association for Computational Linguistics, 7:283–296.
- Cite (Informal):
- Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time (Nederhof, TACL 2019)
- PDF:
- https://preview.aclanthology.org/remove-xml-comments/Q19-1018.pdf