VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY DO THUY DUONG RESEARCH AND APPLY EVOLUTIONARY COMPUTATION TECHNIQUES ON AUTOMATIC TEXT SUMMARIZATION MASTER THESIS IN INFORMATION TECHNOLOGY HANOI - 2015 TIEU LUAN MOI download : skknchat@gmail.com VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY DO THUY DUONG RESEARCH AND APPLY EVOLUTIONARY COMPUTATION TECHNIQUES ON AUTOMATIC TEXT SUMMARIZATION Field: Information technology Major: Software Engineering Code: 60480103 MASTER THESIS IN INFORMATION TECHNOLOGY SUPERVISOR: Assoc. Nguyen Xuan Hoai HANOI - 2015 TIEU LUAN MOI download : skknchat@gmail.com 3 Declaration of authorship I, Do Thuy Duong, declare that this thesis ‘Research and apply evolutionary computation techniques on automatic text summarization’ and the work presented in it are my own. I confirm that: This work was done wholly or mainly while in candidature for a research degree at this University; Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated; Where I have consulted the published work of others, this is always clearly attributed; I have acknowledged all main sources of help; Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself; Signed: …………………………………………………………………………………… Date: …………………………………………………………………………………… TIEU LUAN MOI download : skknchat@gmail.com 4 Acknowledgements I am heartily thankful to my supervisor, Prof. Nguyen Xuan Hoai, whose encouragement, guidance and support from the initial to the final level have enabled me to develop an understanding of the topic.
I would like to show my gratitude to the teachers in the University of Engineering and Technology, Vietnam National University, Hanoi for helping me to gain a large body of knowledge during my two years of studying. Lastly, I offer my regards and blessings to my friends and my family, who have always encouraged me so that I could finish this challenging research. TIEU LUAN MOI download : skknchat@gmail.SUMMARIZATION 5 Contents Declaration of authorship. 5 List of figures.
7 List of tables. Automatic text summarization. Types of text summarization. Methodologies for automatic text summarization.
27 Automatic text summarization using differential evolution algorithm. Automatic text summarization using differential evolution (DE). Document collection representation. Objective/ Fitness function.
28 TIEU LUAN MOI download : skknchat@gmail. Main steps of differential evolution. Experiment, result and discussion. Experiment, result and discussion.
47 Conclusion and future work. 48 TIEU LUAN MOI download : skknchat@gmail.SUMMARIZATION 7 List of figures Figure 2. A typical summarization system. A summarizer highlights all sentences included in an extractive summary.
An example of the abstract summary. Multi-document summarization. The general scheme of an Evolutionary Algorithm in pseudo-code 17 Figure 2. General scheme of evolutionary algorithms.
Correlation between number of generations and best fitness in population. Steps of differential evolution algorithm. Steps to get the next X1 (generation 1). Illustration of mutation operation.
Illustration of crossover operation. Changes in summary length in [DE] method on DUC2004. Changes in summary length in [DE] method on DUC2007. Summary length in [MultiDE] method on DUC2004.
Summary length in [MultiDE] method on DUC2007. Comparison between F-values of [DE] and [MultiDE] on DUC2004. Comparison between F-values of [DE] and [MultiDE] on DUC2007. 46 TIEU LUAN MOI download : skknchat@gmail.SUMMARIZATION 8 List of tables Table 2.
The basic evolutionary computation linking natural evolution to problem solving .Fitness of six individuals at generation 0. Creation of mutant vector V1. Creation of trial vector Z1. Values of X1 in generation 1.
Description of the datasets used in the experiment. Parameter settings of the first experiment. Summary lengths of some document collections in DUC2004 using [DE] method. Summary lengths of some document collections in DUC2007 using [DE] method.
F-Values of three evaluation measures of method [DE] on DUC2004 and DUC2007. Parameter settings of the second experiment. Summary lengths of some document collections in DUC2004 using [MultiDE] method. Summary lengths of some document collections in DUC2007 using [MultiDE] method.
F-Values of three evaluation measures of method [MultiDE] on DUC2004 and DUC2007. 45 TIEU LUAN MOI download : skknchat@gmail. Chapter 1 Introduction Automatic text summarization means detecting important and condensed contents in one or more documents. This is a very challenging problem, relating to many scientific areas such as artificial intelligence, statistics, linguistics, etc.
Many researches have been conducted world wide since 1950 and produced some systems such as SUMMARIST, SweSUM, MEAD, SUMMON, etc. However, this research area is still challenging and attracts more and more attention. In this thesis, we are going to study some evolutionary computation techniques, then apply the differential evolution algorithm to the practical problem: automatic text summarization, in particular, multi-document summarization. Moreover, we also attempt to deal with constraint on the summary length that has not been handled effectively in these stochastic popular-based methods.
Motivation Evolutionary computation techniques use different algorithms to evolve a population of individuals over a certain number of generations. These population are applied with operations on such as mutation, crossover and selection to reproduce new offspring, which then compete with each other and the previous generation to survive based on some evaluation function. The process ends when a stopping criteria is reached and we found the best individual – the best solution to our real-world problem. Evolutionary algorithms have been applied to solve numerous problems in various fields, one of which is automatic text summarization.
However, we have found it has a weak point in handling the summary length, not like other sentence ranking methods. Therefore, this research attempts to improve this aspect of these algorithms. TIEU LUAN MOI download : skknchat@gmail. Research Objectives The thesis is aimed to study evolutionary computation techniques, especially the differential evolution algorithm, and its application to the problem of automatic text summarization.
We find the limitation of other researchers’ ways to handle the summary length of this algorithm, then propose a new method to manage this length constraint satisfying users’ demand, but still keep the quality of the summary. Thesis overview The rest of this thesis is organized as follows. In chapter 2, we review the background knowledge of text summarization, its classification and introduce the main principles of evolutionary computation. In particular, the differential evolution algorithm is discussed.
Chapter 3 explains in details the above algorithm when applied to automatic text summarization, in our case it is on multi-document collections. Then, an experiment is performed to test the original differential evolution algorithm. Besides, we improve the result of the previous experiment, dealing with the summary length so that the document collection is compressed quickly and effectively. Chapter 4 will recapitulate the thesis, present our contributions and state some future research directions in this field.
TIEU LUAN MOI download : skknchat@gmail. Chapter 2 Background knowledge In this chapter, text summarization is reviewed before we introduce and classify evolutionary computation. Then, an evolutionary algorithm namely differential evolution is discussed in details. Automatic text summarization 2.
Definition Automatic text summarization is the generation of a shorter version of a text by a computer program but still keep the most important points of the original text. [16] The aim of automated text summarization is to take a source text, extract the most significant content from it, and present it in a condensed form and in a way sensitive to the user’s or application’s needs. A summarization system experiences some steps to generate a summary from a document or a collection of documents. First of all, the document is preprocessed, for example, handling punctuations, lower/upper case, splitting paragraph, sentences, words, etc… Then, document is represented in a certain data type such as vectors, each of which represent a sentence.
The third step, known as the key phase, is to create the summary representation from the document representation. For instance, after this stage, some of the above vectors are chosen to be included in the summary. Finally, from the summary representation, we could form the summary via summary generation stage.1 represents a typical summarization system. TIEU LUAN MOI download : skknchat@gmail.
A typical summarization system 2. Types of text summarization There are some ways to classify approaches to automatic text summarization as follows: [16] - Content: Extract: An extract-type summary only contains units ranging from single words to whole paragraphs, which are taken verbatim from the original text.2 presents a summarization system which selects important sentences to be included in the extractive summary. TIEU LUAN MOI download : skknchat@gmail. A summarizer highlights all sentences included in an extractive summary Abstract: An abstract-type summary is a newly generated text, covering the source text’s content as well as the source text reviews, which requires the summarizer to have prior knowledge about the source text topic.
The following Figure 2.3 captures an abstract summarizing the content of the whole paper. TIEU LUAN MOI download : skknchat@gmail. An example of the abstract summary - Audience: Generic: A generic summary provides the author’s point of views of the source text, paying the same attention to every aspect of the text. Query-oriented: A query-oriented (or user-oriented) summary prefers some particular aspects of the text, depending on aspects that a user desires to learn about.
- Usage: Indicative: An indicative summary only indicates the main subject matter or domain of the input text without including its contents. After reading an indicative summary, one can explain what the input text was about, but not necessarily what was contained in it. Informative: An informative summary covers (some of) the content, and allows one to describe (parts of) what was in the input text. - Expansiveness: TIEU LUAN MOI download : skknchat@gmail.SUMMARIZATION 15 Background: Assumes readers do not have prior knowledge about the source text topic.
Just-the-news: Supposes reader’s prior knowledge is up-to-date. cross-lingual: Just summarizes in the same language vs. summarizes as well as translates into another language. - Single-document vs.
multi-document source: Summarizes only one source text vs. fuses together many source texts.4 demonstrates a multi-document summarizer, which summarizes five documents into only one summary. Multi-document summarization In this thesis, we intend to generate extractive summaries for multi-document collections. Summarizing a single text is challenging enough, summarizing a document collection poses even more difficulties.
We have to avoid repetitions, manage potential inconsistencies among documents, but can still cover all essential information of the original text. Methodologies for automatic text summarization Up to now, there have been many methods applied to summarize text automatically including [21]: - Traditional methods: term, word, phrase frequencies - Corpus-based approaches: combination of statistical features, learning to extract - Discourse structures: Word-net, Rhetorical analysis - Knowledge rich approaches: different for particular domains Evolutionary computation is a new approach to summarize text automatically, in which solutions are evolved until a certain benchmark is satisfied. TIEU LUAN MOI download : skknchat@gmail. Evolutionary computation In computer science, evolutionary computation is a subfield of artificial intelligence, defined by some types of evolutionary algorithms which is based on Darwinian principles.
They belong to the family of trial and error problem solvers and can be regarded as global optimization methods with meta-heuristic or stochastic optimization character, in which there exists the utilization of a population of candidate solutions [1]. Evolutionary computation uses continuous progression of the population, which is then selected in a guided random search to get the required stop. Automated problem solving that uses Darwinian principles started in the 1950s. However, three different interpretations of this idea started to be implemented in 1960s in three strands.
Evolutionary programming (EP) was invented by Lawrence J.Fogel in the US, while John Henry suggested a method named genetic algorithm (GA). Ingo Rechenberg and Hans-Paul Schwefel introduced evolution strategies (ES). Although these algorithms are proposed quite soon, they are only considered as different types of one technology known as evolutionary computation from the early nineties [1].