Elamur Research⌕
☰
home / papers / 2007 / Experiments with a Higher-Order Projective Dependency Parser

Experiments with a Higher-Order Projective Dependency Parser

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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.
  • I5. 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

Topics: Dependency parsing · Treebanks

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.

Cite

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

@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/}
}

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
  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
  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
  4. X. Carreras, M. Surdeanu, and L. Màrquez. 2006. Projective dependency parsing with perceptron. In Proc. CoNLL-X. find
  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
  6. M. Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc. of EMNLP-2002. find our card
  7. D. Csendes, J. Csirik, T. Gyimóthy, and A. Kocsor. 2005. The Szeged Treebank. Springer. find
  8. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COLING. find our card
  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
  10. Y. Freund and R. E. Schapire. 1999. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296. find
  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
  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 our card
  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 our card
  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/. ↗
  15. R. McDonald and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of EACL-2006. find our card
  16. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL. find our card
  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
  18. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. find
  19. The CoNLL 2007 shared task on dependency parsing. In Proc. of EMNLP-CoNLL. find our card
  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
  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
  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 our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/carreras-2007-experiments-higher-order-projective-dependency/