Elamur Research⌕
☰
home / papers / 2008 / Shift-Reduce Dependency DAG Parsing

Shift-Reduce Dependency DAG Parsing

Paper · 2008 · Kenji Sagae and Jun'ichi Tsujii

Summary

Most data-driven dependency parsers assume a tree, in which every word has exactly one head. Many phenomena need words with several heads, which gives a directed acyclic graph (DAG). Examples are control, relative clauses, long-distance dependencies, anaphora and semantic predicate-argument relations. Sagae and Tsujii extend transition-based shift-reduce parsing to cover these cases, using both Nivre's basic bottom-up algorithm and its arc-eager variant. They add two actions, left-attach and right-attach, which create an arc but keep the dependent available for further heads. The core algorithm outputs projective DAGs. Pseudo-projective transformations and an extra arc-reversing transform recover non-projective arcs. Decisions come from maximum entropy classifiers with beam search. The authors test the approach on English HPSG predicate-argument dependencies from the HPSG Treebank and on the Danish Dependency Treebank. It outperforms tree-only baselines and earlier systems, including McDonald et al.'s graph-based approximate inference and HPSG-based parsers. The method costs about as much as tree parsing. This shows that deeper, graph-shaped analyses can be produced without a full lexicalized grammar formalism.

Key points

  • English HPSG predicate-argument data (labeled): DAG-beam reaches 89.0 precision, 88.5 recall and 88.7 F-score. The comparison systems score lower:
    • a tree-only parser that keeps only each word's closest head: F 87.0, recall 84.3;
    • Sagae et al.: F 88.2;
    • Miyao & Tsujii: F 84.6.
  • Danish Dependency Treebank (unlabeled): DAG-beam scores F 87.2, against 85.0 for tree-only and 85.6 for McDonald et al. Labeled DAG F-score is 82.4.
  • Danish arc types:
    • long-distance dependencies: 83.2 precision, 82.0 recall;
    • anaphoric reference links: 84.9 precision, 84.4 recall.
  • Danish pseudo-projective round trip: transformation followed by detransformation is accurate to 99.4% precision and 98.8% recall. Reducing the beam width to 1 costs only about 1.5 points.
  • Danish data split: the split follows McDonald et al. (2006), and graphs containing cycles were discarded so results are directly comparable.

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

 Institutions

🎓University of Southern CaliforniaLos Angeles · United States162 works · 35,836 citations🎓The University of TokyoTokyo · Japan90 works · 9,156 citations🎓University of ManchesterManchester · United Kingdom87 works · 44,938 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

Cite

Cite as Kenji Sagae and Jun'ichi Tsujii. 2008. Shift-Reduce Dependency DAG Parsing. Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008).

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

@inproceedings{sagae2008shift,
  title = {{Shift-Reduce Dependency DAG Parsing}},
  author = {Kenji Sagae and Jun'ichi Tsujii},
  booktitle = {Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)},
  year = {2008},
  doi = {10.3115/1599081.1599176},
  url = {https://doi.org/10.3115/1599081.1599176}
}

References

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

  1. Briscoe, T., Carroll, J. and Watson, R. 2006. The second release of the RASP system. In Proceedings of the COLING/ACL-06 Demo Session.
  2. Buchholz, Sabine and Erwin Marsi. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X) Shared Task session.
  3. Clark, Stephen, Julia Hockenmaier, and Mark Steedman. 2002. Building Deep Dependency Structures using a Wide-Coverage CCG Parser. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL). find
  4. Covington, Michael A. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the Annual ACM Southeast Conference, 95-102. find
  5. Erkan, Gunes, Arzucan Ozgur, and Dragomir R. Radev. 2007. Semisupervised classification for extracting protein interaction sentences using dependency parsing. In Proceedings of CoNLL-EMNLP. find
  6. Hudson, Richard. 1984. Word Grammar. Oxford: Blackwell. find
  7. Hudson, Richard. 2005. Word Grammar. In K. Brown (Ed.), Encyclopedia of Language and Linguistics (second ed., pp 633-642). Elsevier. find
  8. Hockenmaier, Julia and Mark Steedman. 2007. CCGbank: a corpus of CCG derivations and dependency structures extracted from the Penn Treebank. In Computational Linguistics 33(3), pp 355-396, MIT press.
  9. Kromann, Matthias T. 2003. The Danish dependency treebank and the underlying linguistic theory. In Proceedings of the Second Workshop on Treebanks and Linguistic Theories (TLT). find
  10. McDonald, Ryan and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL).
  11. McDonald, Ryan, Fernando Pereira, Kiril Ribarov and Jan Hajic. 2005. Non-projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT-EMNLP).
  12. Miyao, Yusuke, Takashi Ninomiya, and Jun’ichi Tsujii. 2004. Corpus-oriented grammar development for acquiring a Head-driven Phrase Structure Grammar from the Penn Treebank. In Proceedings of the International Joint Conference on Natural Language Processing (IJCNLP). find
  13. Miyao Yusuke and Jun'ichi Tsujii. 2005. Probabilistic disambiguation models for wide-coverage HPSG parsing. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics.
  14. Nivre, Joakim. 2004. Incrementality in Deterministic Dependency Parsing. In Incremental Parsing: Bringing Engineering and Cognition Together (Workshop at ACL-2004).
  15. Nivre, Joakim, Johan Hall, Sandra Kübler, Ryan McDonald, Jens Nilsson, Sebastian Riedel, Deniz Yuret. 2007. In Proceedings of the CoNLL 2007 Shared Task in the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. find
  16. Nivre, Joakim. and Jens Nilsson. 2005. Pseudo-Projective Dependency Parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 99-106.
  17. Nivre, Joakim. 2007. Incremental non-projective dependency parsing. In Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT’07). find
  18. Saetre, R., Sagae, K., and Tsujii, J. 2007. Syntactic features for protein-protein interaction extraction. In Proceedings of the International Symposium on Languages in Biology and Medicine (LBM short oral presentations). find
  19. Sagae, Kenji., Yusuke Miyao Jun’ichi and Tsujii. 2007. HPSG Parsing with shallow dependency constraints. In Proceedings of the 44th Meeting of the Association for Computational Linguistics. find
  20. Sagae, K., Tsujii, J. 2007. Dependency parsing and domain adaptation with LR models and parser ensembles. In Proceedings of the CoNLL 2007 Shared Task. in EMNLP-CoNLL.
  21. Tsuruoka, Yoshimasa and Tsujii, Jun’ichi. 2005. Bidirectional inference with the easiest-first strategy for tagging sequence data. In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT-EMNLP), pp. 523-530.
  22. Wang, Mengqiu, Noah A. Smith, and Teruko Mitamura. 2007. What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL).

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sagae-2008-shift-reduce-dependency-dag-parsing/