# Inferring Strategies For Sentence Ordering In Multidocument News Summarization

Regina Barzilay **regina@cs.columbia.edu** Noemie Elhadad **noemie@cs.columbia.edu** Kathleen R. McKeown **kathy@cs.columbia.edu**
Columbia University, Computer Science Department 1214 Amsterdam Ave New York, 10027, NY, USA

## Abstract

The problem of organizing information for multidocument summarization so that the generated summary is coherent has received relatively little attention. While sentence ordering for single document summarization can be determined from the ordering of sentences in the input article, this is not the case for multidocument summarization where summary sentences may be drawn from different input articles. In this paper, we propose a methodology for studying the properties of ordering information in the news genre and describe experiments done on a corpus of multiple acceptable orderings we developed for the task. Based on these experiments, we implemented a strategy for ordering information that combines constraints from chronological order of events and topical relatedness. Evaluation of our augmented algorithm shows a significant improvement of the ordering over two baseline strategies.

## 1. Introduction

Multidocument summarization poses a number of new challenges over single document summarization. Researchers have already investigated issues **such as identifying repetitions or**
contradictions across input documents and determining which information is salient enough to include in the summary (Barzilay, McKeown, & Elhadad, 1999; Carbonell & Goldstein, 1998; Elhadad & McKeown, 2001; Mani & Bloedorn, 1997; McKeown, Klavans, Hatzivassiloglou, Barzilay, & Eskin, 1999; Radev & McKeown, 1998; White, Korelsky, Cardie, Ng, Pierce, & Wagstaff, 2001). One issue that has received little **attention is how to organize** the selected information so that the output summary is coherent. Once all the relevant pieces of information have been selected across the input documents, the summarizer has to decide in which order to present them so that the whole text **makes sense. In single** document summarization, one possible ordering of the extracted information is provided by the input document itself. However, Jing (1998) observed that, in single document summaries written by professional summarizers, extracted sentences do not always retain their precedence orders in the summary. Moreover, in the case of multiple input documents, this does not provide a useful solution: information may be drawn **from different documents and** therefore, no single document can provide an ordering. Furthermore, the order between two pieces of information can change significantly from one document to another.

In this paper, we provide a corpus based methodology for studying ordering. Our goal was to develop a good ordering strategy in the context of multidocument summarization