---
title: "Experiments with a Higher-Order Projective — Carreras 2007"
description: "The paper asks whether a graph-based projective dependency parser becomes more accurate when each scored factor includes more of the surrounding tree…"
authors: ["Xavier Carreras"]
year: 2007
venue: "Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)"
source: "https://aclanthology.org/D07-1101/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/carreras-2007-experiments-higher-order-projective-dependency/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/carreras-2007-experiments-higher-order-projective-dependency/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2007](https://md.research.elamur.ai/free/en/papers/2007/) / Experiments with a Higher-Order Projective Dependency Parser

# Experiments with a Higher-Order Projective Dependency Parser

**Authors:** [Xavier Carreras](https://md.research.elamur.ai/free/en/authors/xavier-carreras/) · **Year:** 2007 · **Venue:** Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/D07-1101/) · [PDF](https://aclanthology.org/D07-1101.pdf) · [OpenAlex](https://openalex.org/W47641349)

**Citations:** 231 citations (openalex-snapshot · 2026-10-14) · [127](#cited-by) in our library, of the 140884 papers whose bibliographies we read

## Summary
The paper asks whether a graph-based projective dependency parser becomes more accurate when each scored factor includes more of the surrounding tree than a single arc, or a single arc plus a sibling. Carreras defines a factor as one labeled head–modifier dependency together with three nearby unlabeled arcs:
- the head's child closest to the modifier,
- the modifier's furthest child inside the arc span,
- the modifier's furthest child outside the span.

This gives the model grandparent-style information, which matters for ambiguities such as PP-attachment. To decode with these factors, Eisner's dynamic-programming algorithm is extended, at O(n⁴L) time and O(n²L + n³) memory. Models are trained with the averaged perceptron on projectivized treebanks from the CoNLL-2007 multilingual track, covering ten languages.

On held-out data for Catalan, Czech and English, LAS climbs steadily as each extra relation is added. In the shared task the system ranked first for English and second for Basque and Czech. The main drawback is cost: with many labels or long sentences, training and parsing become impractical. This motivates research on cheaper ways to use higher-order context.

## Key points
- **Factor signature.** Each factor is ⟨h, m, l, c_h, c_mi, c_mo⟩.
  - The score sums one first-order term and three second-order terms, each tied to the label.
  - The secondary arcs interact only with the main dependency, never with each other. This keeps decoding feasible.
- **Ablation on validation data (~10k tokens per language, LAS).** Models are ordered from first-order up to the full c_h + c_mi + c_mo model.
  - Catalan: 86.15 → 88.04
  - Czech: 75.96 → 78.09
  - English: 87.54 → 89.59
  - A first-order model without averaging is far weaker. Czech, for example, drops to 68.98.
- **CoNLL-2007 test results.** Average UAS is 84.79 and average LAS is 79.09.
  - English: LAS 89.61
  - Catalan: LAS 87.60
  - Czech: LAS 78.60
  - Basque: LAS 75.73
  - Arabic is lowest, at LAS 70.20.
- **Training cost.** Speed and memory vary widely by language.
  - Arabic is slowest at about 1.2 sentences per minute, using 1.8 GB.
  - Chinese is fastest at about 1,460 sentences per minute, using 60 MB.
  - Under a 3-day / 15-epoch budget, Arabic and Catalan completed only 2 epochs.
- **Second-order features.** These extend McDonald and Pereira (2006). They are conjunctions of arc direction with the coarse POS tags and word forms of the head, modifier and child.

## Interesting ideas
- **Limit interactions to keep inference tractable.** Rich factors are allowed, but only main-to-secondary interactions are scored. This lets the open and closed chart items be optimized separately. The same trade-off can apply to any structured model where full joint interactions would make inference explode.
- **Projectivize training data with an oracle decoder.** The paper runs its own projective parser with a ±1 oracle score per arc to find the closest projective tree. This gives a simple, decoder-consistent way to fit non-projective treebanks, such as Ukrainian UD data, to a projective model.
- **Ablate one relation type at a time.** Adding c_h, then c_mo, then c_mi shows how much each kind of context contributes. This is a clean template for justifying feature or architecture choices.
- **Report speed and memory per language next to accuracy.** This shows when a model is practically usable, not just accurate. That matters when choosing parsers for languages with long sentences or large label sets.
- **Use a compute-budget stopping rule.** The model was observed not to overfit, and accuracy barely moved after 2–3 epochs. Training therefore stopped at a fixed time or epoch cap rather than tuning epochs per language, which is a pragmatic approach for multilingual training under limited resources.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Dependency parsing](https://md.research.elamur.ai/free/en/topics/dependency-parsing/) · [Treebanks](https://md.research.elamur.ai/free/en/topics/treebanks/)

## Cited by

Cited by

127 papers of our library cite it (of the 140884 whose bibliographies we read); 14 of them have a page here, 113 not yet.

- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://md.research.elamur.ai/free/en/papers/acl-2020-zhang-efficient-second-order-treecrf-neural/)
- [Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers](https://md.research.elamur.ai/free/en/papers/aclbulk-2013-martins-turning-turbo-fast-third-order/)
- [A Dependency Parser for Tweets](https://md.research.elamur.ai/free/en/papers/aclbulk-2014-kong-dependency-parser-tweets/)
- [Syntactic annotation of spontaneous speech: application to call-center conversation data](https://md.research.elamur.ai/free/en/papers/bazillon-2012-syntactic-annotation-spontaneous-speech-application/)
- [Top Accuracy and Fast Dependency Parsing is not a Contradiction](https://md.research.elamur.ai/free/en/papers/bohnet-2010-top-accuracy-fast-dependency-parsing/)
- [A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing](https://md.research.elamur.ai/free/en/papers/bohnet-2012-transition-based-system-joint-part/)
- [The CoNLL-2009 Shared Task: Syntactic and Semantic Dependencies in Multiple Languages](https://md.research.elamur.ai/free/en/papers/hajic-2009-conll-2009-shared-task-syntactic/)
- [Dependency-based Semantic Role Labeling of PropBank](https://md.research.elamur.ai/free/en/papers/johansson-2008-dependency-based-semantic-role-labeling/)
- [Simple Semi-supervised Dependency Parsing](https://md.research.elamur.ai/free/en/papers/koo-2008-simple-semi-supervised-dependency-parsing/)
- [The CoNLL 2008 Shared Task on Joint Parsing of Syntactic and Semantic Dependencies](https://md.research.elamur.ai/free/en/papers/surdeanu-2008-conll-2008-shared-task-joint/)
- [A Graph-based Lattice Dependency Parser for Joint Morphological Segmentation and Syntactic Analysis](https://md.research.elamur.ai/free/en/papers/tacl-2015-seeker-graph-based-lattice-dependency-parser/)
- ['IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks'](https://md.research.elamur.ai/free/en/papers/ud-2017-bjorkelund-ims-conll-2017-ud-shared/)
- [Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement](https://md.research.elamur.ai/free/en/papers/ud-2021-mohammadshahi-recursive-non-autoregressive-graph-graph/)
- [A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing](https://md.research.elamur.ai/free/en/papers/zhang-2008-tale-two-parsers-investigating-combining/)

## Cite

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

```bibtex
@inproceedings{carreras2007experiments,
  title = {{Experiments with a Higher-Order Projective Dependency Parser}},
  author = {Carreras, Xavier},
  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-1101/}
}
```

- [← previous Experiments in Domain Adaptation for Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/koehn-2007-experiments-domain-adaptation-statistical-machine/)
- [next → Extended Constituent-to-Dependency Conversion for English](https://md.research.elamur.ai/free/en/papers/map-2007-johansson-extended-constituent-dependency-conversion-english/)
- [↑ back to papers of 2007](https://md.research.elamur.ai/free/en/papers/2007/)

## References

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

1. A. Abeillé, editor. 2003. Treebanks: Building and Using Parsed Corpora. Kluwer. [find](https://scholar.google.com/scholar?q=A%2E+Abeille%CC%81%2C+editor%2E+2003%2E+Treebanks%3A+Building+and+Using+Parsed+Corpora%2E+Kluwer%2E)
2. I. Aduriz, M. J. Aranzabe, J. M. Arriola, A. Atutxa, A. Diaz de Ilarraza, A. Garmendia, and M. Oronoz. 2003. Construction of a Basque dependency treebank. In Proc. of the 2nd Workshop on Treebanks and Linguistic Theories (TLT), pages 201–204. [find](https://scholar.google.com/scholar?q=I%2E+Aduriz%2C+M%2E+J%2E+Aranzabe%2C+J%2E+M%2E+Arriola%2C+A%2E+Atutxa%2C+A%2E+Diaz+de+Ilarraza%2C+A%2E+Garmendia%2C+and+M%2E+Oronoz%2E+2003%2E+Construction+of+a+Basque+dependency+treebank%2E+In+Proc%2E+of+the+2nd+Workshop+on+Treebanks+and)
3. A. Böhmová, J. Hajič, E. Hajičová, and B. Hladká. 2003. The PDT: a 3-level annotation scenario. In Abeillé (Abeillé, 2003), chapter 7, pages 103–127. [find](https://scholar.google.com/scholar?q=A%2E+Bo%CC%88hmova%CC%81%2C+J%2E+Hajic%CC%8C%2C+E%2E+Hajic%CC%8Cova%CC%81%2C+and+B%2E+Hladka%CC%81%2E+2003%2E+The+PDT%3A+a+3%2Dlevel+annotation+scenario%2E+In+Abeille%CC%81+%28Abeille%CC%81%2C+2003%29%2C+chapter+7%2C+pages+103%E2%80%93127%2E)
4. X. Carreras, M. Surdeanu, and L. Màrquez. 2006. Projective dependency parsing with perceptron. In Proc. CoNLL-X. [find](https://scholar.google.com/scholar?q=X%2E+Carreras%2C+M%2E+Surdeanu%2C+and+L%2E+Ma%CC%80rquez%2E+2006%2E+Projective+dependency+parsing+with+perceptron%2E+In+Proc%2E+CoNLL%2DX%2E)
5. K. Chen, C. Luo, M. Chang, F. Chen, C. Chen, C. Huang, and Z. Gao. 2003. Sinica treebank: Design criteria, representational issues and implementation. In Abeillé (Abeillé, 2003), chapter 13, pages 231–248. [find](https://scholar.google.com/scholar?q=K%2E+Chen%2C+C%2E+Luo%2C+M%2E+Chang%2C+F%2E+Chen%2C+C%2E+Chen%2C+C%2E+Huang%2C+and+Z%2E+Gao%2E+2003%2E+Sinica+treebank%3A+Design+criteria%2C+representational+issues+and+implementation%2E+In+Abeille%CC%81+%28Abeille%CC%81%2C+2003%29%2C+chapter+13%2C+pages+2)
6. M. Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc. of EMNLP-2002. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+2002%2E+Discriminative+training+methods+for+hidden+markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proc%2E+of+EMNLP%2D2002%2E) [our card](https://md.research.elamur.ai/free/en/papers/collins-2002-discriminative-training-methods-hidden-markov/)
7. D. Csendes, J. Csirik, T. Gyimóthy, and A. Kocsor. 2005. The Szeged Treebank. Springer. [find](https://scholar.google.com/scholar?q=D%2E+Csendes%2C+J%2E+Csirik%2C+T%2E+Gyimo%CC%81thy%2C+and+A%2E+Kocsor%2E+2005%2E+The+Szeged+Treebank%2E+Springer%2E)
8. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COLING. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+1996%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proc%2E+COLING%2E) [our card](https://md.research.elamur.ai/free/en/papers/ast-1996-eisner-three-new-probabilistic-models-dependency/)
9. J. Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. In H. C. Bunt and A. Nijholt, editors, New Developments in Natural Language Parsing, pages 29–62. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+2000%2E+Bilexical+grammars+and+their+cubic%2Dtime+parsing+algorithms%2E+In+H%2E+C%2E+Bunt+and+A%2E+Nijholt%2C+editors%2C+New+Developments+in+Natural+Language+Parsing%2C+pages+29%E2%80%9362%2E+Kluwer+Academic+Publisher)
10. Y. Freund and R. E. Schapire. 1999. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296. [find](https://scholar.google.com/scholar?q=Y%2E+Freund+and+R%2E+E%2E+Schapire%2E+1999%2E+Large+margin+classification+using+the+perceptron+algorithm%2E+Machine+Learning%2C+37%283%29%3A277%E2%80%93296%2E)
11. J. Hajič, O. Smrž, P. Zemánek, J. Šnaidauf, and E. Beška. 2004. Prague Arabic dependency treebank: Development in data and tools. In Proc. of the NEMLAR Intern. Conf. on Arabic Language Resources and Tools, pages 110–117. [find](https://scholar.google.com/scholar?q=J%2E+Hajic%CC%8C%2C+O%2E+Smrz%CC%8C%2C+P%2E+Zema%CC%81nek%2C+J%2E+S%CC%8Cnaidauf%2C+and+E%2E+Bes%CC%8Cka%2E+2004%2E+Prague+Arabic+dependency+treebank%3A+Development+in+data+and+tools%2E+In+Proc%2E+of+the+NEMLAR+Intern%2E+Conf%2E+on+Arabic+Language+Resources)
12. R. Johansson and P. Nugues. 2007. Extended constituent-to-dependency conversion for English. In Proc. of the 16th Nordic Conference on Computational Linguistics (NODAL-IDA). [find](https://scholar.google.com/scholar?q=R%2E+Johansson+and+P%2E+Nugues%2E+2007%2E+Extended+constituent%2Dto%2Ddependency+conversion+for+English%2E+In+Proc%2E+of+the+16th+Nordic+Conference+on+Computational+Linguistics+%28NODAL%2DIDA%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/map-2007-johansson-extended-constituent-dependency-conversion-english/)
13. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19(2):313–330. [find](https://scholar.google.com/scholar?q=M%2E+Marcus%2C+B%2E+Santorini%2C+and+M%2E+Marcinkiewicz%2E+1993%2E+Building+a+large+annotated+corpus+of+English%3A+the+Penn+Treebank%2E+Computational+Linguistics%2C+19%282%29%3A313%E2%80%93330%2E) [our card](https://md.research.elamur.ai/free/en/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
14. M. A. Martı́, M. Taulé, L. Màrquez, and M. Bertran. 2007. CESS-ECE: A multilingual and multilevel annotated corpus. Available for download from: [http://www.lsi.upc.edu/∼mbertran/cess-ece/](http://www.lsi.upc.edu/∼mbertran/cess-ece/). [↗](http://www.lsi.upc.edu/∼mbertran/cess-ece/)
15. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of EACL-2006. [find](https://scholar.google.com/scholar?q=R%2E+McDonald+and+F%2E+Pereira%2E+2006%2E+Online+learning+of+approximate+dependency+parsing+algorithms%2E+In+Proc%2E+of+EACL%2D2006%2E) [our card](https://md.research.elamur.ai/free/en/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)
16. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+K%2E+Crammer%2C+and+F%2E+Pereira%2E+2005%2E+Online+large%2Dmargin+training+of+dependency+parsers%2E+In+Proc%2E+ACL%2E) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)
17. S. Montemagni, F. Barsotti, M. Battista, N. Calzolari, O. Corazzari, A. Lenci, A. Zampolli, F. Fanciulli, M. Massetani, R. Raffaelli, R. Basili, M. T. Pazienza, D. Saracino, F. Zanzotto, N. Nana, F. Pianesi, and R. Delmonte. 2003. Building the Italian Syntactic-Semantic Treebank. In Abeillé (Abeill… [find](https://scholar.google.com/scholar?q=S%2E+Montemagni%2C+F%2E+Barsotti%2C+M%2E+Battista%2C+N%2E+Calzolari%2C+O%2E+Corazzari%2C+A%2E+Lenci%2C+A%2E+Zampolli%2C+F%2E+Fanciulli%2C+M%2E+Massetani%2C+R%2E+Raffaelli%2C+R%2E+Basili%2C+M%2E+T%2E+Pazienza%2C+D%2E+Saracino%2C+F%2E+Zanzotto%2C+N%2E+Nana%2C+F%2E+P)
18. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. [find](https://scholar.google.com/scholar?q=J%2E+Nivre%2C+J%2E+Hall%2C+S%2E+Ku%CC%88bler%2C+R%2E+McDonald%2C+J%2E+Nilsson%2C+S%2E+Riedel%2C+and+D%2E+Yuret%2E+2007%2E)
19. The CoNLL 2007 shared task on dependency parsing. In Proc. of EMNLP-CoNLL. [find](https://scholar.google.com/scholar?q=The+CoNLL+2007+shared+task+on+dependency+parsing%2E+In+Proc%2E+of+EMNLP%2DCoNLL%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2007-conll-2007-shared-task-dependency/)
20. K. Oflazer, B. Say, D. Zeynep Hakkani-Tür, and G. Tür. 2003. Building a Turkish treebank. In Abeillé (Abeillé, 2003), chapter 15, pages 261–277. [find](https://scholar.google.com/scholar?q=K%2E+Oflazer%2C+B%2E+Say%2C+D%2E+Zeynep+Hakkani%2DTu%CC%88r%2C+and+G%2E+Tu%CC%88r%2E+2003%2E+Building+a+Turkish+treebank%2E+In+Abeille%CC%81+%28Abeille%CC%81%2C+2003%29%2C+chapter+15%2C+pages+261%E2%80%93277%2E)
21. P. Prokopidis, E. Desypri, M. Koutsombogera, H. Papageorgiou, and S. Piperidis. 2005. Theoretical and practical issues in the construction of a Greek dependency treebank. In Proc. of the 4th Workshop on Treebanks and Linguistic Theories (TLT), pages 149–160. [find](https://scholar.google.com/scholar?q=P%2E+Prokopidis%2C+E%2E+Desypri%2C+M%2E+Koutsombogera%2C+H%2E+Papageorgiou%2C+and+S%2E+Piperidis%2E+2005%2E+Theoretical+and+practical+issues+in+the+construction+of+a+Greek+dependency+treebank%2E+In+Proc%2E+of+the+4th+Workshop+)
22. A. Ratnaparkhi, J. Reinar, and S. Roukos. 1994. A maximum entropy model for prepositional phrase attachment. In Proc. of the ARPA Workshop on Human Language Technology. [find](https://scholar.google.com/scholar?q=A%2E+Ratnaparkhi%2C+J%2E+Reinar%2C+and+S%2E+Roukos%2E+1994%2E+A+maximum+entropy+model+for+prepositional+phrase+attachment%2E+In+Proc%2E+of+the+ARPA+Workshop+on+Human+Language+Technology%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-1994-ratnaparkhi-maximum-entropy-model-prepositional-phrase/)