Fast and Accurate Arc Filtering for Dependency Parsing

Опубликовано 17 августа 2016, 22:24

Graph-based dependency parsing finds direct syntactic relationships between words in a sentence by connecting head-modifier pairs into a tree structure. We propose a series of learned arc filters to speed up this process. 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 the true dependencies. These filters improve the speed of two state-of-the-art dependency parsers, with low overhead and negligible loss in accuracy. We also present ongoing work, where we attempt to improve the performance of overlapping linear filters with joint training, where filter interactions are handled using latent variables.