Adapting Unsupervised Syntactic Parsing Methodology for Discourse Dependency Parsing

Liwen Zhang, Ge Wang, Wenjuan Han, Kewei Tu

Introduction

Discourse parsing—the task of identifying how Elementary Discourse Units (EDUs) relate to form a coherent document structure—is essential for downstream applications like summarization and sentiment analysis. However, it faces a significant "data bottleneck" because labeling discourse data requires specialized linguistic expertise, leading to small and scarce annotated datasets.

In contrast, syntactic parsing (sentence-level structure) has a rich history of unsupervised methods that learn from raw text. This research explores whether these robust syntactic parsing techniques can be adapted for discourse. To do so, the authors address two primary hurdles: the "infinite vocabulary" of unique EDUs and the hierarchical structural constraints inherent in discourse, where dependencies typically form self-contained subtrees within sentences or paragraphs.

Methodology

The proposed framework adapts unsupervised syntactic models through two key innovations:

EDU Clustering

Unlike syntax, which uses a finite set of words or Part-of-Speech (POS) tags, discourse units are unique clauses. To bridge this gap, the authors use BERT to generate embeddings for each EDU and apply K-Means clustering to group them into a fixed number of categories (e.g., 50 clusters). These clusters serve as "pseudo-POS tags," allowing models designed for syntax to process discourse units.

Hierarchical Eisner Algorithm

The classic Eisner algorithm finds optimal dependency trees in $O(n^3)$ time. The authors modified this into a Hierarchical Eisner algorithm that enforces a "subtree constraint." This requires that sentences and paragraphs form complete subtrees before they are linked at the document level, effectively pruning the search space by excluding cross-boundary dependencies that violate discourse hierarchy.

The hierarchical constraint ensures that dependencies respect sentence and paragraph boundaries (top), preventing illegal cross-boundary links (bottom).

This framework was applied to two state-of-the-art syntactic models: NCRFAE (a discriminative Neural CRF Autoencoder) and V-DNDMV (a generative Variational Discriminative Neural Dependency Model).

Key Results and Insights

Performance Benchmarks

The models were evaluated on the RST Discourse Treebank (RST-DT) and SciDTB. In unsupervised settings, both adapted models outperformed standard baselines. Under full supervision, the adapted NCRFAE achieved a 70.2 UAS (Unlabeled Attachment Score) on RST-DT and 79.1 UAS on SciDTB, significantly outperforming previous state-of-the-art discourse-specific models like MOREY18 (66.4 UAS).

Computational Efficiency

Counter-intuitively, adding hierarchical constraints made the parser faster. By restricting the search space to valid subtrees, the empirical complexity was reduced from $O(n^3)$ to nearly $O(n^2)$. As shown in the performance data, the Hierarchical Eisner algorithm maintains a significantly lower memory footprint as document length increases compared to the traditional version.

The Hierarchical Eisner algorithm demonstrates near-quadratic memory growth, making it far more efficient for long documents than the cubic growth of the standard Eisner algorithm.

Conclusion and Future Work

This research demonstrates that models built for sentence-level syntax are surprisingly robust and can outperform specialized discourse models when provided with the right structural priors. While the framework excels at structural prediction, future work is needed to improve the prediction of specific relationship types (e.g., Contrast vs. Elaboration) in unsupervised settings. Additionally, exploring dynamic clustering methods could further refine how the model represents the infinite variety of discourse units.

Summary updated

BibTeX
@inproceedings{zhang2021adapting,
  author = {Liwen Zhang and Ge Wang and Wenjuan Han and Kewei Tu},
  title = {{Adapting Unsupervised Syntactic Parsing Methodology for Discourse Dependency Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  doi = {10.18653/v1/2021.acl-long.449},
}
Figure