Elamur Research
☰
home / papers / 2010 / HILDA: A Discourse Parser Using Support Vector Machine Classification

HILDA: A Discourse Parser Using Support Vector Machine Classification

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/2010.dnd-1.1.pdf

Summary

HILDA (HIgh-Level Discourse Analyzer) builds Rhetorical Structure Theory (RST) trees for whole documents, not just single sentences. Earlier tools either stopped at sentence boundaries, as SPADE does, or were never fully built. The authors split the job into two stages, both handled by Support Vector Machine classifiers trained on the RST Discourse Treebank (RST-DT), a set of annotated Wall Street Journal texts. The first stage segments text into elementary discourse units (EDUs). The second stage scores pairs of adjacent spans and gives each pair a relation label and a nuclearity. A greedy bottom-up procedure then keeps merging the highest-scoring pair, so tree construction runs in time linear in the length of the text. The classifiers use lexical, syntactic and structural features, including lexico-syntactic cues from parse trees. The complete pipeline reaches 78.3% of human annotator performance and improves on a state-of-the-art rule-based parser by 11.6%. Because it is both accurate and fast, it can serve near real-time applications such as question answering and dialogue generation.

Key points

  • The system has two SVM modules. The EDU segmenter reaches about 96% of human-level performance, and the relation classifier with tree builder reaches about 84%.
  • Full text-level parsing reaches 78.3% of human performance and is 11.6% better than a rule-based baseline. It also outperforms SPADE, Sagae (2009) and others on tree structure and relation labeling.
  • For training, RST-DT documents are aligned with Penn Treebank syntax trees. New input is parsed with the Stanford parser. The label set has 18 relations (e.g., ELABORATION, ATTRIBUTION, CONTRAST, SAME-UNIT), each with its nuclearity options.
  • The main weakness is implicit relations. In one error analysis, all ten implicit CONTRAST cases were wrongly labeled, as ELABORATION (6) or JOINT (4). Planned fixes are a separate implicit-relation classifier using word-pair and WordNet similarity features, feature selection, and globally optimal tree building.
  • Intended uses include the Text-to-Dialogue system and generating dialogues from monologues with the CODA corpus (700 expository dialogues).

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.5087/dad.2010.003

