TL;DR
This paper introduces a novel second-order neural dependency parser that achieves state-of-the-art accuracy while being significantly faster than previous methods. It demonstrates that even with powerful pre-trained embeddings like BERT, higher-order parsing still offers benefits, and the impact of certain structural constraints can be diminished by these embeddings.
What Problem Does This Paper Address?
Dependency parsing is a fundamental task in Natural Language Processing (NLP) that aims to uncover the grammatical structure of a sentence by identifying relationships between words. Traditional approaches often score individual dependency edges (first-order), while more advanced methods consider combinations of edges (higher-order) to capture more complex grammatical phenomena. However, higher-order parsing has historically been computationally expensive, limiting its practical application. Recent neural network-based parsers have achieved impressive results, but there's an ongoing quest to balance accuracy with efficiency, especially when incorporating advanced contextual embeddings like BERT, which are believed by some to already encode much of the necessary structural information. This paper tackles the challenge of developing a more efficient and accurate second-order dependency parser that can leverage the power of neural networks and end-to-end training.
Methods
The authors propose two main approaches, both based on message passing inference within a conditional random field (CRF) framework, adapted for end-to-end neural training.
- Modified Single Approach: They adapt a previously proposed second-order semantic dependency parser. The key modifications for syntactic parsing include removing co-parent constraints (which are not applicable to syntax) and using a Maximum Spanning Tree (MST) algorithm during inference to ensure a valid tree structure. This approach treats each potential dependency edge independently.
- Local Second-Order Approach: This is a novel contribution. It enforces the "head-selection" constraint, meaning each word must select exactly one head. This is achieved by defining a discrete random variable for each word that specifies its dependency head. This local constraint leads to a different formulation of the message passing inference steps compared to the Single approach.
Both approaches utilize a biaffine function to score individual edges and trilinear functions to score sibling and grandparent edge combinations, capturing second-order information. For learning, they employ a cross-entropy loss function that combines edge and label prediction losses.
Datasets
The authors evaluate their approaches on three standard datasets:
- Penn Tree Bank 3.0 (PTB): A widely used English dependency parsing corpus.
- Chinese Penn Tree Bank 5.1 (CTB): A Chinese dependency parsing corpus.
- Universal Dependencies (UD) 2.2: A collection of treebanks for 12 different languages, allowing for cross-lingual evaluation.
They note that punctuation is ignored in all evaluations and that sentences longer than 90 words are removed from training sets for faster computation.
Key Insights and Ideas
- Second-order parsing is still valuable with BERT: Contrary to the belief that powerful contextual embeddings like BERT might render higher-order parsing redundant, the authors find that their second-order decoders still provide significant improvements in accuracy.
- Head-selection constraint's role diminishes with BERT: While the head-selection constraint is generally beneficial, its impact appears to be less pronounced when using BERT embeddings. This suggests that BERT might implicitly capture some of the information that this constraint explicitly enforces.
- Efficiency gains are substantial: The proposed second-order parsers are significantly faster than previous state-of-the-art second-order methods, making them more practical for real-world applications.
- Local vs. Single approaches: The relative performance of the Local (with head-selection) and Single (without explicit head-selection) approaches can vary across different treebanks, indicating that the importance of the head-selection constraint is context-dependent.
Key Results
- State-of-the-art accuracy: Their proposed Local2O and Single2O approaches achieve state-of-the-art performance on PTB and CTB, often matching or exceeding recent methods.
- Significant speedup: The Local approach is 1.2-2.3 times faster than GNN and 2.4-2.9 times faster than the second-order tree CRF approach of Zhang et al. (2020) in training and testing. Their second-order parsers are only 12-23% slower than first-order parsers.
- BERT benefits: With BERT embeddings, their Local2O parser achieves the best accuracy on PTB, and Single2O performs best on CTB.
- UD performance: Their second-order approaches outperform GNN and first-order baselines on UD datasets, both with and without BERT.
Limitations and Future Work
- Computational complexity: While significantly faster than previous second-order parsers, their methods still have a higher time complexity (O(n³)) than some first-order parsers (O(n²)). The paper notes that their decoders can be parallelized, which helps mitigate this.
- Head-selection constraint's varying importance: The paper highlights that the usefulness of the head-selection constraint is limited, especially with BERT. Further investigation into why this is the case and how to best leverage or adapt such constraints in the presence of powerful pre-trained models could be a future direction.
- Further exploration of Local vs. Single: The varying performance of Local and Single approaches across different treebanks suggests that more research could be done to understand the specific linguistic phenomena that benefit most from the head-selection constraint.
The authors also make their code publicly available, which is a positive step for reproducibility and future research.
Summary updated