Max-Margin Parsing
Empirical Methods in Natural Language ProcessingPublished 1 July 2004
Ben Taskar, Dan Klein, Michael J. Collins, Daphne Koller, Christopher D. Manning
Citations198
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
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.
Abstract
We present a novel discriminative approach to parsing inspired by the large-margin criterion underlying support vector machines. Our formulation uses a factorization analogous to the standard dynamic programs for parsing. In particular, it allows one to efficiently learn a model which discriminates among the entire space of parse trees, as opposed to reranking the top few candidates. Our models can condition on arbitrary features of input sentences, thus incorporating an important kind of lexical information without the added algorithmic complexity of modeling headedness. We provide an efficient algorithm for learning such models and show experimental evidence of the model’s improved performance over a natural baseline model and a lexicalized probabilistic context-free grammar.
Keywords
Computer Science
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
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.
Feature-rich part-of-speech tagging with a cyclic dependency network
2,851 Citations2003Kristina Toutanova, Dan Klein +2 more
A new part-of-speech tagger is presented that demonstrates the following ideas: explicit use of both preceding and following tag contexts via a dependency network representation, broad use of lexical features, and effective use of priors in conditional loglinear models.
Computational LinguisticsHead-Driven Statistical Models for Natural Language Parsing
1,860 Citations2003Michael Collins
Three statistical models for natural language parsing are described, leading to approaches in which a parse tree is represented as the sequence of decisions corresponding to a head-centered, top-down derivation of the tree.
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.
Hidden Markov support vector machines
469 Citations2003Yasemin Altün, Ioannis Tsochantaridis +1 more
This paper presents a novel discriminative learning technique for label sequences based on a combination of the two most successful learning algorithms, Support Vector Machines and Hidden Markov Models which it is called HM-SVMs and handles dependencies between neighboring labels using Viterbi decoding.
Discriminative Reranking for Natural Language Parsing
443 Citations2000Michael J. Collins
Parsing the WSJ using CCG and log-linear models
279 Citations2004Stephen Clark, James Curran
A parallel implementation of the L-BFGS optimisation algorithm is described, which runs on a Beowulf cluster allowing the complete Penn Treebank to be used for estimation and a new efficient parsing algorithm for CCG which maximises expected recall of dependencies is developed.
Estimators for stochastic "Unification-Based" grammars
168 Citations1999Mark Johnson, Stuart Geman +3 more
Two computationally-tractable ways of estimating the parameters of Stochastic "Unification-Based" Grammars from a training corpus of syntactic analyses are described and applied to estimate a stochastic version of Lexical-Functional Grammar.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Speed and Accuracy in Shallow and Deep Stochastic Parsing
108 Citations2004Ronald M. Kaplan, Stefan Riezler +4 more
This paper reports some experiments that Compare the accuracy and performance of two stochastic parsing systems and found the deep-parsing system to be more accurate than the Collins parser with only a slight reduction in parsing speed.
Maximum entropy estimation for feature forests
100 Citations2002Yusuke Miyao, Tsujii Jun'ichi
An algorithm is proposed for maximum entropy modeling that enables probabilistic modeling of complete structures, such as transition sequences in Markov models and parse trees, without dividing them into independent sub-events.
Text, speech and language technologyParameter Estimation for Statistical Parsing Models: Theory and Practice of Distribution-Free Methods
95 Citations2004Michael Collins
This chapter discusses the statistical theory underlying various parameter-estimation methods, and gives algorithms which depend on alternatives to maximum-likelihood estimation, and describes parameter estimation algorithms which are motivated by these generalization bounds.
Dynamic programming for parsing and estimation of stochastic unification-based grammars
54 Citations2001Stuart Geman, Mark Johnson
A graph-based dynamic programming algorithm for calculating statistics from the packed UBG parse representations of Maxwell and Kaplan (1995) which does not require enumerating all parses.
Using LTAG based features in parse reranking
53 Citations2003Libin Shen, Anoop Sarkar +1 more
This paper extends the notion of a tree kernel over arbitrary sub-trees of the parse to the derivation trees and derived trees provided by the LTAG formalism, and in addition, it extends the original definition of the tree kernel, making it more lexicalized and more compact.
Joint and conditional estimation of tagging and parsing models
51 Citations2001Mark Johnson
This paper compares two different ways of estimating statistical language models by maximizing the joint likelihood of the fully-observed training data and finds that some of the latter models intuitively had access to "more information" than the former.
Text, speech and language technologyNew Developments in Parsing Technology
36 Citations2005Bunt, Harry C. 1944-
This book discusses Parsing Technology from Theory to Application, and proposes a Context-Free Superset Approximation of Unification-Based Grammars B.C. Kiefer and a Probabilistic Parser for SSNs.