Elamur Research⌕
☰
home / papers / 2012 / Constrained Decoding for Text-Level Discourse Parsing

Constrained Decoding for Text-Level Discourse Parsing

Summary

The paper addresses discourse parsing for whole documents rather than single sentences. Earlier full-text parsers built structures greedily from independent local decisions. The authors train local classifiers on pairs of discourse units: one predicts whether two units are attached, and another predicts the coherence relation between them. They then decode a globally optimal structure from these scores. Discourse structures are represented as dependency-style graphs, which abstract over frameworks such as SDRT and RST. Decoding uses A* search, which can enforce linguistic constraints like the Right Frontier Constraint, and is compared with Maximum Spanning Tree (MST) and greedy decoding. Attachment and labeling are tried both jointly and as a pipeline. Experiments use the French Annodis corpus, making this the first discourse parser for French. Despite far less training data than English systems, it reaches 66.2 F1 on unlabeled and 46.8 F1 on labeled structures. These scores are comparable to prior work and show that constrained global decoding is a practical alternative to greedy parsing.

Key points

  • Data: Annodis corpus (French, SDRT-based). Training contains about 2.5k positive attachments out of 13k pairs with pruning, and about 2.7k out of 125k without pruning.
  • Results: unlabeled F1 is 66.2. Labeled F1 is 46.8 with 4 coarse relations and 36.1 with 18 relations. MST and A* decoding performed best.
  • For labeled structures, pipelining relation labeling after attachment beat joint decoding. Pruning the attachment space to a window of 5 units gave no accuracy gain.
  • Comparison with related work: Hernault et al. (2010) report 68.4 F1 on RST structure, and Feng and Hirst (2012) report 69.84 F1 on attachment. Baldridge and Lascarides (2005) report 68/43 on Verbmobil dialogues. The proposed system lands in a similar range with fewer features and much less data.
  • Planned future work includes better relation models, handling intra-sentential links separately, adapting the approach to RST corpora, integrating decoding into learning, and k-best parsing.

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

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

Cite

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

