Discriminative Reranking for Natural Language Parsing 
 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 F-measure 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 . 