A Reranking Approach for Dependency Parsing with Variable-sized Subtree Features

Copyright 2012 by Mo Shen, Daisuke Kawahara, and Sadao Kurohashi 26th Pacific Asia Conference on Language,Information and Computation pages 308–317 A Reranking Approach for Dependency Parsing with Variable-sized Subtree Features Mo Shen, Daisuke Kawahara, and Sadao Kurohashi Graduate School of Informatics Kyoto University Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501, Japan shen@nlp.ist.i.kyoto-u.ac.jp {dk,kuro}@i.kyoto-u.ac.jp Abstract Employing higher-order subtree structures in graph-based dependency parsing has shown substantial improvement over the accuracy, however suffers from the inefficiency increasing with the order of subtrees. We present a new reranking approach for dependency parsing that can utilize complex subtree representation by applying efficient subtree selection heuristics. We demonstrate the effective- ness of the approach in experiments conducted on the Penn Treebank and the Chinese Treebank. Our system improves the baseline accuracy from 91.88% to 93.37% for English, and in the case of Chinese from 87.39% to 89.16%. 1. Introduction In dependency parsing, graph-based models are prevalent for their state-of-the-art accuracy and efficiency, which are gained from their ability to combine exact inference and discriminative learning methods. The ability to perform efficient exact inference lies on the so-called factorization technique which breaks down a parse tree into smaller substructures to perform an efficient dynamic programming search. This treatment however restricts the representation of features to in a local context which can be, for example, single edges or adjacent edges. Such restriction prohibits the model from exploring large or complex structures for linguistic evidence, which can be considered as the major drawback of the graph- based approach. Attempts have been made in developing more complex factorization techniques and corresponding decoding methods. Higher-order models that use grand-child, grand-sibling or tri- sibling factorization were proposed in (Koo and Collins, 2010) to explore more expressive features and have proven significant improvement on parsing accuracy. However, the power of higher- order models comes with the cost of expensive computation and sometimes it requires aggressive pruning in the pre-processing. Another line of research that explores complex feature representations is parse reranking. In its general framework, a K-best list of parse tree candidates is first produced from the base parser; a reranker is then applied to pick up the best parse among these candidates. For constituent parsing, successful results has been reported in (Collins, 2000; Charniak and Johnson, 2005; Huang, 2008). For dependency parsing, the efficient algorithms for produce K-best list for graph-based parsers have been proposed in (Huang and Chiang, 2005) for projective parsing and in (Hall, 2007) for non- projective parsing; Improvements on dependency accuracy has been achieved in (Hall, 2007; Hayashi et al., 2011). However, the feature sets in these studies explored a relatively small context, either by emulating the feature set in the constituent parse reranking, or by factorizing the search space. A desirable approach for the K-best list reranking is to encode features on subtrees extracted from the candidate parse with arbitrary 308 Copyright 2012 by Mo Shen, Daisuke Kawahara, and Sadao Kurohashi 26 th Pacific Asia Conference on Language, Information and Computation pages 308-317 orders and structures, as long as …

Content truncated to 500 words