@inproceedings{muller2012constrained,
  title = {{Constrained Decoding for Text-Level Discourse Parsing}},
  author = {Muller, Philippe and Afantenos, Stergos and Denis, Pascal and Asher, Nicholas},
  booktitle = {Proceedings of COLING 2012},
  year = {2012},
  url = {https://aclanthology.org/C12-1115/}
}

References

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

  1. Afantenos, S., Asher, N., Benamara, F., Bras, M., Fabre, C., Ho-Dac, M., Draoulec, A. L., Muller, P., Pery-Woodley, M.-P., Prevot, L., Rebeyrolles, J., Tanguy, L., Vergez-Couret, M., and Vieu, L. (2012). An empirical resource for discovering cognitive principles of discourse organisation: the annodi… find
  2. Asher, N. and Lascarides, A. (2003). Logics of Conversation. Studies in Natural Language Processing. Cambridge University Press, Cambridge, UK. find
  3. Baldridge, J., Asher, N., and Hunter, J. (2007). Annotation for and Robust Parsing of Discourse Structure on Unrestricted Texts. Zeitschrift fur Sprachwissenschaft, 26:213–239. find
  4. Baldridge, J. and Lascarides, A. (2005). Probabilistic head-driven parsing for discourse structure. In Proceedings of the Ninth Conference on Computational Natural Language Learning (CoNLL). find
  5. Carlson, L., Marcu, D., and Okurowski, M. E. (2003). Building a discourse-tagged corpus in the framework of rhetorical structure theory. In van Kuppevelt, J. and Smith, R., editors, Current Directions in Discourse and Dialogue, pages 85–112. Kluwer Academic Publishers. find our card
  6. Chu, Y. J. and Liu, T. H. (1965). On the shortest arborescence of a directed graph. Science Sinica, 14:1396–1400. find
  7. Curk, T., Demšar, J., Xu, Q., Leban, G., Petrovič, U., Bratko, I., Shaulsky, G., and Zupan, B. (2005). Microarray data mining with visual programming. Bioinformatics, 21:396–398. find
  8. Daumé III, H. (2004). Notes on CG and LM-BFGS optimization of logistic regression. Paper available at http://pub.hal3.name\#daume04cg-bfgs , implementation available at http://hal3.name/megam/ . duVerle, D. and Prendinger, H. (2009). A novel discourse parser based on support vector machine classifica… ↗
  9. Edmonds, J. (1967). Optimum branchings. Journal of Research of the National Bureau of Standards, 71B(233–240). find
  10. Feng, V. W. and Hirst, G. (2012). Text-level discourse parsing with rich linguistic features. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 60–68, Jeju Island, Korea. Association for Computational Linguistics. find our card
  11. Gerber, M., Gordon, A., and Sagae, K. (2010). Open-domain commonsense reasoning using discourse relations from a corpus of weblog stories. In Proceedings of the NAACL HLT 2010 First International Workshop on Formalisms and Methodology for Learning by Reading, pages 43–51, Los Angeles, California. As… find
  12. Hernault, H., Prendinger, H., duVerle, D. A., and Ishizuka, M. (2010). HILDA: A Discourse Parser Using Support Vector Machine Classification. Dialogue and Discourse, 1(3):1–33. find our card
  13. Joty, S., Carenini, G., and Ng, R. (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, Jeju Island, Korea. Associati… find
  14. Lin, Z., Kan, M.-Y., and Ng, H. T. (2009). 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. Association for Computational Linguistics. find our card
  15. Lin, Z., Ng, H. T., and Kan, M.-Y. (2011). Automatically evaluating text coherence using discourse relations. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 997–1006, Portland, Oregon, USA. Association for Computational… find our card
  16. Louis, A., Joshi, A., Prasad, R., and Nenkova, A. (2010). Using entity features to classify implicit discourse relations. In Proceedings of the SIGDIAL 2010 Conference, pages 59–62, Tokyo, Japan. Association for Computational Linguistics. find our card
  17. Mann, W. C. and Thompson, S. A. (1987). Rhetorical Structure Theory: A Framework for the Analysis of Texts. Technical Report ISI/RS-87-185, Information Sciences Institute, Marina del Rey, California. find
  18. Marcu, D. (2000). The Theory and Practice of Discourse Parsing and Summarization. The MIT Press. find
  19. Marcu, D. and Echihabi, A. (2002). An unsupervised approach to recognizing discourse relations. In Proceedings of ACL, pages 368–375. find our card
  20. McDonald, R. T., Pereira, F., Ribarov, K., and Hajic, J. (2005). Non-projective dependency parsing using spanning tree algorithms. In HLT/EMNLP. find our card
  21. Pauls, A. and Klein, D. (2009). K-best a* parsing. 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 958–966, Suntec, Singapore. Association for Computational Linguistics. find
  22. Polanyi, L. (1988). A formal model of the structure of discourse. Journal of Pragmatics, 12:601–638. find
  23. Prasad, R., Dinesh, N., Lee, A., Miltsakaki, E., Robaldo, L., Joshi, A., and Webber, B. L. (2008). The Penn Discourse TreeBank 2.0. In Proceedings of LREC 2008. find our card
  24. Sagae, K. (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, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  25. Somasundaran, S., Namata, G., Wiebe, J., and Getoor, L. (2009). Supervised and unsupervised methods in employing discourse relations for improving opinion polarity classification. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 170–179, Singapore. Ass… find our card
  26. Soricut, R. and Marcu, D. (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, pages 149–156. Association for Compu… find our card
  27. Sporleder, C. and Lascarides, A. (2005). Exploiting linguistic cues to classify rhetorical relations. In Proceedings of Recent Advances in Natural Langauge Processing (RANLP), Bulgaria. find
  28. Sporleder, C. and Lascarides, A. (2008). Using automatically labelled examples to classify rhetorical relations: An assessment. Natural Language Engineering, 14(3):369–416. find
  29. Stede, M. (2011). Discourse Processing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool Publishers. find
  30. Subba, R. and Di Eugenio, B. (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. Associ… find our card
  31. Verberne, S., Boves, L., Oostdijk, N., and Coppen, P.-A. (2007). Evaluating discourse-based answer extraction for why-question answering. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’07, pages 735–736, New York, NY,… find
  32. Wellner, B., Pustejovsky, J., Havasi, C., Rumshisky, A., and Saurí, R. (2006). Classification of discourse coherence relations: an exploratory study using multiple knowledge sources. In Proceedings of the 7th SIGdial Workshop on Discourse and Dialogue, SigDIAL ’06, pages 117–125, Stroudsburg, PA, US… find our card
  33. Wolf, F. and Gibson, E. (2006). Coherence in Natural Language: Data Stuctures and Applications. The MIT Press. find

↑ back to top

This page in Markdown →