Computing Locally Coherent Discourses

Computing Locally Coherent Discourses Ernst Althaus LORIA Universit´e Henri Poincar´e Vandœuvre-l`es-Nancy, France althaus@loria.fr Nikiforos Karamanis School of Informatics University of Edinburgh Edinburgh, UK N.Karamanis@sms.ed.ac.uk Alexander Koller Dept. of Computational Linguistics Saarland University Saarbr¨ucken, Germany koller@coli.uni-sb.de Abstract We present the first algorithm that computes opti- mal orderings of sentences into a locally coherent discourse. The algorithm runs very efficiently on a variety of coherence measures from the literature. We also show that the discourse ordering problem is NP-complete and cannot be approximated. 1 Introduction One central problem in discourse generation and summarisation is to structure the discourse in a way that maximises coherence. Coherence is the property of a good human-authored text that makes it easier to read and understand than a randomly- ordered collection of sentences. Several papers in the recent literature (Mellish et al., 1998; Barzilay et al., 2002; Karamanis and Ma- nurung, 2002; Lapata, 2003; Karamanis et al., 2004) have focused on defining local coherence, which evaluates the quality of sentence-to-sentence transi- tions. This is in contrast to theories of global coher- ence, which can consider relations between larger chunks of the discourse and e.g. structures them into a tree (Mann and Thompson, 1988; Marcu, 1997; Webber et al., 1999). Measures of local coherence specify which ordering of the sentences makes for the most coherent discourse, and can be based e.g. on Centering Theory (Walker et al., 1998; Brennan et al., 1987; Kibble and Power, 2000; Karamanis and Manurung, 2002) or on statistical models (Lap- ata, 2003). But while formal models of local coherence have made substantial progress over the past few years, the question of how to efficiently compute an order- ing of the sentences in a discourse that maximises local coherence is still largely unsolved. The fun- damental problem is that any of the factorial num- ber of permutations of the sentences could be the optimal discourse, which makes for a formidable search space for nontrivial discourses. Mellish et al. (1998) and Karamanis and Manurung (2002) present algorithms based on genetic programming, and Lapata (2003) uses a graph-based heuristic al- gorithm, but none of them can give any guarantees about the quality of the computed ordering. This paper presents the first algorithm that com- putes optimal locally coherent discourses, and es- tablishes the complexity of the discourse ordering problem. We first prove that the discourse order- ing problem for local coherence measures is equiva- lent to the Travelling Salesman Problem (TSP). This means that discourse ordering is NP-complete, i.e. there are probably no polynomial algorithms for it. Worse, our result implies that the problem is not even approximable; any polynomial algorithm will compute arbitrarily bad solutions on unfortunate in- puts. Note that all approximation algorithms for the TSP assume that the underlying cost function is a metric, which is not the case for the coherence mea- sures we consider. Despite this negative result, we show that by ap- plying modern algorithms for TSP, the discourse or- dering problem can be solved efficiently enough for practical applications. …

Content truncated to 500 words