Abstract
This paper introduces a truly end-to-end sequence-to-sequence (seq2seq) dependency parser that directly predicts the relative position of syntactic heads. By incorporating a novel tree-constrained beam search and a "divide-and-conquer" sub-root decomposition strategy, the model achieves state-of-the-art results among seq2seq parsers on both English and Chinese benchmarks, bypassing the need for traditional transition-based algorithms.
Introduction
Dependency parsing has historically been dominated by graph-based models and transition-based models. While researchers have recently applied powerful seq2seq neural networks to parsing, previous attempts often merely predicted transition action sequences, still relying on complex post-processing and traditional algorithms to construct the final tree. The authors tackle the challenge of building a pure seq2seq parser that directly outputs the tree structure, addressing key hurdles like structural integrity and long-distance dependency degradation.
Proposed Architecture
The core of the model is a BiLSTM-based encoder-decoder architecture with attention. Unlike previous models, the decoder directly predicts the relative position of a word's syntactic head (e.g., "L3" means the head is 3 words to the left).
To enhance the model's structural awareness, the encoder utilizes a rich set of embeddings:
- Standard Embeddings: GloVe word embeddings, character-level embeddings, and subword (BPE) embeddings.
- Topological Priors: Node2Vec embeddings, pre-trained on syntactic graphs from the training set, are used to inject structural information into the word representations.
- Tree-Constrained Beam Search: During decoding, a modified beam search enforces core dependency rules—ensuring the output is single-headed, acyclic, and projective—by applying penalty functions to invalid hypotheses.
Handling Long Sequences: Sub-root Decomposition
Seq2seq models often struggle with long sequences. To mitigate this, the authors introduce a "sub-root decomposition" strategy. A separate sequence tagger identifies "sub-roots" (direct children of the main sentence ROOT). Sentences exceeding a length threshold (e.g., 40 words) are split at these sub-roots into smaller, manageable sub-sentences. These are parsed independently and then merged to form the final dependency tree.
Experimental Results
The model was evaluated on the Penn Treebank (PTB) for English and the Chinese Treebank (CTB 5.1). It achieved 94.11% UAS and 92.08% LAS on the English PTB, and 88.78% UAS and 86.23% LAS on the Chinese CTB. While slightly trailing the most highly-engineered graph-based models, it outperforms almost all traditional transition-based neural parsers.
Ablation studies confirmed the importance of the tree constraints, which improved performance by approximately 0.9% UAS. The inclusion of Node2Vec and subword embeddings also provided significant performance gains, validating their inclusion in the final architecture.
Discussion and Future Work
The success of this model demonstrates that direct prediction of relative head positions is a viable and effective alternative to transition-based seq2seq parsing. The use of graph embeddings (Node2Vec) for syntax is a novel contribution that effectively provides structural hints to the neural network.
However, the model currently relies on a separate sub-root tagger, which can become a bottleneck if its accuracy is low. Additionally, the current beam search constraints enforce projectivity, which may limit performance on languages with frequent non-projective dependencies. Future work could involve refining the decomposition tagger and adapting the constraints for a broader range of linguistic structures.
Summary updated