Characterizing the Errors of Data-Driven Dependency Parsing Models

What it is about

The paper compares the two top systems of the CoNLL-X shared task. MSTParser is a global, exhaustive graph-based model with maximum spanning tree decoding and arc-pair features; MaltParser is a local, greedy transition-based model with an SVM classifier. Both reach almost the same labeled accuracy over 13 languages (about 80.8 and 80.8 LAS when the output files are pooled), but they make different kinds of errors. The authors break the errors down by arc length, distance to the root, number of siblings, degree of non-projectivity, part of speech and dependency type. MSTParser is more precise for arcs far from the root and for long arcs; MaltParser is better on short arcs and on nouns and pronouns. A simple oracle over the two outputs reaches 84.5 to 86.9% against about 81% for each system.

Ideas

I1. Error profile by distance to the root in en parse-eval and in gparse (Eisner decoding, gparse/src/eisner.rs): precision and recall of arcs at distance 1, 2, 3–4 and 5 or more, on EWT test; the question is whether the arc-standard parser fragments the tree near the root as the paper suggests for greedy parsers.
I2. Root-modifier check: count predicted root arcs that are not verbs or auxiliaries in en explain output over EWT test; the paper reads low root-modifier precision with stable recall as a sign of fragmented parses.
I3. Oracle diagnostic (test only, not shipped): take the en and gparse outputs on EWT test and measure the oracle LAS and the share of sentences where one of them is fully correct; if the gap is large, a combiner through tools/parsecmp is worth a later decision.
I4. Non-projectivity split: report LAS separately for sentences with a gold arc of degree 1 or more; the arc-standard parser in en/src/parse.rs cannot build those arcs, so the number is its ceiling on EWT and GUM test (GUM is test only).

For Mova

The relevant chapters are languages/en/20-syntax-overview.md (the main clause and root) and 21-clause-structure.md. The code is en/src/parse.rs (arc-standard, beam 8), gparse/src/eisner.rs, and the en parse-eval and tools/parsecmp tools. Measure first: EWT test LAS by distance to the root for both parsers, against the current baseline LAS 80.24. The paper's lesson is that an error analysis by structure says more than one accuracy number.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D07-1013.pdf

Summary

In data-driven dependency parsing, two families of models dominated the CoNLL-X shared task. Graph-based parsers are trained globally and search exhaustively but use only local features. Transition-based parsers are trained locally and decode greedily but can draw on the full parse history. The two families reach nearly identical overall accuracy, so McDonald and Nivre ask whether they nonetheless fail in different ways. They compare the outputs of MSTParser and MaltParser on all 13 CoNLL-X test sets, pooled into one corpus, and break errors down by sentence length, arc length, distance to the root, part of speech and dependency type. The error profiles diverge systematically and match theory. MaltParser suffers from error propagation, so it loses accuracy on long sentences, long arcs and arcs near the root. Its rich features help on short, frequent relations such as subjects and objects. MSTParser's errors are distributed more evenly. Oracle experiments show that combining the parsers could yield substantial gains. This motivates ensemble, hybrid and globally trained transition-based parsers.

Key points

The two systems were the top CoNLL-X participants: MSTParser (McDonald et al., 2006) and MaltParser (Nivre et al., 2006). Their overall LAS was almost tied, at 80.83 vs. 80.75.
The data come from CoNLL-X, which covered 13 languages and 19 systems. Each test set has roughly 5,000 tokens, so pooling them works approximately like an equally weighted average across languages.
Both parsers perform similarly on most coordination categories. The exception is CCH, the arc linking a coordinate structure to its head, where MSTParser leads by almost 20 points in both precision and recall.
Two oracle experiments estimate the gain from combining the parsers, against about 81% LAS for each system alone:
- choosing the better whole parse per sentence gives 84.5%;
- building the best tree from the union of both parsers' arcs, via a spanning-tree search, gives 86.9%.
The authors propose three directions:
- linguistically informed weighting for ensembles in the style of Sagae and Lavie (2006);
- hybrids that decode greedily at first and switch to exhaustive search later in the parse;
- globally trained greedy models, such as the framework of Daumé III et al. (2006).

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{mcdonald2007characterizing,
  title = {{Characterizing the Errors of Data-Driven Dependency Parsing Models}},
  author = {McDonald, Ryan and Nivre, Joakim},
  booktitle = {Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)},
  year = {2007},
  url = {https://aclanthology.org/D07-1013/}
}

References

17 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

A. Böhmová, J. Hajič, E. Hajičová, and B. Hladká. 2003. The PDT: A 3-level annotation scenario. In A. Abeillé, editor, Treebanks: Building and Using Parsed Corpora, chapter 7. Kluwer Academic Publishers. find
S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proc. CoNLL. find our card
Hal Daumé III, John Langford, and Daniel Marcu. 2006. Search-based structured prediction. In Submission. find
Y. Ding and M. Palmer. 2004. Synchronous dependency insertion grammars: A grammar formalism for syntax based statistical MT. In Workshop on Recent Advances in Dependency Grammars (COLING). find
R. Hudson. 1984. Word Grammar. Blackwell. find
H. Maruyama. 1990. Structural disambiguation with constraint propagation. In Proc. ACL. find
R. McDonald, K. Crammer, and F. Pereira. 2005a. Online large-margin training of dependency parsers. In Proc. ACL. find our card
R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proc. HLT/EMNLP. find our card
R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. CoNLL. find
I.A. Mel’čuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. find
J. Nivre, J. Hall, J. Nilsson, G. Eryigit, and S. Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proc. CoNLL. find
J. Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proc. IWPT. find our card
J. Nivre. 2006. Constraints on non-projective dependency parsing. In Proc. EACL. find
K. Sagae and A. Lavie. 2006. Parser combination by reparsing. In Proc. HLT/NAACL. find
P. Sgall, E. Hajičová, and J. Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel. find
R. Snow, D. Jurafsky, and A. Y. Ng. 2004. Learning syntactic patterns for automatic hypernym discovery. In Proc. NIPS. find