Integer Linear Programming for Discourse Parsing

Proceedings of NAACL-HLT 2016, pages 99–109, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Integer Linear Programming for Discourse Parsing J´er´emy Perret Stergos Afantenos Nicholas Asher Mathieu Morey IRIT, Universit´e de Toulouse & CNRS 118 Route de Narbonne, 31062 Toulouse, France {firstname.lastname@irit.fr} Abstract In this paper we present the first, to the best of our knowledge, discourse parser that is able to predict non-tree DAG structures. We use Integer Linear Programming (ILP) to encode both the objective function and the constraints as global decoding over local scores. Our un- derlying data come from multi-party chat dia- logues, which require the prediction of DAGs. We use the dependency parsing paradigm, as has been done in the past (Muller et al., 2012; Li et al., 2014; Afantenos et al., 2015), but we use the underlying formal framework of SDRT and exploit SDRT’s notions of left and right distributive relations. We achieve an F- measure of 0.531 for fully labeled structures which beats the previous state of the art. 1 Introduction Multi-party dialogue parsing, in which complete discourse structures for multi-party dialogue or its close cousin, multi-party chat, are automatically constructed, is still in its infancy. Nevertheless, these are now very common forms of communica- tion on the Web. Dialogue appears also importantly different from monologue. Afantenos et al. (2015) point out that forcing discourse structures to be trees will perforce miss 9% of the links in their corpus, because a significant number of discourse structures in the corpus are not trees. Although Afantenos et al. (2015) is the only prior paper we know of that studies dialogue parsing on multi-party dialogue, and that work relied on methods adapted to treelike structures, we think the area of multi-party dialogue and non-treelike discourse structures is ripe for in- vestigation and potentially important for other gen- res like the discourse analysis of fora (Wang et al., 2011, for example). This paper proposes a method based on constraints using Integer Linear Program- ming decoding over local probability distributions to investigate both treelike and non-treelike, full dis- course structures for multi-party dialogue. We show that our method outperforms that of Afantenos et al. (2015) on the corpus they developed. Discourse parsing involves at least three main steps: the segmentation of a text into elementary discourse units (EDUs), the basic building blocks for discourse structures, the attachment of EDUs to- gether into connected structures for texts, and finally the labelling of the links between discourse units with discourse relations. Much current work in dis- course parsing focuses on the labelling of discourse relations, using data from the Penn Discourse Tree- bank (PDTB) (Prasad et al., 2008). This work has availed itself of increasingly sophisticated features of the semantics of the units to be related (Braud and Denis, 2015); but as the PDTB does not provide full discourse structures for texts, it is not relevant to our concerns here. Rhetorical Structure Theory (RST) (Mann and Thompson, 1987; Mann and Thompson, 1988; Taboada and Mann, 2006) does …

Content truncated to 500 words