A non-projective greedy dependency parser with bidirectional LSTMs

David Vilares, Carlos Gómez-RodríguezarXiv 2017 · arXiv

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.

Figure 1: A non-projective dependency tree

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:

  1. 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)$.
  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.
  3. 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.

Table 1: Set of transitions for BIST-COVINGTON

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

Abstract

The LyS-FASTPARSE team presents BIST-COVINGTON, a neural implementation of the Covington (2001) algorithm for non-projective dependency parsing. The bidirectional LSTM approach by Kipperwasser and Goldberg (2016) is used to train a greedy parser with a dynamic oracle to mitigate error propagation. The model participated in the CoNLL 2017 UD Shared Task. In spite of not using any ensemble methods and using the baseline segmentation and PoS tagging, the parser obtained good results on both macro-average LAS and UAS in the big treebanks category (55 languages), ranking 7th out of 33 teams. In the all treebanks category (LAS and UAS) we ranked 16th and 12th. The gap between the all and big categories is mainly due to the poor performance on four parallel PUD treebanks, suggesting that some `suffixed' treebanks (e.g. Spanish-AnCora) perform poorly on cross-treebank settings, which does not occur with the corresponding `unsuffixed' treebank (e.g. Spanish). By changing that, we obtain the 11th best LAS among all runs (official and unofficial). The code is made available at https://github.com/CoNLL-UD-2017/LyS-FASTPARSE
BibTeX
@misc{vilares2017non,
  author = {David Vilares and Carlos Gómez-Rodríguez},
  title = {{A non-projective greedy dependency parser with bidirectional LSTMs}},
  year = {2017},
  eprint = {1707.03228},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.03228},
}

Loading related content...

Figure