An Empirical Comparison of Parsing Methods for Stanford Dependencies

What it is about

Stanford dependencies are usually obtained by parsing to constituents and then applying head rules (c-parsing), which is slow. The authors re-examine whether direct dependency parsing (d-parsing) can now match it. On PTB section 22 and 23 with BASIC dependencies, the Charniak-Johnson c-parser gives UAS 93.91 and 94.38, while the best d-parser (Full TurboParser) gives 92.29 and 92.20 at about twice the speed of the c-parser, and a basic first-order TurboParser gives 90.25 at about twenty times the speed of the Stanford English PCFG. The gap for CC-processed dependencies falls to about 2.6 F1 points. Three further gains are reported: part-of-speech tags from the Berkeley parser, which tags as part of phrase-structure parsing, narrow the gap (about one point for the d-parsers), Brown-cluster features add about 0.7 UAS to the best d-parser, and stacking on Yamada-Matsumoto dependencies adds about 1.5 LAS points over MSTParser alone.

Ideas

• I1. en/src/ptag.rs and en/src/parse.rs: measure the LAS loss of the Mova parser that comes from tagger errors, by parsing EWT test with gold UPOS and with predicted UPOS, as the paper does for POS tags; this is the first number to get before any parser change.
• I2. en/src/parse.rs features: Brown-style clusters learned from our own open corpus in $MOVA_DATA (not from third-party text), used in place of word forms for rare words; measure LAS on EWT test against the current 80.24 LAS, run twice.
• I3. A stacked second pass: a second en parser trained on another representation (for example the constituency-converted trees from en/src/convert.rs) whose predicted arcs become features for the first; measure LAS on EWT test and the time per sentence, as the paper does.
• I4. en beam-curve in the paper's speed-accuracy layout: the arc-factored point against the beam-8 point and the gparse point, measured on EWT test in tokens per second on the same machine.

For Mova

Touches languages/en/20-syntax-overview, 10-word-classes (tagger input) and 13-verbs, and the en crate (ptag.rs, parse.rs, convert.rs), en beam-curve and gparse for the GPU comparison. The paper's PTB numbers are research-licensed: use them as a reference only. Measure first the gold-tag and predicted-tag LAS on EWT test, because it decides how much tagging work is worth doing before parser work.

Topics: Part-of-speech tagging

Cite

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

@misc{kong2014empirical,
  title = {{An Empirical Comparison of Parsing Methods for Stanford Dependencies}},
  author = {Kong, Lingpeng and Smith, Noah A.},
  year = {2014},
  eprint = {1404.4314},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1404.4314}
}

References

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

