New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron

By Michael Collins, Nigel P. Duffy. Annual Meeting of the Association for Computational Linguistics, 2002

634 citations recorded by the source corpus.

This paper introduces new learning algorithms for natural language processing based on the perceptron algorithm. We show how the algorithms can be efficiently applied to exponential sized representations of parse trees, such as the "all subtrees" (DOP) representation described by (Bod 1998), or a representation tracking all sub-fragments of a tagged sentence. We give experimental results showing significant improvements on two tasks: parsing Wall Street Journal text, and named-entity extraction from web data.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/fe638b5610475d4524684fb2c2b7b08c119c8700

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 Computational Theory and Mathematics

Citations in the corpus

Ranking Algorithms for Named Entity Extraction: Boosting and the VotedPerceptron (2002, methodology): “(Collins and Duffy 2002) describe the voted perceptron applied to the named-entity data in this paper, but us-ing kernel-based features rather than the explicit features described in this paper.”
Discriminative Training of a Neural Network Statistical Parser (2004, neutral): “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.”
Intricacies of Collins’ Parsing Model (2004, background): “…on parsing the Penn Treebank (Marcus, Santorini, and Marcinkiewicz, 1993), and not only did they serve as the basis of Collins’ own future work (Collins, 2000; Collins and Duffy, 2002), but they also served as the basis of important work on parser selection (Henderson and Brill, 1999), an…”
Minimum Bayes-Risk Decoding for Statistical Machine Translation (2004, methodology): “The computation of tree-edit distance involves an unconstrained alignment of the two English parse-trees.”
A Tree-Based Kernel for Graphs (2012, background): “State of the art results on various benchmark datasets prove the effectiveness of our approach.”
Modelling input texts: from Tree Kernels to Deep Learning (2015, methodology): “In this section we introduce some of the most general types of structural kernels used in NLP and throughout this thesis: string kernels (SKs) [140], the Syntactic Tree Kernels (STKs) [32] and the Partial Tree Kernels (PTKs) [93].”
Learning Nonsparse Kernels by Self-Organizing Maps for Structured Data (2009, methodology): “Finally, the SOM for structured data is described.”
Semantic Frames to Predict Stock Price Movement (2013, methodology): “However, there are fast algorithms for kernel computation that run in linear time on average, either by dynamic programming (Collins and Duffy, 2002), or pre-sorting production rules before training (Moschitti, 2006).”
Discriminative Reranking for Natural Language Parsing (2000, methodology): “…gives convergence proofs for the methods; Collins (2002a) directly compares the boosting and perceptron approaches on a named entity task; and Collins and Duffy (2001, 2002) use a reranking approach with kernels, which allow representations of parse trees or labeled sequences in…”
Generative Kernels for Tree-Structured Data (2018, methodology): “The Subset Tree kernel (SST) by [11], for instance, counts the number of matching proper subtrees by a recursive procedure that is O ( N 2 T ) , where N T is the maximum number of nodes among the two trees.”
Training a Multilingual Sportscaster: Using Perceptual Context to Learn Language (2014, methodology): “Recently, kernels over strings and trees have been effectively applied to a variety of problems in text learning and NLP (Lodhi, Saunders, Shawe-Taylor, Cristianini, & Watkins, 2002; Zelenko, Aone, & Richardella, 2003; Collins, 2002; Bunescu & Mooney, 2005).”
Learning with Annotation Noise (2009, methodology): “This algorithm and its many variants are widely used in the computational linguistics community (Collins, 2002a; Collins and Duffy, 2002; Collins, 2002b; Collins and Roark, 2004; Henderson and Titov, 2005; Viola and Narasimhan, 2005; Cohen et al., 2004; Carreras et al., 2005; Shen and Joshi, 2005;…”
A Survey of Multi-View Representation Learning (2016, neutral): “In fact, this method is a special margin ranking perceptron [143], which has been shown to be equivalent to SVM [144].”
Shallow Parsing with Conditional Random Fields (2003, background): “However, work in that direction has so far addressed only parse reranking (Collins and Duffy, 2002; Riezler et al., 2002).”
Learning Semantic Textual Similarity with Structural Representations (2013, methodology): “We have provided an extensive experimental study of four different structural representations, e.g. shallow, constituency, dependency and phrase-dependency trees using STK and PTK.”
Structured Lexical Similarity via Convolution Kernels on Dependency Trees (2011, methodology): “…the other hand, automatic feature engineering of syntactic or shallow semantic structures has been carried out by means of structural kernels, e.g. (Collins and Duffy, 2002; Kudo and Matsumoto, 2003; Cumby and Roth, 2003; Cancedda et al., 2003; Daum´e III and Marcu, 2004; Toutanova et al., 2004;…”