Elamur Research⌕
☰
home / papers / 2019 / A Unified Linear-Time Framework for Sentence-Level Discourse Parsing

A Unified Linear-Time Framework for Sentence-Level Discourse Parsing

Summary

Lin et al. address sentence-level discourse analysis under Rhetorical Structure Theory (RST). This involves two steps: splitting a sentence into elementary discourse units (EDUs) and assembling them into a labeled discourse tree. Earlier systems faced a trade-off. Greedy shift-reduce parsers run fast but decide from local context. Chart parsers search globally but scale cubically.

The authors close this gap with a fully neural framework built on Pointer Networks, using no hand-engineered features. The segmenter points to EDU boundaries. The parser works top-down and depth-first, using a stack of spans. At each step it selects a split point and then classifies the relation and nuclearity of the two new spans. Because the encoder sees the whole sentence, the decoder keeps a global view while the number of steps stays linear in the number of EDUs. A shared encoder also lets both components be trained jointly.

On RST-DT, both the segmenter and the parser clearly beat earlier systems and come close to human agreement. They also run several times faster. This makes accurate discourse structure practical as a building block for document-level parsing and for downstream tasks.

Key points

  • Evaluated on the RST Discourse Treebank (RST-DT). The segmenter reaches 95.4 F1, cutting relative error by about 32% versus the prior best segmenter.
  • With gold EDUs, the parser scores 81.3 F1 on relation labeling. Joint training raises this to 97.44 / 91.34 / 81.70 F1 on Span / Nuclearity / Relation, exceeding human agreement on span and nuclearity (human: 98.3 segmentation, 83.0 relation).
  • The end-to-end pipeline (segmenter→parser, joint training) achieves 77.5 relation F1, about 10 points above the DCRF baseline (67.5). This even beats DCRF run on gold segmentation (77.1).
  • Speed: on GPU, the segmenter is about 6.8x faster than SPADE, the parser about 3.9x faster than CODRA, and the full system about 5.9x faster than the fastest open-source system. The system remains the fastest even on CPU.
  • Most confusions occur between semantically close relations, such as CAUSE vs. EXPLANATION and COMPARISON vs. CONTRAST. Code is released at ntunlpsg.github.io/project/parser/pointer-net-parser.

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: Discourse analysis

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p19-1410 · arXiv 1905.05682

@inproceedings{lin2019unified,
  title = {{A Unified Linear-Time Framework for Sentence-Level Discourse Parsing}},
  author = {Lin, Xiang and Joty, Shafiq and Jwalapuram, Prathyusha and Bari, M Saiful},
  booktitle = {Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1410},
  eprint = {1905.05682},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p19-1410}
}

References

