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.
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.
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