This article considers approaches which rerank the output of an existing probabilistic parser. The base parser produces a set of candidate parses for each input sentence, with associated probabilities that define an initial ranking of these parses. A second model then attempts to improve upon this initial ranking, using additional features of the tree as evidence. The strength of our approach is that it allows a tree to be represented as an arbitrary set of features, without concerns about how these features interact or overlap and without the need to define a derivation or a generative model which takes these features into account. We introduce a new method for the reranking task, based on the boosting approach to ranking problems described in Freund et al. (1998) . We apply the boosting method to parsing the Wall Street Journal treebank. The method combined the log-likelihood under a baseline model (that of Collins [1999]) with evidence from an additional 500,000 features over parse trees that were not included in the original model. The new model achieved 89.75% F-measure, a 13% relative decrease in Fmeasure error over the baseline model's score of 88.2%. The article also introduces a new algorithm for the boosting approach which takes advantage of the sparsity of the feature space in the parsing data. Experiments show significant efficiency gains for the new algorithm over the obvious implementation of the boosting approach. We argue that the method is an appealing alternative-in terms of both simplicity and efficiency-to work on feature selection methods within log-linear (maximum-entropy) models. Although the experiments in this article are on natural language parsing (NLP), the approach should be applicable to many other NLP problems which are naturally framed as ranking tasks, for example, speech recognition, machine translation, or natural language generation. that are believed to be useful in discriminating among candidate trees for a sentence. In practice, however, adding new features to a generative or history-based model can be awkward: The derivation in the model must be altered to take the new features into account, and this can be an intricate task. This article considers approaches which rerank the output of an existing probabilistic parser. The base parser produces a set of candidate parses for each input sentence, with associated probabilities that define an initial ranking of these parses. A second model then attempts to improve upon this initial ranking, using additional features of the tree as evidence. The strength of our approach is that it allows a tree to be represented as an arbitrary set of features, without concerns about how these features interact or overlap and without the need to define a derivation which takes these features into account. We introduce a new method for the reranking task, based on the boosting approach to ranking problems described in Freund et al. (1998) . The algorithm can be viewed as a feature selection method, optimizing a particular loss function (the exponential loss function) that has been studied in the boosting literature. We applied the boosting method to parsing the Wall Street Journal (WSJ) treebank (Marcus, Santorini, and Marcinkiewicz 1993) . The method combines the log-likelihood under a baseline model (that of Collins [1999]) with evidence from an additional 500,000 features over parse trees that were not included in the original model. The baseline model achieved 88.2% F-measure on this task. The new model achieves 89.75% Fmeasure, a 13% relative decrease in F-measure error. Although the experiments in this article are on natural language parsing, the approach should be applicable to many other natural language processing (NLP) problems which are naturally framed as ranking tasks, for example, speech recognition, machine translation, or natural language generation. See Collins (2002a) for an application of the boosting approach to named entity recognition, and Walker, Rambow, and Rogati (2001) for the application of boosting techniques for ranking in the context of natural language generation. The article also introduces a new, more efficient algorithm for the boosting approach which takes advantage of the sparse nature of the feature space in the parsing data. Other NLP tasks are likely to have similar characteristics in terms of sparsity. Experiments show an efficiency gain of a factor of 2,600 for the new algorithm over the obvious implementation of the boosting approach. Efficiency issues are important, because the parsing task is a fairly large problem, involving around one million parse trees and over 500,000 features. The improved algorithm can perform 100,000 rounds of feature selection on our task in a few hours with current processing speeds. The 100,000 rounds of feature selection require computation equivalent to around 40 passes over the entire training set (as opposed to 100,000 passes for the ''naive'' implementation). The problems with history-based models and the desire to be able to specify features as arbitrary predicates of the entire tree have been noted before. In particular, previous work (Riezler et al. 2002) has investigated the use of Markov random fields (MRFs) or log-linear models as probabilistic models with global features for parsing and other NLP tasks. (Log-linear models are often referred to as maximum-entropy models in the NLP literature.) Similar methods have also been proposed for machine translation (Och and Ney 2002) and language understanding in dialogue systems Ward 1997, 1998). Previous work (Friedman, Hastie, and Tibshirani 1998) has drawn connections between log-linear models and 26 Computational Linguistics Volume 31, Number 1 1 Note, however, that log-linear models which employ regularization methods instead of feature selection-see, for example, Johnson et al. (1999) and Lafferty, McCallum, and Pereira (2001)-are likely to be comparable in terms of efficiency to our feature selection approach. See section 6.3 for more discussion.
Feature-based integration is also similar to parse re-ranking REF , where one parser produces a set of candidate parses and a secondstage classifier chooses the most likely one.
Discriminative Reranking for Natural Language Parsing
Computational Linguistics
Computational Linguistics
Computer Science