Fast and Accurate Non-Projective Dependency Tree Linearization

Xiang Yu, Simon Tannert, Ngoc Thang Vu, Jonas Kuhn


Abstract
We propose a graph-based method to tackle the dependency tree linearization task. We formulate the task as a Traveling Salesman Problem (TSP), and use a biaffine attention model to calculate the edge costs. We facilitate the decoding by solving the TSP for each subtree and combining the solution into a projective tree. We then design a transition system as post-processing, inspired by non-projective transition-based parsing, to obtain non-projective sentences. Our proposed method outperforms the state-of-the-art linearizer while being 10 times faster in training and decoding.
Anthology ID:
2020.acl-main.134
Volume:
Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics
Month:
July
Year:
2020
Address:
Online
Editors:
Dan Jurafsky, Joyce Chai, Natalie Schluter, Joel Tetreault
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
1451–1462
Language:
URL:
https://aclanthology.org/2020.acl-main.134
DOI:
10.18653/v1/2020.acl-main.134
Bibkey:
Cite (ACL):
Xiang Yu, Simon Tannert, Ngoc Thang Vu, and Jonas Kuhn. 2020. Fast and Accurate Non-Projective Dependency Tree Linearization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1451–1462, Online. Association for Computational Linguistics.
Cite (Informal):
Fast and Accurate Non-Projective Dependency Tree Linearization (Yu et al., ACL 2020)
Copy Citation:
PDF:
https://aclanthology.org/2020.acl-main.134.pdf
Video:
 http://slideslive.com/38928825