---
title: "Pseudo-Projective Dependency Parsing — Nivre 2005"
description: "Many treebanks, including the Prague Dependency Treebank, contain non-projective (crossing) dependencies, but efficient data-driven dependency parsers…"
authors: ["Joakim Nivre", "Jens Nilsson"]
year: 2005
venue: "Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)"
source: "https://aclanthology.org/P05-1013/"
doi: "10.3115/1219840.1219853"
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/nivre-2005-pseudo-projective-dependency-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2005](https://md.research.elamur.ai/free/en/papers/2005/) / Pseudo-Projective Dependency Parsing

# Pseudo-Projective Dependency Parsing

**Authors:** [Joakim Nivre](https://md.research.elamur.ai/free/en/authors/joakim-nivre/), [Jens Nilsson](https://md.research.elamur.ai/free/en/authors/jens-nilsson/) · **Year:** 2005 · **Venue:** Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05) · **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/P05-1013/) · [PDF](https://aclanthology.org/P05-1013.pdf) · [DOI 10.3115/1219840.1219853](https://doi.org/10.3115/1219840.1219853) · [OpenAlex](https://openalex.org/W2161795601)

**Citations:** 292 citations (OpenAlex, 2026-10-14) · [169](https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/cited-by/) in our library, of the 140884 papers whose bibliographies we read

## Summary
Many treebanks, including the Prague Dependency Treebank, contain non-projective (crossing) dependencies, but efficient data-driven dependency parsers usually build only projective trees. Such parsers can never fully match the gold annotation. Only 1–2% of arcs are non-projective, but they affect 15–25% of sentences. Nivre and Nilsson keep a fast deterministic projective parser and wrap it in graph transformations. Before training, each non-projective tree is made projective with a minimal sequence of single-step "lifts." Each lift moves a dependent up to the head of its head, and the lift is recorded in enriched arc labels. The parser, which uses memory-based classifiers built with TiMBL, learns to predict these labels. A deterministic breadth-first search then uses the predicted labels to lower lifted arcs back to their likely true heads. Three label-encoding schemes (Head, Head+Path, Path) are compared on Czech data. The pseudo-projective system clearly outperforms both a plain projective baseline and direct training on non-projective trees, with the largest gain on exact match. It achieved the best reported robust non-projective parsing results for Czech at the time.

## Key points
- Data: the Prague Dependency Treebank is used for full parsing experiments. Both PDT and the Danish Dependency Treebank are used to evaluate the transformations alone. POS tags come from the treebank's uncorrected HMM tagger output.
- Parsing accuracy on PDT:
  - Training directly on non-projective trees gives UAS 78.5 and LAS 71.3.
  - The projectivized baseline without special labels gives 79.1 and 72.0.
  - Head+Path gives 80.0 UAS and 72.8 LAS.
  - Head+Path raises unlabeled exact match from 29.2 to 31.8.
- All gains over the baseline are significant at p \< 0.01 (McNemar's test). Differences among the three encoding schemes in overall accuracy are negligible.
- On non-projective arcs alone, Head+Path scores best, with a labeled F of 54.0 versus 52.4 for Head and 48.2 for Path. Path is significantly worse than Head+Path.
- The previous best robust non-projective parser for Czech reached 73% UAS (Holan, 2004). Strong projective parsers, Collins at 82% and an adapted Charniak at 84%, still outperform this approach.

## Interesting ideas
- **Encode a structural transformation in the labels, then invert it afterwards.** A restricted model can thus output structures it cannot represent directly. The same trick could let simple taggers or parsers handle discontinuities, coordination, or other awkward annotations.
- **Choose the smallest transformation that removes the problem.** The method lifts the shortest non-projective arc first, one step at a time, which keeps the transformed training data as close to the original as possible. This principle suits any preprocessing that bends gold data to fit a model.
- **Weigh label informativeness against learnability.** Richer labels make reconstruction easier but enlarge the label set, quadratically for Head and only linearly for Path. Comparing several encodings openly is a good template whenever labels are augmented, for example in Ukrainian UD morphosyntactic tagging.
- **Score the transformation separately from the full system.** The authors first test how well the round-trip conversion recovers gold trees and only then evaluate end-to-end parsing. This separates the loss caused by the encoding from the loss caused by the learner.
- **Report sentence-level and phenomenon-specific metrics.** Rare constructions barely change attachment score but noticeably improve exact match and precision/recall on the targeted arcs. Measuring these exposes progress that token-level averages hide.

*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/)

## Cite

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

```bibtex
@inproceedings{nivre2005pseudo,
  title = {{Pseudo-Projective Dependency Parsing}},
  author = {Nivre, Joakim and Nilsson, Jens},
  booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
  year = {2005},
  doi = {10.3115/1219840.1219853},
  url = {https://doi.org/10.3115/1219840.1219853}
}
```

- [← previous Edinburgh System Description for the 2005 IWSLT Speech Translation Evaluation](https://md.research.elamur.ai/free/en/papers/koehn-2005-edinburgh-system-description-2005-iwslt/)
- [next → Reading Level Assessment Using Support Vector Machines and Statistical Language Models](https://md.research.elamur.ai/free/en/papers/schwarm-2005-reading-level-assessment-support-vector/)
- [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/)

## References

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

1. Cahill, A., Burke, M., O’Donovan, R., Van Genabith, J. and Way, A. 2004. Long-distance dependency resolution in automatically acquired wide-coverage PCFG-based LFG approximations. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Cahill%2C+A%2E%2C+Burke%2C+M%2E%2C+O%E2%80%99Donovan%2C+R%2E%2C+Van+Genabith%2C+J%2E+and+Way%2C+A%2E+2004%2E+Long%2Ddistance+dependency+resolution+in+automatically+acquired+wide%2Dcoverage+PCFG%2Dbased+LFG+approximations%2E+In+Proceedings+of+AC)
2. Campbell, R. 2004. Using linguistic principles to recover empty categories. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Campbell%2C+R%2E+2004%2E+Using+linguistic+principles+to+recover+empty+categories%2E+In+Proceedings+of+ACL%2E)
3. Charniak, E. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL. [find](https://scholar.google.com/scholar?q=Charniak%2C+E%2E+2000%2E+A+maximum%2Dentropy%2Dinspired+parser%2E+In+Proceedings+of+NAACL%2E) [our card](https://md.research.elamur.ai/free/en/papers/charniak-2000-maximum-entropy-inspired-parser/)
4. Collins, M., Hajič, J., Brill, E., Ramshaw, L. and Tillmann, C. 1999. A statistical parser for Czech. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Collins%2C+M%2E%2C+Hajic%CC%8C%2C+J%2E%2C+Brill%2C+E%2E%2C+Ramshaw%2C+L%2E+and+Tillmann%2C+C%2E+1999%2E+A+statistical+parser+for+Czech%2E+In+Proceedings+of+ACL%2E) [our card](https://md.research.elamur.ai/free/en/papers/collins-1999-statistical-parser-czech/)
5. Collins, M. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Collins%2C+M%2E+1999%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
6. Covington, M. A. 1990. Parsing discontinuous constituents in dependency grammar. Computational Linguistics, 16:234– 236. [find](https://scholar.google.com/scholar?q=Covington%2C+M%2E+A%2E+1990%2E+Parsing+discontinuous+constituents+in+dependency+grammar%2E+Computational+Linguistics%2C+16%3A234%E2%80%93+236%2E)
7. Daelemans, W., Zavrel, J., van der Sloot, K. and van den Bosch, A. 2003. TiMBL: Tilburg Memory Based Learner, version 5.0, Reference Guide. Technical Report ILK 03-10, Tilburg University, ILK. [find](https://scholar.google.com/scholar?q=Daelemans%2C+W%2E%2C+Zavrel%2C+J%2E%2C+van+der+Sloot%2C+K%2E+and+van+den+Bosch%2C+A%2E+2003%2E+TiMBL%3A+Tilburg+Memory+Based+Learner%2C+version+5%2E0%2C+Reference+Guide%2E+Technical+Report+ILK+03%2D10%2C+Tilburg+University%2C+ILK%2E)
8. Dienes, P. and Dubey, A. 2003. Deep syntactic processing by combining shallow methods. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Dienes%2C+P%2E+and+Dubey%2C+A%2E+2003%2E+Deep+syntactic+processing+by+combining+shallow+methods%2E+In+Proceedings+of+ACL%2E)
9. Duchier, D. and Debusmann, R. 2001. Topological dependency trees: A constraint-based account of linear precedence. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Duchier%2C+D%2E+and+Debusmann%2C+R%2E+2001%2E+Topological+dependency+trees%3A+A+constraint%2Dbased+account+of+linear+precedence%2E+In+Proceedings+of+ACL%2E)
10. Eisner, J. M. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING. [find](https://scholar.google.com/scholar?q=Eisner%2C+J%2E+M%2E+1996%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proceedings+of+COLING%2E) [our card](https://md.research.elamur.ai/free/en/papers/ast-1996-eisner-three-new-probabilistic-models-dependency/)
11. Foth, K., Daum, M. and Menzel, W. 2004. A broad-coverage parser for German based on defeasible constraints. In Proceedings of KONVENS. [find](https://scholar.google.com/scholar?q=Foth%2C+K%2E%2C+Daum%2C+M%2E+and+Menzel%2C+W%2E+2004%2E+A+broad%2Dcoverage+parser+for+German+based+on+defeasible+constraints%2E+In+Proceedings+of+KONVENS%2E)
12. Hajič, J., Krbec, P., Oliva, K., Kveton, P. and Petkevic, V. 2001. Serial combination of rules and statistics: A case study in Czech tagging. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Hajic%CC%8C%2C+J%2E%2C+Krbec%2C+P%2E%2C+Oliva%2C+K%2E%2C+Kveton%2C+P%2E+and+Petkevic%2C+V%2E+2001%2E+Serial+combination+of+rules+and+statistics%3A+A+case+study+in+Czech+tagging%2E+In+Proceedings+of+ACL%2E)
13. Hajič, J., Vidova Hladka, B., Panevová, J., Hajičová, E., Sgall, P. and Pajas, P. 2001. Prague Dependency Treebank 1.0. LDC, 2001T10. [find](https://scholar.google.com/scholar?q=Hajic%CC%8C%2C+J%2E%2C+Vidova+Hladka%2C+B%2E%2C+Panevova%CC%81%2C+J%2E%2C+Hajic%CC%8Cova%CC%81%2C+E%2E%2C+Sgall%2C+P%2E+and+Pajas%2C+P%2E+2001%2E+Prague+Dependency+Treebank+1%2E0%2E+LDC%2C+2001T10%2E)
14. Hajič, J. 1998. Building a syntactically annotated corpus: The Prague Dependency Treebank. In Issues of Valency and Meaning, pages 106–132. Karolinum. [find](https://scholar.google.com/scholar?q=Hajic%CC%8C%2C+J%2E+1998%2E+Building+a+syntactically+annotated+corpus%3A+The+Prague+Dependency+Treebank%2E+In+Issues+of+Valency+and+Meaning%2C+pages+106%E2%80%93132%2E+Karolinum%2E)
15. Hellwig, P. 2003. Dependency unification grammar. In Dependency and Valency, pages 593–635. Walter de Gruyter. [find](https://scholar.google.com/scholar?q=Hellwig%2C+P%2E+2003%2E+Dependency+unification+grammar%2E+In+Dependency+and+Valency%2C+pages+593%E2%80%93635%2E+Walter+de+Gruyter%2E)
16. Holan, T., Kuboň, V. and Plátek, M. 2001. Word-order relaxations and restrictions within a dependency grammar. In Proceedings of IWPT. [find](https://scholar.google.com/scholar?q=Holan%2C+T%2E%2C+Kubon%CC%8C%2C+V%2E+and+Pla%CC%81tek%2C+M%2E+2001%2E+Word%2Dorder+relaxations+and+restrictions+within+a+dependency+grammar%2E+In+Proceedings+of+IWPT%2E)
17. Holan, T. 2004. Tvorba zavislostniho syntaktickeho analyza-toru. In Proceedings of MIS’2004. [find](https://scholar.google.com/scholar?q=Holan%2C+T%2E+2004%2E+Tvorba+zavislostniho+syntaktickeho+analyza%2Dtoru%2E+In+Proceedings+of+MIS%E2%80%992004%2E)
18. Jijkoun, V. and de Rijke, M. 2004. Enriching the output of a parser using memory-based learning. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Jijkoun%2C+V%2E+and+de+Rijke%2C+M%2E+2004%2E+Enriching+the+output+of+a+parser+using+memory%2Dbased+learning%2E+In+Proceedings+of+ACL%2E)
19. Johnson, M. 2002. A simple pattern-matching algorithm for recovering empty nodes and their antecedents. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Johnson%2C+M%2E+2002%2E+A+simple+pattern%2Dmatching+algorithm+for+recovering+empty+nodes+and+their+antecedents%2E+In+Proceedings+of+ACL%2E)
20. Kahane, S., Nasr, A. and Rambow, O. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In Proceedings of ACL-COLING. [find](https://scholar.google.com/scholar?q=Kahane%2C+S%2E%2C+Nasr%2C+A%2E+and+Rambow%2C+O%2E+1998%2E+Pseudo%2Dprojectivity%3A+A+polynomially+parsable+non%2Dprojective+dependency+grammar%2E+In+Proceedings+of+ACL%2DCOLING%2E)
21. Kromann, M. T. 2003. The Danish Dependency Treebank and the DTAG treebank tool. In Proceedings of TLT 2003. [find](https://scholar.google.com/scholar?q=Kromann%2C+M%2E+T%2E+2003%2E+The+Danish+Dependency+Treebank+and+the+DTAG+treebank+tool%2E+In+Proceedings+of+TLT+2003%2E)
22. Levy, R. and Manning, C. 2004. Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Levy%2C+R%2E+and+Manning%2C+C%2E+2004%2E+Deep+dependencies+from+context%2Dfree+statistical+parsers%3A+Correcting+the+surface+dependency+approximation%2E+In+Proceedings+of+ACL%2E)
23. Mel’čuk, I. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. [find](https://scholar.google.com/scholar?q=Mel%E2%80%99c%CC%8Cuk%2C+I%2E+1988%2E+Dependency+Syntax%3A+Theory+and+Practice%2E+State+University+of+New+York+Press%2E)
24. Nivre, J. and Scholz, M. 2004. Deterministic dependency parsing of English text. In Proceedings of COLING. [find](https://scholar.google.com/scholar?q=Nivre%2C+J%2E+and+Scholz%2C+M%2E+2004%2E+Deterministic+dependency+parsing+of+English+text%2E+In+Proceedings+of+COLING%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2004-nivre-deterministic-dependency-parsing-english-text/)
25. Nivre, J., Hall, J. and Nilsson, J. 2004. Memory-based dependency parsing. In Proceedings of CoNLL. [find](https://scholar.google.com/scholar?q=Nivre%2C+J%2E%2C+Hall%2C+J%2E+and+Nilsson%2C+J%2E+2004%2E+Memory%2Dbased+dependency+parsing%2E+In+Proceedings+of+CoNLL%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2004-memory-based-dependency-parsing/)
26. Nivre, J. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of IWPT. [find](https://scholar.google.com/scholar?q=Nivre%2C+J%2E+2003%2E+An+efficient+algorithm+for+projective+dependency+parsing%2E+In+Proceedings+of+IWPT%2E) [our card](https://md.research.elamur.ai/free/en/papers/parsers-2003-nivre-efficient-algorithm-projective-dependency-parsing/)
27. Oflazer, K., Say, B., Hakkani-Tür, D. Z. and Tür, G. 2003. Building a Turkish treebank. In Treebanks: Building and Using Parsed Corpora, pages 261–277. Kluwer Academic Publishers. [find](https://scholar.google.com/scholar?q=Oflazer%2C+K%2E%2C+Say%2C+B%2E%2C+Hakkani%2DTu%CC%88r%2C+D%2E+Z%2E+and+Tu%CC%88r%2C+G%2E+2003%2E+Building+a+Turkish+treebank%2E+In+Treebanks%3A+Building+and+Using+Parsed+Corpora%2C+pages+261%E2%80%93277%2E+Kluwer+Academic+Publishers%2E)
28. Oflazer, K. 2003. Dependency parsing with an extended finite-state approach. Computational Linguistics, 29:515–544. [find](https://scholar.google.com/scholar?q=Oflazer%2C+K%2E+2003%2E+Dependency+parsing+with+an+extended+finite%2Dstate+approach%2E+Computational+Linguistics%2C+29%3A515%E2%80%93544%2E)
29. Sleator, D. and Temperley, D. 1993. Parsing English with a link grammar. In Proceedings of IWPT. [find](https://scholar.google.com/scholar?q=Sleator%2C+D%2E+and+Temperley%2C+D%2E+1993%2E+Parsing+English+with+a+link+grammar%2E+In+Proceedings+of+IWPT%2E) [our card](https://md.research.elamur.ai/free/en/papers/parsers-1993-sleator-parsing-english-link-grammar/)
30. Tapanainen, P. and Järvinen, T. 1997. A non-projective dependency parser. In Proceedings of ANLP. [find](https://scholar.google.com/scholar?q=Tapanainen%2C+P%2E+and+Ja%CC%88rvinen%2C+T%2E+1997%2E+A+non%2Dprojective+dependency+parser%2E+In+Proceedings+of+ANLP%2E) [our card](https://md.research.elamur.ai/free/en/papers/tapanainen-1997-non-projective-dependency-parser/)
31. Wang, W. and Harper, M. P. 2004. A statistical constraint dependency grammar (CDG) parser. In Proceedings of the Workshop in Incremental Parsing (ACL). [find](https://scholar.google.com/scholar?q=Wang%2C+W%2E+and+Harper%2C+M%2E+P%2E+2004%2E+A+statistical+constraint+dependency+grammar+%28CDG%29+parser%2E+In+Proceedings+of+the+Workshop+in+Incremental+Parsing+%28ACL%29%2E)
32. Yamada, H. and Matsumoto, Y. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT. [find](https://scholar.google.com/scholar?q=Yamada%2C+H%2E+and+Matsumoto%2C+Y%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proceedings+of+IWPT%2E) [our card](https://md.research.elamur.ai/free/en/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)