Multi-Document Summarization Using A* Search and Discriminative Learning

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 482–491, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Multi-document summarization using A* search and discriminative training Ahmet Aker Trevor Cohn Department of Computer Science University of Sheffield, Sheffield, S1 4DP, UK {a.aker, t.cohn, r.gaizauskas}@dcs.shef.ac.uk Robert Gaizauskas Abstract In this paper we address two key challenges for extractive multi-document summarization: the search problem of finding the best scoring summary and the training problem of learn- ing the best model parameters. We propose an A* search algorithm to find the best extractive summary up to a given length, which is both optimal and efficient to run. Further, we pro- pose a discriminative training algorithm which directly maximises the quality of the best sum- mary, rather than assuming a sentence-level decomposition as in earlier work. Our ap- proach leads to significantly better results than earlier techniques across a number of evalua- tion metrics. 1 Introduction Multi-document summarization aims to present multiple documents in form of a short summary. This short summary can be used as a replacement for the original documents to reduce, for instance, the time a reader would spend if she were to read the original documents. Following dominant trends in summarization research (Mani, 2001), we focus solely on extractive summarization which simplifies the summarization task to the problem of identify- ing a subset of units from the document collection (here sentences) which are concatenated to form the summary. Most multi-document summarization systems de- fine a model which assigns a score to a candidate summary based on the features of the sentences in- cluded in the summary. The research challenges are then twofold: 1) the search problem of finding the best scoring summary for a given document set, and 2) the training problem of learning the model pa- rameters to best describe a training set consisting of pairs of document sets with model or reference sum- maries – typically human authored extractive or ab- stractive summaries. Search is typically performed by a greedy al- gorithm which selects each sentence in decreasing order of model score until the desired summary length is reached (see, e.g., Saggion (2005)) or us- ing heuristic strategies based on position in docu- ment or lexical clues (Edmundson, 1969; Brandow et al., 1995; Hearst, 1997; Ouyang et al., 2010).1 We show in this paper that the search problem can be solved optimally and efficiently using A* search (Russell et al., 1995). Assuming the model only uses features local to each sentence in the summary, our algorithm finds the best scoring extractive summary up to a given length in words. Framing summarization as search suggests that many of the popular training techniques are max- imising the wrong objective. These approaches train a classifier, regression or ranking model to distin- guish between good and bad sentences under an evaluation metric, e.g., ROUGE (Lin, 2004). The model is then used during search to find a summary composed of high scoring (‘good’) sentences (see for …

Content truncated to 500 words