Non-projective dependency parsing using spanning tree algorithms
Published 1 January 2005Open access
Ryan McDonald, Fernando Pereira, Kiril Ribarov, Jan Hajič
Citations857
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
Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n3) time and is extended naturally to non-projective parsing using Chu-Liu-Edmonds (Chu and Liu, 1965; Edmonds, 1967) MST algorithm, yielding an O( n2) parsing algorithm.
Abstract
We formalize weighted dependency parsing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n3) time. More surprisingly, the representation is extended naturally to non-projective parsing using Chu-Liu-Edmonds (Chu and Liu, 1965; Edmonds, 1967) MST algorithm, yielding an O(n2) parsing algorithm. We evaluate these methods on the Prague Dependency Treebank using online large-margin learning techniques (Crammer et al., 2003; McDonald et al., 2005) and show that MST parsing increases efficiency and accuracy for languages with non-projective dependencies.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Building a Large Annotated Corpus of English: The Penn Treebank
7,528 Citations1993Mitchell P. Marcus
Discriminative training methods for hidden Markov models
1,889 Citations2002Michael Collins
Experimental results on part-of-speech tagging and base noun phrase chunking are given, in both cases showing improvements over results for a maximum-entropy tagger.
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
Dependency tree kernels for relation extraction
825 Citations2004Aron Culotta, Jeffrey Sorensen
This work extends previous work on tree kernels to estimate the similarity between the dependency trees of sentences, and uses this kernel within a Support Vector Machine to detect and classify relations between entities in the Automatic Content Extraction (ACE) corpus of news articles.
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.
Neural Information Processing SystemsLearning Syntactic Patterns for Automatic Hypernym Discovery
676 Citations2004Rion Snow, Daniel Jurafsky +1 more
This paper presents a new algorithm for automatically learning hypernym (is-a) relations from text, using "dependency path" features extracted from parse trees and introduces a general-purpose formalization and generalization of these patterns.
Three new probabilistic models for dependency parsing
630 Citations1996Jason Eisner
Preliminary empirical results from evaluating the three models' parsing performance on annotated Wall Street Journal training text (derived from the Penn Treebank) suggest the generative model performs significantly better than the others, and does about equally well at assigning part-of-speech tags.
Statistical Dependency Analysis with Support Vector Machines
605 Citations2003Hiroyasu Yamada, Yūji Matsumoto
Though the result is little worse than the most up-to-date phrase structure based parsers, it looks satisfactorily accurate considering that the parser uses no information from phrase structures.
NetworksFinding optimum branchings
371 Citations1977Robert E. Tarjan
An implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges is given, and a modification for dense graphs gives a running time of 0(n2).
Pseudo-projective dependency parsing
291 Citations2005Joakim Nivre, Jens Nilsson
Experiments show that the combined system can handle non-projective constructions with a precision sufficient to yield a significant improvement in overall parsing accuracy, leading to the best reported performance for robust non- projective parsing of Czech.
Deterministic dependency parsing of English text
222 Citations2004Joakim Nivre, Mario Scholz
This paper presents a deterministic dependency parser based on memory-based learning, which parses English text in linear time, and produces labeled dependency graphs, using as arc labels a combination of bracket labels and grammatical role labels taken from the Penn Treebank II annotation scheme.
Lecture notes in computer scienceUltraconservative Online Algorithms for Multiclass Problems
221 Citations2001Koby Crammer, Yoram Singer
This paper designs and analyzes online classification algorithms for multiclass problems in the mistake bound model and describes a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores.
Machine translation using probabilistic synchronous dependency insertion grammars
200 Citations2005Yuan Chun Ding, Martha Palmer
This paper presents a syntax-based statistical machine translation system based on a probabilistic synchronous dependency insertion grammar and describes the graphical model for the machine translation task, which can also be viewed as a stochastic tree-to-tree transducer.
Empirical Methods in Natural Language ProcessingMax-Margin Parsing
198 Citations2004Ben Taskar, Dan Klein +3 more
A novel discriminative approach to parsing inspired by the large-margin criterion underlying support vector machines is presented, which allows one to efficiently learn a model which discriminates among the entire space of parse trees, as opposed to reranking the top few candidates.
A statistical parser for Czech
197 Citations1999Michael Collins, Lance Ramshaw +2 more
This paper considers statistical parsing of Czech, which differs radically from English in at least two respects: (1) it is a highly inflected language, and (2) it has relatively free word order.
Automatic paraphrase acquisition from news articles
178 Citations2002Yusuke Shinyama, Satoshi Sekine +1 more
This is the initial attempt at automatically extracting paraphrases from a corpus, and the results are promising.
arXiv (Cornell University)Three New Probabilistic Models for Dependency Parsing: An Exploration
165 Citations1997Jason Eisner
Neural Information Processing SystemsOnline Passive-Aggressive Algorithms
74 Citations2003Shai Shalev‐Shwartz, Koby Crammer +2 more
This work presents a unified view for online classification, regression, and uni-class problems, and proves worst case loss bounds for various algorithms for both the realizable case and the non-realizable case.
Learning and robust learning of product distributions
60 Citations1993Klaus-U. Höffgen
The main theorem shows that all classes in C’PCPk are robustly learnable, and develops a combinatorial algorithm for the efficient proper learnability of Markov expansions.
Theoretical Computer ScienceArborescence optimization problems solvable by Edmonds’ algorithm
42 Citations2003Leonidas Georgiadis
An algorithm is presented, which can be considered as a generalization of Edmonds' algorithm for the solution of the minimum sum arborescence problem, which includes as special cases the standard minimum sum Arborescence Problem, the bottleneck and lexicographically optimal arborescent problem, as well as the widest-minimum sum ar borescence problem.
A statistical constraint dependency grammar (CDG) parser
35 Citations2004Wen Wang, Mary P. Harper
This paper describes a statistical CDG (SCDG) parser that performs parsing incrementally and evaluates it on the Wall Street Journal Penn Treebank to achieve a parsing accuracy comparable to several state-of-the-art context-free grammar (CFG) based statistical parsers using a dependency-based evaluation metric.