tailieunhanh - Báo cáo khoa học: "Computing Locally Coherent Discourses"

We present the first algorithm that computes optimal 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. | Computing Locally Coherent Discourses Ernst Althaus LORIA Universite Henri Poincare Vandreuvre-lès-Nancy France althaus@ Nikiforos Karamanis Alexander Koller School of Informatics Dept. of Computational Linguistics University of Edinburgh Saarland University Edinburgh UK Saarbrucken Germany koller@ Abstract We present the first algorithm that computes optimal 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 transitions. This is in contrast to theories of global coherence which can consider relations between larger chunks of the discourse and . 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 . 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 ordering of the sentences in a discourse that maximises local coherence is still largely unsolved. The fundamental problem is that any of the factorial number of permutations