Elamur Research⌕
☰
home / papers / 2016 / Integer Linear Programming for Discourse Parsing

Integer Linear Programming for Discourse Parsing

Summary

Discourse parsing of multi-party chat is still poorly developed, and tree-based frameworks such as RST do not fit well. In these dialogues, replies cross between concurrent threads, and a single move can acknowledge several earlier ones, so many structures are not trees. Perret et al. build what they describe as the first discourse parser that can output non-tree DAGs. They score candidate attachments and relation labels with local probabilistic models. A global Integer Linear Programming (ILP) decoder then combines these scores under structural constraints, handling attachment and labelling together in one objective. The work follows the SDRT framework and uses the Settlers of Catan chat corpus. The authors also revisit how complex discourse units (CDUs) are flattened. The usual head replacement step distorts meaning, so they propose distributing relations over CDU members according to whether each relation is left- or right-distributive. ILP decoding beats the MST approach of Afantenos et al. (2015) on the same data. This shows that graph-based discourse parsing for dialogue is feasible and leaves more room for improvement than tree-only methods.

Key points

  • Data: the Settlers corpus contains 39 games annotated in SDRT style, totalling 1091 dialogues, 10677 EDUs and 1284 CDUs. About 10% (123 dialogues) is held out for testing.
  • Why trees fail: restricting structures to trees loses roughly 9% of the corpus's discourse links.
  • CDU translations: three ways of turning CDUs into dependency graphs are compared: head replacement, partial distribution and full distribution. Distribution uses the left- and right-distributivity of SDRT relations.
  • Best result: with head replacement, ILP reaches F1 0.531 on fully labelled structures and 0.689 unlabelled. MST decoding scores 0.516 and 0.671 on the same measures.
  • Turn constraint: the turn constraint is built directly into ILP decoding rather than applied outside it. The authors see future potential for predicting CDUs and full hierarchical structure.

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/n16-1013

@inproceedings{perret2016integer,
  title = {{Integer Linear Programming for Discourse Parsing}},
  author = {Perret, Jérémy and Afantenos, Stergos and Asher, Nicholas and Morey, Mathieu},
  booktitle = {Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2016},
  doi = {10.18653/v1/n16-1013},
  url = {https://doi.org/10.18653/v1/n16-1013}
}

References

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

  1. Stergos Afantenos, Nicholas Asher, Farah Benamara, Anas Cadilhac, Cdric Degremont, Pascal Denis, Markus Guhe, Simon Keizer, Alex Lascarides, Oliver Lemon, Philippe Muller, Soumya Paul, Verena Rieser, and Laure Vieu. 2012. Developing a corpus of strategic conversation in the settlers of catan. In Nor… find
  2. Nicholas Asher and Alex Lascarides. 2003. Logics of Conversation. Studies in Natural Language Processing. find
  3. Cambridge University Press, Cambridge, UK. Nicholas Asher. 1993. Reference to Abstract Objects in Discourse. find
  4. Kluwer Academic Publishers. 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). find
  5. A. Berger, S. Della Pietra, and V. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71. Chloé Braud and Pascal Denis. 2015. Comparing word representations for implicit discourse relation classification. In Proceedings of the 2015 Con… find our card
  6. Anais Cadilhac, Nicholas Asher, Farah Benamara, and Alex Lascarides. 2013. Grounding strategic conversation: Using negotiation dialogues to predict trades in a win-lose game. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 357–368, Seattle, Washington… find
  7. Lynn Carlson, Daniel Marcu, and Mary Ellen Okurowski. 2003. Building a discourse-tagged corpus in the framework of rhetorical structure theory. In Jan van Kuppevelt and Ronnie Smith, editors, Current Directions in Discourse and Dialogue, pages 85–112. Kluwer Academic Publishers. Dipanjan Das, Desai… find our card
  8. Pascal Denis and Jason Baldridge. 2007. Joint determination of anaphoricity and coreference resolution using integer programming. In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pa… find our card
  9. Pascal Denis and Philippe Muller. 2011. Predicting globally-coherent temporal structures from texts via endpoint inference and graph decomposition. In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI). David duVerle and Helmut Prendinger. 2009. A novel discourse parser b… find our card
  10. Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING-96), volume 1, pages 340–345, Copenhagen, Denmark. find our card
  11. Micha Elsner and Eugene Charniak. 2010. Disentangling chat. Computational Linguistics, 36(3):389– 409. find
  12. Micha Elsner and Eugene Charniak. 2011. Disentangling chat with local coherence models. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 1179–1189, Portland, Oregon, USA, June. Association for Computational Linguistics. find
  13. 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 (Volume 1: Long Papers), pages 60–68, Jeju Island, Korea, July. Association for Computational Linguistics. D… find our card
  14. Tsutomu Hirao, Yasuhisa Yoshida, Masaaki Nishino, Norihito Yasuda, and Masaaki Nagata. 2013. Single-document summarization as a tree knapsack problem. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1515–1520, Seattle, Washington, USA, October. Associ… find
  15. 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 (Volume 1: Long Papers), pages 486–496, Sofi… find
  16. Shafiq Joty, Giuseppe Carenini, and Raymond Ng. 2015. Codra: A novel discriminative framework for rhetorical analysis. Computational Linguistics. find our card
  17. Sujian Li, Liang Wang, Ziqiang Cao, and Wenjie Li. 2014. Text-level discourse dependency parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 25–35, Baltimore, Maryland, June. Association for Computational Linguistics. find
  18. Ziheng Lin, Min-Yen Kan, and Hwee Tou Ng. 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, August. Association for Computational Linguistics. find our card
  19. William C. Mann and Sandra A. Thompson. 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
  20. William C. Mann and Sandra A. Thompson. 1988. Rhetorical Structure Theory: Towards a Functional Theory of Text Organization. Text, 8(3):243–281. find
  21. Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014. The Stanford CoreNLP natural language processing toolkit. In Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 55–60. find our card
  22. Daniel Marcu and Abdessamad Echihabi. 2002. An unsupervised approach to recognizing discourse relations. In Proceedings of ACL, pages 368–375. find our card
  23. Andre Martins, Noah Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 34– 44, Cambridge, MA, October. Association for Com… find our card
  24. Ryan T. McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In HLT/EMNLP. find our card
  25. 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 our card
  26. The COLING 2012 Organizing Committee. find
  27. Rashmi Prasad, Nikhil Dinesh, Alan Lee, Eleni Milt-sakaki, Livio Robaldo, Aravind Joshi, and Bonnie L. Webber. 2008. The Penn Discourse TreeBank 2.0. In Proceedings of LREC 2008. find our card
  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, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  29. R. Soricut and D. 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, pages 149–156. Association for Computat… find our card
  30. Caroline Sporleder and Alex Lascarides. 2005. Exploiting linguistic cues to classify rhetorical relations. In Proceedings of Recent Advances in Natural Langauge Processing (RANLP), Bulgaria. find
  31. 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, J… find our card
  32. Maite Taboada and William C. Mann. 2006. Rhetorical Structure Theory: Looking Back and Moving Ahead. Discourse Studies, 8(3):423–459, June. find
  33. Li Wang, Marco Lui, Su Nam Kim, Joakim Nivre, and Timothy Baldwin. 2011. Predicting thread discourse structure over technical web forums. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 13–25, Edinburgh, Scotland, UK., July. Association for Computatio… find

↑ back to top

This page in Markdown →