1 Introduction
One phenomenon of the digital age is the presence of a large amount of online information in various forms on the internet and other computer networks, and their ever-increasing growth rate. In the meantime, textual documents are the most frequently used forms of information. Users’ effective access to concise information is one of the problems caused by this phenomenon, so that searching news topics in the search engines offers thousands and perhaps millions of web pages to the users. In this way, the major problem for the user is the time-consuming (and perhaps impossible) process of exploring this data to reach a definite and concise conclusion about the subject. On the other hand, there are also other problems such as inconsistency or conflict between data and information, completion, and updates of this information in short periods of time, uncertainty about coherence and suitability of data and information, etc. (Nenkova Reference Nenkova2006).
Automatic summarization of textual documents is a solution that has been widely regarded by researchers in recent years. A summary of information could be produced by using textual documents summarization mechanisms so that the user can be informed about the content of documents by reading the summary. So in a short time, he can decide whether to use the documents or not. The concept of summarization has been mentioned and explored in natural language processing issues for more than six decades. However, this topic has been researched seriously for less than two decades. The most important reasons for this phenomenon are the spreading of the internet and other communication networks, the large amounts of data and information on them, and the need to summarize this data to save time and effort (Das and Martins Reference Das and Martins2007).
An automatic document summarization system is a system that receives one or more documents as inputs and processes them without human intervention to produce a coherent and versatile summary with a fixed length (Nenkova Reference Nenkova2006). By ‘summary’, we mean a text that has been produced from one or more documents, contains the most important information of the original documents, and its length is shorter than half of the original document (Radev, Hovy and McKeown Reference Radev, Hovy and McKeown2002). In fact, the summarization system aims to produce a summary that has maximum coverage of original information contents with minimum redundancy. This type of summarization is called informative summarization. Also, there is another type of summarization that is called indicative summarization and its goal is to find relevant documents with same information. On the other hand, the informative summary that has been generated by the system must have an acceptable level of performance, compliance and readability in comparison with the summary that has been written by a human expert, so that the reader can be truly conversant with the most important contents of the input documents via reading the summary (Lin Reference Lin2004; Lin et al. Reference Lin, Cao, Gao and Nie2006; Rankel et al. Reference Rankel, Conroy, Dang and Nenkova2013).
Document summarization systems have been categorized into two categories according to the number of input documents: single-document summarization and multi-document summarization. Also, they have been categorized into two groups according to the summary generation approach: extractive summarization and abstractive summarization. In the extractive approach, the summary is generated by selecting some sentences from sentences of the input documents according to a combination of some features (such as sentence position, correspondence with keywords, word frequency and so on) and a ranking strategy. In the abstractive approach, the summary is generated via language generation mechanisms according to syntactic and semantic forms of input documents, and it necessarily does not contain input sentences of documents. Of course, parameters such as relation to the subject domain, summary generation according to a query that has been provided by the user, updating the generated summary by new input documents, etc., also, affect the summary generation approach (Nenkova and McKewon Reference Nenkova and McKeown2012).
As mentioned earlier, in extractive multi-document summarization systems, the summary is generated via extracting some sentences from input documents. For this purpose, the sentences of input documents are ranked according to a scoring and ranking strategy and then, the best sentences are selected to generate the final summary (Liu and Liu Reference Liu and Liu2009). Among different approaches to perform this process, nowadays, more attention is paid to semantic relation between sentences. In fact, sentences with close semantic relations are ranked in such a way that one or few sentences are selected among them for generating the final summary, thereby increasing its coverage (Gong and Liu Reference Gong and Liu2001; Schluter and Sogaard Reference Schluter and Sogaard2015; Yasunaga et al. Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017). In this regard, using textual entailment relation, as a proper approach for checking the semantic relation between two sentences, can increase the system performance (Bentivogli et al. Reference Bentivogli, Clark, Dagan and Giampiccolo2009; Gupta et al. Reference Gupta, Kathuria, Singh, Sachdeva and Bhati2012; Pado et al. Reference Pado, Noh, Stern, Wang and Zanoli2015). On the other hand, due to some redundant information in the sentences of input documents, using sentence compression techniques for decreasing their lengths, while reducing redundancy if the final summary, could increase its coverage, too (Madnani et al. Reference Madnani, Zajic, Dorr, Ayan and Lin2007; Liu and Liu Reference Liu and Liu2009). In addition, formulating the summarization problem as an optimization problem is one of the most important approaches for selecting the best sentences (according to their scores and lengths while satisfying the length constraint of the final summary) and has been used in some summarization systems (Hirao et al. Reference Hirao, Yoshida, Nishino, Yasuda and Nagata2013).
The presented paper is focused on multi-document extractive summarization based on textual entailment and sentence compression. In this way, the outlined problem has been formulated as an optimization problem (knapsack problem), where sentences are the problem items, and their value has been calculated by the production of their textual entailment score and Tf-Idf value. Then, greedy and dynamic programming approaches have been used to solve the knapsack problem. Also, before generating the final summary, to reduce the space that has been occupied by each sentence, sentence compression methods have been applied to adjust the length of sentences. Rest of the paper has been organized as follows: in Section 2, we review the related works and subject background and define textual entailment and sentence compression concepts. Section 3 presents the proposed method. In Section 4, experiments and results are presented. Finally, in Section 5, we conclude the paper and present an outline for future works.
2 Background and literature review
Extractive summarization systems are categorized into two categories based on a need to change the form of input documents: systems without transformation and transformation-based system.
2.1 Transformation-based systems
Transformation-based systems transform the input document(s) to a new format, and use this new format to extract the summary.Footnote 1 One of the most widespread transformation-based summarization systems uses Latent Semantic Analysis which is a reliable and unsupervised method. In this method, input documents are represented as a word–sentence matrix, and then this matrix is used for measuring similarity between sentences and key words via Latent Semantic Analysis. In this matrix, the rows represent the words and the columns represent sentences. To evaluate the sentences, Singular Value Decomposition is used. One of the biggest disadvantages of this method is the matrix dimension; by increasing the input size, the matrix size increases exponentially, thus the chance of generating unsuitable and worthless summaries increases too (Gong and Liu Reference Gong and Liu2001). In Dunlavy et al. (Reference Dunlavy, O’Leary, Conroy and Schlesinger2007), this method is combined with the Hidden Markov Model.
As another transformation-based system, we can mention Graph-based systems. In this system, input documents are mapped to a graph at first, so that the graph vertices show the text units, and the graph edges show relation between text units. Then, by processing the resulting graph, suitable text units are selected to generate the summary. As an example of this method, we can mention Brazilay and Elhadad (Reference Brazilay and Elhadad1997) in which lexical chains are used to understand discourse structure and generate a coherent and cohesive summary. LexRank or PageRank algorithms that have been proposed in Erkan and Radev (Reference Erkan and Radev2004) and are used by Google search engine for scoring documents are additional examples of these systems. In this algorithm, the graph vertices include sentences from the input document(s) and the edges are created according to some form of semantic similarity (cosine similarity) or content overlap (Tf-Idf vector).
Rhetorical structure theory, which was introduced in 1988, is another example of transformation-based summarization systems, and tries to represent input documents as a tree. In this method, the input is divided into two non-overlapping sections so that there is a semantic relation between them. One of these sections is called nucleus and the other is called satellite. The nucleus section is more important for the author and is independent from the satellite section. Also, the reverse relation is invalid (Marcu Reference Marcu1997). It worth mentioning that different nucleuses and satellites could be selected via different approaches according to the intended relation such as antithesis, concession, condition, circumstance and so on.
2.2 Systems without transformation
Systems without transformation are systems that do not change the content or structure of documents, and work directly on the content of entry. These systems deal with each sentence separately, and generate the final summary via extracting a subset of sentences from input documents. The first step in these systems is extracting features of input sentences. In the next step, the score of each sentence is calculated based on a combination of values of its features. Finally, according to theses scores, the best sentences are selected to make the final summary. Of course, assuring confidence in coherence and non-redundancy of the summary in the final step is essential (Nenkova and McKewon Reference Nenkova and McKeown2011, Reference Nenkova and McKeown2012).
The simplest and oldest methods of these systems use frequency of words (Das and Martins Reference Das and Martins2007), probability distribution of words (Nenkova, Vanderwende and McKeown Reference Nenkova, Vanderwende and McKeown2006; Vanderwende et al. Reference Vanderwende, Suzuki, Brockett and Nenkova2007; Lin and Chen Reference Lin and Chen2010), position of words (Baxendale Reference Baxendale1958; Edmundson Reference Edmundson1969; Lin and Hovu Reference Lin and Hovy1997; Havy and Lin Reference Hovy and Lin1998; Orasan, Pekar and Hasler Reference Orasan, Pekar and Hasler2004), cue words (Pollock and Zamora Reference Pollock and Zamora1999), title words (Lopez, Prince and Roche Reference Lopez, Prince and Roche2011; Suzuki and Fukumoto Reference Suzuki and Fukumoto2014) and key phrases (Kutlu, Cigir and Cicekli Reference Kutlu, Cigir and Cicekli2010). Most of these methods do not have desired performances due to focusing just on the words and not paying attention to the semantic relation between words and sentences of input document(s). Another method for systems without transformation uses the centroid of document sets. In this method, each document of the set is represented as a phrase vector, which is called vector space. Vectors include numerical values which show the importance of phrases in the document. In other words, the centroid of a document set is calculated by dividing the sum of document vectors by the number of all documents. The most common technique for determining these values uses Tf-Idf (Filatova and Hatzivassiloglou Reference Filatova and Hatzivassiloglou2004).
Bayesian models have been used in without transformation summarization systems, too. Bayesian models are one of the most complex approaches of document summarization and their popularity is increasing. The first instance of these models was proposed in Lopez, Buenaga and Gomez-Hidalgo (Reference Lopez, Buenaga and Gomez-Hidalgo2004), Daume and Marcu (Reference Daume and Marcu2006) and Haghighi and Vanderwende (Reference Haghighi and Vanderwende2009), which used some different probability distributions for words of input document(s). These distributions are general probability of the language, which is called G, probability distribution of the whole cluster that is being summarized, which is called C and a probability distribution for each document in the input document set. Each of these distributions includes a word table and their probability or weight. Of course, in each distribution, the weight of words can be different. Then, the most important words are selected according to these distributions and by using a non-supervised learning method. After that sentences are selected to generate the summary. Also, the most popular method for sentence selection after determining their scores, is the greedy method. It is mentionable that for improving evaluation and sentence selection process, Kullback–Leiber divergence has been used in Donaway, Drummey and Mather (Reference Donaway, Drummey and Mather2000), Radev et al. (Reference Radev, Teufel, Saggion, Lam, Blitzer, Qi, Elebi, Liu and Drabek2003) and in Litvak, Vanetik and Last (Reference Litvak, Vanetik and Last2015), MDL algorithm has been used based on database transactions. Also, Jensen–Shannon divergence has been used for evaluation of the generated summary (Louis and Nenkova Reference Louis and Nenkova2009).
In query-based systems, a query is given to the system in company with the document(s). This query shows the user preference or need, and it can be expressed as a set of words. In these systems, sentences with more similarity to the query are given higher scores (Baumel, Cohen and Elhadad Reference Baumel, Cohen and Elhadad2014). A common way to measure similarity between the text and the query is to use the soft cosine similarity. In this method, same as the centroid of documents set, the query sentence is represented as a Tf-Idf vector, and the similarity between each sentence of the text and the query is calculated as equation (1).
\begin{equation}
\text{Cos}(q,s)=\frac{\sum _{i \in N}{((\text{tf}*\text{idf})_{i,q} \times (\text{tf}*\text{idf})_{i,s}})}{\sqrt{\sum _{i \in N}((\text{tf}*\text{idf})_{i,q})^2} \times \sqrt{\sum _{i \in N}((\text{tf}*\text{idf})_{i,s})^2}}
\end{equation}
Of course, using stemming, semantic similarity of words and word synonyms can improve performance of this process (Baumel et al. Reference Baumel, Cohen and Elhadad2014; Wang et al. Reference Wang, Raghavan, Castelli, Florian and Cardie2016). Also, we can use more than one feature simultaneously to improve the sentence ranking process. In these conditions, different features should be combined in a predefined way. The most common way to combine different features is by using a linear combination of all features (Saggion and Gaizauskas Reference Saggion and Gaizauskas2004). One of the problems with this method is determining the weight of each feature in linear combination. For solving this problem, some papers suggested examining the different weight for each feature manually to find the most appropriate weights. It is evident that this process is very time consuming, costly, and in most circumstances, it is impossible. So other ways have been examined to find the best weight for each feature.
For instance, the unsupervised machine learning method and the Naive–Bayesian classifier have been used for combining feature sets (Daume and Marcu Reference Daume and Marcu2005; Silva et al. Reference Silva, Ferreira, Dueire Lins, Cabral, Oliveira, Simske and Riss2015). It has been showed that this form of feature combination improves the results (Jin et al. Reference Jin, Abu-Ata, Xiang and Ruan2008). Also, other methods of machine learning, such as decision trees (Chuang and Yang Reference Chuang and Yang2000), hidden Markov model (Conroy and O’Leary Reference Conroy and O’leary2001; Knight and Marcu Reference Knight and Marcu2002; Zhou and Hovy Reference Zhou and Hovy2003), support vector machine (Hirao et al. Reference Hirao, Isozaki, Maeda and Matsumoto2002; Fuentes, Alfonseca and Rodriguez Reference Fuentes, Alfonseca and Rodriguez2007), genetic algorithm (Litvak, Last and Friedman Reference Litvak, Last and Friedman2010), conditional random fields (Galley Reference Galley2006; Shen et al. Reference Shen, Sun, Li, Yang and Chen2007), integer linear programming models (Martins and Smith Reference Martins and Smith2009; Woodsend and Lapata Reference Woodsend and Lapata2012), log-linear models (Osborne Reference Osborne2002) and supervised and unsupervised machine learning algorithms (Hong and Nankova Reference Hong and Nenkova2014; Hong, Marcus and Nenkova Reference Hong, Marcus and Nenkova2015; Li, Liu and Zhao Reference Li, Liu and Zhao2015; Schluter and Sogaard Reference Schluter and Sogaard2015) have also been used to solve this problem.
One problem with the above methods is that ranking algorithms specify whether a sentence is suitable and valuable for generating the summary or not. In these circumstances, if there are many helpful sentences, then the above algorithms would not be useful for selecting the best subset of sentences to maximize coverage of the summary. Mainly, to solve this problem, learning-based ranking algorithms have been used. In these methods, a complementary algorithm is used for ranking proper sentences, and finally, sentences with higher rankings are selected to generate the summary (Amini, Usunier and Gallinari Reference Amini, Usunier and Gallinari2005; Toutanova et al. Reference Toutanova, Brockett, Gamon, Jagarlamudi, Suzuki and Vanderwende2007; Metzler and Kanungo Reference Metzler and Kanungo2008; Amini and Usunier Reference Amini and Usunier2009; Cai and Li Reference Cai and Li2013). Another method of ranking sentences uses regression. These methods, which use support vector regression, have better classification and ranking quality (Li et al. Reference Li, Ouyang, Wang and Sun2007; Ouyand et al. Reference Ouyang, Li, Li and Lu2011). In addition, neural networks have been used for text summarization (Mani and Maybury Reference Mani and Maybury1999; Cao et al. Reference Cao, Wei, Li, Li, Zhou and Wang2015). Also, Yasunaga et al. (Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017) have used a graph convolutional network and recurrent neural networks to propose a neural multi-document summarization system; Cao et al. (Reference Cao, Li, Li and Wei2017) have used convolutional neural networks and text classification models for this purpose; and Cao et al. (Reference Cao, Wei, Dong, Li and Zhou2015) have used recursive neural networks to develop a sentence ranking framework for summarization. Also, Cao et al. (Reference Cao, Li, Li, Wei and Li2016) have proposed a summarization system called Attsum, which uses convolutional neural networks to learn query relevance ranking and sentence saliency ranking simultaneously.
However, despite the importance of paying attention to the semantic relation between the sentences, this concept has received less attention in most of the previous researches. In fact, many of the sentences that ranked as valuable sentences in the most of the above methods are semantically close to each other and the presence of one of them in the final summary is enough. So detecting a semantic relation between sentences via methods such as textual entailment, and using this relation to remove sentences that have meanings close to each other, could decrease the summary length and make it possible to increase its coverage by including other sentences. Of course, in some researches, some instances of relation between sentences, such as discourse relation through an approximate discourse graph (called G-flow) to balance coherence and salience in the summary (Christensen, Soderland and Etzioni Reference Christensen, Soderland and Etzioni2013) or relations based on G-flow, Tf-Idf cosine similarity and personalized discourse graph (Yasunaga et al. Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017) through three sentence relation graphs have been used for sentence ranking or extraction and decreasing redundancy in the summary. Nevertheless, textual entailment as a new and powerful tool for detecting semantic relation between two sentences, has been less used for this goal. Also, most of the sentences that are selected to generate the summary have additional parts (such as relative clauses or redundant constituents), so removing these parts in the compression phase could improve the summary quality, too.
2.3 Textual entailment
One of the ways that have been used in the last decade for detecting the relations of sentences in the summarization systems is textual entailment. Textual entailment is a one-way relation between a text (T) and a hypothesis (H) that shows whether the hypothesis can be inferred from the text, or not. In fact, the purpose of textual entailment is that taking a text (T) and using relevant knowledge, determines whether or not the hypothesis (H) is inferred from the text. We should mention that in this process the focus should not be just on the knowledge and the text must play a vital role. Table 1 shows some sample of textual entailment pairs and their results.
Samples of textual entailment (Dagan, Glickman and Mafnini Reference Dagan, Glickman and Magnini2006)
It is mentionable that natural language is ambiguous. In other words, a text could contain more than one meaning, and a single meaning could be expressed by multiple different phrases. This would cause a many-to-many mapping between natural language phrases and their meanings. On the other hand, as mentioned earlier, one of the key processes of text summarization is to identify and select sentences with higher values. In other words, we have to identify sentences which satisfy the constraints on the desired length of summary and also have the most coverage of the text content and meaning. In this way, if we could identify and classify sentences with the same meaning and choose the sentence with minimum length and maximum coverage of meaning from each class of sentences, we could make an important step in generating a proper summary. In fact, we can use textual entailment to determine semantic relation between sentences and, according to the result of this process, we can perform the sentence ranking process more effectively. Different approaches are suggested for performing this task. Among them, we can mention word embedding, logical models, graphical models, rule systems, contextual focusing and machine learning (Dagan, Glickman and Mafnini Reference Dagan, Glickman and Magnini2006).
In Tatar et al. (Reference Tatar, Tamaianu-Morita, Mihis and Lupsa2008) and Gupta et al. (Reference Gupta, Kathuria, Singh, Sachdeva and Bhati2012), textual entailment has been used for detecting highly relevant sentences. Also, in Gupta et al. (Reference Gupta, Kaur, Singh, Goel and Mirkin2014), textual entailment and minimum vertex cover have been used to summarize a text. However, all of the above papers have focused on single-document summarization and have high-time complexity because of exploring textual entailment relation between all sentences.
2.4 Sentence compression
Sentence compression is a method for creating a compact version of a sentence while preserving syntactic and semantic relations, and the main information of the original sentence (Wang et al. Reference Wang, Raghavan, Castelli, Florian and Cardie2016). In fact, sentence compression aims to decrease sentence length, while preserving its syntactic and semantic structures. In other words, if we could identify excessive constituents of each sentence, which do not have much impact on its meaning, and remove them from the sentence while preserving its grammatical structure, we can compress or summarize it. This task could be done via different approaches. For example, in the sentence, ‘Microsoft founder, Bill Gates, said . . .’, removing the phrase, ‘Bill Gates’, does not have any effect on the meaning of the sentence, but reduces its length and could increase its score in the sentence ranking process. So we can summarize or compress the above sentence as ‘Microsoft founder said . . .’.
It is worth mentioning that most sentences of textual documents, such as news articles, have redundant information which cause prolongation of the sentence, and result in a decrease of its value in the summarization process. So according to summary length limits, using sentence compression in multi-document summarization processes could improve its performance. In Knight and Marcu (Reference Knight and Marcu2000), Knight and Marcu (Reference Knight and Marcu2002), Madnani et al. (Reference Madnani, Zajic, Dorr, Ayan and Lin2007) and Liu and Liu (Reference Liu and Liu2009), sentence compression mechanisms have been used in textual document summarization. Also, in Martins and Smith (Reference Martins and Smith2009) and Berg-Kirkpatrick, Gillick and Klein (Reference Berg-Kirkpatrick, Gillick and Klein2011), a joint model for sentence extraction and compression has been used in text summarization system. In addition, in Woodsend and Lapata (Reference Woodsend and Lapata2012), Almeida and Martins (Reference Almeida and Martins2013) and Yasunaga et al. (Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017), compression has been used in multi-document summarization systems, too. However, most of the above researches have focused only on one aspect of text summarization such as redundancy (see Yasunaga et al. Reference Yasunaga, Zhang, Meelu, Pareek, Srinivasan and Radev2017) or coverage (see Martins and Smith Reference Martins and Smith2009; Woodsend and Lapata Reference Woodsend and Lapata2012) along with compression, but our proposed method is trying to increase coverage and decrease redundancy through deploying sentence compression and textual entailment.
2.5 Knapsack problem
Despite differences between various text summarization methods, in general, these systems can be formulated as a knapsack problem. Knapsack problem is a classic NP-hard problem in combinatorial optimization which, by given a set of n item as S = {item1, item2, . . ., itemn} each of them with a weight (w i) and a value (p i), aims to choose a subset of S such that maximizes total values, while total weights is less and or equal to a predefined limit (knapsack weight limit or W). In other words, the object of this problem is to satisfy equation (2).
\begin{equation}
\text{maximize} \sum _{i=1}^{n} p_i x_i \textrm {\quad \quad \quad } \text{Subject to} \sum _{i=1}^{n} w_i x_i \le W \textrm {\quad and \quad } x_i \in \lbrace 0,1\rbrace
\end{equation}
Accordingly, in extractive summarization systems, a score of a sentence in ranking component can be formulated as the value of item (p i), the length of sentence as the weight of the item (w i) and desired length of the summary can be formulated as weight limit of knapsack (W). So the summarization problem can be formulated as knapsack problem, and in this way, we can claim that the summarization problem (using above formulation) is an NP-hard problem.
In Riedhammer et al. (Reference Riedhammer, Gillick, Favre and Hakkani-Tur2008), Takamura and Okumura (Reference Takamura and Okumura2009) and Hirao et al. (Reference Hirao, Yoshida, Nishino, Yasuda and Nagata2013), this formulation has been used for extractive text summarization, but all of them have focused on single-document summarization. Also, in Nishikawa et al. (Reference Nishikawa, Hirao, Makino and Matsuo2012), redundancy constrained knapsack problem has been used for document summarization.
3 Proposed method
Our proposed method is shown in Figure 1, consists of the following components:
(1) Preprocessing component.
(2) Primitive sentence ranking component.
(3) Sentence selection component.
(4) Textual entailment score calculating component.
(5) Sentence compression component.
(6) Final score calculating component.
(7) Final summary generating component.
Outline of the proposed method.
We will elaborate on these components in the following sections.
3.1 Preprocessing component
This component is responsible for reading the input documents and the user query (if there exist any) in text format and performing the following process on them:
• Text segmentation: This process is to divide input text into meaningful units such as sentences. Despite the existence of obvious signs for the end of a sentence, this task is not trivial because there are some signs, such as full stop in abbreviations, which make it harder than we think. For example, the abbreviation of, ‘Mr.’, in the sentence, ‘Mr. James went to the park’, is not a sentence solitarily. Often a table containing exceptions such as abbreviations is used to solve this problem.
• Tokenization: This term is applied for the task of splitting a text stream into words, phrases, symbols and other meaningful units that are called tokens. Usually, output of this task is used in the next steps of the natural language processing pipeline, such as parsing or text mining. Typically, this process is done at the word level, but defining a word is not trivial, and tokenizers often use some heuristic ways, such as punctuation and whitespace, to identify words. Also, it is possible to use more complex methods, such as applying exception tables or language models in this process.
• Normalization: Normalization is the process of transforming a text into a single canonical form in order to make it consistent for performing integrated processes. In fact, sometimes a single term can be expressed in several ways; but in order to simplify natural language processes, we have to unify them. For example, the terms ‘A.I.’, ‘AI’ and ‘A.I’ could be unified to a single and standard format such as ‘AI’; or the terms ‘Windows’ and ‘windows’ could be converted to lowercase. To do this task carefully, being informed from text nature and the manner of the next process is critical. It is mentionable that there is no general purpose normalization process.
• Stemming: This term is applied generally to the process of mapping a derived word to its root. For example, all of the words ‘argue’, ‘argued’, ‘argues’ and ‘argus’ are mapped to ‘argue’ but the words ‘argument’ and ‘arguments’ are reduced to ‘argument’. We should mention that a word root is not always a word and there are different algorithms for stemming that differs from each other based on performance and accuracy. The simplest stemming algorithms use a lookup table, which is a simple and fast method and it can handle exceptions easily; but this method cannot find the root of new and unknown words. On the other hand, more complex approaches use Stochastic algorithms, lemmatization, n-gram analysis and suffix-stripping and matching.
• Removing stop words: Stop words are common words that are used repeatedly in sentences of a language. Due to this high occurrence, word-based analyses grant higher values to them and which may be contrary to the truth. Some examples of stop words in English include ‘the’, ‘is’, ‘at’, ‘which’. Because of the negative impact of these words on the natural language process, in most processes, these words are removed before doing any other task. Unfortunately, there is no universal, single list for these words, and each natural language processing tool uses its own list to do this important task.
3.2 Sentence ranking component
Because of the high time complexity of calculating the textual entailment score, in this phase, we use a ranking system to select the most appropriate sentences. At first, having the set S contains all sentences obtained from the preprocessing component, each score of each sentence, s ∈ S, is calculated according to equation (3).
\begin{equation}
\text{Score}(s)=\frac{\sum _{a \in s}{(\alpha _a \times \text{tf}(a,s) \times \text{idf}(a,S))}}{l}
\end{equation}
\begin{equation}
\text{tf}(a,s)=0.5+0.5 \times \frac{f_{a,s}}{\text{max}_{\lbrace a^{\prime },s\rbrace }f_{a^{\prime },s}}
\end{equation}
\begin{equation}
\text{idf}(a,S)=\text{log} \frac{N}{|s \in S: a \in s|}
\end{equation}
Also, in equation (3), α is the impact factor of the query. In other words, in the case of generic summarization, this factor is equal to 1 for all words, but in query-based summarization, each word of query has an impact factor greater than 1, according to the system training process based on the training dataset, and this factor is, respectively, 2.17 and 2.03 for two datasets that have been used (see section 4.1). At the end of this phase, a list of sentences is sorted non-increasingly according to their scores.
3.3 Sentence selection
Based on the high time complexity of the textual entailment process and computing its scores (see Section 3.4.1), performing it on all of the sentences is not commodious. So after ranking the sentences according to primitive score, a fraction of them which have the highest score are selected (based on training set analysis and concerning the balance between runtime and accuracy of the results) and stored in a list named Sen′. According to the training data, for two datasets, this fraction is twenty per cent and twenty five per cent, respectively (see Section 4.1).
3.4 Calculation of textual entailment scores of sentences
3.4.1 Primary textual entailment score
In this component, at first, we have defined an entailment score for each pair of text and hypothesis according to equation (6).
\begin{equation}
\text{EntailmentScore}(T,H) = \left\lbrace \begin{array}{lr}0 & \textrm {If the entailment result is False}\\
C & \textrm {If the entailment result is True} \end{array} \right.
\end{equation}
\begin{equation}
\forall s_i,s_j \in \text{Sen}^{\prime } \textrm {\quad } \text{TEM}(s_i,s_j)= \left\lbrace \begin{array}{lr}0 & \textrm { If } s_i=s_j\\
\text{EntailmentScore}(s_i,s_j) & \textrm { Otherwise} \end{array} \right.
\end{equation}
For instance, if we have five sentences S 1, . . ., S 5 in Sen′, then TEM would be as Table 2.
An instance for textual entailment matrix
3.4.2 Final textual entailment score
After calculating TEM, the final textual entailment score of each sentence s i, is calculated according to equation (8).
\begin{equation}
\forall s_i \in \text{Sen}^{\prime } \textrm {\quad } \text{FTEscore}(s_i)= \left\lbrace \begin{array}{lr}\displaystyle \frac{\sum _{s_j \in S^{\prime }}\text{TEM}(s_i,s_j)}{\sum _{s_j \in S^{\prime }}\text{TEM}(s_j,s_i)} & \textrm { If } \sum _{s_j \in S^{\prime }}\text{TEM}(s_j,s_i) \ne 0\\
[8pt] +\infty & \textrm { If } \sum _{s_j \in S^{\prime }}\text{TEM}(s_j,s_i) = 0 \end{array} \right.
\end{equation}
\begin{equation}
\text{FTEscore}(S_1)=\frac{0.43+0.80+0.65}{0.35+0.42}=\frac{1.88}{0.77}=2.44
\end{equation}
It is mentionable that, higher FTEscore of a sentence means that the sentence entails more sentences and is entailed form less sentences. In other words, higher FTEscore of a sentence means that the sentence has more potential to be selected for generating the final summary because it increases the coverage measure of the summary.
3.5 Sentence compression
After calculating the textual entailment score of sentences, and before generating the final summary, sentence compression is used to decrease the length of sentences and to increase their final score. Here, we have used rule-based compression according to the extended form of the framework that has been proposed in Wang et al. (Reference Wang, Raghavan, Castelli, Florian and Cardie2016) to achieve this goal. In other words, we have used Table 3 rules to compress sentences. Also, to prevent undesirable effects of compression on the sentence, we have avoided removing more than eight words per each compression rule.
Compression rules : Parts between brackets are removed or changed
3.6 Final score calculation
After sentence compression, the final score of each sentence is calculated based on its Score and FTEscore, as shown in equation (10).
\begin{equation}
\forall s_i \in S^{\prime } \textrm {\quad } \text{FinalScore}(s_i)=\frac{l_i \times \text{Score}(s_i) \times \text{FEscore}(s_i)}{l^{\prime }_i}
\end{equation}
3.7 Final summary generation and postprocessing
After that, we can try to generate the final summary. To this end, and as mentioned in Section 2.5, we have formulated the summary generation problem as a zero-one knapsack problem and tried to solve it using greedy and dynamic programming approaches. So according to each approach, we solve the zero-one knapsack problem. The result of each approach is a set of sentences that satisfies the approach constraints. For example, in the dynamic programming approach, the result is a set of sentences that have the maximum value (value of the set is equal to summation of the final score of each sentence) and whose length is not more than the desired length of the summary. We should mention that the greedy approach is used to ensure speed, and dynamic programming approach is used to guarantee the accuracy of the final results. After that, the resulting sentences were sorted according to their positions in the documents and chronological order. Finally, coreference resolution was done on the sorted sentences to solve the missing references. This process was done on original sentences (before compression) and the obtained results was applied on the compressed sentences to guarantee that it will work as expected. A sample part of a query-based summary which is generated by our system is shown in Table 4.
A sample part of a query-based summary generated by our system
The words between brackets are removed or changed according to the compression rules.
4 Experiments and results
4.1 Experimental settings
We have performed our experiments on two datasets: DUC 2007 (main task) and MultiLingPilot 2011. DUC 2007 consists of forty five datasets which each include twenty five documents about a news topic and a related query. We have used cross-validation to evaluate the performance of the proposed system. So each time we selected thirty datasets for the training phase and fifteen datasets for the testing phase. In this dataset, summary length is 250 words and it is generated via a query-based summarization approach. MultiLingPilot 2011 consists of ten datasets which each include ten documents about a special topic. We have used cross-validation to evaluate the performance of the proposed system. So each time we selected seven datasets for training and three datasets for testing. In this dataset, summary length is 250 words, and it is generated via a generic summarization approach.
In preprocessing component, we have used Python 3.4.3 and its Natural Language Toolkit (NLTK 3.0) for sentence segmentation, tokenization, normalization, stemming and removing stop words. In ranking, sentence selection, sentence compression, calculating final scores and generating final summary, we have also used the above toolkit. For coreference resolution, we have used Stanford CoreNLP toolkit integrated with NLTK. In the textual entailment component, we have used the BIUTEE component of Excitement Open Platform 1.2.3 which is a transformation-based textual entailment system for calculating the textual entailment score of a pair of sentences (Magnini et al. Reference Magnini, Zanoli, Dagan, Eichler, Neumann, Noh, Pado, Stern and Levy2014; Pado et al. Reference Pado, Noh, Stern, Wang and Zanoli2015). This component was trained with 400 text–hypothesis pairs from the RTE-5 (Bentivogli et al. Reference Bentivogli, Clark, Dagan and Giampiccolo2009) dataset and hundred pairs that had been generated manually from training datasets.
4.2 Baselines
We have compared the performance of our system with the baselines in two situations: generic summarization and query-based summarization. To this end, we have used the two best participating systems of each dataset, the average of participating systems of each dataset, the best-proposed system in Wang et al. (Reference Wang, Raghavan, Castelli, Florian and Cardie2016) and the suggested systems of Conroy, Schlesinger and O’Learry (Reference Conroy, Schlesinger and O’Leary2007), Toutanova et al. (Reference Toutanova, Brockett, Gamon, Jagarlamudi, Suzuki and Vanderwende2007), Haghighi and Vanderwende (Reference Haghighi and Vanderwende2009), Mason and Charniak (Reference Mason and Charniak2011), He et al. (Reference He, Chen, Bu, Wang, Zhang, Cai and He2012), Cai and Li (Reference Cai and Li2013), Li et al. (Reference Li, Bing, Lam, Li and Liao2015), Canhasi and Kononenko (Reference Canhasi and Kononenko2016) and Cao et al. (Reference Cao, Li, Li, Wei and Li2016) as baselines.
4.3 Evaluation metrics
4.3.1 Human evaluation
Nenkova and Passonneau (Reference Nenkova and Passonneau2004) developed the Pyramid method to manually asses how many relevant facts or Summarization Content Units are captured by summaries that have been generated by an automatic summarization system. So we asked a highly experienced professional annotator (who is not one of the authors and fluent in English) to perform a Pyramid evaluation on eight randomly selected topics from each of the above datasets (DUC 2007 and MultiLingPilot 2011). Also, to evaluate the of the above selected topics, we asked five undergraduate students to read the summaries (generated by the system) examine their linguistic quality in different areas, and rate them from one (very poor) to five (very good).
4.3.2 Automatic evaluation
To compare proposed system performance with the baselines, we have used ROUGE automatic evaluation system (Lin Reference Lin2004). This system automatically measures the quality of a system by comparing its results with a gold-standard summary (the summary that has been generated by human expert) according to different metrics, and shows its performance as precision, recall and F-measure. Among various metrics of ROUGE, we have selected ROUGE-1, ROUGE-2 and ROUGE SU-4 because of their high corelation with human judgment (Lin and Hovy Reference Lin and Hovy2003).
4.4 Results
4.4.1 Human evaluation results
Human evaluation results of the DUC 2007 dataset (query-based summarization) are shown in Table 5. Here, we asked the evaluators to evaluate the summaries in the following six areas: Grammaticality (Gr), Referential Clarity (RC), Focus (Fo), Coherence and Structure (CS), Non-Redundancy (Non-R) and Content Responsiveness (CR). Also, human evaluation results of MultiLingPilot 2011 are shown in Table 6. Here and due to a lack of suitable information, we have just evaluated the summaries based on the overall grade that evaluators assigned to the summaries. In these tables, the best value in each column is bolded.
Human evaluation Results of our system (greedy and dynamic programming approaches) compared with the best DUC 2007 peers according to ROUGE and linguistic quality (LQ)(Grammaticality (Gr), Referential Clarity (RC), Focus (Fo), Coherence and Structure (CS), Non-Redundancy (Non-R) and Content Responsiveness (CR))
Human evaluation results of our system (greedy and dynamic programming approaches) compared with the best MultiLingPilot 2011 peers according to ROUGE and Linguistic Quality (LQ)
4.4.2 Automatic evaluation results
Automatic evaluation results of DUC 2007 dataset (query-based summarization) are shown in Tables 7 and 8 (respectively, for datasets participating systems and other baselines according to access to suitable information). Also, the automatic evaluation results of MultiLingPilot 2011 (generic summarization) are shown in Table 9. It is mentionable that bold values in each table show the best value per each metric for automatic summarization systems. Also, in Table 7, human summarization results are provided for better comparison between human summarization performance and the automatic systems. Also, Table 10 represents modular evaluation results which show the impact of system component on the final results of DUC 2007 dataset and MultiLingPilot 2011 dataset.
Query-based summarization results of DUC 2007 (DUC 2007 participating systems)
Query-based summarization results of DUC 2007 (other baselines)
Generic summarization results of MultiLingPilot 2011
Modular evaluation results (F-Score) of DUC 2007 and MultiLingPilot 2011
4.5 Analysis
Applying semantic relations between the sentences of an input set of documents has received less attention in the previous multi-document summarization systems. So in this paper, we tried to apply these relations by using textual entailment as a powerful tool for detecting the semantic relation between two sentences. As Tables 5 and 6 imply, the linguistic quality of our system’s generated summaries is higher than the baseline’s. This means that our system outperforms the other systems in generating summaries that are closer to human judgment. Using textual entailment to identify the semantic-related sentences in a set of documents, and classifying and ranking the sentences according to the textual entailment score of them, is one of the important reasons for our system’s high performance. Also, beside using textual entailment, for sentence ranking, formulating the summarization problem as a knapsack problem has impressively improved the performance of the summarization system.
As the results of Tables 7–9 show, the significant impact of this approach is to improve the recall parameter. Improving the recall parameter means that the system has remarkable potential for generating a summary with the selected sentences which have a higher correlation with human experts’ selected sentences. In other words, this approach can select the most similar sentences to human experts’ viewpoints for generating the final summary. So it has the closest performance to the best human summary (as shown in Table 7). Also, as expressed before, using sentence compression could decrease length of the selected sentences, making it possible to generate the summary with more sentences and thus increasing information coverage of the summary. In other words, our system increased information coverage of the generated summaries by using sentence compression.
Regarding the diversity aspect of a summarization system, we can mention that using equations (8) and (10) for calculating the final score of each sentence, would increase the score of sentences that entails more other sentences and be entailed from less other sentences. In other words, in a group of similar sentences, the sentence that has more potential to entail others, gives higher score and other sentences give lower scores. So, when generating the final summary, fewer sentences of a similar group of sentences are selected and as a consequence, we could select more diverse sentences and so the diversity of the system will increase. In addition, using sentence compression process increased the number of sentences in the final summary through reducing the length of the sentences, and as a consequence, increased the system’s diversity, too. In this regard, non-redundancy parameter of Table 5 can be a good testimony for this claim, which shows the redundancy of the proposed system is fewer than other baseline systems.
On the other hand, in generic summarization, the dynamic programming approach for solving the knapsack problem was completed as expected, because this approach tries to optimize the value according to the different aspects, but the greedy approach has lower performance. However, in query-based summarization, especially for ROUGE-1 and ROUGE-2, the results of the greedy method are very close to the results of dynamic programming. With respect to the correlation of greedy method to the human problem-solving approaches, we can conclude that ROUGE-1 and ROUGE-2 have a higher correlation with the human experts’ summary evaluation judgment.
5 Conclusion and future works
This paper presents a novel method for multi-document extractive text summarization. In this paper, we formulated the summarization problem as a knapsack optimization problem and have used extended Tf-Idf, and textual entailment approaches for sentence ranking and sentence compression to decrease the sentences lengths. Finally, we have used greedy and dynamic programming methods to solve the problem and generate the summary. Our methods performance impressively outperforms other similar systems, so that, according to the best of our knowledge, our system has increased F-measure of query-based summarization systems by two per cent and F-measure of generic summarization systems by five per cent.
As future work, we are interested in the reinforcement of our ranking strategy by adding features such as sentence position and also, using sequence-based and tree-based sentence compression to decrease the sentence length. Also, applying our algorithm on update summarization and question answering systems, using phrase-based textual entailment, and applying other semantic similarity approaches such as word embedding formulations are our other future objectives. In addition, improving the scalability and complexity of the proposed system and using other optimization approached such as integer linear programming are other goals for our future researches.
