📄 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.

For Mova

• 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.

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.

Cite

Cite as Lingpeng Kong and Noah A. Smith. 2014. An Empirical Comparison of Parsing Methods for Stanford Dependencies. arXiv:1404.4314.

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 = {Lingpeng Kong and Noah A. Smith},
  year = {2014},
  eprint = {1404.4314},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1404.4314}
}

References

47 references, 22 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. our card
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. 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. 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. 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. 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. our card
22. D. Klein and C. D. Manning. Accurate unlexicalized parsing. In Proc. of ACL, 2003. 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. our card
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. our card
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. our card
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. our card
31. D. McClosky, E. Charniak, and M. Johnson. Effective self-training for parsing. In Proc. of NAACL-HLT, 2006. our card
32. R. McDonald and F. Pereira. Online learning of approximate dependency parsing algorithms. In Proc. of EACL, 2006. 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. our card
34. J. Nivre. Incrementality in deterministic dependency parsing. In Proc. of ACL Workshop on Incremental Parsing: Bringing Engineering and Cognition Together, 2004. our card
35. J. Nivre. Non-projective dependency parsing in expected linear time. In Proc. of ACL-IJCNLP, 2009. our card
36. J. Nivre and R. McDonald. Integrating graph-based and transition-based dependency parsers. In Proc. of ACL-HLT, 2008. our card
37. J. Nivre, J. Hall, and J. Nilsson. Maltparser: A data-driven parser-generator for dependency parsing. In Proc. of LREC, 2006. our card
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. 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. our card
45. J. Turian, L. Ratinov, and Y. Bengio. Word representations: a simple and general method for semi-supervised learning. In Proc. of ACL, 2010. our card
46. H. Yamada and Y. Matsumoto. Statistical dependency analysis with support vector machines. In Proc. of IWPT, 2003. our card
47. H. Zhang, L. Huang, K. Zhao, and R. McDonald. Online learning for inexact hypergraph search. In Proc. of EMNLP, 2013. find

↑ back to top

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