Elamur Research
☰
home / papers / 2014 / A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing

A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P14-1048.pdf

Summary

This paper tackles RST-style text-level discourse parsing: building a full discourse tree over a document's elementary discourse units (EDUs). The previous best system, by Joty et al. (2013), was accurate but too slow for real documents because of its DCRF classifiers and cubic-time CKY-like search. Feng and Hirst build a greedy bottom-up parser whose running time grows linearly with the number of sentences. It first parses each sentence on its own and then joins the sentence-level trees into a document tree. At each merge step, two linear-chain CRFs run in cascade: one picks which adjacent constituents to merge (structure), and the other labels the relation. The Viterbi decoding of the structure CRF is restricted by common-sense constraints. A new post-editing step then revisits each finished tree using information from higher levels; currently that information is only subtree depth. On the RST Discourse Treebank (RST-DT), the parser beats Joty et al. on accuracy and runs in seconds per document, which makes discourse parsing usable in practice.

Key points

  • Tested on RST-DT with manual EDU segmentation. The greedy CRF parser (gCRF) beats Joty et al.'s 55.73% overall relation accuracy by about 1.5 points.
  • Post-editing (gCRF PE) adds about 1 more point, a significant gain (p < .01), for 58.2% overall. That is close to 90% of human agreement.
  • Speed on the 38 RST-DT test documents: gCRF averages about 5.5 s per document and needs about 40 s for the largest (187 sentences). The HILDA-style SVM baseline (gSVM FH) averages about 11 s. Joty et al.'s parser would take an estimated 16+ hours on the largest document.
  • Post-editing roughly doubles the parsing time.
  • Rare and abstract relations remain weak: macro-averaged F1 is about 30% over all constituents. TOPIC-CHANGE and TEXTUAL-ORGANIZATION are never recovered.

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p14-1048

@inproceedings{feng2014linear,
  title = {{A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing}},
  author = {Feng, Vanessa Wei and Hirst, Graeme},
  booktitle = {Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2014},
  doi = {10.3115/v1/p14-1048},
  url = {https://doi.org/10.3115/v1/p14-1048}
}

References

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

  1. Jason Baldridge and Alex Lascarides. 2005. Probabilistic head-driven parsing for discourse structure. In Proceedings of the Ninth Conference on Computational Natural Language Learning (CoNLL-2005), pages 96–103, Ann Arbor, Michigan, June. Association for Computational Linguistics. find
  2. Regina Barzilay and Mirella Lapata. 2008. Modeling local coherence: an entity-based approach. Computational Linguistics, 34(1):1–34. find our card
  3. Lynn Carlson, Daniel Marcu, and Mary Ellen Okurowski. 2001. Building a discourse-tagged corpus in the framework of Rhetorical Structure Theory. In Proceedings of Second SIGDial Workshop on Discourse and Dialogue (SIGDial 2001), pages 1–10. find our card
  4. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC 2006). find our card
  5. Vanessa Wei 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: Human Language Technologies (ACL 2012), pages 60–68, Jeju, Korea. find our card
  6. Hugo Hernault, Helmut Prendinger, David A. duVerle, and Mitsuru Ishizuka. 2010. HILDA: A discourse parser using support vector machine classification. Dialogue and Discourse, 1(3):1–33. find our card
  7. Shafiq Joty, Giuseppe Carenini, and Raymond T. 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, EMNLP-CoNLL 2012, pages 904–915. find
  8. Shafiq Joty, Giuseppe Carenini, Raymond Ng, and Yashar Mehdad. 2013. Combining intra- and multi-sentential rhetorical parsing for document-level discourse analysis. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL 2013), pages 486–496, Sofia, Bulgaria, August. find
  9. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics (ACL 2003), ACL 2003, pages 423–430, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  10. Alistair Knott and Robert Dale. 1994. Using linguistic phenomena to motivate a set of coherence relations. Discourse Processes, 18(1):35–64. find
  11. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML 2001, pages 282–289, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. find
  12. Gideon S. Mann and Andrew McCallum. 2008. Generalized Expectation Criteria for semi-supervised learning of Conditional Random Fields. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL 2008), pages 870–878, Columbus, Ohio, June. Association for Computational Linguistics. find
  13. William Mann and Sandra Thompson. 1988. Rhetorical structure theory: Toward a functional theory of text organization. Text, 8(3):243–281. find our card
  14. Daniel Marcu. 2000. The Theory and Practice of Discourse Parsing and Summarization. The MIT Press. find
  15. Andrew Kachites McCallum. 2002. MAL-LET: A machine learning for language toolkit. http://mallet.cs.umass.edu. ↗
  16. Philippe Muller, Stergos Afantenos, Pascal Denis, and Nicholas Asher. 2012. Constrained decoding for text-level discourse parsing. In Proceedings of COLING 2012, pages 1883–1900, Mumbai, India, December. find
  17. The COLING 2012 Organizing Committee. find
  18. Naoaki Okazaki. 2007. CRFsuite: a fast implementation of conditional random fields (CRFs). http://www.chokkan.org/software/crfsuite/. ↗
  19. Marta Recasens, Marie-Catherine de Marneffe, and Christopher Potts. 2013. The life and death of discourse entities: Identifying singleton mentions. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 627–633, Atlanta, Georgia, June. Association for Computational Linguistics. find
  20. Rajen Subba and Barbara Di Eugenio. 2009. An effective discourse parser that uses rich linguistic information. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 566–574, Boulder, Colorado, June. Association for Computational Linguistics. find
  21. Charles Sutton, Andrew McCallum, and Khashayar Rohanimanesh. 2007. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. The Journal of Machine Learning Research, 8:693–723, May. find
  22. Christian Wojek and Bernt Schiele. 2008. A dynamic conditional random field model for joint labeling of object and scene classes. In European Conference on Computer Vision (ECCV 2008), pages 733–747, Marseille, France. find
  23. Dong Yang, Paul Dixon, Yi-Cheng Pan, Tasuku Oonishi, Masanobu Nakamura, and Sadaoki Furui. 2009. Combining a two-step conditional random field model and a joint source channel model for machine transliteration. In Proceedings of the 2009 Named Entities Workshop: Shared Task on Transliteration (NEWS 2009), pages 72–75, Suntec, Singapore, August. Association for Computational Linguistics. find