Evaluating Hierarchical Discourse Segmentation

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 993–1001, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Evaluating Hierarchical Discourse Segmentation Lucien Carroll Linguistics Dept. UC San Diego San Diego, CA 92093 lucien@ling.ucsd.edu Abstract Hierarchical discourse segmentation is a use- ful technology, but it is difficult to eval- uate. I propose an error measure based on the word error rate of Beeferman et al. (1999). I then show that this new measure not only reliably distinguishes baseline seg- mentations from lexically-informed hierarchi- cal segmentations and more informed segmen- tations from less informed segmentations, but it also offers an improvement over previous linear error measures. 1 Introduction Discourse segmentation is the task of identifying co- herent clusters of sentences and the points of transi- tion between those groupings. Discourse segmenta- tion can be viewed as shallow parsing of discourse structure. The segments and the relations between them are left unlabeled, focusing instead on the boundaries between the segments (i.e., the bracket- ing). Discourse segmentation is thought to facilitate automatic summarization (Angheluta et al., 2002; Boguraev and Neff, 2000), information retrieval (Kaszkiel and Zobel, 1997), anaphora resolution (Walker, 1997) and question answering (Chai and Jin, 2004). Automatic discourse segmentation, as shallow annotation of discourse structure, also pro- vides a testing grounds for linguistic theories of dis- course (Passonneau and Litman, 1997) and provides a natural unit of measure in linguistic corpora (Biber et al., 2004). 1.1 The structure of discourse Research in discourse structure theory (Hobbs, 1985; Grosz and Sidner, 1986; Mann and Thomp- son, 1988; Kehler, 2002; Asher and Lascarides, 2003; Webber, 2004) and discourse parsing (Marcu, 2000; Forbes et al., 2003; Polanyi et al., 2004; Baldridge et al., 2007) has variously defined dis- course structure in terms of communicative inten- tion, attention, topic/subtopic structure, coherence relations, and cohesive devices. There is much dis- agreement about the units and elementary relations of discourse structure, but they agree that the struc- tures are hierarchical, most commonly trees (Marcu, 2000), while others have argued for directed acyclic graphs (Danlos, 2004), or general graphs (Wolf and Gibson, 2004). In contrast, most of the segmentation research to date has focused on linear segmentation, in which segments are non-overlapping and sequen- tial, and it has been argued that this sequence model is sufficient for many purposes (Hearst, 1994). I fo- cus here on tree discourse segmentation, in which larger segments are composed of sequences of sub- segments. This is potentially more informative and more faithful to linguistic theory than linear dis- course segmentation is, but it poses a more challeng- ing evaluation problem. 1.2 Hierarchical segmentation Four studies have described hierarchical discourse segmentation algorithms, but none of them rigor- ously evaluated the segmentation in its hierarchi- cal form. Yaari (1997) used a hierarchical cluster- ing algorithm for hierarchical discourse segmenta- tion, and to evaluate it, he linearized the tree (tak- ing all boundaries equally) and compared the result- 993 ing precision and recall to contemporary linear …

Content truncated to 500 words