# Efficient Second-Order TreeCRF for Neural Dependency Parsing

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2020.

## Built on by (most cited first, 30 of 48)

- [Masked Language Modeling and the Distributional Hypothesis: Order Word Matters Pre-training for Little](https://mlsanity.com/paper/2104.06644/) (2021)
- [How much do language models copy from their training data? Evaluating linguistic novelty in text generation using RAVEN](https://mlsanity.com/paper/2111.09509/) (2021)
- [Natural Language to Code Translation with Execution](https://mlsanity.com/paper/2204.11454/) (2022)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Disentangling Syntax and Semantics in the Brain with Deep Networks](https://mlsanity.com/paper/2103.01620/) (2021)
- [SynGEC: Syntax-Enhanced Grammatical Error Correction with a Tailored GEC-Oriented Parser](https://mlsanity.com/paper/2210.12484/) (2022)
- [Substructure Substitution: Structured Data Augmentation for NLP](https://mlsanity.com/paper/2101.00411/) (2021)
- [Fusing Heterogeneous Factors with Triaffine Mechanism for Nested Named Entity Recognition](https://mlsanity.com/paper/2110.07480/) (2021)
- [Semantic Role Labeling as Dependency Parsing: Exploring Latent Tree Structures Inside Arguments](https://mlsanity.com/paper/2110.06865/) (2021)
- [Nested Named Entity Recognition as Latent Lexicalized Constituency Parsing](https://mlsanity.com/paper/2203.04665/) (2022)
- [Dependency Parsing as MRC-based Span-Span Prediction](https://mlsanity.com/paper/2105.07654/) (2021)
- [Augmented 2D-TAN: A Two-stage Approach for Human-centric Spatio-Temporal Video Grounding](https://mlsanity.com/paper/2106.10634/) (2021)
- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [Joint Entity and Relation Extraction with Span Pruning and Hypergraph Neural Networks](https://mlsanity.com/paper/2310.17238/) (2023)
- [A Modest Pareto Optimisation Analysis of Dependency Parsers in 2021](https://mlsanity.com/paper/2106.04216/) (2021)
- [Unsupervised Vision-Language Parsing: Seamlessly Bridging Visual Scene Graphs with Language Structures via Dependency Relationships](https://mlsanity.com/paper/2203.14260/) (2022)
- [PiTe: Pixel-Temporal Alignment for Large Video-Language Model](https://mlsanity.com/paper/2409.07239/) (2024)
- [Causal Graphical Models for Vision-Language Compositional Understanding](https://mlsanity.com/paper/2412.09353/) (2024)
- [Dependency Parsing with Bottom-up Hierarchical Pointer Networks](https://mlsanity.com/paper/2105.09611/) (2021)
- [Combining (second-order) graph-based and headed-span-based projective dependency parsing](https://mlsanity.com/paper/2108.05838/) (2021)
- [Sparse Fuzzy Attention for Structured Sentiment Analysis](https://mlsanity.com/paper/2109.06719/) (2021)
- [Substructure Distribution Projection for Zero-Shot Cross-Lingual Dependency Parsing](https://mlsanity.com/paper/2110.08538/) (2021)
- [Investigating Non-local Features for Neural Constituency Parsing](https://mlsanity.com/paper/2109.12814/) (2021)
- [Instance-Based Neural Dependency Parsing](https://mlsanity.com/paper/2109.13497/) (2021)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)
- [Hexatagging: Projective Dependency Parsing as Tagging](https://mlsanity.com/paper/2306.05477/) (2023)
- [Syntactic Language Change in English and German: Metrics, Parsers, and Convergences](https://mlsanity.com/paper/2402.11549/) (2024)
- [Scaling Structured Inference with Randomization](https://mlsanity.com/paper/2112.03638/) (2021)
- [Building an Endangered Language Resource in the Classroom: Universal Dependencies for Kakataibo](https://mlsanity.com/paper/2206.10343/) (2022)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)

## Abstract (arXiv)

In the deep learning (DL) era, parsing models are extremely simplified with little hurt on performance, thanks to the remarkable capability of multi-layer BiLSTMs in context representation. As the most popular graph-based dependency parser due to its high efficiency and performance, the biaffine parser directly scores single dependencies under the arc-factorization assumption, and adopts a very simple local token-wise cross-entropy training loss. This paper for the first time presents a second-order TreeCRF extension to the biaffine parser. For a long time, the complexity and inefficiency of the inside-outside algorithm hinder the popularity of TreeCRF. To address this issue, we propose an effective way to batchify the inside and Viterbi algorithms for direct large matrix operation on GPUs, and to avoid the complex outside algorithm via efficient back-propagation. Experiments and analysis on 27 datasets from 13 languages clearly show that techniques developed before the DL era, such as structural learning (global TreeCRF loss) and high-order modeling are still useful, and can further boost parsing performance over the state-of-the-art biaffine parser, especially for partially annotated training data. We release our code at https://github.com/yzhangcs/crfpar.