Discriminative Reranking for Natural Language Parsing

By Michael Collins, Terry Koo. 2000

834 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

Evidence Aggregation for Answer Re-Ranking in Open-Domain Question Answering (2017, methodology): “Re-ranking has been commonly used in NLP problems, such as in parsing and translation, in order to make use of high-order or global features that are too expensive for decoding algorithms (Collins & Koo, 2005; Shen et al., 2004; Huang, 2008; Dyer et al., 2016).”
Parsing Algebraic Word Problems into Equations (2015, background): “Our work is also related to parser re-ranking (Collins, 2005; Ge and Mooney, 2005), where a re-ranker model attempts to improve the output of an existing probabilistic parser.”
Effective Self-Training for Parsing (2006, methodology): “It does this using the reranking methodology described in Collins (2000), using a Maximum Entropy model with Gaussian regularization as described in Johnson et al. (1999).”
Kernel methods in machine learning (2007, neutral): “Specifically for the structured case, recent work by Collins [30] and Taskar et al. [132] deals with explicit constructions to obtain better scaling behavior in terms of the number of class labels.”
Head-Driven Statistical Models for Natural Language Parsing (2003, methodology): “Two models (Collins 2000; Char-niak 2000) outperform models 2 and 3 on section 23 of the treebank.”
Modeling Local Coherence: An Entity-Based Approach (2005, methodology): “5 Our selection of this corpus was motivated by its similarity to the DUC corpus which primarily consists of news stories.”
Discriminative Training of a Neural Network Statistical Parser (2004, background): “For comparison to previous results, table 2 lists the results for our best model (DGSSN-Freq (cid:21) 20, rerank) 9 and several other statistical parsers (Ratnaparkhi, 1999; Collins, 1999; Collins and Du(cid:11)y, 2002; Charniak, 2000; Collins, 2000; Bod, 2003) on the entire testing set.”
Identifying Well-formed Natural Language Questions (2018, methodology): “We augment their system by training a discriminative reranker (Collins and Koo, 2005) with the model score of the question generation model and the well-formedness probability of our classiﬁer as features to optimize BLEU score (Papineni et al., 2002) be-tween the selected question from the 10…”
A Primer on Neural Network Models for Natural Language Processing (2015, methodology): “A similar model was also used by (Hashimoto et al., 2013) to encode subtrees in semantic-relation classification task.”
Individual and Domain Adaptation in Sentence Planning for Dialogue (2007, methodology): “Tree features capture declaratively the way in which merge, infer and cue-word operations are applied to the tp-trees, and were inspired by the parsing features used by Collins (2000). They count the occurrences of certain structural linguistic configurations in the sp-trees and associated d-trees t”
Discriminative Reranking for Semantic Parsing (2006, methodology): “While reranking has benefited many tagging and parsing tasks (Collins, 2000; Collins, 2002c; Charniak and Johnson, 2005) including semantic role labeling (Toutanova et al.”
Corpus Variation and Parser Performance (2001, methodology): “The parsing models of Charniak (2000) and Collins (2000) add more complex features to the parsing model that we use as our baseline.”
Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus (2007, background): “Of the many features that we have tried, one feature set stands out as being the most effective, the two-level rules in Collins and Koo (2005), which give the number of times a given rule is used to expand a non-terminal in a given parent rule.”
Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing (2015, methodology): “This concern prompted a movement in NLP to training using conditional likelihood (Collins, 2000; Johnson, 2001; Charniak & Johnson, 2005; Clark & Curran, 2007; Finkel et al., 2008).”
A Joint Model for Semantic Role Labeling (2005, methodology): “To overcome this problem, we adopt a discriminative re-ranking approach reminiscent of (Collins, 2000).”
Sentence Level Discourse Parsing using Syntactic and Lexical Information (2003, background): “, 1993), research on probabilistic models of syntax has driven the performance of syntactic parsers to about 90% accuracy (Charniak, 2000; Collins, 2000).”
Joint POS Tagging and Transition-based Constituent Parsing in Chinese with Non-local Features (2014, methodology): “To further improve the performance of our transition-based constituent parser, we consider two group of complex structural features: non-local features (Charniak and Johnson, 2005; Collins and Koo, 2005) and semi-supervised word cluster features (Koo et al., 2008).”