Text Summarization Model Based on Maximum Coverage Problem and its Variant

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 781–789, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Text Summarization Model based on Maximum Coverage Problem and its Variant Hiroya Takamura and Manabu Okumura Precision and Intelligence Laboratory, Tokyo Institute of Technology 4259 Nagatsuta Midori-ku Yokohama, 226-8503 takamura@pi.titech.ac.jp oku@pi.titech.ac.jp Abstract We discuss text summarization in terms of maximum coverage problem and its vari- ant. We explore some decoding algorithms including the ones never used in this sum- marization formulation, such as a greedy algorithm with performance guarantee, a randomized algorithm, and a branch-and- bound method. On the basis of the results of comparative experiments, we also aug- ment the summarization model so that it takes into account the relevance to the doc- ument cluster. Through experiments, we showed that the augmented model is su- perior to the best-performing method of DUC’04 on ROUGE-1 without stopwords. 1 Introduction Automatic text summarization is one of the tasks that have long been studied in natural language processing. This task is to create a summary, or a short and concise document that describes the content of a given set of documents (Mani, 2001). One well-known approach to text summariza- tion is the extractive method, which selects some linguistic units (e.g., sentences) from given doc- uments in order to generate a summary. The ex- tractive method has an advantage that the gram- maticality is guaranteed at least at the level of the linguistic units. Since the actual generation of linguistic expressions has not achieved the level of the practical use, we focus on the extractive method in this paper, especially the method based on the sentence extraction. Most of the extractive summarization methods rely on sequentially solv- ing binary classification problems of determining whether each sentence should be selected or not. In such sequential methods, however, the view- point regarding whether the summary is good as a whole, is not taken into consideration, although a summary conveys information as a whole. We represent text summarization as an opti- mization problem and attempt to globally solve the problem. In particular, we represent text sum- marization as a maximum coverage problem with knapsack constraint (MCKP). One of the advan- tages of this representation is that MCKP can di- rectly model whether each concept in the given documents is covered by the summary or not, and can dispense with rather counter-intuitive ap- proaches such as giving penalty to each pair of two similar sentences. By formally apprehending the target problem, we can use a lot of knowledge and techniques developed in the combinatorial mathe- matics, and also analyse results more precisely. In fact, on the basis of the results of the experiments, we augmented the summarization model. The contributions of this paper are as follows. We are not the first to represent text summarization as MCKP. However, no researchers have exploited the decoding algorithms for solving MCKP in the summarization task. We conduct compre- hensive comparative experiments of those …

Content truncated to 500 words