TL;DR
BIST-COVINGTON is a neural dependency parser that combines the classic Covington algorithm for non-projective parsing with modern BiLSTM feature extraction and a dynamic oracle. Despite its simplicity—eschewing ensemble methods and custom pre-processing—it ranked 7th out of 33 teams in the CoNLL 2017 UD Shared Task for large treebanks, demonstrating the power of robust transition-based architectures.
What Problem Does This Paper Address?
Dependency parsing involves identifying the syntactic structure of a sentence by linking words (dependents) to their heads. While many parsers focus on "projective" structures—where dependency arcs do not cross—many human languages frequently employ "non-projective" constructions.
Traditional transition-based parsers often struggle with non-projectivity or require complex swap operations. Furthermore, greedy parsers are prone to "error propagation," where a single wrong move leads the parser into states it never saw during training, causing a cascade of failures. The authors sought to build a neural implementation of an unrestricted non-projective algorithm that uses a dynamic oracle to learn how to recover from such mistakes.
Methods
The authors introduce BIST-COVINGTON, which integrates three core components:
- The Covington (2001) Algorithm: A transition-based algorithm that considers all pairs of words in a sentence, allowing it to generate any non-projective structure. It operates with a theoretical complexity of $O(n^2)$.
- BiLSTM Feature Extractors: Following the BIST-parser architecture, the system uses bidirectional Long Short-Term Memory networks to create dense, context-aware vector representations for each word. The input features include word embeddings, universal and specific Part-of-Speech (PoS) tags, and morphological features.
- Dynamic Oracle: Unlike a static oracle that only shows the parser the "gold" path, a dynamic oracle allows the parser to explore suboptimal states during training. It teaches the model the best possible transitions to take even after it has already made a mistake, significantly mitigating error propagation.
The transition system uses four primary moves: LEFT-ARC, RIGHT-ARC, SHIFT, and NO-ARC, governed by specific preconditions to ensure valid tree structures.
Datasets
The model was evaluated using the CoNLL 2017 UD Shared Task data:
- Universal Dependencies (UD) 2.0: 60 treebanks across 45 languages.
- Surprise Languages: Four low-resource languages (Buryat, Kurmanji, North Sami, and Upper Sorbian) with very limited training data.
- Parallel (PUD) Treebanks: 14 parallel test sets used to evaluate cross-treebank performance.
Key Insights and Ideas
- The "Suffixed" Treebank Trap: The authors discovered that models trained on specific large treebanks (e.g.,
Spanish-AnCora) performed significantly worse on parallel test sets (PUD) than models trained on general, "unsuffixed" treebanks (e.g.,Spanish). This suggests that while these treebanks share the same language and UD standards, their underlying syntactic distributions or annotation quirks diverge enough to hurt cross-treebank generalization. - Multilingualism for Low-Resource Scenarios: For "surprise" languages with almost no data, the authors found success by training a single multilingual model on the top three most syntactically similar languages rather than relying on the tiny provided samples.
- Greedy is Good Enough: By using a dynamic oracle and BiLSTMs, the parser achieved high accuracy without the need for expensive beam search or ensemble methods, which are common in top-tier systems.
Key Results
- Big Treebanks Category: Ranked 7th out of 33 teams in both Labeled Attachment Score (LAS) and Unlabeled Attachment Score (UAS) across 55 languages.
- Top 10 Performance: The parser achieved top-10 LAS rankings for 35 different languages.
- PUD Recovery: In unofficial runs, switching from "suffixed" training models to "unsuffixed" ones improved Spanish PUD LAS from 53.73 to 78.90 and Finnish PUD from 40.66 to 80.70.
- Efficiency: The parser averaged 18.27 tokens per second. While slower than some projective parsers due to its $O(n^2)$ complexity, it remains practical for many applications.
Limitations and Future Work
- Hardware Constraints: The implementation using the DyNet library was memory-intensive. Training models with external embeddings often required over 32GB of RAM, preventing the authors from using these embeddings for all languages due to resource limits.
- Speed on Long Sentences: Because the Covington algorithm is quadratic, its performance degrades on very long sentences (e.g., 300+ words), which occurred in some treebanks due to automatic segmentation errors.
- Future Directions: The authors suggest exploring non-monotonic transition systems and approximate dynamic oracles, which have shown promise in improving both the accuracy and efficiency of non-projective parsing beyond the standard Covington approach.
Summary updated