Forest Reranking through Subtree Ranking

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1038–1047, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Forest Reranking through Subtree Ranking Rich´ard Farkas, Helmut Schmid Institute for Natural Language Processing University of Stuttgart {farkas,schmid}@ims.uni-stuttgart.de Abstract We propose the subtree ranking approach to parse forest reranking which is a general- ization of current perceptron-based reranking methods. For the training of the reranker, we extract competing local subtrees, hence the training instances (candidate subtree sets) are very similar to those used during beam- search parsing. eter optimization.This leads to better param- Another chief advantage of the framework is that arbitrary learning to rank methods can be applied. We evaluated our reranking approach on German and En- glish phrase structure parsing tasks and com- pared it to various state-of-the-art reranking approaches such as the perceptron-based for- est reranker. The subtree ranking approach with a Maximum Entropy model significantly outperformed the other approaches. 1 Introduction Reranking has become a popular technique for solving various structured prediction tasks, such as phrase-structure (Collins, 2000) and depen- dency parsing (Hall, 2007), semantic role labeling (Toutanova et al., 2008) and machine translation (Shen et al., 2004). The idea is to (re)rank candi- dates extracted by a base system exploiting a rich feature set and operating at a global (usually sen- tence) level. Reranking achieved significant gains over the base system in many tasks because it has access to information/features which are not com- putable in the base system. Reranking also outper- forms discriminative approaches which try to han- dle the entire candidate universe (cf. Turian et al. (2006)) because the base system effectively and ef- ficiently filters out many bad candidates and makes the problem tractable. The standard approach for reranking is the n-best list ranking procedure, where the base system ex- tracts its top n global-level candidates with associ- ated goodness scores that define an initial ranking. Then the task is to rerank these candidates by us- ing a rich feature set. The bottleneck of this ap- proach is the small number of candidates consid- ered. Compared to n-best lists, packed parse forests encode more candidates in a compact way. For- est reranking methods have been proposed, which can exploit the richer set of candidates and they have been successfully applied for phrase-structure (Huang, 2008), dependency (Hayashi et al., 2011) parsing and machine translation (Li and Khudanpur, 2009) as well. Huang (2008) introduced the perceptron-based forest reranking approach. The core of the algo- rithm is a beam-search based decoder operating on the packed forest in a bottom-up manner. It follows the assumption that the feature values of the whole structure are the sum of the feature values of the lo- cal elements and they are designed to the usage of the perceptron update. Under these assumptions a 1-best Viterbi or beam-search decoder can be effi- ciently employed at parsing and training time. Dur- ing training, it decodes the 1-best complete parse then …

Content truncated to 500 words