Topic-based Multi-document Summarization using Differential Evolution forCombinatorial Optimization of Sentences

PACLIC 28 !152 Topic-based Multi-document Summarization using Differential Evolution for Combinatorial Optimization of Sentences Haruka Shigematsu Graduate School of Humanities and Sciences, Ochanomizu University Bunkyo-ku, Tokyo 112-8610 Japan shigematsu.haruka@is.ocha.ac.jp Ichiro Kobayashi Graduate School of Humanities and Sciences, Ochanomizu University Bunkyo-ku, Tokyo 112-8610 Japan koba@is.ocha.ac.jp Abstract This paper describes a method of multi- document summarization with evolutionary computation. In automatic document sum- marization, the method to make a summary by finding the best combination of important sentences in target documents is popular ap- proach. To find the best combination of sen- tences, explicit solution techniques such as in- teger linear programming, branch and bound method, and so on are usually adopted. How- ever, there is a problem with them in terms of calculation efficiency. So, we apply evolution- ary computation, especially differential evo- lution which is regarded as a method having a good feature in terms of calculation cost to obtain a reasonable quasi-optimum solution in real time, to the problem of combinatorial op- timization of important sentences. Moreover, we consider latent topics in deciding the im- portance of a sentence, and define three fitness functions to compare the results. As a result, we have confirmed that our proposed meth- ods reduced the calculation time necessary to make a summary considerably, although pre- cision is more worse than the method with an explicit solution technique. 1 Introduction As a general method of automatic multi-document summarization, we often use the important sen- tence extraction method which obtains the most proper combination of important sentences in tar- get documents for a summary, avoiding redundancy in the generated summary. The explicit solution techniques, e.g., integer programming, branch and bound method, for optimal combination are often used under some constraints for the best combina- tion of sentences. They have however a problem in terms of calculation costs. In general, if the size of target data sets is huge, the problem of combinatorial optimization becomes NP-hard. On the other hand, as an optimization method to obtain quasi-optimum solution in real time, it is reported that evolution- ary computation is useful for realistic solutions. In this context, we employ differential evolution (DE) known as superior to other evolutionary computa- tion algorithms in terms of calculation costs and the accuracy of solution, and apply it to multi-document summarization. Besides, under an assumption that multiple topics are included in documents, latent topics in documents are extracted by means of latent Dirichlet allocation, we make a summary, consider- ing the latent topics. 2 Related studies As for document summarization using combina- torial optimization techniques, many studies em- ploy explicit solution techniques such as branch and bound method, dynamic programming, integer lin- ear programming, and so on (Mcdonald, 2007; Yih et al., 2007; Gillick et al., 2008; Takamura et al., 2009; Lin et al., 2010). However, the explicit so- lution techniques often face NP-hard, they require much calculation time for solving a problem of com- binatorial optimization, though they provide opti- mal solution. In this context, Nishikawa et al.(2012) have proposed …

Content truncated to 500 words