Branch and Bound Algorithm for Dependency Parsing with Non-local Features

Xian Qian, Yang Liu


Abstract
Graph based dependency parsing is inefficient when handling non-local features due to high computational complexity of inference. In this paper, we proposed an exact and efficient decoding algorithm based on the Branch and Bound (B&B) framework where non-local features are bounded by a linear combination of local features. Dynamic programming is used to search the upper bound. Experiments are conducted on English PTB and Chinese CTB datasets. We achieved competitive Unlabeled Attachment Score (UAS) when no additional resources are available: 93.17% for English and 87.25% for Chinese. Parsing speed is 177 words per second for English and 97 words per second for Chinese. Our algorithm is general and can be adapted to non-projective dependency parsing or other graphical models.
Anthology ID:
Q13-1004
Volume:
Transactions of the Association for Computational Linguistics, Volume 1
Month:
Year:
2013
Address:
Cambridge, MA
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
37–48
Language:
URL:
https://aclanthology.org/Q13-1004
DOI:
10.1162/tacl_a_00208
Bibkey:
Cite (ACL):
Xian Qian and Yang Liu. 2013. Branch and Bound Algorithm for Dependency Parsing with Non-local Features. Transactions of the Association for Computational Linguistics, 1:37–48.
Cite (Informal):
Branch and Bound Algorithm for Dependency Parsing with Non-local Features (Qian & Liu, TACL 2013)
Copy Citation:
PDF:
https://preview.aclanthology.org/update-css-js/Q13-1004.pdf