Fast and Accurate Arc Filtering for Dependency Parsing

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 53–61, Beijing, August 2010 Fast and Accurate Arc Filtering for Dependency Parsing Shane Bergsma Department of Computing Science University of Alberta sbergsma@ualberta.ca Colin Cherry Institute for Information Technology National Research Council Canada colin.cherry@nrc-cnrc.gc.ca Abstract We propose a series of learned arc fil- ters to speed up graph-based dependency parsing. A cascade of filters identify im- plausible 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 con- text, words that are roots or leaves of de- pendency 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 retain- ing 99.5% of the true dependencies. These filters improve the speed of two state-of- the-art dependency parsers, with low over- head and negligible loss in accuracy. 1 Introduction Dependency parsing finds direct syntactic rela- tionships between words by connecting head- modifier pairs into a tree structure. Depen- dency information is useful for a wealth of nat- ural language processing tasks, including ques- tion answering (Wang et al., 2007), semantic pars- ing (Poon and Domingos, 2009), and machine translation (Galley and Manning, 2009). We propose and test a series of arc filters for graph-based dependency parsers, which rule out potential head-modifier pairs before parsing be- gins. In doing so, we hope to eliminate im- plausible links early, saving the costs associated with them, and speeding up parsing. In addi- tion to the scaling benefits that come with faster processing, we hope to enable richer features for parsing by constraining the set of arcs that need to be considered. This could allow ex- tremely large feature sets (Koo et al., 2008), or the look-up of expensive corpus-based features such as word-pair mutual information (Wang et al., 2006). These filters could also facilitate expen- sive learning algorithms, such as semi-supervised approaches (Wang et al., 2008). We propose three levels of filtering, which are applied in a sequence of increasing complexity: Rules: A simple set of machine-learned rules based only on parts-of-speech. They prune over 25% of potential arcs with almost no loss in cover- age. Rules save on the wasted effort for assessing implausible arcs such as DT → DT. Linear: A series of classifiers that tag words ac- cording to their possible roles in the dependency tree. By treating each word independently and en- suring constant-time feature extraction, they oper- ate in linear time. We view these as a dependency- parsing analogue to the span-pruning proposed by Roark and Hollingshead (2008). Our fast linear filters prune 54.2% of potential arcs while recov- ering 99.7% of true pairs. Quadratic: A final stage that looks at pairs of words to prune unlikely arcs from the dependency tree. By employing a light-weight feature set, this high-precision filter can enable more expensive processing on the remaining plausible …

Content truncated to 500 words