Forest Reranking: Discriminative Parsing with Non-Local Features

Proceedings of ACL-08: HLT, pages 586–594, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Forest Reranking: Discriminative Parsing with Non-Local Features∗ Liang Huang University of Pennsylvania Philadelphia, PA 19104 lhuang3@cis.upenn.edu Abstract Conventional n-best reranking techniques of- ten suffer from the limited scope of the n- best list, which rules out many potentially good alternatives. We instead propose forest reranking, a method that reranks a packed for- est of exponentially many parses. Since ex- act inference is intractable with non-local fea- tures, we present an approximate algorithm in- spired by forest rescoring that makes discrim- inative training practical over the whole Tree- bank. Our final result, an F-score of 91.7, out- performs both 50-best and 100-best reranking baselines, and is better than any previously re- ported systems trained on the Treebank. 1 Introduction Discriminative reranking has become a popular technique for many NLP problems, in particular, parsing (Collins, 2000) and machine translation (Shen et al., 2005). Typically, this method first gen- erates a list of top-n candidates from a baseline sys- tem, and then reranks this n-best list with arbitrary features that are not computable or intractable to compute within the baseline system. But despite its apparent success, there remains a major drawback: this method suffers from the limited scope of the n- best list, which rules out many potentially good al- ternatives. For example 41% of the correct parses were not in the candidates of ∼30-best parses in (Collins, 2000). This situation becomes worse with longer sentences because the number of possible in- terpretations usually grows exponentially with the ∗ Part of this work was done while I was visiting Institute of Computing Technology, Beijing, and I thank Prof. Qun Liu and his lab for hosting me. I am also grateful to Dan Gildea and Mark Johnson for inspirations, Eugene Charniak for help with his parser, and Wenbin Jiang for guidance on perceptron aver- aging. This project was supported by NSF ITR EIA-0205456. local non-local conventional reranking only at the root DP-based discrim. parsing exact N/A this work: forest-reranking exact on-the-fly Table 1: Comparison of various approaches for in- corporating local and non-local features. sentence length. As a result, we often see very few variations among the n-best trees, for example, 50- best trees typically just represent a combination of 5 to 6 binary ambiguities (since 25 < 50 < 26). Alternatively, discriminative parsing is tractable with exact and efficient search based on dynamic programming (DP) if all features are restricted to be local, that is, only looking at a local window within the factored search space (Taskar et al., 2004; Mc- Donald et al., 2005). However, we miss the benefits of non-local features that are not representable here. Ideally, we would wish to combine the merits of both approaches, where an efficient inference algo- rithm could integrate both local and non-local fea- tures. Unfortunately, exact search is intractable (at least in theory) for features with unbounded scope. So we propose forest reranking, a technique inspired by forest …

Content truncated to 500 words