Evaluation of Dependency Parsers on Unbounded Dependencies
Published 23 August 2010
Joakim Nivre, Laura Rimell, Ryan McDonald, Carlos Gómez‐Rodríguez
Citations57
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The evaluation of two dependency parsers shows that when combined with simple post-processing heuristics, the parsers correctly recall unbounded dependencies roughly 50% of the time, which is only slightly worse than two grammar-based parsers specifically designed to cope with such dependencies.
Abstract
We evaluate two dependency parsers, MSTParser and MaltParser, with respect to their capacity to recover unbounded de-pendencies in English, a type of evalu-ation that has been applied to grammar-based parsers and statistical phrase struc-ture parsers but not to dependency parsers. The evaluation shows that when combined with simple post-processing heuristics, the parsers correctly recall unbounded dependencies roughly 50 % of the time, which is only slightly worse than two grammar-based parsers specifically de-signed to cope with such dependencies. 1
Keywords
Computer Science
Accurate unlexicalized parsing
3,055 Citations2003Dan Klein, Christopher D. Manning
It is demonstrated that an unlexicalized PCFG can parse much more accurately than previously shown, by making use of simple, linguistically motivated state splits, which break down false independence assumptions latent in a vanilla treebank grammar.
Generating Typed Dependency Parses from Phrase Structure Parses
2,304 Citations2006Marie-Catherine de Marneffe, Bill MacCartney +1 more
A system for extracting typed dependency parses of English sentences from phrase structure parses that captures inherent relations occurring in corpus texts that can be critical in real-world applications is described.
CoNLL-X shared task on multilingual dependency parsing
976 Citations2006Sabine Buchholz, Erwin Marsi
How treebanks for 13 languages were converted into the same dependency format and how parsing performance was measured is described and general conclusions about multi-lingual parsing are drawn.
Coarse-to-fine <i>n</i>-best parsing and MaxEnt discriminative reranking
888 Citations2005Eugene Charniak, Mark Johnson
This paper describes a simple yet novel method for constructing sets of 50- best parses based on a coarse-to-fine generative parser that generates 50-best lists that are of substantially higher quality than previously obtainable.
Online large-margin training of dependency parsers
816 Citations2005Ryan McDonald, Koby Crammer +1 more
An effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training on top of efficient parsing techniques for dependency trees is presented.
Natural Language EngineeringMaltParser: A language-independent system for data-driven dependency parsing
805 Citations2007Joakim Nivre, Johan Hall +6 more
Experimental evaluation confirms that MaltParser can achieve robust, efficient and accurate parsing for a wide range of languages without language-specific enhancements and with rather limited amounts of training data.
Online Learning of Approximate Dependency Parsing Algorithms.
479 Citations2006Ryan McDonald, Fernando C. N. Pereira
This paper extends the maximum spanning tree dependency parsing framework to incorporate higher-order feature representations and allow dependency structures with multiple parents per word, and shows that those extensions can make the MST framework computationally intractable, but that the intractability can be circumvented with new approximate parsing algorithms.
MaltParser: A Data-Driven Parser-Generator for Dependency Parsing
466 Citations2006Joakim Nivre, Johan Hall +1 more
MaltParser supports several parsing algorithms and learning algorithms, and allows user-defined feature models, consisting of arbitrary combinations of lexical features, part-of-speech features and dependency features, for dependency parsing.
Procedure for quantitatively comparing the syntactic coverage of English grammars
436 Citations1991Judith L. Klavans, Mark Liberman +12 more
Computational LinguisticsWide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models
409 Citations2007Stephen Clark, James Curran
This article describes a number of log-linear parsing models for an automatically extracted lexicalized grammar and develops a new model and efficient parsing algorithm which exploits all derivations, including CCG's nonstandard derivations.
Dependency Parsing
367 Citations2009Sandra Kübler, Ryan McDonald +2 more
The second release of the RASP system
356 Citations2006Ted Briscoe, John M. Carroll +1 more
The new release of the RASP (robust accurate statistical parsing) system, designed for syntactic annotation of free text, is described, including a revised and more semantically-motivated output representation, an enhanced grammar and part-of-speech tagger lexicon, and a more flexible and semi-supervised training method for the structural parse ranking model.
SVMTool: A general POS Tagger Generator Based on Support Vector Machines
336 Citations2004Jesús Giménez, Lluı́s Màrquez
Characterizing the Errors of Data-Driven Dependency Parsing Models
271 Citations2007Ryan McDonald, Joakim Nivre
A comparative error analysis of the two dominant approaches in datadriven dependency parsing: global, exhaustive, graph-based models, and local, greedy, transition- based models shows that, in spite of similar performance, the two models produce different types of errors.
Forest Reranking: Discriminative Parsing with Non-Local Features
260 Citations2008Liang Huang
This work presents an approximate algorithm inspired by forest rescoring that makes discriminative training practical over the whole Treebank, and outperforms both 50-best and 100-best reranking baselines and is better than any previously reported systems trained on the Treebank.
Non-projective dependency parsing in expected linear time
233 Citations2009Joakim Nivre
A novel transition system for dependency parsing, which constructs arcs only between adjacent words but can parse arbitrary non-projective trees by swapping the order of words in the input, shows state-of-the-art accuracy.
Multilingual dependency analysis with a two-stage discriminative parser
220 Citations2006Ryan McDonald, Kevin Lerman +1 more
A two-stage multilingual dependency parser based on the unlabeled dependency parsing models described by McDonald and Pereira (2006) augmented with morphological features for a subset of the languages is presented.
Labeled pseudo-projective dependency parsing with support vector machines
191 Citations2006Joakim Nivre, Johan Hall +3 more
This work uses SVM classifiers to predict the next action of a deterministic parser that builds labeled projective dependency graphs in an incremental fashion and presents evaluation results and an error analysis focusing on Swedish and Turkish.
Parser combination by reparsing
181 Citations2006Kenji Sagae, Alon Lavie
A novel parser combination scheme that works by reparsing input sentences once they have already been parsed by several different parsers is presented, generating results that surpass state-of-the-art accuracy levels for individual parsers.
Discriminative learning and spanning tree algorithms for dependency parsing
142 Citations2006Fernando Pereira, Ryan McDonald
This thesis develops a discriminative learning method for dependency parsing using online large-margin training combined with spanning tree inference algorithms and shows that this method provides state-of-the-art accuracy, is extensible through the feature set and can be implemented efficiently.
Text, speech and language technologySingle Malt or Blended? A Study in Multilingual Parser Optimization
117 Citations2010Johan Hall, Jens Nilsson +1 more
A two-stage optimization of the MaltParser system for the ten languages in the multilingual track of the CoNLL 2007 shared task on dependency parsing results in an ensemble system that combines six different parsing strategies, extrapolating from the optimal parameter settings for each language.
On the complexity of non-projective data-driven dependency parsing
116 Citations2007Ryan McDonald, Giorgio Satta
This paper investigates several non-projective parsing algorithms for dependency parsing, providing novel polynomial time solutions under the assumption that each dependency decision is independent of all the others, called here the edge-factored model.
TAG, dynamic programming, and the perceptron for efficient, feature-rich parsing
114 Citations2008Xavier Carreras, Michael J. Collins +1 more
A parsing approach that makes use of the perceptron algorithm, in conjunction with dynamic programming methods, to recover full constituent-based parse trees, using a Tree Adjoining Grammar (TAG) based parsing formalism.
Long-distance dependency resolution in automatically acquired wide-coverage PCFG-based LFG approximations
112 Citations2004Aoife Cahill, Michael Burke +3 more
This paper shows how finite approximations of long distance dependency (LDD) resolution can be obtained automatically for wide-coverage, robust, probabilistic Lexical-Functional Grammar (LFG) resources acquired from treebanks.
Probabilistic disambiguation models for wide-coverage HPSG parsing
107 Citations2005Yusuke Miyao, Jun’ichi Tsujii
The development of log-linear models for the disambiguation in wide-coverage HPSG parsing using techniques to reduce the estimation cost and a series of experiments empirically evaluated the estimation techniques, and also examined the performance of the dis Ambiguation models on the parsing of real-world sentences.
Unbounded Dependency Recovery for Parser Evaluation
86 Citations2009Laura Rimell, Stephen Clark +1 more
QuestionBank
77 Citations2006John Judge, Aoife Cahill +1 more
Using QuestionBank training data improves parser performance to 89.75% labelled bracketing f-score, and a new method for recovering empty nodes and their antecedents (capturing long distance dependencies) from parser output in CFG trees using LFG f-structure reentrancies is introduced.
Discriminative classifiers for deterministic dependency parsing
45 Citations2006Johan Hall, Joakim Nivre +1 more
A systematic comparison of memory-based learning and support vector machines for inducing classifiers for deterministic dependency parsing, using data from Chinese, English and Swedish, together with a variety of different feature models shows that SVM gives higher accuracy for richly articulated feature models across all languages, albeit with considerably longer training times.