Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing

Tim Vieira, Jason Eisner


Abstract
Pruning hypotheses during dynamic programming is commonly used to speed up inference in settings such as parsing. Unlike prior work, we train a pruning policy under an objective that measures end-to-end performance: we search for a fast and accurate policy. This poses a difficult machine learning problem, which we tackle with the lols algorithm. lols training must continually compute the effects of changing pruning decisions: we show how to make this efficient in the constituency parsing setting, via dynamic programming and change propagation algorithms. We find that optimizing end-to-end performance in this way leads to a better Pareto frontier—i.e., parsers which are more accurate for a given runtime.
Anthology ID:
Q17-1019
Volume:
Transactions of the Association for Computational Linguistics, Volume 5
Month:
Year:
2017
Address:
Cambridge, MA
Editors:
Lillian Lee, Mark Johnson, Kristina Toutanova
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
263–278
Language:
URL:
https://aclanthology.org/Q17-1019
DOI:
10.1162/tacl_a_00060
Bibkey:
Cite (ACL):
Tim Vieira and Jason Eisner. 2017. Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing. Transactions of the Association for Computational Linguistics, 5:263–278.
Cite (Informal):
Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing (Vieira & Eisner, TACL 2017)
Copy Citation:
PDF:
https://aclanthology.org/Q17-1019.pdf
Video:
 https://aclanthology.org/Q17-1019.mp4
Data
Penn Treebank