---
title: "Labeled Pseudo-Projective Dependency Parsing — Nivre 2006"
description: "This paper describes the system the authors entered in the CoNLL-X shared task."
authors: ["Joakim Nivre", "Johan Hall", "Jens Nilsson", "Gülşen Eryiǧit", "Svetoslav Marinov"]
year: 2006
venue: "Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X)"
source: "https://aclanthology.org/W06-2933/"
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/papers/nivre-2006-labeled-pseudo-projective-dependency-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/nivre-2006-labeled-pseudo-projective-dependency-parsing/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2006](https://md.research.elamur.ai/free/papers/2006/) / Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines

# Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines

**Authors:** [Joakim Nivre](https://md.research.elamur.ai/free/authors/joakim-nivre/), [Johan Hall](https://md.research.elamur.ai/free/authors/johan-hall/), [Jens Nilsson](https://md.research.elamur.ai/free/authors/jens-nilsson/), [Gülşen Eryiǧit](https://md.research.elamur.ai/free/authors/gulsen-eryi-it/), Svetoslav Marinov · **Year:** 2006 · **Venue:** Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X) · **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/W06-2933/) · [PDF](https://aclanthology.org/W06-2933.pdf) · [OpenAlex](https://openalex.org/W2015238682)

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

## Summary
This paper describes the system the authors entered in the CoNLL-X shared task. The task required one trainable dependency parser to handle treebanks in many languages. The parser is built with MaltParser 0.4. It reads each sentence once, left to right, and makes a deterministic choice at each step. A stack and four basic transitions build a labeled projective dependency graph. At every step, an SVM classifier picks the next transition from symbolic features of the parsing history.

The algorithm can only produce projective trees. To handle crossing arcs, the training trees are first made projective, and the moved arcs get enriched labels. After parsing, an inverse transformation restores the non-projective structure. For each language, the authors tuned feature sets and SVM settings. Across the twelve required languages, the system reached a labeled attachment score (LAS) of 80.19, which placed it at or near the top. The paper closes with an error analysis that looks most closely at Swedish and Turkish. Together, these results show that a fast, greedy, classifier-driven parser can compete across very different languages.

## Key points
- The parser has four components:
  - a deterministic transition algorithm with the actions SHIFT, REDUCE, RIGHT-ARC(r) and LEFT-ARC(r);
  - history-based features;
  - LIBSVM classifiers with a quadratic kernel and a one-versus-all multi-class strategy;
  - pseudo-projective graph transformations using the HEAD label encoding (r↑h).
- Test-set results:
  - Total LAS was 80.19 (Bulgarian excluded), compared with 80.46 in the dry run. This small gap suggests the models were not overfitted.
  - LAS ranged from 91.65 for Japanese to 65.68 for Turkish.
  - The system had the best reported LAS for Japanese, Swedish and Turkish.
  - Unlabeled scores were less competitive; only Turkish had the top UAS.
- Model settings:
  - Tuned models used between 16 features (Turkish) and 30 (Spanish).
  - An artificial root token was added only for Arabic, Czech, Portuguese and Slovene, whose root labels carry information.
  - For some languages, the training data was split by the POS or CPOS of the next input token, which speeds up training.
- Root errors and non-projectivity:
  - Treebanks with many non-projective structures produced fragmented output and lower root precision.
  - Root precision was about 69% for Czech, 71% for Dutch and 41% for Slovene.
- Turkish results:
  - Turkish is parsed over inflectional groups (IGs), not whole words. Its IG-level UAS of 75.8% corresponds to a word-level score of 82.7%.
  - Accuracy was much lower when the head belonged to a word with several IGs: 53.2% versus 83.7% for single-IG heads.

## Interesting ideas
- **Pseudo-projective encoding.** The authors keep a simple projective parser and push non-projectivity into the labels. Lifted arcs remember their original head's label, and a post-processing step undoes the lifting. This pre-/post-transformation trick lets a restricted model handle richer output structures.
- **Splitting morphological features.** The FEATS field is broken into atomic attributes such as case and possessive, rather than treated as one combined value. The classifier then chooses which attributes matter in each context. This is likely valuable for morphologically rich languages such as Ukrainian.
- **Splitting the training data by the next token's POS/CPOS.** Separate classifiers are trained for each POS or CPOS value of the next input token. Rare categories are pooled using a frequency threshold. This reduces SVM training time with little loss in accuracy, and it is a generic way to scale kernel methods.
- **Diagnostic evaluation beyond LAS.** The error analysis uses root precision and recall to reflect global structure, and accuracy by arc length to reflect local versus distant attachments. These measures help explain why languages with similar LAS behave differently.
- **Evaluating at the right unit.** For segmented annotations like Turkish IGs, the authors report both unit-level and word-level scores. They also break results down by single-unit versus multi-unit heads, which keeps cross-language comparisons fair.

*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: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

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

## Cited by

Cited by

104 papers of our library cite it (of the 140673 whose bibliographies we read); 10 of them have a page here, 94 not yet.

- [Evaluation of Dependency Parsers on Unbounded Dependencies](https://md.research.elamur.ai/free/papers/aclbulk-2010-nivre-evaluation-dependency-parsers-unbounded-dependencies/)
- [Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers](https://md.research.elamur.ai/free/papers/aclbulk-2013-martins-turning-turbo-fast-third-order/)
- [Characterizing the Errors of Data-Driven Dependency Parsing Models](https://md.research.elamur.ai/free/papers/missing4-2007-mcdonald-characterizing-errors-data-driven-dependency/)
- [Algorithms for Deterministic Incremental Dependency Parsing](https://md.research.elamur.ai/free/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/)
- [Non-Projective Dependency Parsing in Expected Linear Time](https://md.research.elamur.ai/free/papers/nivre-2009-non-projective-dependency-parsing-expected/)
- [CoNLL-X Shared Task on Multilingual Dependency Parsing](https://md.research.elamur.ai/free/papers/parsers-2006-buchholz-conll-x-shared-task-multilingual/)
- [The CoNLL 2008 Shared Task on Joint Parsing of Syntactic and Semantic Dependencies](https://md.research.elamur.ai/free/papers/surdeanu-2008-conll-2008-shared-task-joint/)
- [Evaluating Universal Dependency Parser Recovery of Predicate Argument Structure via CompChain Analysis](https://md.research.elamur.ai/free/papers/ud-2021-indurkhya-evaluating-universal-dependency-parser-recovery/)
- [A Two-Stage Parsing Method for Text-Level Discourse Analysis](https://md.research.elamur.ai/free/papers/wang-2017-two-stage-parsing-method-text/)
- [A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing](https://md.research.elamur.ai/free/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{nivre2006labeled,
  title = {{Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines}},
  author = {Nivre, Joakim and Hall, Johan and Nilsson, Jens and Eryiǧit, Gülşen and Marinov, Svetoslav},
  booktitle = {Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X)},
  year = {2006},
  doi = {10.3115/1596276.1596318},
  url = {https://doi.org/10.3115/1596276.1596318}
}
```

- [← previous Kernel-Based Pronoun Resolution with Structured Syntactic Knowledge](https://md.research.elamur.ai/free/papers/yang-2006-kernel-based-pronoun-resolution-structured/)
- [next → Learning Accurate, Compact, and Interpretable Tree Annotation](https://md.research.elamur.ai/free/papers/aclbulk-2006-petrov-learning-accurate-compact-interpretable-tree/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/papers/2006/)

## References

28 references, 6 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, volume 20 of Text, Speech and Language Technology. Kluwer Academic Publishers, Dordrecht. [find](https://scholar.google.com/scholar?q=A%2E+Abeille%CC%81%2C+editor%2E+2003%2E+Treebanks%3A+Building+and+Using+Parsed+Corpora%2C+volume+20+of+Text%2C+Speech+and+Language+Technology%2E+Kluwer+Academic+Publishers%2C+Dordrecht%2E)
2. S. Afonso, E. Bick, R. Haber, and D. Santos. 2002. “Floresta sintá(c)tica”: a treebank for Portuguese. In Proc. of LREC-2002, pages 1698–1703. [find](https://scholar.google.com/scholar?q=S%2E+Afonso%2C+E%2E+Bick%2C+R%2E+Haber%2C+and+D%2E+Santos%2E+2002%2E+%E2%80%9CFloresta+sinta%CC%81%28c%29tica%E2%80%9D%3A+a+treebank+for+Portuguese%2E+In+Proc%2E+of+LREC%2D2002%2C+pages+1698%E2%80%931703%2E) [our card](https://md.research.elamur.ai/free/papers/afonso-2002-floresta-sinta-c-tica-treebank/)
3. N. B. Atalay, K. Oflazer, and B. Say. 2003. The annotation process in the Turkish treebank. In Proc. of LINC-2003. [find](https://scholar.google.com/scholar?q=N%2E+B%2E+Atalay%2C+K%2E+Oflazer%2C+and+B%2E+Say%2E+2003%2E+The+annotation+process+in+the+Turkish+treebank%2E+In+Proc%2E+of+LINC%2D2003%2E) [our card](https://md.research.elamur.ai/free/papers/atalay-2003-annotation-process-turkish-treebank/)
4. E. Black, F. Jelinek, J. D. Lafferty, D. M. Magerman, R. L. Mercer, and S. Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proc. of the 5th DARPA Speech and Natural Language Workshop, pages 31–37. [find](https://scholar.google.com/scholar?q=E%2E+Black%2C+F%2E+Jelinek%2C+J%2E+D%2E+Lafferty%2C+D%2E+M%2E+Magerman%2C+R%2E+L%2E+Mercer%2C+and+S%2E+Roukos%2E+1992%2E+Towards+history%2Dbased+grammars%3A+Using+richer+models+for+probabilistic+parsing%2E+In+Proc%2E+of+the+5th+DARPA+Speech)
5. 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. [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%2E)
6. S. Brants, S. Dipper, S. Hansen, W. Lezius, and G. Smith. 2002. The TIGER treebank. In Proc. of TLT-2002. [find](https://scholar.google.com/scholar?q=S%2E+Brants%2C+S%2E+Dipper%2C+S%2E+Hansen%2C+W%2E+Lezius%2C+and+G%2E+Smith%2E+2002%2E+The+TIGER+treebank%2E+In+Proc%2E+of+TLT%2D2002%2E)
7. C.-C. Chang and C.-J. Lin, 2001. LIBSVM: A Library for Support Vector Machines. Software available at [http://www.csie.ntu.edu.tw/](http://www.csie.ntu.edu.tw/) cjlin/libsvm. [↗](http://www.csie.ntu.edu.tw/)
8. 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)
9. M. Civit Torruella and Ma A. Martı́ Antonı́n. 2002. Design principles for a Spanish treebank. In Proc. of TLT-2002. [find](https://scholar.google.com/scholar?q=M%2E+Civit+Torruella+and+Ma+A%2E+Mart%C4%B1%CC%81+Anton%C4%B1%CC%81n%2E+2002%2E+Design+principles+for+a+Spanish+treebank%2E+In+Proc%2E+of+TLT%2D2002%2E)
10. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+1999%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
11. S. Džeroski, T. Erjavec, N. Ledinek, P. Pajas, Z. Žabokrtsky, and A. Žele. 2006. Towards a Slovene dependency treebank. In Proc. of LREC-2006. [find](https://scholar.google.com/scholar?q=S%2E+Dz%CC%8Ceroski%2C+T%2E+Erjavec%2C+N%2E+Ledinek%2C+P%2E+Pajas%2C+Z%2E+Z%CC%8Cabokrtsky%2C+and+A%2E+Z%CC%8Cele%2E+2006%2E+Towards+a+Slovene+dependency+treebank%2E+In+Proc%2E+of+LREC%2D2006%2E)
12. G. Eryiğit and K. Oflazer. 2006. Statistical dependency parsing of Turkish. In Proc. of EACL-2006. [find](https://scholar.google.com/scholar?q=G%2E+Eryig%CC%86it+and+K%2E+Oflazer%2E+2006%2E+Statistical+dependency+parsing+of+Turkish%2E+In+Proc%2E+of+EACL%2D2006%2E)
13. 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 NEMLAR-2004, 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+NEMLAR%2D2004%2C+pages+110%E2%80%93117%2E)
14. Y. Kawata and J. Bartels. 2000. Stylebook for the Japanese treebank in VERBMOBIL. Verbmobil-Report 240, Seminar für Sprachwissenschaft, Universität Tübingen. [find](https://scholar.google.com/scholar?q=Y%2E+Kawata+and+J%2E+Bartels%2E+2000%2E+Stylebook+for+the+Japanese+treebank+in+VERBMOBIL%2E+Verbmobil%2DReport+240%2C+Seminar+fu%CC%88r+Sprachwissenschaft%2C+Universita%CC%88t+Tu%CC%88bingen%2E)
15. M. T. Kromann. 2003. The Danish dependency treebank and the underlying linguistic theory. In Proc. of TLT-2003. [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Kromann%2E+2003%2E+The+Danish+dependency+treebank+and+the+underlying+linguistic+theory%2E+In+Proc%2E+of+TLT%2D2003%2E)
16. T. Kudo and Y. Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In Proc. of CoNLL-2002, pages 63–69. [find](https://scholar.google.com/scholar?q=T%2E+Kudo+and+Y%2E+Matsumoto%2E+2002%2E+Japanese+dependency+analysis+using+cascaded+chunking%2E+In+Proc%2E+of+CoNLL%2D2002%2C+pages+63%E2%80%9369%2E)
17. J. Nilsson, J. Hall, and J. Nivre. 2005. MAMBA meets TIGER: Reconstructing a Swedish treebank from antiquity. In Proc. of the NODALIDA Special Session on Treebanks. [find](https://scholar.google.com/scholar?q=J%2E+Nilsson%2C+J%2E+Hall%2C+and+J%2E+Nivre%2E+2005%2E+MAMBA+meets+TIGER%3A+Reconstructing+a+Swedish+treebank+from+antiquity%2E+In+Proc%2E+of+the+NODALIDA+Special+Session+on+Treebanks%2E)
18. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. of ACL-2005, pages 99–106. [find](https://scholar.google.com/scholar?q=J%2E+Nivre+and+J%2E+Nilsson%2E+2005%2E+Pseudo%2Dprojective+dependency+parsing%2E+In+Proc%2E+of+ACL%2D2005%2C+pages+99%E2%80%93106%2E)
19. J. Nivre, J. Hall, and J. Nilsson. 2004. Memory-based dependency parsing. In Proc. CoNLL-2004, pages 49–56. [find](https://scholar.google.com/scholar?q=J%2E+Nivre%2C+J%2E+Hall%2C+and+J%2E+Nilsson%2E+2004%2E+Memory%2Dbased+dependency+parsing%2E+In+Proc%2E+CoNLL%2D2004%2C+pages+49%E2%80%9356%2E) [our card](https://md.research.elamur.ai/free/papers/nivre-2004-memory-based-dependency-parsing/)
20. J. Nivre, J. Hall, and J. Nilsson. 2006. MaltParser: A data-driven parser-generator for dependency parsing. In Proc. of LREC-2006. [find](https://scholar.google.com/scholar?q=J%2E+Nivre%2C+J%2E+Hall%2C+and+J%2E+Nilsson%2E+2006%2E+MaltParser%3A+A+data%2Ddriven+parser%2Dgenerator+for+dependency+parsing%2E+In+Proc%2E+of+LREC%2D2006%2E) [our card](https://md.research.elamur.ai/free/papers/nivre-2006-maltparser-data-driven-parser-generator/)
21. J. Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proc. of IWPT-2003, pages 149–160. [find](https://scholar.google.com/scholar?q=J%2E+Nivre%2E+2003%2E+An+efficient+algorithm+for+projective+dependency+parsing%2E+In+Proc%2E+of+IWPT%2D2003%2C+pages+149%E2%80%93160%2E) [our card](https://md.research.elamur.ai/free/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/)
22. J. Nivre. 2006. Inductive Dependency Parsing. Springer. [find](https://scholar.google.com/scholar?q=J%2E+Nivre%2E+2006%2E+Inductive+Dependency+Parsing%2E+Springer%2E)
23. K. Oflazer, B. Say, D. Zeynep Hakkani-Tür, and G. Tür. 2003. Building a Turkish treebank. In Abeillé (Abeillé, 2003), chapter 15. [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%2E)
24. K. Simov and P. Osenova. 2003. Practical annotation scheme for an HPSG treebank of Bulgarian. In Proc. of LINC-2003, pages 17–24. [find](https://scholar.google.com/scholar?q=K%2E+Simov+and+P%2E+Osenova%2E+2003%2E+Practical+annotation+scheme+for+an+HPSG+treebank+of+Bulgarian%2E+In+Proc%2E+of+LINC%2D2003%2C+pages+17%E2%80%9324%2E)
25. K. Simov, P. Osenova, A. Simov, and M. Kouylekov. 2005. Design and implementation of the Bulgarian HPSG-based treebank. In Journal of Research on Language and Computation – Special Issue, pages 495–522. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=K%2E+Simov%2C+P%2E+Osenova%2C+A%2E+Simov%2C+and+M%2E+Kouylekov%2E+2005%2E+Design+and+implementation+of+the+Bulgarian+HPSG%2Dbased+treebank%2E+In+Journal+of+Research+on+Language+and+Computation+%E2%80%93+Special+Issue%2C+pages+495%E2%80%9352)
26. O. Smrž, J. Šnaidauf, and P. Zemánek. 2002. Prague dependency treebank for Arabic: Multi-level annotation of Arabic corpus. In Proc. of the Intern. Symposium on Processing of Arabic, pages 147–155. [find](https://scholar.google.com/scholar?q=O%2E+Smrz%CC%8C%2C+J%2E+S%CC%8Cnaidauf%2C+and+P%2E+Zema%CC%81nek%2E+2002%2E+Prague+dependency+treebank+for+Arabic%3A+Multi%2Dlevel+annotation+of+Arabic+corpus%2E+In+Proc%2E+of+the+Intern%2E+Symposium+on+Processing+of+Arabic%2C+pages+147%E2%80%93155%2E)
27. L. van der Beek, G. Bouma, R. Malouf, and G. van Noord. 2002. The Alpino dependency treebank. In Computational Linguistics in the Netherlands (CLIN). [find](https://scholar.google.com/scholar?q=L%2E+van+der+Beek%2C+G%2E+Bouma%2C+R%2E+Malouf%2C+and+G%2E+van+Noord%2E+2002%2E+The+Alpino+dependency+treebank%2E+In+Computational+Linguistics+in+the+Netherlands+%28CLIN%29%2E)
28. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT-2003, pages 195–206. [find](https://scholar.google.com/scholar?q=H%2E+Yamada+and+Y%2E+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proc%2E+of+IWPT%2D2003%2C+pages+195%E2%80%93206%2E) [our card](https://md.research.elamur.ai/free/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)