Elamur Research⌕
☰
home / papers / 2005 / Pseudo-Projective Dependency Parsing

Pseudo-Projective Dependency Parsing

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

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

Topics: Dependency parsing · Treebanks

Cited by

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

Cite

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

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

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
  2. Campbell, R. 2004. Using linguistic principles to recover empty categories. In Proceedings of ACL. find
  3. Charniak, E. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL. find our card
  4. Collins, M., Hajič, J., Brill, E., Ramshaw, L. and Tillmann, C. 1999. A statistical parser for Czech. In Proceedings of ACL. find our card
  5. Collins, M. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  6. Covington, M. A. 1990. Parsing discontinuous constituents in dependency grammar. Computational Linguistics, 16:234– 236. find
  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
  8. Dienes, P. and Dubey, A. 2003. Deep syntactic processing by combining shallow methods. In Proceedings of ACL. find
  9. Duchier, D. and Debusmann, R. 2001. Topological dependency trees: A constraint-based account of linear precedence. In Proceedings of ACL. find
  10. Eisner, J. M. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING. find our card
  11. Foth, K., Daum, M. and Menzel, W. 2004. A broad-coverage parser for German based on defeasible constraints. In Proceedings of KONVENS. find
  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
  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
  14. Hajič, J. 1998. Building a syntactically annotated corpus: The Prague Dependency Treebank. In Issues of Valency and Meaning, pages 106–132. Karolinum. find
  15. Hellwig, P. 2003. Dependency unification grammar. In Dependency and Valency, pages 593–635. Walter de Gruyter. find
  16. Holan, T., Kuboň, V. and Plátek, M. 2001. Word-order relaxations and restrictions within a dependency grammar. In Proceedings of IWPT. find
  17. Holan, T. 2004. Tvorba zavislostniho syntaktickeho analyza-toru. In Proceedings of MIS’2004. find
  18. Jijkoun, V. and de Rijke, M. 2004. Enriching the output of a parser using memory-based learning. In Proceedings of ACL. find
  19. Johnson, M. 2002. A simple pattern-matching algorithm for recovering empty nodes and their antecedents. In Proceedings of ACL. find
  20. Kahane, S., Nasr, A. and Rambow, O. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In Proceedings of ACL-COLING. find
  21. Kromann, M. T. 2003. The Danish Dependency Treebank and the DTAG treebank tool. In Proceedings of TLT 2003. find
  22. Levy, R. and Manning, C. 2004. Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation. In Proceedings of ACL. find
  23. Mel’čuk, I. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
  24. Nivre, J. and Scholz, M. 2004. Deterministic dependency parsing of English text. In Proceedings of COLING. find our card
  25. Nivre, J., Hall, J. and Nilsson, J. 2004. Memory-based dependency parsing. In Proceedings of CoNLL. find our card
  26. Nivre, J. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of IWPT. find our card
  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
  28. Oflazer, K. 2003. Dependency parsing with an extended finite-state approach. Computational Linguistics, 29:515–544. find
  29. Sleator, D. and Temperley, D. 1993. Parsing English with a link grammar. In Proceedings of IWPT. find our card
  30. Tapanainen, P. and Järvinen, T. 1997. A non-projective dependency parser. In Proceedings of ANLP. find our card
  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
  32. Yamada, H. and Matsumoto, Y. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/