Abstract
We describe two approaches to single-root dependency parsing that yield significant speed ups in such parsing. One approach has been previously used in dependency parsers in practice, but remains undocumented in the parsing literature, and is considered a heuristic. We show that this approach actually finds the optimal dependency tree. The second approach relies on simple reweighting of the inference graph being input to the dependency parser and has an optimal running time. Here, we again show that this approach is fully correct and identifies the highest-scoring parse tree. Our experiments demonstrate a manyfold speed up compared to a previous graph-based state-of-the-art parser without any loss in accuracy or optimality.- Anthology ID:
- 2021.emnlp-main.823
- Volume:
- Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing
- Month:
- November
- Year:
- 2021
- Address:
- Online and Punta Cana, Dominican Republic
- Editors:
- Marie-Francine Moens, Xuanjing Huang, Lucia Specia, Scott Wen-tau Yih
- Venue:
- EMNLP
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 10540–10557
- Language:
- URL:
- https://aclanthology.org/2021.emnlp-main.823
- DOI:
- 10.18653/v1/2021.emnlp-main.823
- Cite (ACL):
- Miloš Stanojević and Shay B. Cohen. 2021. A Root of a Problem: Optimizing Single-Root Dependency Parsing. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10540–10557, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
- Cite (Informal):
- A Root of a Problem: Optimizing Single-Root Dependency Parsing (Stanojević & Cohen, EMNLP 2021)
- PDF:
- https://preview.aclanthology.org/emnlp22-frontmatter/2021.emnlp-main.823.pdf
- Code
- stanojevic/fast-mst-algorithm