Elamur Research⌕
☰
home / papers / 2009 / A Novel Discourse Parser Based on Support Vector Machine Classification

A Novel Discourse Parser Based on Support Vector Machine Classification

Summary

The paper addresses automatic discourse parsing in the Rhetorical Structure Theory (RST) framework. It concentrates on the harder step: building a labeled RST tree over text that has already been split into elementary discourse units (edus). The authors use two Support Vector Machine classifiers:

  • S, a binary classifier that decides whether two neighbouring spans should be joined.
  • L, a multi-class classifier that assigns the rhetorical relation together with nuclearity.

Both are trained on the RST Discourse Treebank (RST-DT), drawing on a broad collection of surface-level features that capture lexical, syntactic and structural information. The syntactic features come from lexicalized Penn Treebank parses. A greedy bottom-up procedure repeatedly merges the best-scoring adjacent pair, so parsing runs in linear time.

When results are normalised by each study's human agreement, the parser scores higher than the earlier text-level systems of Marcu and LeThanh et al. It also degrades much less when given automatic SPADE segmentation instead of gold edus. This shows that a fast, feature-driven supervised parser can approach human-level RST annotation, which makes real-time applications such as text-to-dialogue generation practical.

Key points

  • The label space has 41 classes: the 18 grouped RST-DT relations combined with their valid nuclearity options. The feature space contains roughly 10^5 features, and n-ary relations are binarized.
  • Evaluation used the 41-file RST-DT test set and the 52 doubly-annotated files, with the remaining 340–350 documents used for training. Each setup was run with both gold and SPADE segmentation.
  • On LeThanh et al.'s 21-document test set, the system reached F-scores of 72.8 (structure), 58.1 (nuclearity) and 48.1 (relations). LeThanh et al. scored 53.7, 47.1 and 39.9 on the same set.
  • Relative to human agreement, the system achieves 83.0%, 75.6% and 73.9% for structure, nuclearity and relations, compared with 73.9%, 71.8% and 70.1% for LeThanh et al.
  • Switching from gold to automatic segmentation lowers structure and relation F-scores by about 12–13%, compared with 46% and 67% for Marcu's parser. The full parser was later released online as HILDA.

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{duverle2009novel,
  title = {{A Novel Discourse Parser Based on Support Vector Machine Classification}},
  author = {duVerle, David and Prendinger, Helmut},
  booktitle = {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},
  year = {2009},
  url = {https://aclanthology.org/P09-1075/}
}

References

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

  1. M.A. Aizerman, E.M. Braverman, and L.I. Rozonoer. 1964. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25(6):821–837. find
  2. N. Asher and A. Lascarides. 2003. Logics of conversation. Cambridge University Press. find
  3. J. Baldridge and A. Lascarides. 2005. Probabilistic head-driven parsing for discourse structure. In Proceedings of the Ninth Conference on Computational Natural Language Learning, volume 96, page 103. find
  4. E. Black, S. Abney, S. Flickenger, C. Gdaniec, C. Grishman, P. Harrison, D. Hindle, R. Ingria, F. Jelinek, J. Klavans, M. Liberman, et al. 1991. Procedure for quantitatively comparing the syntactic coverage of English grammars. Proceedings of the workshop on Speech and Natural Language, pages 306–31… find
  5. L. Carlson, D. Marcu, and M.E. Okurowski. 2001. Building a discourse-tagged corpus in the framework of Rhetorical Structure Theory. Proceedings of the Second SIGdial Workshop on Discourse and Dialogue-Volume 16, pages 1–10. find our card
  6. D. Chen, Q. He, and X. Wang. 2007. On linear separability of data sets in feature space. Neurocomputing, 70(13-15):2441–2448. find
  7. M. Collins. 2003. Head-Driven Statistical Models for Natural Language Parsing. Computational Linguistics, 29(4):589–637. find our card
  8. K. Crammer and Y. Singer. 2002. On the algorithmic implementation of multiclass kernel-based vector machines. The Journal of Machine Learning Research, 2:265–292. find
  9. H. Hernault, P. Piwek, H. Prendinger, and M. Ishizuka. 2008. Generating dialogues for virtual agents using nested textual coherence relations. Proceedings of the 8th International Conference on Intelligent Virtual Agents (IVA’08), LNAI, 5208:139–145, Sept. find
  10. S. Kirkpatrick, CD Gelatt, and MP Vecchi. 1983. Optimization by Simulated Annealing. Science, 220(4598):671–680. find
  11. H. LeThanh, G. Abeysinghe, and C. Huyck. 2004. Generating discourse structures for written texts. Proceedings of the 20th international conference on Computational Linguistics. find
  12. D.M. Magerman. 1995. Statistical decision-tree models for parsing. Proceedings of the 33rd annual meeting on Association for Computational Linguistics, pages 276–283. find
  13. W.C. Mann and S.A. Thompson. 1988. Rhetorical structure theory: Toward a functional theory of text organization. Text, 8(3):243–281. find our card
  14. D. Marcu. 1996. Building Up Rhetorical Structure Trees. Proceedings of the National Conference on Artificial Intelligence, pages 1069–1074. find
  15. D. Marcu. 2000. The theory and practice of discourse parsing and summarization. MIT Press. find
  16. J. Oberlander, J.D. Moore, J. Oberlander, A. Knott, and J. Moore. 1999. Cue phrases in discourse: further evidence for the core: contributor distinction. Proceedings of the 1999 Levels of Representation in Discourse Workshop (LORID’99), pages 87–93. find
  17. P. Piwek, H. Hernault, H. Prendinger, and M. Ishizuka. 2007. Generating dialogues between virtual agents automatically from text. Proceedings of the 7th International Conference on Intelligent Virtual Agents (IVA ’07), LNCS, 4722:161. find
  18. D. Reitter. 2003a. Rhetorical Analysis with Rich-Feature Support Vector Models. Unpublished Master’s thesis, University of Potsdam, Potsdam, Germany. find
  19. D. Reitter. 2003b. Simple Signals for Complex Rhetorics: On Rhetorical Analysis with Rich-Feature Support Vector Models. Language, 18(52). find
  20. F. Schilder. 2002. Robust discourse parsing via discourse markers, topicality and position. Natural Language Engineering, 8(2-3):235–255. find
  21. B. Scholkopf, C. Burges, and V. Vapnik. 1995. Extracting Support Data for a Given Task. Knowledge Discovery and Data Mining, pages 252–257. find
  22. R. Soricut and D. Marcu. 2003. 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. find our card
  23. C. Staelin. 2003. Parameter selection for support vector machines. Hewlett-Packard Company, Tech. Rep. HPL-2002-354R1. find
  24. V.N. Vapnik. 1995. The nature of statistical learning theory. Springer-Verlag New York, Inc., New York, NY, USA. find

↑ back to top