Online Learning of Approximate Dependency Parsing Algorithms.
Published 1 April 2006
Ryan McDonald, Fernando C. N. Pereira
Citations479
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
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.
Abstract
In this paper we extend the maximum spanning tree (MST) dependency parsing framework of McDonald et al. (2005c) to incorporate higher-order feature representations and allow dependency structures with multiple parents per word. We show that those extensions can make the MST framework computationally intractable, but that the intractability can be circumvented with new approximate parsing algorithms. We conclude with experiments showing that discriminative online learning using those approximate algorithms achieves the best reported parsing accuracy for Czech and Danish. 1
Keywords
Computer Science
Machine LearningLearning Bayesian networks: The combination of knowledge and statistical data
2,043 Citations1995David Heckerman, Dan Geiger +1 more
It is shown that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—aprior network—and a single measure of confidence for that network.
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.
A maximum-entropy-inspired parser
1,496 Citations2000Eugene Charniak
A new parser for parsing down to Penn tree-bank style parse trees that achieves 90.1% average precision/recall for sentences of length 40 and less and 89.5% when trained and tested on the previously established sections of the Wall Street Journal treebank is presented.
Maximum Entropy Model for Part-Of-Speech Tagging
1,276 Citations1996Adwait Ratnaparkhi
A statistical model which trains from a corpus annotated with Part Of Speech tags and assigns them to previously unseen text with state of the art accuracy and discusses the corpus consistency problems discovered during the implementation of these features.
Non-projective dependency parsing using spanning tree algorithms
857 Citations2005Ryan McDonald, Fernando Pereira +2 more
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.
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.
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.
Text, speech and language technologyThe Prague Dependency Treebank
406 Citations2003Alena Böhmová, Jan Hajič +2 more
Inspired by the Penn Treebank, the most widely used syntactically annotated corpus of English, this work decided to develop a similarly sized corpus of Czech with a rich annotation scheme.
Incremental parsing with the perceptron algorithm
384 Citations2004Michael Collins, Brian Roark
It is demonstrated 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.
Applied Physics Letters10.1162/jmlr.2003.3.4-5.951
323 Citations2000
This paper 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.
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.
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.
A discriminative framework for bilingual word alignment
139 Citations2005Robert C. Moore
This paper demonstrates a discriminative approach to training simple word alignment models that are comparable in accuracy to the more complex generative models normally used.
Flexible text segmentation with structured multilabel classification
94 Citations2005Ryan McDonald, Koby Crammer +1 more
A new model of text segmentation based on ideas from multilabel classification is presented, which can naturally represent segmentation problems involving overlapping and non-contiguous segments and is evaluated on entity extraction and noun-phrase chunking.
Corrective modeling for non-projective dependency parsing
45 Citations2005Keith Hall, Václav Novák
A corrective model for recovering non-projective dependency structures from trees generated by state-of-the-art constituency-based parsers improves overall dependency accuracy by .7% (a 4.5% reduction in error) with over 50% accuracy for non- projective structures.