Combining (Second-Order) Graph-Based and Headed-Span-Based Projective Dependency Parsing

Songlin Yang, Kewei Tu


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://aclanthology.org/2022.findings-acl.112
DOI:
10.18653/v1/2022.findings-acl.112
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/2022.findings-acl.112.pdf
Code
 sustcsonglin/span-based-dependency-parsing