Đang chuẩn bị liên kết để tải về tài liệu:
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@loria.fr Nikiforos Karamanis Alexander Koller School of Informatics Dept. of Computational Linguistics University of Edinburgh Saarland University Edinburgh UK Saarbrucken Germany N.Karamanis@sms.ed.ac.uk koller@coli.uni-sb.de 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 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 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