PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Second-Order TreeCRF for Neural Dependency Parsing

Yu Zhang, Zhenghua Li, Min Zhang

arXiv:2005.00975v2cs.CL

TL;DR

The paper asks whether structural learning and high-order modeling can improve the biaffine parser, while addressing the computational cost that has hindered TreeCRF. It introduces a second-order TreeCRF with GPU-batched algorithms and reports benefits across 27 datasets from 13 languages, including partially annotated data.

  • Problem

    The paper asks whether structural learning and high-order modeling can improve the biaffine parser, while TreeCRF’s inside-outside computation remains complex and inefficient for GPU-heavy deep learning.

    Source: §1 · p. 2

  • Method

    The paper extends the biaffine parser with second-order TreeCRF and triaffine subtree scoring, batching inside computation on GPUs and using back-propagation instead of the outside algorithm.

    Source: §1 · p. 2

  • Results

    Across 27 datasets from 13 languages, structural learning and high-order modeling improved convergence, sub- and full-tree performance, and use of partially annotated data.

    Source: §6 · p. 9

  • Takeaways & Limitations

    On partially annotated data, TreeCRF outperformed local training by a large margin, and second-order modeling further improved parsing performance.

    Source: §4.2 · p. 7

    Third- and fourth-order models showed little accuracy improvement, probably because of feature sparsity.

    Source: §1 · p. 1

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether structural learning and higher-order modeling can improve the biaffine parser, while addressing TreeCRF’s computational burden. It presents a second-order TreeCRF extension and GPU-oriented algorithms, reporting benefits across multilingual datasets.

1 Introduction

  • Earlier graph-based parsers used structural learning, while second-order models added dependency-pair scores but reduced efficiency and complicated decoding.The introduction contrasts these approaches with the neural biaffine parser’s first-order scoring and local head-selection training.Source: §1 · pp. 1–2
  • The motivating question is whether structural learning and high-order modeling can further improve the state-of-the-art biaffine parser, and where they help.Source: §1 · p. 2
  • TreeCRF models tree probabilities and subtree marginals, which can support high-level NLP uses, MBR decoding, and token-level active learning.The cited work presents marginal probabilities as a theoretically sound measure of subtree confidence.Source: §1 · p. 2
  • TreeCRF’s inside-outside computation was considered complex and inefficient, with CPU computation mismatched to GPU-heavy deep learning.The paper asks whether inside computation can be batched directly on GPUs.Source: §1 · p. 2
  • The paper introduces second-order TreeCRF for neural dependency parsing and triaffine scoring of second-order subtrees.It also proposes GPU-batched inside computation and replaces the outside algorithm with back-propagation for gradients and marginal probabilities.Source: §1 · p. 2
  • Across 27 datasets from 13 languages, structural learning and high-order modeling improved the biaffine parser in multiple ways.The introduction frames these techniques as beneficial in the deep-learning era.Source: §1 · p. 2

2 The Basic Biaffine Parser

The basic biaffine parser uses contextualized token representations to score dependencies, trains with local head-selection loss, and decodes projective trees with Eisner’s algorithm.

2 The Basic Biaffine Parser

  • The parser uses word embeddings and CharLSTM representations, which consistently improve results over POS tag embeddings and avoid POS-tag generation.The reimplementation also uses first-order Eisner projective decoding rather than the non-projective MST algorithm.Source: §2 · pp. 2–3
  • Three BiLSTM layers encode sentence context, and shared MLPs produce syntax-focused head and modifier representations for scoring.The scoring architecture is depicted in Figure 2.Source: §2 · pp. 2–3, Figure 2 · p. 3
  • Biaffine attention scores each candidate head–modifier dependency.Dependency labels are handled separately: tree search and labeling are independent during training and cascaded during parsing.Source: §2 · p. 3
  • Local cross-entropy independently maximizes each word’s probability of selecting its correct head, without considering tree structure during training.Losses for all words in a minibatch are accumulated, and Eisner decoding finds the optimal projective tree from dependency scores.Source: §2 · p. 3

3 Second-order TreeCRF

The section extends biaffine parsing with structural TreeCRF training and adjacent-sibling scores, then makes second-order inference more practical through batched GPU computation and back-propagation. It also applies the model to partially annotated training data.

3 Second-order TreeCRF

  • TreeCRF extends the first-order biaffine model with structural training and adjacent-sibling subtree scores.It models conditional probabilities over legal projective trees and trains to maximize the gold tree's conditional probability.Source: §3 · p. 3

3.1 Scoring Second-order Subtrees

  • Three extra MLPs extract head, sibling, and modifier representations, which triaffine scoring combines for adjacent-sibling subtrees.The triaffine operation uses a three-way tensor and can be computed with PyTorch's einsum function.Source: §3.1 · p. 4

3.2 Computing TreeCRF Loss Efficiently

  • The second-order inside algorithm replaces max-product with sum-product and batches same-width span scores across sentences for GPU tensor computation.The outside algorithm is usually at least twice slower than the inside algorithm, motivating the more efficient approach.Source: §3.2 · p. 4
  • The batchified inference techniques are also applicable to CKY-style constituency parsing.Grandparent-modifier subtree scores are left for future work and would use a Viterbi algorithm with O(n^4) time complexity.Source: §3 · p. 3, §3.2 · p. 4

3.3 Outside via Back-propagation

  • Back-propagation empirically verifies its equivalence to the outside algorithm for dependency parsing, and TreeCRF marginals support MBR decoding with a slight, consistent accuracy increase.Marginal probabilities directly correspond to gradients after back-propagating log Z(x) as the loss.Source: §3.3 · p. 5

