A Novel Discourse Parser Based on Support Vector Machine Classification

David duVerle, Helmut PrendingerACL 2009

TL;DR

This paper introduces a novel algorithm for automatically parsing the rhetorical structure of text using Support Vector Machines (SVMs). By leveraging a rich set of features and an efficient SVM-based classification approach, the parser achieves state-of-the-art accuracy in identifying hierarchical coherence relations within text, outperforming previous methods.

What Problem Does This Paper Address?

Understanding the underlying structure of text, beyond just its grammatical syntax, is crucial for many natural language processing tasks like text summarization, generation, and question answering. Rhetorical Structure Theory (RST) provides a formal framework for analyzing this hierarchical coherence, representing text as a tree of "rhetorical relations" between elementary discourse units (edus). However, automatically parsing this structure has been a significant challenge. Previous attempts often struggled with computational complexity, accuracy, or were limited to specific text types. This paper aims to bridge this gap by developing an efficient and accurate RST parser that can handle general text.

Methods

The core of the proposed system is a two-step process:

  1. Segmentation: The input text is first broken down into elementary discourse units (edus). While the paper focuses on the parsing step, it acknowledges the importance of segmentation and uses an existing tool (SPADE) for this purpose.
  2. Rhetorical Structure Tree Generation: This is the main contribution. The system uses Support Vector Machines (SVMs) for classification. Specifically, it employs two SVM classifiers:
  3. Binary Classifier (S): Determines if a structural relation exists between two adjacent text spans (edus or sub-trees).
  4. Multi-class Classifier (L): Labels the type of rhetorical relation and its nuclearity (the more important part of the relation).

The system utilizes a rich set of features extracted from the text, including:

  • Textual Organization Features: Information about sentence and paragraph boundaries, span lengths, and positions within sentences.
  • Lexical Clues and Punctuation: N-gram dictionaries derived from the training corpus to capture discourse markers and other linguistic signals.
  • Simple Syntactic Clues: Part-of-speech tags for prefixes and suffixes of spans.
  • Dominance Sets: Features derived from the syntactic parse tree to infer hierarchical relationships between edus.
  • Strong Compositionality Criterion: Features based on a representative edu (main constituent) of each span.
  • Rhetorical Sub-structure: Features encoding the rhetorical subtree of each span.

The tree-building process is a naive bottom-up approach, recursively merging adjacent sub-trees based on the SVM classifier outputs. A key aspect is the use of a reduced set of 18 rhetorical relations and the conversion of n-ary relations into nested binary ones for algorithmic manageability.

Datasets

  • RST Discourse Treebank (RST-DT): This is the primary dataset used for both training and evaluation. The paper mentions using the official test subset and doubly-annotated subsets for comparison.
  • Penn Treebank: Used for obtaining syntactic parse trees.
  • SPADE segmenter output: Used to evaluate the system's performance with imperfect segmentation.

Key Insights and Ideas

  • SVMs for Discourse Parsing: The paper demonstrates the effectiveness of SVMs, particularly their ability to handle high-dimensional feature spaces and their resilience to noisy input, for the complex task of discourse parsing.
  • Rich Feature Engineering: The success of the parser is heavily attributed to the comprehensive set of features, combining shallow lexical, syntactic, and structural information. This multi-faceted approach captures various aspects of text coherence.
  • Efficiency through SVMs and Bottom-up Parsing: By using linear-time SVMs and a bottom-up tree construction algorithm, the system achieves excellent time complexity (O(n)), making it suitable for real-time applications.
  • Dominance Sets for Structural Ambiguity: The use of dominance sets derived from syntactic parse trees is a clever way to resolve structural ambiguities in discourse parsing, guiding the selection of the correct rhetorical relation.
  • Robustness to Segmentation Errors: The system shows a notable degree of robustness to imperfect segmentation, a significant practical advantage over methods that are highly sensitive to segmentation quality.

Key Results

  • The parser achieves 73.9% of professional annotators' human agreement F-score on the full labeling task.
  • It is 5% to 12% more accurate than current state-of-the-art parsers.
  • The system demonstrates linear time-complexity for parsing.
  • When using perfectly segmented input, the system achieves F-scores of 70.9% for structure, 58.3% for nuclearity, and 45.8% for relations on the standard test subset.
  • The system's performance decreases by only 12.3% and 12.9% when switching from manual to automatic segmentation, compared to much larger drops for other systems.

Limitations and Future Work

  • Segmentation Dependency: While robust, the system's performance is still affected by the quality of the input segmentation. The authors suggest that improved segmenting algorithms could further enhance results.
  • Tree-building Algorithm: The authors acknowledge that the naive bottom-up tree-building algorithm could be improved. Future work could explore better tree-building strategies, potentially using global optimization meta-algorithms like simulated annealing to explore the solution space more effectively.
  • Reduced Relation Set: The use of a reduced set of 18 rhetorical relations simplifies the problem but might not capture the full nuance of the original 75 relations.

The paper concludes by highlighting the potential for real-time applications and the availability of an online discourse parser.

Summary updated

BibTeX
@inproceedings{duverle2009novel,
  author = {David duVerle and Helmut Prendinger},
  title = {{A Novel Discourse Parser Based on Support Vector Machine Classification}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2009},
}
Figure