A Machine Learning Approach to Sentence Ordering for Multidocument Summarization and Its Evaluation

A Machine Learning Approach to Sentence Ordering for Multidocument Summarization and Its Evaluation Danushka Bollegala, Naoaki Okazaki, and Mitsuru Ishizuka University of Tokyo, Japan Abstract. Ordering information is a difficult but a important task for natural language generation applications. A wrong order of information not only makes it difficult to understand, but also conveys an entirely different idea to the reader. This paper proposes an algorithm that learns orderings from a set of human ordered texts. Our model consists of a set of ordering experts. Each expert gives its precedence preference between two sentences. We combine these preferences and order sentences. We also propose two new metrics for the evaluation of sentence orderings. Our experimental results show that the proposed algorithm outperforms the existing methods in all evaluation metrics. 1 Introduction The task of ordering sentences arises in many fields. Multidocument Summa- rization (MDS) [5], Question and Answer (QA) systems and concept to text generation systems are some of them. These systems extract information from different sources and combine them to produce a coherent text. Proper ordering of sentences improves readability of a summary [1]. In most cases it is a trivial task for a human to read a set of sentences and order them coherently. Hu- mans use their wide background knowledge and experience to decide the order among sentences. However, it is not an easy task for computers. This paper pro- poses a sentence ordering algorithm and evaluate its performance with regard to MDS. MDS is the task of generating a human readable summary from a given set of documents. With the increasing amount of texts available in electronic format, automatic text summarization has become necessary. It can be considered as a two-stage process. In the first stage the source documments are analyzed and a set of sentences are extracted. However, the document set may contain repeating information as well as contradictory information and these challenges should be considered when extracting sentences for the summary. Researchers have already investigated this problem and various algorithms exist. The second stage of MDS creates a coherent summary from this extract. When summarizing a single document, a naive strategy that arranges extracted sentences according to the appearance order may yield a coherent summary. However, in MDS the extracted sentences belong to different source documents. The source documents R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 624–635, 2005. c ⃝ Springer-Verlag Berlin Heidelberg 2005 A Machine Learning Approach to Sentence Ordering 625 may have been written by various authors and on various dates. Therefore we cannot simply order the sentences according to the position of the sentences in the original document to get a comprehensible summary. This second stage of MDS has received lesser attention compared to the first stage. Chronological ordering; ordering sentences according to the pub- lished date of the documents they belong to [6], is one solution to this problem. However, showing that this approach is insufficient, Barzilay [1] proposed an refined algorithm which integrates chronology ordering with …

Content truncated to 500 words