3.4 Handling Partial Annotation

  • For partial trees, the TreeCRF loss considers only compatible legal trees, allowing annotated dependencies to influence unannotated words' probability distributions.The authors apply the partial-annotation TreeCRF approach to the neural biaffine parser and note that high-order modeling promotes inter-token interaction.Source: §3.4 · p. 5

4 Experiments

Experiments compare local and TreeCRF parsers on PTB, CoNLL09, NLPCC19, and Universal Dependencies, with analyses of efficiency, convergence, tree-level accuracy, and partial-data learning. CRF2O shows its strongest reported benefits across UD languages and partially annotated data, while results vary by dataset and analysis.

4.1 Efficiency Comparison

  • On PTB-test, GPU batchification and back-propagation yield about 500 sentences per second for CRF and 400 for CRF2O; CRF is over 10 times faster than multi-threaded CPU CRF.The CRF2O speed is reported as sufficient for a real-time system.Source: §4.1 · p. 6, Figure 4 · p. 6

4.2 Main Results

  • On CoNLL09, CRF significantly outperforms LOC and CRF2O improves further, while neither TreeCRF model improves PTB accuracy beyond LOC.The authors suggest PTB's already-high accuracy may explain the lack of gains there.Source: §4.2 · pp. 6–7
  • On NLPCC19's partially annotated data, CRF substantially outperforms LOC, and CRF2O improves further by modeling second-order subtree features.The authors attribute the large CRF-over-LOC margin to structural learning's usefulness with partial annotation.Source: §4.2 · p. 7

4.3 Analysis

  • CRF2O converges faster and reaches steadily higher accuracy than LOC; the plotted curves show peak LAS every 20 epochs on PTB, CoNLL09, and NLPCC19 dev data.Source: §4.3 · p. 7, Figure 5 · p. 7
  • Adjacent-sibling modeling improves SIB performance more than CRF or LOC and contributes to larger full-tree matching gains in UCM and LCM.The subtree analysis omits partially labeled NLPCC19 data; LCM requires correct labels as well as a complete skeletal tree.Source: §4.3 · pp. 7–8, Table 2 · p. 7
  • CRF2O's advantage over LOC stays steady as training sentences are removed but widens as annotated dependencies per sentence decrease, indicating better use of partial data.The analysis compares retained full-tree sentences with retained dependencies in partial trees.Source: Figure 6 · p. 7, §4.3 · p. 8

4.4 Results on Universal Dependencies

  • CRF2O ranks highest for 10 of 12 languages on UD2.2 and UD2.3, with significant gains in more than 7 languages and average improvements of 0.45 and 0.29, respectively.The reported averages are significant at p < 0.005.Source: §4.4 · p. 8
  • CRF2O outperforms Ji et al. (2019) by 2.30 on UD2.2 raw texts and Zhang et al. (2019) by 0.91 on UD2.3 with gold POS tags.For the German comparison, Ji et al.'s parser was rerun with predicted XPOS tags; CRF2O averaged LAS 87.64 using those tags.Source: §4.4 · p. 8

5 Related Works

Prior work explores structural context through implicit neural representations and explicit second-order scoring, while this paper combines explicit high-order scores with global TreeCRF training. Earlier analyses differ on whether BiLSTMs make explicit high-order modeling redundant.

  • Eisner (2016) proved outside computation equivalent to back-propagation for constituent parsing and discussed dependency grammar; this paper reports an empirical dependency-parsing study.Source: §5 · p. 9
  • Explicit high-order modeling helps alongside the BiLSTM encoder, unlike the conclusion of Falenska and Kuhn (2019), who found it redundant using a weaker parser.Their analysis extended a first-order parser with adjacent-sibling scores and used max-margin loss and second-order Eisner decoding.Source: §5 · p. 9
  • Ji et al. (2019) add high-order information implicitly through a three-layer GAT but retain local head-selection loss; this work instead uses global TreeCRF loss and explicit high-order scores.Source: §5 · p. 9
  • Zhang et al. (2019) found TreeCRF slightly superior to max-margin overall and structural learning modestly improved LAS for some languages, while improving sentence-level complete matching substantially.They computed inside and outside algorithms on CPUs; this work extends the biaffine parser to second-order TreeCRF and provides more in-depth analysis.Source: §5 · p. 9

6 Conclusions

The paper introduces second-order TreeCRF for neural dependency parsing and a GPU-oriented inside algorithm, using back-propagation rather than explicit outside computation. Experiments across 27 datasets in 13 languages find benefits from structural learning and high-order modeling.

  • The paper presents second-order TreeCRF for neural dependency parsing, using triaffine scoring to represent second-order subtrees.Source: §6 · p. 9
  • Structural learning and high-order modeling further enhance the state-of-the-art biaffine parser across convergence, sub- and full-tree performance, and partially annotated data.Source: §6 · p. 9
  • The inside algorithm is batchified for GPUs, while back-propagation implicitly performs the outside algorithm and produces gradients and marginal probabilities.Source: §6 · p. 9

A More on Efficiency

The section reports training-time comparisons, a PTB-test LAS comparison for local MST decoding, and a strategy that avoids Eisner decoding when greedy assignments already form legal projective trees.

  • On PTB, average one-iteration training times are about 1min for LOC, 2.5min for CRF, and 3.5min for CRF2O.The corresponding speeds are about 700, 300, and 200 sentences per second.Source: A More on Efficiency · p. 11
  • 94.43 LAS on PTB-test for LOCMST, versus 94.47 for LOC; LOCMST parses over 1000 sentences per second.Source: A More on Efficiency · p. 11
  • More than 99% of PTB-test sentences already yield legal projective trees from greedy marginal-probability head assignments, avoiding the decoding algorithm for those sentences.Legality is checked for a single root and no cycles, followed by projectivity.Source: A More on Efficiency · p. 11

Related papers

Loading 2005.00975v2…