Abstract
Graph-based methods, which decompose the score of a dependency tree into scores of dependency arcs, are popular in dependency parsing for decades. Recently, (CITATION) propose a headed-span-based method that decomposes the score of a dependency tree into scores of headed spans. They show improvement over first-order graph-based methods. However, their method does not score dependency arcs at all, and dependency arcs are implicitly induced by their cubic-time algorithm, which is possibly sub-optimal since modeling dependency arcs is intuitively useful. In this work, we aim to combine graph-based and headed-span-based methods, incorporating both arc scores and headed span scores into our model. First, we show a direct way to combine with O(n4) parsing complexity. To decrease complexity, inspired by the classical head-splitting trick, we show two O(n3) dynamic programming algorithms to combine first- and second-order graph-based and headed-span-based methods. Our experiments on PTB, CTB, and UD show that combining first-order graph-based and headed-span-based methods is effective. We also confirm the effectiveness of second-order graph-based parsing in the deep learning age, however, we observe marginal or no improvement when combining second-order graph-based and headed-span-based methods .- Anthology ID:
- 2022.findings-acl.112
- Volume:
- Findings of the Association for Computational Linguistics: ACL 2022
- Month:
- May
- Year:
- 2022
- Address:
- Dublin, Ireland
- Editors:
- Smaranda Muresan, Preslav Nakov, Aline Villavicencio
- Venue:
- Findings
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 1428–1434
- Language:
- URL:
- https://preview.aclanthology.org/add_missing_videos/2022.findings-acl.112/
- DOI:
- 10.18653/v1/2022.findings-acl.112
- Cite (ACL):
- Songlin Yang and Kewei Tu. 2022. Combining (Second-Order) Graph-Based and Headed-Span-Based Projective Dependency Parsing. In Findings of the Association for Computational Linguistics: ACL 2022, pages 1428–1434, Dublin, Ireland. Association for Computational Linguistics.
- Cite (Informal):
- Combining (Second-Order) Graph-Based and Headed-Span-Based Projective Dependency Parsing (Yang & Tu, Findings 2022)
- PDF:
- https://preview.aclanthology.org/add_missing_videos/2022.findings-acl.112.pdf
- Code
- sustcsonglin/span-based-dependency-parsing