1. J. Björne, J. Heimonen, F. Ginera, A. Airola, T. Pahkkala, and T. Salakoski. Extracting complex biological events with rich graph-based feature sets. In Proc. of BioNLP the Workshop on Current Trends in Biomedical Natural Language Processing: Shared Task, 2009. find
2. B. Bohnet. Very high accuracy and fast dependency parsing is not a contradiction. In Proc. of COLING, 2010. find
3. P. Brown, P. Desouza, R. Mercer, V. Pietra, and J. Lai. Class-based n-gram models of natural language. Computational linguistics, 18(4):467–479, 1992. find
4. D. Cer, M. C. de Marneffe, D. Jurafsky, and C. D Manning. Parsing to Stanford dependencies: Trade-offs between speed and accuracy. In Proc. of LREC, 2010. find our card
5. Ö. Çetinoğlu, J. Foster, J. Nivre, D. Hogan, A. Cahill, and J. Genabith. LFG without C-structures. In Proc. of TLT, 2010. find
6. C. Chang and C. Lin. Libsvm: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27, 2011. find
7. E. Charniak and M. Johnson. Coarse-to-fine n-best parsing and maxent discriminative reranking. In Proc. of ACL, 2005. find our card
8. PTB §22 UAS LAS 90.06 87.17 93.11 90.16 92.16 89.50 92.82 90.14 92.29 89.64 92.96 90.31 PTB §23 UAS LAS 90.09 87.48 92.80 90.10 91.95 89.40 92.50 89.95 92.20 89.67 92.75 90.20 Speed (tokens/s.) 123.63 66.57 413.67 243.83 209.98 179.26 E. Charniak, D. Blaheta, N. Ge, K. Hall, J. Hale, and M. Johnson. Bllip 1987-89 wsj corpus release 1. find
9. Linguistic Data Consortium, Philadelphia, 2000. find
10. W. Che, V. I. Spitkovsky, and T. Liu. A comparison of Chinese parsers for Stanford dependencies. In Proc. of ACL, 2012. find
11. J. Choi and A. McCallum. Transition-based dependency parsing with selectional branching. In Proc. of ACL, 2013. find
12. R. Collobert and J. Weston. A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proc. of ICML, 2008. find
13. M. C. de Marneffe and C. D Manning. The Stanford typed dependencies representation. In Proc. of COLING workshop on Cross-Framework and Cross-Domain Parser Evaluation, 2008. find our card
14. M. C. de Marneffe, B. MacCartney, and C. D. Manning. Generating typed dependency parses from phrase structure parses. In Proc. of LREC, 2006. find our card
15. J. Elming, A. Johannsen, S. Klerke, E. Lapponi, H. Martinez, and A. Søgaard. Down-stream effects of tree-to-dependency conversions. In Proc. of NAACL-HLT, 2013. find
16. R. Fan, K. Chang, C. Hsieh, X. Wang, and C. Lin. Liblinear: A library for large linear classification. The Journal of Machine Learning Research, 9:1871–1874, 2008. find
17. Y. Goldberg and M. Elhadad. An efficient algorithm for easy-first non-directional dependency parsing. In Proc. of ACL, 2010. find
18. D. Graff. North american news text corpus, 1995. find
19. J. Hatori, T. Matsuzaki, Y. Miyao, and J. Tsujii. Incremental joint pos tagging and dependency parsing in chinese. In Proc. of IJCNLP, 2011. find
20. L. Huang and K. Sagae. Dynamic programming for linear-time incremental parsing. In Proc. of ACL, 2010. find
21. L. Huang, S. Fayong, and Y. Guo. Structured perceptron with inexact search. In Proc. of NAACL-HLT, 2012. find our card
22. D. Klein and C. D. Manning. Accurate unlexicalized parsing. In Proc. of ACL, 2003. find our card
23. T. Koo and M. Collins. Efficient third-order dependency parsers. In Proc. of ACL, 2010. find
24. T. Koo, X. Carreras, and M. Collins. Simple semi-supervised dependency parsing. In Proc. of ACL, 2008. find
25. D. Lewis, Y. Yang, T. Rose, and F. Li. Rcv1: A new benchmark collection for text categorization research. The Journal of Machine Learning Research, 5:361–397, 2004. find
26. Z. Li, M. Zhang, W. Che, T. Liu, W. Chen, and H. Li. Joint models for chinese pos tagging and dependency parsing. In Proc. of EMNLP, 2011. find
27. A. F. T Martins, D. Das, N. A. Smith, and E. P. Xing. Stacking dependency parsers. In Proc. of EMNLP, 2008. find
28. A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T. Figueiredo, and P. M. Q. Aguiar. Turbo parsers: Dependency parsing by approximate variational inference. In Proc. of EMNLP, 2010. find
29. A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and M. A. T. Figueiredo. Dual decomposition with many overlapping components. In Proc. of EMNLP, 2011. find
30. A. F. T. Martins, M. Almeida, and N. A. Smith. Turning on the turbo: Fast third-order non-projective turbo parsers. In Proc. of ACL, 2013. find our card
31. D. McClosky, E. Charniak, and M. Johnson. Effective self-training for parsing. In Proc. of NAACL-HLT, 2006. find our card
32. R. McDonald and F. Pereira. Online learning of approximate dependency parsing algorithms. In Proc. of EACL, 2006. find our card
33. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP, 2005. find our card
34. J. Nivre. Incrementality in deterministic dependency parsing. In Proc. of ACL Workshop on Incremental Parsing: Bringing Engineering and Cognition Together, 2004. find our card
35. J. Nivre. Non-projective dependency parsing in expected linear time. In Proc. of ACL-IJCNLP, 2009. find
36. J. Nivre and R. McDonald. Integrating graph-based and transition-based dependency parsers. In Proc. of ACL-HLT, 2008. find
37. J. Nivre, J. Hall, and J. Nilsson. Maltparser: A data-driven parser-generator for dependency parsing. In Proc. of LREC, 2006. find
38. J. Nivre, M. Kuhlmann, and J. Hall. An improved oracle for dependency parsing with online reordering. In Proc. of IWPT, 2009. find
39. S. Petrov, L. Barrett, R. Thibaux, and D. Klein. Learning accurate, compact, and interpretable tree annotation. In Proc. of COLING-ACL, 2006. find our card
40. A. M. Rush and S. Petrov. Vine pruning for efficient multi-pass dependency parsing. In Proc. of NAACL, 2012. find
41. R. Socher, J. Bauer, C. D. Manning, and A. Ng. Parsing with compositional vector grammars. In Proc. of ACL, 2013. find
42. D. Stein, S. Peitz, D. Vilar, and H. Ney. A cocktail of deep syntactic features for hierarchical machine translation. In Proc. of AMTA, 2010. find
43. J. Tetreault, J. Foster, and M. Chodorow. Using parse features for preposition selection and error detection. In Proc. of ACL, 2010. find
44. K. Toutanova, D. Klein, C. D. Manning, and Y. Singer. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proc. of COLING-ACL, 2003. find
45. J. Turian, L. Ratinov, and Y. Bengio. Word representations: a simple and general method for semi-supervised learning. In Proc. of ACL, 2010. find
46. H. Yamada and Y. Matsumoto. Statistical dependency analysis with support vector machines. In Proc. of IWPT, 2003. find our card
47. H. Zhang, L. Huang, K. Zhao, and R. McDonald. Online learning for inexact hypergraph search. In Proc. of EMNLP, 2013. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/enud-2014-kong-empirical-comparison-parsing-methods-stanford/