Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training

Xinyu Wang, Kewei Tu

Abstract

In this paper, we propose second-order graph-based neural dependency parsing using message passing and end-to-end neural networks. We empirically show that our approaches match the accuracy of very recent state-of-the-art second-order graph-based neural dependency parsers and have significantly faster speed in both training and testing. We also empirically show the advantage of second-order parsing over first-order parsing and observe that the usefulness of the head-selection structured constraint vanishes when using BERT embedding.

Introduction

Dependency parsing is a fundamental task in natural language processing that involves mapping the grammatical structure of a sentence by identifying dependencies between words (modifiers and their heads). Modern parsers are typically graph-based. First-order parsers score individual edges independently, offering high speed but failing to capture complex structural dependencies. In contrast, higher-order parsers consider groups of edges, such as siblings or grandparent-child relationships, which improves accuracy but often introduces significant computational overhead and parallelization difficulties.

This work introduces a highly efficient second-order neural dependency parser that utilizes Mean Field Variational Inference (MFVI) to capture these complex relationships. By unfolding the inference process into an end-to-end neural network, the proposed model achieves state-of-the-art accuracy while maintaining high execution speeds, demonstrating that higher-order decoding remains valuable even when using powerful contextual embeddings like BERT.

Methodology

The proposed parser is derived from Message Passing Inference on a Conditional Random Field (CRF).

Scoring Mechanism

The model employs a "Biaffine" function to score single edges and a "Trilinear" function to score second-order structures:

  • Siblings: Two words modified by the same head.
  • Grandparents: A chain of three words (Head -> Modifier/Head -> Modifier).

Message Passing (MFVI)

To avoid the slow, exact algorithms typical of higher-order parsing, the authors use Mean Field Variational Inference. This allows the model to "pass messages" between potential edges to iteratively find the most likely structure. This process is "unfolded" into neural network layers, making it fully differentiable and highly parallelizable on GPUs.

Structural Approaches

Two variations were evaluated:

  • Single: Each edge is treated as an independent binary choice without structural constraints during training.
  • Local: Enforces a "head-selection" constraint, ensuring each word chooses exactly one head.

The entire system, from the BiLSTM or BERT encoder to the message-passing decoder, is trained end-to-end using cross-entropy loss.

Experimental Results

The model was evaluated on the English Penn Tree Bank (PTB 3.0), Chinese Penn Tree Bank (CTB 5.1), and Universal Dependencies (UD 2.2) across 12 languages.

Accuracy and the Impact of BERT

The model achieved state-of-the-art (SOTA) or near-SOTA results. Notably, on the CTB dataset, it established a new benchmark with a 90.81 Unlabeled Attachment Score (UAS). A key finding is that even with BERT, second-order decoding provides a consistent accuracy boost, suggesting that dedicated structural decoders are better at distilling the high-order information captured by contextual embeddings.

Performance comparison on PTB and CTB datasets, including BERT-enhanced models.

Efficiency and Speed

The standout result of this work is the efficiency gain. By leveraging MFVI and parallelization, the proposed approaches are significantly faster than previous GNN-based or second-order Tree CRF models during both training and testing phases.

Speed and complexity comparison between different parsing systems.

Discussion and Conclusion

The research highlights that parallelization is crucial for modern parsing. By bypassing sequential $O(n^3)$ algorithms in favor of parallelizable MFVI, the decoder achieves massive speedups.

An interesting observation is the "Constraint Vanishing" phenomenon: the "head-selection" constraint (Local approach), typically beneficial for first-order parsers, becomes less important or even slightly detrimental when using BERT. The simpler "Single" approach often performs just as well in these cases.

Future work may explore integrating global tree constraints while maintaining $O(n^3)$ complexity and investigating the specific interactions between contextual embeddings and structural constraints.

Summary updated

Abstract

In this paper, we propose second-order graph-based neural dependency parsing using message passing and end-to-end neural networks. We empirically show that our approaches match the accuracy of very recent state-of-the-art second-order graph-based neural dependency parsers and have significantly faster speed in both training and testing. We also empirically show the advantage of second-order parsing over first-order parsing and observe that the usefulness of the head-selection structured constraint vanishes when using BERT embedding.
BibTeX
@inproceedings{wang2020second,
  author = {Xinyu Wang and Kewei Tu},
  title = {{Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training}},
  booktitle = {AACL/IJCNLP},
  year = {2020},
  url = {https://openreview.net/forum?id=o72TytuCUGC},
}
Figure