A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing
Published 1 January 2014Open access
Vanessa Wei Feng, Graeme Hirst
Citations152
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 much faster model whose time complexity is linear in the number of sentences, with two linear-chain CRFs applied in cascade as local classifiers and a novel approach of post-editing, which modifies a fully-built tree by considering information from constituents on upper levels, can improve the accuracy.
Abstract
Text-level discourse parsing remains a challenge. The current state-of-the-art overall accuracy in relation assignment is 55.73%, achieved by However, their model has a high order of time complexity, and thus cannot be applied in practice. In this work, we develop a much faster model whose time complexity is linear in the number of sentences. Our model adopts a greedy bottom-up approach, with two linear-chain CRFs applied in cascade as local classifiers. To enhance the accuracy of the pipeline, we add additional constraints in the Viterbi decoding of the first CRF. In addition to efficiency, our parser also significantly outperforms the state of the art. Moreover, our novel approach of post-editing, which modifies a fully-built tree by considering information from constituents on upper levels, can further improve the accuracy.
Keywords
Computer Science
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.
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.
Dynamic conditional random fields
746 Citations2004Charles Sutton, Khashayar Rohanimanesh +1 more
Computational LinguisticsModeling Local Coherence: An Entity-Based Approach
687 Citations2008Regina Barzilay, Mirella Lapata
This article re-conceptualize coherence assessment as a learning task and shows that the proposed entity-grid representation of discourse is well-suited for ranking-based generation and text classification tasks.
The MIT Press eBooksThe Theory and Practice of Discourse Parsing and Summarization
629 Citations2000Daniel Marcu
This book documents the first serious attempt to construct automatically and use nonsemantic computational structures for text summarization and develops a semantics-free theoretical framework that is both general enough to be applicable to naturally occurring texts and concise enough to facilitate an algorithmic approach to discourse analysis.
Building a discourse-tagged corpus in the framework of Rhetorical Structure Theory
600 Citations2001Lynn Carlson, Daniel Marcu +1 more
Working in the framework of Rhetorical Structure Theory, a large annotated resource with very high consistency is created, using a well-defined methodology and protocol to enable researchers to develop empirically grounded, discourse-specific applications.
Text, speech and language technologyBuilding a Discourse-Tagged Corpus in the Framework of Rhetorical Structure Theory
294 Citations2003Lynn Carlson, Daniel Marcu +1 more
Edinburgh Research Explorer (University of Edinburgh)Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data
292 Citations2007Charles Sutton, Andrew McCallum +1 more
On a natural-language chunking task, it is shown that a DCRF performs better than a series of linear-chain CRFs, achieving comparable performance using only half the training data.
Discourse ProcessesUsing linguistic phenomena to motivate a set of coherence relations
270 Citations1994Alistair Knott, Robert Dale
Dialogue & DiscourseHILDA: A Discourse Parser Using Support Vector Machine Classification
212 Citations2010Hugo Hernault, Helmut Prendinger +2 more
This article presents HILDA, an implemented discourse parser based on RST and Support Vector Machine (SVM) classification that outperforms other discourse parsers for tree structure construction and discourse relation labeling.
Text-level Discourse Parsing with Rich Linguistic Features
150 Citations2012Vanessa Wei Feng, Graeme Hirst
An RST-style text-level discourseparser, based on the HILDA discourse parser, is developed, which significantly improves its tree-building step by incorporating its own rich linguistic features.
Combining Intra- and Multi-sentential Rhetorical Parsing for Document-level Discourse Analysis
138 Citations2013Shafiq Joty, Giuseppe Carenini +2 more
A novel approach for developing a two-stage document-level discourse parser by applying an optimal parsing algorithm to probabilities inferred from two Conditional Random Fields, which significantly outperforms the state of the art.
CORE Scholar (Wright State University)Generalized Expectation Criteria for Semi-Supervised Learning of Conditional Random Fields
130 Citations2008Gideon Mann, Andrew McCallum
This paper presents a semi-supervised training method for linear-chain conditional random fields that makes use of labeled features rather than labeled instances by using generalized expectation criteria to express a preference for parameter settings in which the model’s distribution on unlabeled data matches a target distribution.
The Life and Death of Discourse Entities: Identifying Singleton Mentions
122 Citations2013Marta Vilar Recasens, Marie-Catherine de Marneffe +1 more
A logistic regression model is built for predicting the singleton/coreferent distinction, drawing on linguistic insights about how discourse entity lifespans are affected by syntactic and semantic features.
An effective discourse parser that uses rich linguistic information
116 Citations2009Rajen Subba, Barbara Di Eugenio
The modified shift-reduce parsing model that uses the authors' relation classifier significantly outperforms a right-branching majority-class baseline and a statistically significant improvement in classifying relations over attribute-value learning paradigms such as Decision Trees, RIPPER and Naive Bayes.
Lecture notes in computer scienceA Dynamic Conditional Random Field Model for Joint Labeling of Object and Scene Classes
108 Citations2008Christian Wojek, Bernt Schiele
A novel approach based on conditional random field models that is applicable to highly dynamic scenes including both fast camera and object movements and systematically integrating dynamic information for the object detection task as well as for the scene labeling task is proposed.
A Novel Discriminative Framework for Sentence-Level Discourse Analysis
76 Citations2012Shafiq Joty, Giuseppe Carenini +1 more
This work proposes a complete probabilistic discriminative framework for performing sentence-level discourse analysis that outperforms the state-of-the-art, often by a wide margin.
HAL (Le Centre pour la Communication Scientifique Directe)Constrained decoding for text-level discourse parsing
64 Citations2012Philippe Müller, Stergos Afantenos +2 more
This paper presents a novel approach to document-based discourse analysis by performing a global A* search over the space of possible structures while optimizing a global criterion over the set of potential coherence relations.
Probabilistic Head-Driven Parsing for Discourse Structure
48 Citations2005Jason Baldridge, Alex Lascarides
Probabilistic head-driven parsing for discourse structure
34 Citations2005Jason Baldridge, Alex Lascarides
A data-driven approach to building interpretable discourse structures for appointment scheduling dialogues that represents discourse structures as headed trees and model them with probabilistic head-driven parsing techniques, significantly beating a right-branching baseline that uses the most frequent relations.
Combining a two-step conditional random field model and a joint source channel model for machine transliteration
14 Citations2009Dong Yang, Paul R. Dixon +4 more
A new two-step conditional random field (CRF) model for DOP machine transliteration, in which the first CRF segments a source word into chunks and the second CRF maps the chunks to a word in the target language.