Combining Hierarchical Clustering and Machine Learning to Predict High-Level Discourse Structure

Combining Hierarchical Clustering and Machine Learning to Predict High-Level Discourse Structure Caroline Sporleder and Alex Lascarides School of Informatics University of Edinburgh 2 Buccleuch Place, Edinburgh EH8 9LW � csporled, alex � @inf.ed.ac.uk Abstract We propose a novel method to predict the inter- paragraph discourse structure of text, i.e. to infer which paragraphs are related to each other and form larger segments on a higher level. Our method com- bines a clustering algorithm with a model of seg- ment “relatedness” acquired in a machine learning step. The model integrates information from a va- riety of sources, such as word co-occurrence, lexi- cal chains, cue phrases, punctuation, and tense. Our method outperforms an approach that relies on word co-occurrence alone. 1 Introduction For the interpretation of texts, it is not enough to un- derstand each sentence individually; one also needs to have an idea of how sentences relate to each other, i.e. one needs to know the discourse structure of the text. This knowledge is important for many NLP applications, e.g. text summarisation or question an- swering. Most discourse theories, such as Rhetori- cal Structure Theory (RST) (Mann and Thompson, 1987), assume that discourse structure can be rep- resented as a tree whose leaves are the elementary discourse units (edus) of the text, e.g. sentences or clauses. Edus are linked to each other by rhetorical relations, such as Contrast or Elaboration, and then form larger text segments (represented by interme- diate nodes in the tree), which in turn can be linked to other segments via rhetorical relations, giving rise to even larger segments. Discourse parsing is concerned with inferring discourse structure automatically and can be viewed as consisting of three co-dependent subtasks: (i) identifying the edus, (ii) determining which dis- course segments (edus or larger segments) relate to each other, i.e. finding the correct attachment site for each segment, and (iii) identifying how dis- course segments are related to each other, i.e. infer- ring the rhetorical relation. While these tasks have been dealt with quite well for small structures (i.e. on clause and sentence level) (Soricut and Marcu, 2003), many of these approaches cannot be applied directly to higher- level structures (e.g. on multi-sentence and inter- paragraph level) because they rely nearly exclu- sively on cue phrases, which are much less useful for large structures (Marcu, 2000, p. 129). In this paper, we focus exclusively on inferring high-level structure. In particular, we investigate ways to auto- matically determine the correct attachment site for paragraph and multi-paragraph segments. Finding a good attachment site is a complex task; even if one requires the final structure to be a tree, the number of valid structures grows rapidly with the number of edus in a text. An exhaustive search is often not feasible, even for relatively small texts. One way to address this problem is by making an assumption that discourse structure correlates with higher-level text structure, i.e. that it obeys sen- tence, paragraph and section breaks (Marcu, 2000). Under this assumption a non-sentential edu …

Content truncated to 500 words