Finding Optimal 1-Endpoint-Crossing Trees

Emily Pitler, Sampath Kannan, Mitchell Marcus


Abstract
Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8–99.8% of dependency parses in various natural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing property can be found with an O(n4) parsing algorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint-Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP.
Anthology ID:
Q13-1002
Volume:
Transactions of the Association for Computational Linguistics, Volume 1
Month:
Year:
2013
Address:
Cambridge, MA
Editors:
Dekang Lin, Michael Collins
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
13–24
Language:
URL:
https://aclanthology.org/Q13-1002
DOI:
10.1162/tacl_a_00206
Bibkey:
Cite (ACL):
Emily Pitler, Sampath Kannan, and Mitchell Marcus. 2013. Finding Optimal 1-Endpoint-Crossing Trees. Transactions of the Association for Computational Linguistics, 1:13–24.
Cite (Informal):
Finding Optimal 1-Endpoint-Crossing Trees (Pitler et al., TACL 2013)
Copy Citation:
PDF:
https://aclanthology.org/Q13-1002.pdf
Video:
 https://aclanthology.org/Q13-1002.mp4