Incremental Parsing with the Perceptron Algorithm

By Michael Collins, Brian Roark. 2004

449 citations recorded by the source corpus.

This paper describes an incremental parsing approach where parameters are estimated using a variant of the perceptron algorithm. A beam-search algorithm is used during both training and decoding phases of the method. The perceptron approach was implemented with the same feature set as that of an existing generative model (Roark, 2001a), and experimental results show that it gives competitive performance to the generative model on parsing the Penn treebank. We demonstrate that training a perceptron model to combine with the generative model during search provides a 2.1 percent F-measure improvement over the generative model alone, to 88.8 percent.

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

Grammar as a Foreign Language (2014, methodology): “As a sequence-to-sequence prediction model it is somewhat related to the incremental parsing models, pioneered by [26] and extended by [27].”
Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks (2015, background): “Other approaches have considered the problem from a ranking perspective, in particular for parsing tasks [12] where the target output is a tree.”
Globally Normalized Transition-Based Neural Networks (2016, methodology): “Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 2442–2452, Berlin, Germany, August 7-12, 2016. c©2016 Association for Computational Linguistics”
Sequence-to-Sequence Learning as Beam-Search Optimization (2016, background): “The early-update (Collins and Roark, 2004) and LaSO (Daumé III and Marcu,”
Fast and Accurate Shift-Reduce Constituent Parsing (2013, methodology): “We apply the early update strategy (Collins and Roark, 2004), stopping parsing for parameter updates when the gold-standard state item falls off the agenda.”
Modeling the effects of memory on human online sentence processing with particle filters (2008, background): “Previous work has addressed the issues of feature locality and resource constraints by adop ting a pruning approach, in which hard locality constraints on probabilistic dependence are aban doned and only high-probability candidate structures are maintained after each step of incremental pa rsing [6,”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, methodology): “At each training iteration i, we randomly sample a set of training instances, and perform on-line learning with early update (Collins & Roark, 2004).”
Broad-coverage CCG Semantic Parsing with AMR (2015, background): “However, in contrast to Collins and Roark (2004) our data does not include gold derivations.”
Joint POS Tagging and Transition-based Constituent Parsing in Chinese with Non-local Features (2014, methodology): “To train the weight vector ~w , we employ the averaged perceptron algo-rithm with early update (Collins and Roark, 2004).”
Incremental Joint Extraction of Entity Mentions and Relations (2014, methodology): “(2012) proved the convergency of structured perceptron when inexact search is applied with violation-fixing update methods such as earlyupdate (Collins and Roark, 2004).”
Collective Entity Disambiguation with Structured Gradient Tree Boosting (2018, methodology): “The early update (Collins and Roark, 2004) and LaSO (Daum´e III and Marcu, 2005; Xu and Fern, 2007) strategies are widely adopted with beam search for updating model parameters in previous work.”
Distributed Training Strategies for the Structured Perceptron (2010, background): “…inference, which is often required for problems where the search space is too large and where strong structural independence assumptions are insufﬁcient, such as parsing (Collins and Roark, 2004; McDonald and Pereira, 2006; Zhang and Clark, 2008) and machine translation (Liang et al., 2006).”
Discriminative Syntax-Based Word Ordering for Text Generation (2015, unknown): “It was ﬁrst proposed by Collins and Roark (2004) for incremental parsing, and later gained popularity in the investigations of many NLP tasks, including POS-tagging (Zhang and Clark 2010), transition-based dependency parsing (Zhang and Clark 2008; Huang and Sagae 2010), and machine translation (Liu…”
Online Large-Margin Training of Dependency Parsers (2005, methodology): “Discriminatively trained parsers that score entire trees for a given sentence have only recently been investigated (Riezler et al., 2002; Clark and Curran, 2004; Collins and Roark, 2004; Taskar et al., 2004).”
Modeling Joint Entity and Relation Extraction with Table Representation (2014, methodology): “We instead employ a beam search to ﬁnd the best assignment with the highest score (Collins and Roark, 2004).”
Towards Understanding Situated Natural Language (2010, unknown): “As soon as ˆ y t is no longer y -good we make an “early update” to the model, similar to (Collins & Roark, 2004).”
Imitation learning for language generation from unaligned data (2016, methodology): “We further propose a variant of LOLS using sequence correction and updates (Collins and Roark, 2004), and an exponential decay schedule (Daum´e III et al., 2009) .”