Online Large-Margin Training of Dependency Parsers

By Ryan T. McDonald, Koby Crammer, Fernando C Pereira. 2005

923 citations recorded by the source corpus.

We present an effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training (Crammer and Singer, 2003; Crammer et al., 2003) on top of efficient parsing techniques for dependency trees (Eisner, 1996). The trained parsers achieve a competitive dependency accuracy for both English and Czech with no language specific enhancements.

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

Semantic Parsing on Freebase from Question-Answer Pairs (2013, methodology): “Second, we introduce features on the POS tags involved in a composition, inspired by dependency parsing (McDonald et al., 2005).”
Image Description using Visual Dependency Representations (2013, methodology): “Recall from Section 2.1 that the descriptions were dependency-parsed using the parser of McDonald et al. (2005) and alignments were calculated between the nodes in the VDRs and the words in the parsed image descriptions.”
Domain Adaptation with Structural Correspondence Learning (2006, methodology): “We emphasize the importance of PoS tagging in a pipelined NLP system by incorporating our SCL (2005b).”
Unbounded Dependency Recovery for Parser Evaluation (2009, methodology): “The RASP parser is based on a manually constructed POS tag-sequence grammar, with a statistical parse selection component and a robust 1 One obvious omission is any form of dependency parser (McDonald et al., 2005; Nivre and Scholz, 2004).”
Dependency Parsing by Belief Propagation (2008, methodology): “A ﬁrst-order (or “edge-factored”) parsing model (McDonald et al., 2005) contains only L INK factors, along with a global T REE or PT REE factor.”
What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA (2007, methodology): “The resulting POS-tagged sentences were then parsed using MSTParser (McDonald et al., 2005), trained on the entire Penn Treebank to produce labeled dependency parse trees (we used a coarse dependency label set that includes twelve label types).”
Detecting and parsing architecture at city scale from range data (2010, methodology): “After estimating b, we learn θ using an averaged structured perceptron [6, 22].”
Neural Machine Translation with Source-Side Latent Graph Parsing (2017, result): “This approach is similar to that of graph-based dependency parsing (McDonald et al., 2005) in that a sentence is represented with a set of weighted arcs between the words.”
Transition-based Dependency Parsing with Rich Non-local Features (2011, methodology): “Compared to graph-based dependency parsing, it typically offers linear time complexity and the comparative freedom to define non-local features, as exemplified by the comparison between MaltParser and MSTParser (Nivre et al., 2006b; McDonald et al., 2005; McDonald and Nivre, 2007).”
Deep Multitask Learning for Semantic Dependency Parsing (2017, methodology): “Graph-based parsing was originally invented to handle non-projective syntax (McDonald et al., 2005; Koo et al., 2010; Martins et al., 2013, inter alia ), but has been adapted to semantic parsing (Flanigan et al., 2014; Martins and Almeida, 2014; Thomson et al., 2014; Kuhlmann, 2014, inter alia ).”
A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing (2008, methodology): “Following MSTParser (McDonald et al., 2005; McDonald and Pereira, 2006), we define the graphVariables: agenda – the beam for state items item – partial parse tree output – a set of output items index, prev – word indexes Input: x – POS-tagged input sentence.”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, background): “Graphbased parsers (McDonald et al., 2005; Koo and Collins, 2010; Lei et al., 2014) perform global inference and although they are more accurate in some cases, inference tends to be slower.”
A Joint Model for Answer Sentence Ranking and Answer Extraction (2016, methodology): “They use the MXPOST tagger (Ratnaparkhi, 1996) for POS tagging, the MSTParser (McDonald et al., 2005) to generate typed dependency trees, and the BBN Iden-tiﬁnder (Bikel et al., 1999) for NER tagging.”
Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks (2008, methodology): “In the experiments below we use a feature set f(x,h,m) similar to that in McDonald et al. (2005) and Koo et al. (2007), resulting in 2,500,554 features.”