@inproceedings{hernault2010hilda,
  title = {{HILDA: A Discourse Parser Using Support Vector Machine Classification}},
  author = {Hernault, Hugo and Prendinger, Helmut and Verle, David A. du and Ishizuka, Mitsuru},
  booktitle = {Dialogue \& Discourse},
  year = {2010},
  doi = {10.5087/dad.2010.003},
  url = {https://doi.org/10.5087/dad.2010.003}
}

References

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

  1. Nicholas Asher and Alex Lascarides. Logics of conversation. Cambridge University Press, 2003. find
  2. Jason Baldridge and Alex Lascarides. 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 2005. Association for Computational Linguistics. find
  3. Ezra Black, Steven P. Abney, D. Flickenger, Claudia Gdaniec, Ralph Grishman, P. Harrison, Donald Hindle, Robert Ingria, Frederick Jelinek, Judith L. Klavans, Mark Liberman, Mitchell P. Marcus, Salim Roukos, Beatrice Santorini, and Tomek Strzalkowski. A procedure for quantitatively comparing the syntactic coverage of english grammars. In Proceedings of Workshop on Speech and Natural Language, pages 306–311. Association for Computational Linguistics Morristown, NJ, USA, 1991. find
  4. Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. find our card
  5. Lynn Carlson, Daniel Marcu, and Mary Ellen Okurowski. Building a discourse-tagged corpus in the framework of Rhetorical Structure Theory. Proceedings of Second SIGdial Workshop on Discourse and Dialogue-Volume 16, pages 1–10, 2001. find our card
  6. Joyce Y. Chai and Rong Jin. Discourse structure for context question answering. In Sanda Harabagiu and Finley Lacatusu, editors, HLT-NAACL 2004: Workshop on Pragmatics of Question Answering, pages 23–30, Boston, Massachusetts, USA, May 2 - May 7 2004. Association for Computational Linguistics. find
  7. Eugene Charniak. A maximum-entropy-inspired parser. In Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference, pages 132–139, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. find
  8. Degang Chen, Qiang He, and Xizhao Wang. On linear separability of data sets in feature space. Neurocomputing, 70(13-15):2441–2448, 2007. find
  9. David duVerle and Helmut Prendinger. A novel discourse parser based on support vector machine classification. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 665–673, Suntec, Singapore, August 2009. Association for Computational Linguistics. find
  10. Christiane Fellbaum, editor. WordNet: An electronic lexical database. MIT Press, 1998. find
  11. Hugo Hernault, Paul Piwek, Helmut Prendinger, and Mitsuru Ishizuka. Generating dialogues for virtual agents using nested textual coherence relations. In IVA ’08: Proceedings of the 8th international conference on Intelligent Virtual Agents, pages 139–145, Berlin, Heidelberg, 2008. Springer-Verlag. find
  12. Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671–680, 1983. find
  13. Dan Klein and Christopher D. Manning. Fast exact inference with a factored model for natural language parsing. In Advances in Neural Information Processing Systems, volume 15, pages 3–10. MIT Press, 2003. find
  14. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML’01: Proceedings of the Eighteenth International Conference on Machine Learning, pages 282–289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. find
  15. Huong Le Thanh, Geetha Abeysinghe, and Christian Huyck. Automated discourse segmentation by syntactic information and cue phrases. In Proceedings of AIA’04, Innsbruck, Austria, February 16–18 2004a. find
  16. Huong Le Thanh, Geetha Abeysinghe, and Christian Huyck. Generating discourse structures for written texts. In Proceedings of the 20th International Conference on Computational Linguistics, pages 329–335, Geneva, Switzerland, Aug 23–Aug 27 2004b. COLING. find
  17. Ziheng Lin, Min-Yen Kan, and Hwee Tou Ng. Recognizing implicit discourse relations in the Penn Discourse Treebank. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 343–351, Singapore, August 2009. Association for Computational Linguistics. find our card
  18. David M. Magerman. Statistical decision-tree models for parsing. Proceedings of the 33rd annual meeting on Association for Computational Linguistics, pages 276–283, 1995. find
  19. William C. Mann and Sandra A. Thompson. Rhetorical structure theory: Toward a functional theory of text organization. Text, 8(3):243–281, 1988. find our card
  20. Christopher D. Manning and Hinrich Schütze. Foundations of Statistical Natural Language processing. MIT Press, 1999. find
  21. Daniel Marcu. Building up rhetorical structure trees. Proceedings of the National Conference on Artificial Intelligence, pages 1069–1074, 1996. find
  22. Daniel Marcu. The Theory and Practice of Discourse Parsing and Summarization. MIT Press, 2000. find
  23. Daniel Marcu and Abdessamad Echihabi. An unsupervised approach to recognizing discourse relations. In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pages 368–375, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/1073083.1073145. ↗ our card
  24. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus of English: the Penn treebank. Computational Linguistics, 19(2):313–330, 1993. find our card
  25. Johanna D. Moore and Peter Wiemer-Hastings. Discourse in computational linguistics and artificial intelligence. In A. Graesser, M. Gernsbacher, and S. Goldman, editors, Handbook of Discourse Processes, pages 439–486. Erlbaum, Mahwah, NJ, 2003. find
  26. Jon Oberlander and Johanna D. Moore. Cue phrases in discourse: Further evidence for the core:contributor distinction. In Workshop on Levels of Representation in Discourse, pages 87–93, Edinburgh, UK, 1999. find
  27. Emily Pitler, Mridhula Raghupathy, Hena Mehta, Ani Nenkova, Alan Lee, and Aravind Joshi. Easily identifiable discourse relations. In Coling 2008: Companion volume: Posters, pages 87–90, Manchester, UK, August 2008. Coling 2008 Organizing Committee. find
  28. Emily Pitler, Annie Louis, and Ani Nenkova. Automatic sense prediction for implicit discourse relations in text. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 683–691, Suntec, Singapore, August 2009. Association for Computational Linguistics. find our card
  29. Helmut Prendinger, Paul Piwek, and Mitsuru Ishizuka. A novel method for automatically generating multi-modal dialogue from text. International Journal of Semantic Computing, 1(3):319–334, 2007. find
  30. David Reitter. Rhetorical Analysis with Rich-Feature Support Vector Models. Unpublished Master’s thesis, University of Potsdam, Potsdam, Germany, 2003a. find
  31. David Reitter. Simple signals for complex rhetorics: On rhetorical analysis with rich-feature support vector models. LDV Forum, 18(1/2):38–52, 2003b. find
  32. Kenji Sagae. 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, Paris, France, October 2009. Association for Computational Linguistics. find
  33. Frank Schilder. Robust discourse parsing via discourse markers, topicality and position. Natural Language Engineering, 8(2-3):235–255, 2002. find
  34. Radu Soricut and Daniel Marcu. Sentence level discourse parsing using syntactic and lexical information. Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, 1:149–156, 2003. find our card
  35. Carl Staelin. Parameter selection for Support Vector Machines. Hewlett-Packard Company, Tech. Rep. HPL-2002-354R1, 2003. find
  36. Svetlana Stoyanchev and Paul Piwek. Constructing the coda corpus: A parallel corpus of monologues and expository dialogues. In Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10), Valletta, Malta, May 2010. European Language Resources Association. find
  37. Rajen Subba and Barbara Di Eugenio. Automatic discourse segmentation using neural networks. In Proceedings of 11th Workshop on the Semantics and Pragmatics of Dialogue, pages 189–190, Trento, Italy, 2007. find
  38. Rajen Subba and Barbara Di Eugenio. 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 2009. Association for Computational Linguistics. find
  39. Maite Taboada. Discourse markers as signals (or not) of rhetorical relations. Journal of Pragmatics, 38(4):567–592, 2006. find
  40. Milan Tofiloski, Julian Brooke, and Maite Taboada. A syntactic and lexical-based discourse segmenter. In ACL ’09, pages 77–80, Suntec, Singapore, August 2009. Association for Computational Linguistics. find
  41. Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag New York, Inc., New York, NY, USA, 1995. find
  42. Bonnie Webber. Genre distinctions for discourse in the penn treebank. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 674–682, Suntec, Singapore, August 2009. Association for Computational Linguistics. . . find