Third-order Variational Reranking on Packed-Shared Dependency Forests

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1479–1488, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Third-order Variational Reranking on Packed-Shared Dependency Forests Katsuhiko Hayashi†, Taro Watanabe‡, Masayuki Asahara†, Yuji Matsumoto† †Nara Insutitute of Science and Technology Ikoma, Nara, 630-0192, Japan ‡National Institute of Information and Communications Technology Sorakugun, Kyoto, 619-0289, Japan {katsuhiko-h,masayu-a,matsu}@is.naist.jp taro.watanabe@nict.go.jp Abstract We propose a novel forest reranking algorithm for discriminative dependency parsing based on a variant of Eisner’s generative model. In our framework, we define two kinds of gener- ative model for reranking. One is learned from training data offline and the other from a for- est generated by a baseline parser on the fly. The final prediction in the reranking stage is performed using linear interpolation of these models and discriminative model. In order to efficiently train the model from and decode on a hypergraph data structure representing a forest, we apply extended inside/outside and Viterbi algorithms. Experimental results show that our proposed forest reranking algorithm achieves significant improvement when com- pared with conventional approaches. 1 Introduction Recently, much of research on statistical parsing has been focused on k-best (or forest) reranking (Collins, 2000; Charniak and Johnson, 2005; Huang, 2008). Typically, reranking methods first generate a list of top-k candidates (or a forest) from a base- line system, then rerank the candidates with arbi- trary features that are intractable within the baseline system. In the reranking framework, the baseline system is usually modeled with a generative model, and a discriminative model is used for reranking. Sangati et al. (2009) reversed the usual order of the two models for dependency parsing by employing a generative model to rescore the k-best candidates provided by a discriminative model. They use a vari- ant of Eisner’s generative model C (Eisner, 1996b; Eisner, 1996a) for reranking and extend it to capture higher-order information than Eisner’s second-order generative model. Their reranking model showed large improvements in dependency parsing accu- racy. They reported that the discriminative model is very effective at filtering out bad candidates, while the generative model is able to further refine the se- lection among the few best candidates. In this paper, we propose a forest generative reranking algorithm, opposed to Sangati et al. (2009)’s approach which reranks only k-best candi- dates. Forests usually encode better candidates more compactly than k-best lists (Huang, 2008). More- over, our reranking uses not only a generative model obtained from training data, but also a sentence spe- cific generative model learned from a forest. In the reranking stage, we use linearly combined model of these models. We call this variational rerank- ing model. The model proposed in this paper is factored in the third-order structure, therefore, its non-locality makes it difficult to perform the rerank- ing with an usual 1-best Viterbi search. To solve this problem, we also propose a new search algo- rithm, which is inspired by the third-order dynamic programming parsing algorithm (Koo and Collins, 2010). This algorithm enables us an exact …

Content truncated to 500 words