Syntactic Processing Using the Generalized Perceptron and Beam Search

By Yue Zhang, Stephen Clark. 2011

221 citations recorded by the source corpus.

We study a range of syntactic processing tasks using a general statistical framework that consists of a global linear model, trained by the generalized perceptron together with a generic beam-search decoder. We apply the framework to word segmentation, joint segmentation and POS-tagging, dependency parsing, and phrase-structure parsing. Both components of the framework are conceptually and computationally very simple. The beam-search decoder only requires the syntactic processing task to be broken into a sequence of decisions, such that, at each stage in the process, the decoder is able to consider the top-n candidates and generate all possibilities for the next stage. Once the decoder has been defined, it is applied to the training data, using trivial updates according to the generalized perceptron to induce a model. This simple framework performs surprisingly well, giving accuracy results competitive with the state-of-the-art on all the tasks we consider. The computational simplicity of the decoder and training algorithm leads to significantly higher test speeds and lower training times than their main alternatives, including log-linear and large-margin training algorithms and dynamic-programming for decoding. Moreover, the framework offers the freedom to define arbitrary features which can make alternative training and decoding algorithms prohibitively slow. We discuss how the general framework is applied to each of the problems studied in this article, making comparisons with alternative learning and decoding algorithms. We also show how the comparability of candidates considered by the beam is an important factor in the performance. We argue that the conceptual and computational simplicity of the framework, together with its language-independent nature, make it a competitive choice for a range of syntactic processing tasks and one that should be considered for comparison by developers of alternative approaches.

Subfields: Artificial Intelligence, Molecular Biology

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 Molecular Biology

Citations in the corpus

Neural Architectures for Named Entity Recognition (2016, background): “3 It is a greedy model that apply locally optimal actions until the entire sentence is processed, further improvements might be obtained with beam search (Zhang and Clark, 2011) or training with exploration (Ballesteros et al.”
Using Structured Events to Predict Stock Price Movement: An Empirical Investigation (2014, methodology): “We extract the predicate verb P of a sentence based on the dependency parser of Zhang and Clark (2011), and then ﬁnd the longest sequence of words P v , such that P v starts at P and satis-ﬁes the syntactic and lexical constraints proposed by Fader et al. (2011).”
Deep Learning for Event-Driven Stock Prediction (2015, methodology): “Given a sentence obtained from news text, we first use ReVerb [Fader et al., 2011] to extract the candidate tuples of the event (O 1 , P , O 2 ), and then parse the sentence with ZPar [Zhang and Clark, 2011] to extract the subject, object and predicate.”
Query Expansion Techniques for Information Retrieval: a Survey (2017, unknown): “Another important approach that improves the linguistic information of the initial query is syntactic analysis [289].”
Discriminative Syntax-Based Word Ordering for Text Generation (2015, unknown): “A DD ( c , e ) 37: end while One way of viewing the training process is that it pushes gold-standard edges towards the top of the agenda, and, crucially, pushes them above non-gold edges (Zhang and Clark 2011).”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, methodology): “A direct adaptation of the framework of Zhang and Clark (2011b) or Huang et al. (2012) under the neural probabilistic model setting does not yield good results.”
Measuring the Information Content of Financial News (2016, methodology): “We parse sentences with ZPar (Zhang and Clark, 2011) 3 and adopt the N-ary Tree-LSTM of Tai et al. (2015) with peephole connections to run on a binarized dependency-based parse tree.”
Learning the Curriculum with Bayesian Optimization for Task-Specific Word Representation Learning (2016, methodology): “We use an off-the-shelf syntactic parser2 (Zhang and Clark, 2011) to parse our training corpus.”
Neural Word Segmentation with Rich Pretraining (2017, methodology): “To train the main segmentor, we adopt the global transition-based learning and beam-search strategy of Zhang and Clark (2011).”
Event Extraction by Answering (Almost) Natural Questions (2020, methodology): “Zhang et al. (2019a) utilizes a neural transition-based extraction framework (Zhang and Clark, 2011), which requires specially designed transition actions, which still requires recognizing entities during decoding, though the entity recognition and argument role prediction is done in a joint way.”
Cross-Domain Generalization of Neural Constituency Parsers (2019, methodology): “Non-neural models We use publicly released code and models for the Berkeley Parser (Petrov and Klein, 2007) and BLLIP Parser (Charniak, 2000; Charniak and Johnson, 2005) for English; and ZPar (Zhang and Clark, 2011) for Chinese.”
Knowledge-Driven Event Embedding for Stock Prediction (2016, methodology): “The structured events are extracted from news text using Open IE (Fader et al., 2011) and dependency parsing (Zhang and Clark, 2011), by strictly following the method of Ding et al. (2015).”