Loss Minimization in Parse Reranking

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 560–567, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Loss Minimization in Parse Reranking Ivan Titov Department of Computer Science University of Geneva 24, rue G´en´eral Dufour CH-1211 Gen`eve 4, Switzerland ivan.titov@cui.unige.ch James Henderson School of Informatics University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW, United Kingdom james.henderson@ed.ac.uk Abstract We propose a general method for reranker construction which targets choosing the candidate with the least expected loss, rather than the most probable candidate. Different approaches to expected loss ap- proximation are considered, including es- timating from the probabilistic model used to generate the candidates, estimating from a discriminative model trained to rerank the candidates, and learning to ap- proximate the expected loss. The pro- posed methods are applied to the parse reranking task, with various baseline mod- els, achieving significant improvement both over the probabilistic models and the discriminative rerankers. When a neural network parser is used as the probabilistic model and the Voted Perceptron algorithm with data-defined kernels as the learning algorithm, the loss minimization model achieves 90.0% labeled constituents F1 score on the standard WSJ parsing task. 1 Introduction The reranking approach is widely used in pars- ing (Collins and Koo, 2005; Koo and Collins, 2005; Henderson and Titov, 2005; Shen and Joshi, 2003) as well as in other structured classifica- tion problems. For structured classification tasks, where labels are complex and have an internal structure of interdependency, the 0-1 loss consid- ered in classical formulation of classification al- gorithms is not a natural choice and different loss functions are normally employed. To tackle this problem, several approaches have been proposed to accommodate loss functions in learning algo- rithms (Tsochantaridis et al., 2004; Taskar et al., 2004; Henderson and Titov, 2005). A very differ- ent use of loss functions was considered in the ar- eas of signal processing and machine translation, where direct minimization of expected loss (Min- imum Bayes Risk decoding) on word sequences was considered (Kumar and Byrne, 2004; Stol- cke et al., 1997). The only attempt to use Mini- mum Bayes Risk (MBR) decoding in parsing was made in (Goodman, 1996), where a parsing al- gorithm for constituent recall minimization was constructed. However, their approach is limited to binarized PCFG models and, consequently, is not applicable to state-of-the-art parsing meth- ods (Charniak and Johnson, 2005; Henderson, 2004; Collins, 2000). In this paper we consider several approaches to loss approximation on the basis of a candidate list provided by a baseline probabilistic model. The intuitive motivation for expected loss mini- mization can be seen from the following example. Consider the situation where there are a group of several very similar candidates and one very dif- ferent candidate whose probability is just slightly larger than the probability of any individual candi- date in the group, but much smaller than their total probability. A method which chooses the maxi- mum probability candidate will choose this outlier candidate, which is correct if you …

Content truncated to 500 words