34 references, 16 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. 2015. Neural Machine Translation by Jointly Learning to Align and Translate. In ICLR. find our card
  2. Chloé Braud, Maximin Coavoux, and Anders Søgaard. 2017. Cross-lingual rst discourse parsing. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 292–304. Association for Computational Linguistics. find our card
  3. Lynn Carlson, Daniel Marcu, and Mary Ellen Okurowski. 2002. RST Discourse Treebank (RST– DT) LDC2002T07. Linguistic Data Consortium, Philadelphia. find
  4. Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Lan… find
  5. Timothy Dozat and Christopher D. Manning. 2016. Deep biaffine attention for neural dependency parsing. CoRR, abs/1611.01734. find our card
  6. Vanessa Feng and Graeme Hirst. 2012. Text-level Discourse Parsing with Rich Linguistic Features. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, ACL ’12, pages 60–68, Jeju Island, Korea. ACL. find our card
  7. Vanessa Feng and Graeme Hirst. 2014a. A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL ’14, pages 511–521, Baltimore, USA. ACL. find our card
  8. Vanessa Wei Feng and Graeme Hirst. 2014b. A linear-time bottom-up discourse parser with constraints and post-editing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 511–521. Association for Computational Linguistics. find our card
  9. Seeger Fisher and Brian Roark. 2007. The Utility of Parse-derived Features for Automatic Discourse Segmentation. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, ACL’07, pages 488–495, Prague, Czech Republic. ACL. find
  10. Francisco Guzmán, Shafiq Joty, Lluı́s Màrquez, and Preslav Nakov. 2014. Using discourse structure improves machine translation evaluation. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 687–698, Baltimore, Maryland. ACL. find
  11. Hugo Hernault, Helmut Prendinger, David duVerle, and Mitsuru Ishizuka. 2010. HILDA: A Discourse Parser Using Support Vector Machine Classification. Dialogue and Discourse, 1(3):1–33. find our card
  12. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735–1780. find
  13. Yangfeng Ji and Jacob Eisenstein. 2014. Representation learning for text-level discourse parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13–24, Baltimore, Maryland. ACL. find our card
  14. Shafiq Joty, Giuseppe Carenini, and Raymond Ng. 2012. A novel discriminative framework for sentence-level discourse analysis. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 904–915. Association for Co… find
  15. Shafiq Joty, Giuseppe Carenini, and Raymond T Ng. 2015. Codra: A novel discriminative framework for rhetorical analysis. Computational Linguistics, 41:3:385–435. find our card
  16. Jing Li, Aixin Sun, and Shafiq Joty. 2018. Segbot: A generic neural text segmentation model with pointer network. In Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence, IJCAI-ECAI-2018, pages 4166 – 4172, Stoc… find
  17. Jiwei Li, Rumeng Li, and Eduard Hovy. 2014. Recursive deep models for discourse parsing. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2061–2069, Doha, Qatar. ACL. find our card
  18. Qi Li, Tianshi Li, and Baobao Chang. 2016. Discourse parsing with attention-based hierarchical neural networks. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 362–371. Association for Computational Linguistics. find our card
  19. Xuezhe Ma, Zecong Hu, Jingzhou Liu, Nanyun Peng, Graham Neubig, and Eduard H. Hovy. 2018. Stack-pointer networks for dependency parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018, Volume 1: Long Papers… find
  20. William Mann and Sandra Thompson. 1988. Rhetorical Structure Theory: Toward a Functional Theory of Text Organization. Text, 8(3):243–281. find our card
  21. Daniel Marcu. 1999. The automatic construction of large-scale corpora for summarization research. In Proceedings of SIGIR, pages 137–144. find
  22. Daniel Marcu. 2000. The Rhetorical Parsing of Unrestricted Texts: A Surface-based Approach. Computational Linguistics, 26:395–448. editors, Advances in Neural Information Processing Systems 28, pages 2692–2700. Curran Associates, Inc. find our card
  23. Mitchell Marcus, Mary Marcinkiewicz, and Beatrice Santorini. 1994. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
  24. Yizhong Wang, Sujian Li, and Houfeng Wang. 2017. A two-stage parsing method for text-level discourse analysis. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 184–188. Association for Computational Linguistics. find our card
  25. Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543. find
  26. Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In Proc. of NAACL. find
  27. Yizhong Wang, Sujian Li, and Jingfeng Yang. 2018. Toward fast and accurate neural discourse segmentation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP 2018). find
  28. Kenji Sagae. 2009. Analysis of discourse structure with syntactic dependencies and data-driven shift-reduce parsing. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09), pages 81–84. Association for Computational Linguistics. find
  29. Abigail See, Peter J. Liu, and Christopher D. Manning. 2017. Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1073– 1083. Association for Computational Linguistic… find
  30. Radu Soricut and Daniel Marcu. 2003. Sentence Level Discourse Parsing Using Syntactic and Lexical Information. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1, NAACL’03, pages 149–156, Edmont… find our card
  31. Caroline Sporleder and Mirella Lapata. 2005. Discourse Chunking and its Application to Sentence Compression. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, HLT-EMNLP’05, pages 257–264, Vancouver, British Columbia, Canada. ACL. find
  32. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3104–3112. Curran Associates, Inc. find
  33. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998–6008. find
  34. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lin-2019-unified-linear-time-framework-sentence/