Elamur Research
☰
home / papers / 2017 / A Minimal Span-Based Neural Constituency Parser

A Minimal Span-Based Neural Constituency Parser

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/P17-1076.pdf

Summary

The paper asks how much machinery a constituency parser actually needs once it has strong neural features. Earlier chart parsers relied on extra scaffolding, such as full context-free grammars and pruning by weaker models. The best recent systems were transition-based. The authors treat a tree as a set of labeled spans and score each span with two independent components: one rates possible labels and one rates whether the span should exist. A span is encoded by subtracting bidirectional LSTM states at its boundaries, an extension of LSTM-Minus features. Small feedforward networks on top produce the scores. Because label and structure decisions are separate, the model supports two decoders: exact CKY-style chart parsing and a fast greedy procedure that splits spans recursively from the top down. Training uses a margin objective with a Hamming loss on labeled spans. On the Penn Treebank both decoders reach state-of-the-art single-model accuracy, and results on the French Treebank are competitive. This shows that simple span-based global models can match the best transition-based parsers.

Key points

  • Penn Treebank results: the chart parser reaches 91.79 F1 and the top-down parser 91.77 F1. Both beat Cross and Huang (2016) at 91.3 and Liu and Zhang (2016) at 91.7, among single models trained without external parse data.
  • French Treebank results: the top-down parser scores 82.23 F1 and the chart parser 82.14. This trails Cross and Huang (2016) at 83.11 but exceeds the 81.25 achieved by Durrett and Klein's (2015) neural conditional random field parser.
  • Complexity and speed: chart decoding runs in O(n³) and top-down decoding in O(n²). On a c4.4xlarge Amazon EC2 instance, the parsers process 20.3 and 75.5 sentences per second, respectively.
  • Label handling: unary chains are collapsed into single atomic labels. A special empty label ∅ marks spans that only arise from implicit binarization. Part-of-speech tags are supplied by an external tagger.
  • Precision–recall gap: the parsers show a wider gap between precision and recall than other top systems, which the authors attribute to the structured label loss. The near-identical scores of the two decoders suggest that global inference is not essential for strong accuracy.

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: Linguistics & languages

Topics: Treebanks

Cited by

120 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 112 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p17-1076

@inproceedings{stern2017minimal,
  title = {{A Minimal Span-Based Neural Constituency Parser}},
  author = {Stern, Mitchell and Andreas, Jacob and Klein, Dan},
  booktitle = {Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2017},
  doi = {10.18653/v1/p17-1076},
  url = {https://doi.org/10.18653/v1/p17-1076}
}

References

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

  1. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural machine translation by jointly learning to align and translate. CoRR abs/1409.0473. http://arxiv.org/abs/1409.0473. ↗ our card
  2. James Henderson. 2004. Discriminative training of a neural network statistical parser. In Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. Association for Computational Linguistics, page 95. find
  3. 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
  4. Diederik P. Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. CoRR abs/1412.6980. http://arxiv.org/abs/1412.6980. ↗
  5. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional lstm feature representations. arXiv preprint arXiv:1603.04351 . find our card
  6. Anders Björkelund, Ozlem Cetinoglu, Agnieszka Falenska, Richárd Farkas, Thomas Müller, Wolfgang Seeker, and Zsolt Szántó. 2014. The ims-wrocław-szeged-cis entry at the spmrl 2014 shared task: Reranking and morphosyntax meet unlabeled data. Notes of the SPMRL . find
  7. Dan Klein and Christopher D Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. pages 423–430. find our card
  8. Danqi Chen and Christopher D Manning. 2014. A fast and accurate dependency parser using neural networks. In EMNLP. pages 740–750. find our card
  9. Jiangming Liu and Yue Zhang. 2016. Shift-reduce constituent parsing with neural lookahead features. CoRR abs/1612.00567. http://arxiv.org/abs/1612.00567. ↗
  10. Michael Collins. 2003. Head-driven statistical models for natural language parsing. Computational linguistics 29(4):589–637. find our card
  11. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: The penn treebank. Comput. Linguist. 19(2):313–330. http://dl.acm.org/citation.cfm?id=972470.972475. ↗ our card
  12. James Cross and Liang Huang. 2016. Span-based constituency parsing with a structure-label system and provably optimal dynamic oracles. In EMNLP. find
  13. Timothy Dozat and Christopher D. Manning. 2016. Deep biaffine attention for neural dependency parsing. CoRR abs/1611.01734. http://arxiv.org/abs/1611.01734. ↗ our card
  14. Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Greg Durrett and Dan Klein. 2015. Neural crf parsing. arXiv preprint a… find
  15. Sam Wiseman and Alexander M Rush. 2016. Sequence-to-sequence learning as beam-search optimization. arXiv preprint arXiv:1606.02960 . find
  16. Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul Michel, Yusuke Oda, Matthew Richardson, Naomi Saphra, Swabha Swayamdipta, and Pengcheng Yin. 2017. Dynet: The dynamic neural network toolkit. arXiv preprint arXiv:1701.03980 . find our card
  17. Slav Petrov and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics. Assocation for Computational Linguistics. find
  18. 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. Dublin City… find
  19. Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. 2005. Learning structured prediction models: A large margin approach. In Proceedings of the 22Nd International Conference on Machine Learning. ACM, New York, NY, USA, ICML ’05, pages 896–903. https://doi.org/10.1145/1102351.1102464… — [doi:10.1145/1102351.1102464](https://doi.org/10.1145/1102351.1102464) ↗
  20. Le Quang Thang, Hiroshi Noji, and Yusuke Miyao. 2015. Optimal shift-reduce constituent parsing with structured perceptron. In Proceedings of the Annual Meeting of the Association for Computational Linguistics. volume 1, pages 1534–1544. find
  21. 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 the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Vol… find
  22. 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 2773–2781. find
  23. Peilu Wang, Yao Qian, Frank K. Soong, Lei He, and Hai Zhao. 2015. A unified tagging solution: Bidirectional LSTM recurrent neural network with word embedding. CoRR abs/1511.00215. http://arxiv.org/abs/1511.00215. — [arXiv:1511.00215](https://arxiv.org/abs/1511.00215) ↗
  24. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional LSTM. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. http://aclweb.org/anthology/P/P16/P16-1218.pdf. ↗