TL;DR
This paper presents an enhanced Universal Dependency (EUD) parser that adapts second-order inference techniques from semantic dependency parsing alongside strong multilingual pretrained representations (XLMR). To tackle extreme data scarcity in low-resource languages like Tamil, the authors mix cross-lingual unlabeled graph structures into training, which boosts accuracy by up to 3.05 ELAS and tops the IWPT 2020 Shared Task leaderboards in post-evaluation.
What Problem Does This Paper Address?
Standard Universal Dependency (UD) trees are strictly rooted trees, meaning words have exactly one syntactic head. However, natural language syntax frequently requires reentrancies (nodes with multiple heads), cycles, or empty nodes (e.g., elided predicates). Enhanced Universal Dependencies (EUD) resolve this by modeling syntax as general graphs rather than strict trees.
Parsing general graphs is computationally challenging, especially when datasets are small. For instance, the Tamil EUD corpus contains only 400 training sentences, making end-to-end neural parsing prone to poor generalization. This paper tackles two primary challenges: accurately modeling non-tree structural dependencies and dramatically improving parser accuracy in extremely low-resource settings.
Methods
The authors reformulate EUD parsing into a bi-lexical graph parsing problem reminiscent of semantic dependency parsing (SDP):
- Data Pre- and Post-processing: Empty nodes are collapsed into surface tokens with composite dependency labels, and multi-arcs between identical head-dependent pairs are merged using composite
+labels. - Encoder: A 3-layer BiLSTM sits on top of pretrained token representations. The authors use XLM-R for most languages, combined with Flair and FastText embeddings specifically for Tamil.
- Second-Order Inference: Rather than scoring candidate edges independently (first-order), the parser uses Biaffine and Trilinear feed-forward networks to capture unary (single arc) and binary (arc interaction) potentials. These potentials feed into a Mean-Field Variational Inference (MFVI) network to calculate edge probabilities $P(\mathbf{Y}|\mathbf{w})$.
- Connectivity Decoding: Minimum Spanning Tree (MST) or Eisner’s algorithms are run first to guarantee global connectivity, followed by adding any non-tree arcs with $P(y_{ij} > 0.5)$.
- Cross-Lingual Mixture Training: Because label inventories vary across languages in EUD, the authors mix data from a resource-rich language (English or Czech) with Tamil by stripping the foreign language's edge labels (backpropagating only arc existence loss) and upsampling the Tamil dataset to balance sample sizes.
Datasets
The model was evaluated on the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, spanning 17 languages across multiple treebanks (e.g., Arabic PADT, Czech PDT/CAC/FicTree/PUD, English EWT/PUD, Tamil TTB).
- Tamil served as the primary low-resource benchmark (400 train, 80 dev sentences).
- Czech (102k sentences) and English (12.5k sentences) were used as auxiliary data sources to augment Tamil.
Key Insights and Ideas
- Syntactic Structures Transfer Even When Labels Differ: EUD label sets are language-specific, preventing naive multi-task learning. By stripping relation labels and training the encoder purely on edge existence for the auxiliary language, cross-lingual syntactic scaffolding transfers successfully to Tamil.
- Bigger Helps More than Closer: Training Tamil with Czech data (+3.05 ELAS over baseline) yielded substantially higher performance than training with English (+1.17 ELAS over baseline), showing that dataset size outweighed typological proximity in this multilingual setup.
- Non-Projective vs. Projective: Applying non-projective tree decoding (MST) prior to thresholding produced slightly better results (+0.2 ELAS) than projective decoding (Eisner's algorithm), aligning with the non-projective nature of enhanced dependencies.
- Enforcing Tree Connectivity Slightly Hurts Graph Scores: Non-connected graphs produced marginally higher raw ELAS scores than MST-constrained connected graphs. Tree algorithms are necessary only to meet submission/downstream validity constraints, though unconstrained argmax decoding is faster.
Key Results
- Overall Shared Task: Due to formatting issues (submitting invalid unconnected graphs), the official submission ranked 6th (71.7 ELAS). In post-evaluation, enforcing connectivity using the MST algorithm achieved 85.1 ELAS, outperforming the official 1st-place team (TurkuNLP at 84.5 ELAS) by 0.6 ELAS overall.
- First-Order vs. Second-Order Inference: Second-order inference improved labeled F1 across all evaluated languages (averaging 89.95% vs. 89.57% for XLMR).
- Tamil Data Mixture:
- Tamil Baseline (400 sentences): 55.39 ELAS
- Tamil + English (12,543 sentences): 56.56 ELAS
- Tamil + Czech (102,131 sentences): 58.44 ELAS (+3.05 ELAS gain)
Limitations and Future Work
- Limited Cross-Lingual Exploration: The data mixture experiments were applied only to Tamil, pairing it solely with English and Czech; the authors leave broader typological language pairs and combinations to future work.
- Decoding Speed: Running iterative second-order inference followed by MST/Eisner algorithms is computationally heavier and slower than simple first-order edge thresholding via argmax.
Summary updated