Elamur Research⌕
☰
home / papers / 2016 / Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles

Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles

Summary

Cross and Huang address the gap between neural greedy parsers, which lead in dependency parsing, and the best constituency parsers. They propose a shift-reduce variant in which stack elements are plain sentence spans, not partial trees. The parser alternates between structural moves (shift, or a non-directional combine of the top two spans) and label moves (assign a nonterminal or a unary chain to the top span, or skip it). Because of this design, n-ary productions need no binarization, and every sentence takes exactly 4n−2 steps. Each span is encoded as the difference of forward and backward outputs from a two-layer bi-directional LSTM, extending LSTM-Minus. The authors also derive a dynamic oracle that is provably optimal for F1, precision and recall and runs in amortized O(1) time. Training uses this oracle together with exploration. With strictly greedy, linear-time decoding, the parser obtains the best results among single-model, closed-data parsers without reranking on both the Penn Treebank and the French Treebank. The work shows that a simple span-centric design can match far more complex parsers.

Key points

  • Very few features are needed: structural decisions rely on 4 span features, while label decisions rely on 3. No pre-trained embeddings are used.
  • Results on the Penn Treebank (WSJ section 23):
    • The dynamic oracle with exploration reaches F1 91.3, compared with 91.0 for the static oracle.
    • POS tags come from the Stanford tagger with 10-way jackknifing.
  • Results on the PTB development set:
    • The static and dynamic oracles alone both give F1 91.38.
    • Adding exploration with α=1.0 raises F1 to 91.64, gaining precision at some cost to recall.
  • Results on the French Treebank (SPMRL 2014 data, with predicted morphology and lemmas): F1 83.31 with dynamic training versus 83.18 with static training. This exceeds Björkelund et al. (2014) at 82.53, a system that used reranking and external data.
  • Code is available at github.com/jhcross/span-parser. The authors list beam search and dynamic programming as future extensions.

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: Other

Topics: Syntax & grammar formalisms

Institutions

🎓Oregon State UniversityCorvallis · United States4 works · 618 citations

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1612.06475 · arXiv 1612.06475

@misc{cross2016span,
  title = {{Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles}},
  author = {Cross, James and Huang, Liang},
  year = {2016},
  doi = {10.48550/arxiv.1612.06475},
  eprint = {1612.06475},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1612.06475}
}

References

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

  1. Anne Abeillé, Lionel Clément, and François Toussenel. 2003. Building a treebank for french. In Treebanks, pages 165–187. Springer. find
  2. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. Proceedings of ACL. find our card
  3. Miguel Ballesteros, Chris Dyer, and Noah A Smith. 2015. Improved transition-based parsing by modeling characters instead of words with lstms. arXiv preprint arXiv:1508.00657. find our card
  4. Miguel Ballesteros, Yoav Goldberg, Chris Dyer, and Noah A Smith. 2016. Training with exploration improves a greedy stack-lstm parser. arXiv preprint arXiv:1603.03793. find
  5. Anders Björkelund, Ozlem Cetinoglu, Agnieszka Falenska, Richárd Farkas, Thomas Mueller, Wolfgang Seeker, and Zsolt Szántó. 2014. Introducing the ims-wrocław-szeged-cis entry at the spmrl 2014 shared task: Reranking and morpho-syntax meet unlabeled data. In Proceedings of the First Joint Workshop… find
  6. Xavier Carreras, Michael Collins, and Terry Koo. 2008. Tag, dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proceedings of the Twelfth Conference on Computational Natural Language Learning, pages 9–16. Association for Computational Linguistics. find
  7. Danqi Chen and Christopher D Manning. 2014. A fast and accurate dependency parser using neural networks. In Empirical Methods in Natural Language Processing (EMNLP). find our card
  8. Maximin Coavoux and Benoı̂t Crabbé. 2016. Neural greedy constituent parsing with dynamic oracles. Proceedings of ACL. find
  9. James Cross and Liang Huang. 2016. Incremental parsing with minimal features using bi-directional lstm. Proceedings of ACL. find
  10. Greg Durrett and Dan Klein. 2015. Neural crf parsing. Proceedings of ACL. find
  11. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A Smith. 2015. Transition-based dependency parsing with stack long short-term memory. Empirical Methods in Natural Language Processing (EMNLP). find our card
  12. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. 2016. Recurrent neural network grammars. Proceedings of HLT-NAACL. find
  13. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the association for Computational Linguistics, 1:403–414. find
  14. Yoav Goldberg, Francesco Sartorio, and Giorgio Satta. 2014. A tabular method for dynamic oracles in transition-based parsing. Trans. of ACL. find
  15. James Henderson. 2004. Discriminative training of a neural network statistical parser. In Proceedings of ACL. find
  16. Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. CoRR, abs/1207.0580. find
  17. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  18. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. find
  19. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proceedings of the ACL: HLT, Columbus, OH, June. find
  20. Eliyahu Kiperwasser and Yoav Goldberg. 2016a. Easy-first dependency parsing with hierarchical tree lstms. arXiv preprint arXiv:1603.00375. find
  21. Eliyahu Kiperwasser and Yoav Goldberg. 2016b. Simple and accurate dependency parsing using bidirectional LSTM feature representations. CoRR, abs/1603.04351. find our card
  22. Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: The penn treebank. Computational linguistics, 19(2):313–330. find our card
  23. David McClosky, Eugene Charniak, and Mark Johnson. 2006. Reranking and self-training for parser adaptation. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, pages 337–344. Association for Co… find our card
  24. Haitao Mi and Liang Huang. 2015. Shift-reduce constituency parsing with dynamic programming and pos tag lattice. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. find
  25. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of HLT-NAACL. find our card
  26. Kenji Sagae and Alon Lavie. 2006. A best-first probabilistic shift-reduce parser. In Proceedings of the COLING/ACL on Main conference poster sessions, pages 691–698. Association for Computational Linguistics. find
  27. Djamé Seddah, Sandra Kübler, and Reut Tsarfaty. 2014. Introducing the spmrl 2014 shared task on parsing morphologically-rich languages. In Proceedings of the First Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Analysis of Non-Canonical Languages, pages 103–1… find
  28. Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, and Masaaki Nagata. 2012. Bayesian symbol-refined tree substitution grammars for syntactic parsing. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1, pages 440–448. Association for Computat… find
  29. Richard Socher, John Bauer, Christopher D Manning, and Andrew Y Ng. 2013. Parsing with compositional vector grammars. In ACL (1), pages 455–465. find
  30. Martin Sundermeyer, Ralf Schlüter, and Hermann Ney. 2012. Lstm neural networks for language modeling. In INTERSPEECH, pages 194–197. find
  31. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112. find
  32. Le Quang Thang, Hiroshi Noji, and Yusuke Miyao. 2015. Optimal shift-reduce constituent parsing with structured perceptron. find
  33. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In Advances in Neural Information Processing Systems, pages 2755– 2763. find
  34. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional lstm. In Proceedings of ACL. find
  35. Taro Watanabe and Eiichiro Sumita. 2015. Transition-based neural constituent parsing. Proceedings of ACL-IJCNLP. find
  36. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of ACL. find
  37. Matthew D. Zeiler. 2012. ADADELTA: an adaptive learning rate method. CoRR, abs/1212.5701. find our card
  38. Muhua Zhu, Yue Zhang, Wenliang Chen, Min Zhang, and Jingbo Zhu. 2013. Fast and accurate shift-reduce constituent parsing. In ACL (1), pages 434–443. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/cross-2016-span-based-constituency-parsing-structure/