# Dependency Parsing with Backtracking using Deep Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 28 Jun 2022.

## Builds on (most cited first, 9 of 9)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Fast R-CNN](https://mlsanity.com/paper/1504.08083/) (2015)
- [Enriching Word Vectors with Subword Information](https://mlsanity.com/paper/1607.04606/) (2016)
- [Transition-Based Dependency Parsing with Stack Long Short-Term Memory](https://mlsanity.com/paper/1505.08075/) (2015)
- [Rewarding Smatch: Transition-Based AMR Parsing with Reinforcement Learning](https://mlsanity.com/paper/1905.13370/) (2019)
- [AMR Parsing using Stack-LSTMs](https://mlsanity.com/paper/1707.07755/) (2017)
- [Multi-Task Semantic Dependency Parsing with Policy Gradient for Learning Easy-First Strategies](https://mlsanity.com/paper/1906.01239/) (2019)
- [Training with Exploration Improves a Greedy Stack-LSTM Parser](https://mlsanity.com/paper/1603.03793/) (2016)
- [Tackling Error Propagation through Reinforcement Learning: A Case of Greedy Dependency Parsing](https://mlsanity.com/paper/1702.06794/) (2017)

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

- [Dynamic Layer Tying for Parameter-Efficient Transformers](https://mlsanity.com/paper/2401.12819/) (2024)

## Abstract (arXiv)

Greedy algorithms for NLP such as transition based parsing are prone to error propagation. One way to overcome this problem is to allow the algorithm to backtrack and explore an alternative solution in cases where new evidence contradicts the solution explored so far. In order to implement such a behavior, we use reinforcement learning and let the algorithm backtrack in cases where such an action gets a better reward than continuing to explore the current solution. We test this idea on both POS tagging and dependency parsing and show that backtracking is an effective means to fight against error propagation.