Automatic Feature Selection for Agenda-Based Dependency Parsing
Research Portal (King's College London)Published 1 August 2014Open access
Miguel Ballesteros, Bernd Bohnet
Citations14
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
An in-depth study on automatic feature selection for beam-search dependency parsers with results that are on par with models trained with a larger set of feature templates, and this implies that the models provide faster training and parsing times.
Abstract
In this paper we present an in-depth study on automatic feature selection for beam-search dependency parsers. The search strategy is inherited from the one implemented in MaltOptimizer, but searches in a much larger set of feature templates that could lead to a higher number of combinations. Our models provide results that are on par with models trained with a larger set of feature templates, and this implies that our models provide faster training and parsing times. Moreover, the results establish the state of the art for some of the languages.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
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.
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.
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.
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.
RECERCAT (Consorci de Serveis Universitaris de Catalunya)Simple Semi-supervised Dependency Parsing
444 Citations2008Terry Koo, Xavier Carreras +1 more
This work focuses on the problem of lexical representation, introducing features that incorporate word clusters derived from a large unannotated corpus, and shows that the cluster-based features yield substantial gains in performance across a wide range of conditions.
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.
Transition-based Dependency Parsing with Rich Non-local Features
329 Citations2011Yue Zhang, Joakim Nivre
This paper shows that it can improve the accuracy of transition-based dependency parsers by considering even richer feature sets than those employed in previous systems by improving the accuracy in the standard Penn Treebank setup and rivaling the best results overall.
Experiments with a Higher-Order Projective Dependency Parser
238 Citations2007Xavier Carreras
In the multilingual exercise of the CoNLL-2007 shared task (Nivre et al., 2007), the system obtains the best accuracy for English, and the second best accuracies for Basque and Czech.
A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing
229 Citations2012Bernd Bohnet, Joakim Nivre
This work presents a transition-based system for joint part-of-speech tagging and labeled dependency parsing with non-projective trees that shows consistent improvements in both tagging and parsing accuracy when compared to a pipeline system.
Dynamic Programming for Linear-Time Incremental Parsing
213 Citations2010Liang Huang, Kenji Sagae
It is shown that, surprisingly, dynamic programming is in fact possible for many shift-reduce parsers, by merging "equivalent" stacks based on feature values, and the final parser outperforms all previously reported dependency parsers for English and Chinese, yet is much faster.
Efficient Third-Order Dependency Parsers
200 Citations2010Terry Koo, Michael Collins
Algorithms for higher-order dependency parsing that are "third-order", "efficient", and "efficient" in the sense that they require only O(n4) time are presented and can utilize both sibling-style and grandchild-style interactions.
A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing
195 Citations2008Yue Zhang, Stephen Clark
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.
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.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Turbo Parsers: Dependency Parsing by Approximate Variational Inference
116 Citations2018André F. T. Martins, Noah A. Smith +3 more
A unified view of two state-of-the-art non-projective dependency parsers, both approximate, is presented and a new aggressive online algorithm to learn the model parameters is proposed, which makes use of the underlying variational representation.
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.
Synthesis lectures on human language technologiesLinguistic Structure Prediction
101 Citations2011Noah A. Smith
Transactions of the Association for Computational LinguisticsJoint Morphological and Syntactic Analysis for Richly Inflected Languages
86 Citations2013Bernd Bohnet, Joakim Nivre +4 more
Evaluation on five morphologically rich languages shows consistent improvements in both morphological and syntactic accuracy for joint prediction over a pipeline model, with further improvements thanks to lexical constraints and word clusters.
An empirical study of semi-supervised structured conditional models for dependency parsing
78 Citations2009Jun Suzuki, Hideki Isozaki +2 more
The effectiveness of the proposed methods on dependency parsing experiments using two widely used test collections: the Penn Treebank for English, and the Prague Dependency Tree-bank for Czech are demonstrated.
Joint Models for Chinese POS Tagging and Dependency Parsing
73 Citations2011Zhenghua Li, Min Zhang +4 more
This paper designs several joint models and their corresponding decoding algorithms to incorporate different feature sets and presents an effective pruning strategy to reduce the search space of candidate POS tags, leading to significant improvement of parsing speed.
International Joint Conference on Natural Language ProcessingIncremental Joint POS Tagging and Dependency Parsing in Chinese
70 Citations2011Jun Hatori, Takuya Matsuzaki +2 more
The first incremental approach to the task of joint POS tagging and dependency parsing, which is built upon a shift-reduce parsing framework with dynamic programming is proposed, achieving the new state-of-the-art performance on this joint task.
Conference of the European Chapter of the Association for Computational LinguisticsThe Best of BothWorlds -- A Graph-based Completion Model for Transition-based Parsers
65 Citations2012Bernd Bohnet, Jonas Kuhn
It is argued at length that an arrow of complexity does indeed occur in evolution, which can be most reasonably interpreted as the result of a passive trend rather than a driven one, and that, with regard to the growth of complexity, evolution is very much a double-edged sword.
Development of a Dependency Treebank for Russian and its Possible Applications in NLP
47 Citations2002Igor Boguslavsky, Ivan Chardin +5 more
A tagging scheme designed for the Russian Treebank is described and tools used for corpus creation are presented, which gives a more fine-grained representation of syntactic phenomena.
Dependency treebank for Russian
44 Citations2000Igor Boguslavsky, Svetlana Grigorieva +3 more
The paper describes a tagging scheme designed for the Russian Treebank, and presents tools used for corpus creation.
Dynamic Feature Selection for Dependency Parsing
40 Citations2013He He, Hal Daumé +1 more
This work proposes a faster framework of dynamic feature selection, where features are added sequentially as needed, edges are pruned early, and decisions are made online for each sentence.
Improving Dependency Parsing with Semantic Classes
32 Citations2011Eneko Agirre, Kepa Bengoetxea +2 more
This paper presents the introduction of WordNet semantic classes in a dependency parser, obtaining improvements on the full Penn Treebank for the first time and thinks there is ample room for future improvements.
Single Malt or Blended? A Study in Multilingual Parser Optimization.
26 Citations2010Johan Hall, Jens Nilsson +1 more
Natural Language EngineeringMaltOptimizer: Fast and effective parser optimization
15 Citations2014Miguel Ballesteros, Joakim Nivre
MaltOptimizer is a tool developed to automatically explore parameters and features for MaltParser, a transition-based dependency parsing system that can be used to train parser's given treebank data.
Dependency Parsing of Hungarian: Baseline Results and Challenges
15 Citations2012Richárd Farkas, Veronika Vincze +1 more
Results on dependency parsing of Hungarian that employ a 80K, multi-domain, fully manually annotated corpus, the Szeged Dependency Treebank are introduced and show that the results achieved by state-of-the-art data-driven parsers on Hungarian and English are quite similar to each other in terms of attachment scores.
Effective Morphological Feature Selection with MaltOptimizer at the SPMRL 2013 Shared Task
12 Citations2013Miguel Ballesteros
This paper presents an extension of MaltOptimizer that explores, one by one and in combination, the features that are geared towards morphology, and extracts an in-depth study that shows which features are actually useful for transition-based parsing.
Automatic Discovery of Feature Sets for Dependency Parsing
10 Citations2010Peter Nilsson, Pierre Nugues
This paper describes a search procedure to discover optimal feature sets for dependency parsers using the shift-reduce algorithm and the feature sets are extracted from the parser configuration using a set of rules founded on the assumption that topological neighbors of significant features in the dependency graph may also have a significant contribution.
Publications (Konstfack University of Arts, Crafts, and Design)Transition-Based Natural Language Parsing with Dependency and Constituency Representations
6 Citations2008Johan Hall
Denna doktorsavhandling undersoker undersoker olika aspekter av automatisk syntaktisk analys av texter pa naturligt sprak yn ôl i denna avhandling.