Fast and Accurate Arc Filtering for Dependency Parsing

  1. (PDF, 255 KB)
AuthorSearch for: ; Search for:
Proceedings titleProceedings of the 23rd International Conference on Computational Linguistics (Coling 2010)
Conference23rd International Conference on Computational Linguistics (COLING 2010), August 23-27, 2010, Beijing, China
Pages5361; # of pages: 9
AbstractWe propose a series of learned arc filters to speed up graph-based dependency parsing. A cascade of filters identify implausible head-modifier pairs, with time complexity that is first linear, and then quadratic in the length of the sentence. The linear filters reliably predict, in context, words that are roots or leaves of dependency trees, and words that are likely to have heads on their left or right. We use this information to quickly prune arcs from the dependency graph. More than 78% of total arcs are pruned while retaining 99.5%of the true dependencies. These filters improve the speed of two state-ofthe- art dependency parsers, with low overhead and negligible loss in accuracy.
Publication date
AffiliationNational Research Council Canada (NRC-CNRC); NRC Institute for Information Technology
Peer reviewedYes
NPARC number16285590
Export citationExport as RIS
Report a correctionReport a correction
Record identifier0d559e8d-f4dc-47a7-bdb7-5b6253e5c95c
Record created2010-11-03
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)