# Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set

arXiv: https://arxiv.org/abs/1708.09403 · HTML: https://mlsanity.com/paper/1708.09403/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2017.

## Built on by (most cited first, 5 of 5)

- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [Syntactic Nuclei in Dependency Parsing -- A Multilingual Exploration](https://mlsanity.com/paper/2101.11959/) (2021)
- [Assessment of Pre-Trained Models Across Languages and Grammars](https://mlsanity.com/paper/2309.11165/) (2023)
- [Algorithms for Weighted Pushdown Automata](https://mlsanity.com/paper/2210.06884/) (2022)
- [Transition-based Bubble Parsing: Improvements on Coordination Structure Prediction](https://mlsanity.com/paper/2107.06905/) (2021)

## Abstract (arXiv)

We first present a minimal feature set for transition-based dependency parsing, continuing a recent trend started by Kiperwasser and Goldberg (2016a) and Cross and Huang (2016a) of using bi-directional LSTM features. We plug our minimal feature set into the dynamic-programming framework of Huang and Sagae (2010) and Kuhlmann et al. (2011) to produce the first implementation of worst-case O(n^3) exact decoders for arc-hybrid and arc-eager transition systems. With our minimal features, we also present O(n^3) global training methods. Finally, using ensembles including our new parsers, we achieve the best unlabeled attachment score reported (to our knowledge) on the Chinese Treebank and the "second-best-in-class" result on the English Penn Treebank.