Parsing to Stanford Dependencies: Trade-offs between Speed and Accuracy

What it is about

The authors compare ways of producing Stanford Dependencies quickly. One group is constituency parsers (Stanford, Charniak, Charniak-Johnson reranker, Bikel, Berkeley) followed by a conversion to dependencies; the other is dependency parsers trained directly on the basic dependencies (MaltParser's Nivre variants, Covington, MSTParser's Eisner algorithm), plus the rule-based RelEx. They use Penn Treebank section 22. The reranking parser is most accurate (89.1% labeled attachment F1) but takes about ten minutes. The fast Malt-based parsers take about 16 seconds but score around 76%. Nivre Eager with feature interactions reaches 81.1% in about three and a half minutes. Tuning the reranker's search space gives a balanced setting that is nearly as accurate and much faster. The reranker runs fastest with two threads, not four.

Ideas

• I1. en beam-curve: plot LAS against seconds per 1,000 tokens for beams 1, 2, 4, 8 and 16 on EWT test, and pick the knee of the curve as the paper picks its balanced setting; Mova's beam 8 gives LAS 80.24 against 79.0 for greedy.
• I2. gparse/src/eisner.rs: compare exact Eisner decoding with greedy argmax over the biaffine scores, measuring LAS and seconds on EWT test; the paper's gap between MST and Malt (78.8 against 76.3) shows what exact decoding buys.
• I3. en batch annotation: measure throughput with 1, 2 and 4 threads on the school corpus, and check that the outputs stay byte-identical, as the determinism rule requires.

For Mova

Touches 20. Syntax: the Universal Dependencies frame. The speed trade-off decides how many silver sentences the annot pipeline can parse per run. Measure I1 first, since en beam-curve already exists and needs no new code.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.63317/3aixhxswiwe3

@inproceedings{cer2010parsing,
  title = {{Parsing to Stanford Dependencies: Trade-offs between Speed and Accuracy}},
  author = {Cer, Daniel and Marneffe, Marie-Catherine de and Jurafsky, Dan and Manning, Chris},
  booktitle = {Proceedings of the Seventh International Conference on Language Resources and Evaluation (LREC'10)},
  year = {2010},
  doi = {10.63317/3aixhxswiwe3},
  url = {https://doi.org/10.63317/3aixhxswiwe3}
}

References

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

1. Rod Adams, Gabriel Nicolae, Cristina Nicolae, and Sanda Harabagiu. 2007. Textual entailment through extended lexical overlap and lexico-semantic matching. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pages 119–124, Prague, June. find
2. Michele Banko, Michael J. Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni. 2007. Open information extraction from the web. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). find
3. Daniel M. Bikel. 2004. A distributional analysis of a lexicalized statistical parsing model. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP 2004). find
4. Jari Björne, Juho Heimonen, Filip Ginter, Antti Airola, Tapio Pahikkala, and Tapio Salakoski. 2009. Extracting complex biological events with rich graph-based feature sets. In Proceedings of the Association for Computational Linguistics Workshop on BioNLP: Shared Task. find
5. Catherine Blake. 2007. The role of sentence structure in recognizing textual entailment. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pages 101–106, Prague, June. find
6. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine n-best parsing and maxent discriminative reranking. In Proceedings of the 43rd Annual Meeting of the ACL. find our card
7. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL-2000. find
8. Andrew B. Clegg and Adrian J. Shepherd. 2007. Benchmarking natural-language parsers for biological applications using dependency graphs. BMC Bioinformatics, 8(24). find
9. Andrew B. Clegg. 2008. Computational-Linguistic Approaches to Biological Text Mining. Ph.D. thesis, School of Crystallography, Birkbeck, University of London. find
10. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference. find
11. Marie-Catherine de Marneffe and Christopher D. Manning. 2008. The Stanford typed dependencies representation. In COLING Workshop on Cross-framework and Cross-domain Parser Evaluation. find our card
12. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In 5th International Conference on Language Resources and Evaluation (LREC 2006). find our card
13. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96), pages 340–345, Copenhagen, August. find our card
14. Cory B. Giles and Jonathan D. Wren. 2008. Large-scale directional relationship extraction and resolution. BMC Bioinformatics, 9(Suppl 9):S11. find
15. Mark A. Greenwood and Mark Stevenson. 2007. A semi-supervised approach to learning relevant protein-protein interaction articles. In Proceedings of the Second BioCreAtIvE Challenge Workshop, Madrid, Spain. find
16. Stefan Harmeling. 2007. An extensible probabilistic transformation-based approach to the third recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pages 137–142, Prague, June. find
17. Jason S. Kessler. 2008. Polling the blogosphere: a rule-based approach to belief classification. In International Conference on Weblogs and Social Media. find
18. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Meeting of the Association for Computational Linguistics. find our card
19. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLT-EMNLP. find our card
20. Arun Meena and T. V. Prabhakar. 2007. Sentence level sentiment analysis in the presence of conjuncts using linguistic analysis. In Advances in Information Retrieval, volume 4425 of Lecture Notes in Computer Science. Springer. find
21. Yusuke Miyao, Rune Saetre, Kenji Sagae, Takuya Matsuzaki, and Jun’ichi Tsujii. 2008. Task-oriented evaluation of syntactic parsers and their representations. In Proceedings of ACL-08:HLT. find our card
22. Joakim Nivre, Johan Hall, and Jens Nilsson. 2006. Malt-Parser: A data-driven parser-generator for dependency parsing. In Proceedings of the fifth international conference on Language Resources and Evaluation (LREC 2006). find
23. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03). find our card
24. Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of COLING-ACL 2006). find our card
25. Sampo Pyysalo, Filip Ginter, Katri Haverinen, Juho Heimonen, Tapio Salakoski, and Veronika Laippala. 2007. On the unification of syntactic annotations under the Stanford dependency scheme: A case study on BioInfer and GENIA. In Proceedings of BioNLP 2007: Biological, translational, and clinical language processing (ACL07). find
26. Mike Ross and Linas Vepstas, 2008. RelEx. OpenCog Project. http://opencog.org/wiki/RelEx. ↗
27. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of HLT-NAACL 2003. find
28. Jay Urbain, Nazli Goharian, and Ophir Frieder. 2007. find
29. IIT TREC 2007 genomics track: Using concept-based semantics in context for genomics literature passage retrieval. In The Sixteenth Text REtrieval Conference (TREC 2007) Proceedings. find
30. Sofie Van Landeghem, Yvan Saeys, Bernard De Baets, and Yves Van de Peer. 2009. Analyzing text in search of bio-molecular events: a high-precision machine learning framework. In Proceedings of the Association for Computational Linguistics Workshop on BioNLP: Shared Task. find
31. Amal Zouaq, Roger Nkambou, and Claude Frasson. 2007. Building domain ontologies from text for educational purposes. In Proceedings of the Second European Conference on Technology Enhanced Learning: Creating new learning experiences on a global scale. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/bank-2010-cer-parsing-stanford-dependencies-trade-offs/