Incremental Non-Projective Dependency Parsing

Joakim NivreNAACL 2007 · OpenReview

Abstract: An open issue in data-driven dependency parsing is how to handle non-projective dependencies, which seem to be required by linguistically adequate representations, but which pose problems in parsing with respect to both accuracy and efficiency. Using data from five different languages, we evaluate an incremental deterministic parser that derives non-projective dependency structures in O(n 2 ) time, supported by SVM classifiers for predicting the next parser action. The experiments show that unrestricted non-projective parsing gives a significant improvement in accuracy, compared to a strictly projective baseline, with up to 35% error reduction, leading to state-of-the-art results for the given data sets. Moreover, by restricting the class of permissible structures to limited degrees of non-projectivity, the parsing time can be reduced by up to 50% without a significant decrease in accuracy.

Introduction

This paper addresses a fundamental challenge in syntax: efficiently parsing sentences where grammatical relations cross each other. While many dependency parsers assume projectivity for simplicity, real-world linguistic data—especially from languages with flexible word order—often requires non-projective representations.

The Challenge of Non-Projectivity

In dependency parsing, we draw arcs from "head" words to their "dependents" (e.g., from a verb to its subject). In languages like English, these arcs rarely cross, a property known as projectivity. However, in languages like Dutch, German, or Czech, words belonging to the same phrase can be separated by other sentence elements, leading to crossing arcs.

Example of a non-projective dependency structure with crossing arcs.

Historically, researchers faced a trade-off: projective parsers are fast ($O(n)$ or $O(n \log n)$) but linguistically inadequate for many languages, while non-projective parsers are more accurate but often computationally expensive or reliant on post-processing "hacks."

Methodology

Joakim Nivre proposes an incremental, deterministic parser that handles non-projective structures natively in $O(n^2)$ time. The approach adapts Covington’s (2001) algorithm, moving through a sentence left-to-right and deciding whether to add a dependency arc between the current word and any previous word.

SVM-Guided Parsing

The parser uses Support Vector Machines (SVMs) to predict the next action (Add Arc $i \to j$, Add Arc $j \to i$, or Do Nothing) based on features like word forms, parts-of-speech, and existing dependency labels. This allows the system to learn complex linguistic patterns directly from data.

Constrained Non-Projectivity

A key innovation is the introduction of a degree constraint ($d$). By restricting the parser to only consider arcs that do not exceed a certain "degree" of non-projectivity, the search space is narrowed:

  • $d=0$: Strictly projective.
  • $d=1, 2$: "Mildly" non-projective structures.
  • $d=\infty$: Unrestricted non-projective parsing.

Experimental Setup

The parser was evaluated using five diverse languages from the CoNLL-X Shared Task (2006): Danish, Dutch, German, Portuguese, and Slovene. These languages represent varying levels of non-projectivity, with Dutch and German providing the most significant challenges.

Key Results

The experiments demonstrate that unrestricted non-projective parsing significantly outperforms projective baselines. As shown in the results table, the transition to non-projective parsing yielded a 36.18% error reduction for Dutch and a 21.51% reduction for German.

Attachment scores (AS) and error reduction (ER) relative to the projective baseline across different constraints.

Efficiency and Accuracy Trade-offs

One of the paper's most practical findings is the "mildly non-projective" sweet spot. By limiting the degree of non-projectivity to $d=1$, the author achieved parsing time reductions of up to 50% in languages like Dutch and Slovene with negligible impact on attachment scores. This suggests that most linguistic crossing arcs are relatively simple and can be captured without the full computational cost of unrestricted parsing.

Conclusion

Nivre’s incremental non-projective parser offers a robust middle ground between efficiency and linguistic adequacy. By building non-projective graphs directly and using SVMs to navigate the search space, the system achieved state-of-the-art results for its time, proving that deterministic, incremental parsing is a viable and powerful strategy for complex syntax.

Reference: Nivre, J. (2007). Incremental Non-Projective Dependency Parsing. Proceedings of NAACL HLT 2007, 396–403.

Summary updated

Abstract

An open issue in data-driven dependency parsing is how to handle non-projective dependencies, which seem to be required by linguistically adequate representations, but which pose problems in parsing with respect to both accuracy and efficiency. Using data from five different languages, we evaluate an incremental deterministic parser that derives non-projective dependency structures in O(n 2 ) time, supported by SVM classifiers for predicting the next parser action. The experiments show that unrestricted non-projective parsing gives a significant improvement in accuracy, compared to a strictly projective baseline, with up to 35% error reduction, leading to state-of-the-art results for the given data sets. Moreover, by restricting the class of permissible structures to limited degrees of non-projectivity, the parsing time can be reduced by up to 50% without a significant decrease in accuracy.
BibTeX
@inproceedings{nivre2007incremental,
  author = {Joakim Nivre},
  title = {{Incremental Non-Projective Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=r1Eh4QWdZB},
}
Figure