# Approximation-Aware Dependency Parsing by Belief Propagation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2015.

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

- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [The Quantified Boolean Bayesian Network: Theory and Experiments with a Logical Graphical Model](https://mlsanity.com/paper/2402.06557/) (2024)
- [Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference](https://mlsanity.com/paper/2204.03619/) (2022)
- [Statistical Parsing for Logical Information Retrieval](https://mlsanity.com/paper/2602.12170/) (2026)
- [Transferring Neural Potentials For High Order Dependency Parsing](https://mlsanity.com/paper/2306.10469/) (2023)

## Abstract (arXiv)

We show how to train the fast dependency parser of Smith and Eisner (2008) for improved accuracy. This parser can consider higher-order interactions among edges while retaining O(n^3) runtime. It outputs the parse with maximum expected recall -- but for speed, this expectation is taken under a posterior distribution that is constructed only approximately, using loopy belief propagation through structured factors. We show how to adjust the model parameters to compensate for the errors introduced by this approximation, by following the gradient of the actual loss on training data. We find this gradient by back-propagation. That is, we treat the entire parser (approximations and all) as a differentiable circuit, as Stoyanov et al. (2011) and Domke (2010) did for loopy CRFs. The resulting trained parser obtains higher accuracy with fewer iterations of belief propagation than one trained by conditional log-likelihood.