Rough sets based span and its application to extractive text summarization

Abstract

Rough Sets provide a mathematical tool to handle decision making under uncertainty. One major domain that can be characterized with inherent ambiguity is natural language texts which often leads to uncertainty in understanding the intent and relative importance of a sentence with respect to its context in the whole text. As a consequence, the process of sentence selection for generation of extractive summary can logically be considered as a process of decision making under uncertainty. In this paper we use rough set based techniques to deal with this uncertainty. This paper’s contribution is two-fold. Firstly, this paper proposes a novel Rough Set based uncertainty measure called span and define special Rough subsets of universe called spanning sets. Span is Rough Set based measure for salience of a subset of universe and spanning set is the subset that maximizes the span. This corresponds to the key elements representing a problem and can be used to solve various real-life applications. Secondly, the concepts are applied to determine extracts of text documents. The idea behind the present work is to determine the most suitable subset(s) of the universe of sentences under consideration. An optimization problem is formulated to generate the extract for the text under consideration using the proposed uncertainty measure of span and is solved using Particle Swarm Optimization. The experimental results on DUC2001, DUC2002 single document data sets and Enron Email datasets establish the effectiveness of the proposed technique. There has been substantial work on Rough Sets though considering a stochastic Rough-subset of the universe and determining its aptness as a representative of the universe is still unexplored. The proposed technique is a novel effort to fill this gap.

Keywords

Rough set extractive text summarization span spanning set particle swarm optimization ROUGE extraction lexical chains DUC2001 DUC2002 LSA graph random indexing GLOVE

1 Introduction

Text Summarization [20] condenses a source text into a concise version that preserves the information content while reducing the size of the input text. Typically, summarization is of two types: extractive and abstractive. While abstractive summarization generates new sentences conveying the gist of the input text, an extractive summarization method typically selects important sentences from the original document as they are, and concatenates them to form the summary. Thus, extractive summarization can be viewed as a decision making process, where with respect to each input sentence the system takes a decision regarding possible inclusion of the sentence in the summary.

Summarization systems in recent times have assumed significant importance because of preponderance of text data in electronic form available through the web, various repositories, data centers, among others. Although various techniques have been developed for Text Summarization over the last 60 years or more, no significant work has so far been reported on Text Summarization using Rough Set based techniques.

Rough Set [24, 25] theory is a well-developed mathematical methodology to deal with imperfect data. Rough Set based techniques have been used in different areas of Artificial Intelligence, including Economics and Finance [32], Data Mining [11], Data Classification [12 , 27], Information Retrieval [29, 31], Feature Selection [14 , 35] among others.

The foundation of Rough Set lies in partitioning a given data set into three classes: positive region, negative region and boundary region with respect to a given knowledge, viz. set of entities represented as attribute-value pairs. While the positive and negative regions clearly demarcate the entities belonging to a specific class or outside it, the boundary region comprises of entities for which such a clear decision cannot be made with certainty. The basic partitioning tool used here is called indiscernibility relation. The underlying intuition is to identify elements that are not discernible from each other in terms of the knowledge R, where R stands for the set of attributes of the elements of U, the universe. The pair (U, R) is typically termed as Information System. In the theory of Rough Set any subset of the universe is represented as a pair of lower approximation and upper approximation using the indiscernibility relation. With respect to classical Rough Sets [24] the indiscernibility relation establishes a collection of equivalence classes that partitions the universe into disjoint collection of elements.

The motivation behind the work is to propose a novel Rough Set based uncertainty measure called span to evaluate the importance of a subset of a given universe. The span of a subset is the weighted average of the proportion of certainly covered concepts, as given by the lower approximation, and proportion of possibly covered concepts, as given by the boundary region of the subset. The subset of the universe that maximizes the proposed measure of span shall be referred to as spanning set. A spanning set is an equivalent representation of the universe satisfying certain user-specific criteria, and will have cardinality smaller than the universe. Several, Rough Set based uncertainty measures, such as membership value, accuracy and roughness have been studied in literature [9 , 39] though none of them deals with the spanning capabilities of a subset of universe. The aim of this paper is to apply the proposed concepts to solve the problem of Extractive Text Summarization.

Rough Set based Text Summarization was proposed in literature by Yadav & Chatterjee [34]. The overall scheme proposed therein consists of two major steps. Firstly, determining the key sentences using heuristic function and secondly, selection of sentences using Rough Sets based lower approximation and memberships. We consider this as our baseline system for comparing results. In our experiments with the baseline system we observed the following. Firstly, selecting the candidate set of sentences based entirely on heuristics is not adequate for the task. Secondly, selection from this set based on approximations and membership alone is not suffice for an efficient summarization.

We, in this paper have worked on these drawbacks and improved upon them in the following way. Typically, for extractive summarization of an input text an upper bound is imposed on the size of the target summary in terms of number of words, or number of sentences included in the summary. Hence the task of extractive summarization may be viewed as a problem of generating a subset of the universe of sentences which is the best representation of the universe with a reduced cardinality and without losing on essential information.

The above problem can be viewed as an application of the proposed uncertainty measure i.e. span. The subsets are generated in a dynamic manner and corresponding spanning sets are computed. We have defined the concept of complete span to address the drawback which arises due to sparse indiscernibility relation. The complete span measures the cumulative effect of each attribute of the Information System to produce a spanning set. A spanning set of a collection of sentences under certain constraints represents a set of distinct sentences having maximum information. The extract is computed using spanning set and document similarity. The optimization problem of finding spanning set is solved using Particle Swarm Optimization. Although applied to the domain of extractive text summarization, the novelty of the proposed uncertainty measure is that it can be used to solve various real-life applications as well.

The paper is organized as follows. Section 2 presents the previous work on Text Summarization. Section 3 gives introduction to Rough Sets and the notations used. In Section 4 the proposed concepts of Rough Set based span and spanning set are defined and explained. Section 5 provide the techniques to apply these concepts to compute extractive summary of text documents. Section 6 discusses the results of experiments conducted on single document Text Summarization viz. DUC2001, DUC2002 and Enron datasets. Finally, Section 7 concludes the paper.

2 Previous works on text summarization

A significant amount of research has been done in the area of Text Summarization over the last 50 years or more. We here discuss some of the important and novel techniques developed and used over the last few decades. In 1950s, due to the lack of powerful computers and difficulty in natural language processing (NLP), early works in this direction [8, 19] focused on the study of text genres using statistical and/or heuristic approaches. Some heuristics that were found to be useful have been word frequency, sentence location, presence of title keyword etc. However, the major contributions towards extractive Text Summarization have been in last two decades or so as mentioned below.

Latent Semantic Analysis (LSA) has been popularly used for Text Summarization [10, 30]. In this approach the term by sentence matrix of the given input text is decomposed into three matrices and subsequently important sentences are extracted depending on the compression degree. However, the major shortcoming of the LSA based techniques is that the matrix computations are expensive in both time and space. As a consequence, better approach has to be developed when a large volume of electronic data is made available and rapid processing of these documents is needed for summarization and corresponding information extraction.

Graph based methods [21, 22] are language independent summarization techniques. Graph based techniques work on ranking algorithm viz. Google’s PageRank algorithm [23]. The method is well established, but it is based on ranking of the sentences of a document. Hence problems may arise when multiple sentences with similar information are present in the text document.

Random indexing (RI) based Text Summarization was first proposed by [4]. Random Indexing differs from traditional Word Space Models in the sense that here instead of conventional word vectors one uses ternary vectors of predetermined size to represent words. Chatterjee & Sahoo [5] have advanced the basic RI based model using convolution in their Modified Random Indexing approach. The benefits of using Random Indexing based techniques are: (i) Here computational cost is much lower as compared to LSA. (ii) The dimensionality is maintained at a fixed number and does not increase with the addition of new sentences in the document. (iii) Experimental results show improved accuracy. However, one disadvantage of this technique is that it uses PageRank based ranking, and consequently is limited by the disadvantages of the graph based methods as mentioned earlier.

Some of the other summarization methods that have used optimization techniques for Text Summarization are the following:

Integer Linear Programming [1] method for summarization constructs summaries by solving 0-1 Integer Programing Problem, where either a sentence belongs to a summary or it does not. The linear constraints to the optimization problem are to maximize the importance of the selected sentences and minimize their pairwise similarity.

Archetypal Analysis (AA) [2 , 6] works on the concept that the input text can be represented by archetypes such that input is represented as convex combination of these archetypes which themselves are convex combination of input. Further, archetypes are utilized to determine the best sentences. However, to determine these archetypes various convex programming problems need to be solved, making summary extraction a difficult task.

Evolutionary Algorithms. Genetic Algorithms have been used to create text summaries [37]. The population for Genetic Algorithm is a collection of chromosomes which have genes with binary values of ones and zeros. Optimization is based on maximizing topic relation factor and cohesion. Karwa & Chatterjee [16] have recently used differential evolution for extractive Text Summarization.

3 Rough sets

Rough Set theory [24, 25] is a well-developed mathematical tool for decision making under uncertainty. Since its inception Rough Set has been used in different areas including classification, feature selection, data mining, knowledge acquisition, information retrieval, decision analysis to mention few. As discussed above, a knowledge representation system is a pair (U, R) where U, the universe, is a nonempty, finite set of objects, and R is a nonempty, finite set of attributes. Every attribute imposes an equivalence relation on U. For any set of attributes P ⊆ R, the indiscernibility relation is defined as: $IND (P) = {(x, y) \in U \times U | a (x) = a (y), \forall a \in P}$

The equivalence classes of IND(P) are denoted by $\frac{U}{P}$ . Each individual equivalence class shall be referred to as a concept. Given a set of objects, X ⊆ U and an attribute set P ⊆ R, X is represented by a pair of sets called lower approximation and upper approximation denoted by $\underline{P} X$ and $\bar{P} X$ , respectively, as mentioned in Section 1. The objects of universe are partitioned into three classes: positive, negative and boundary region. The positive region of X, denoted as POS_P (X), consists of elements of universe that can certainly be classified as elements of X and is called the lower approximation. The boundary region, denoted as BN_P (X), is the set of elements that are not decidable with certainty to be element of set X. The negative region, viz. NEG_P (X), are the elements which cannot be classified as elements of X using the given knowledge. The boundary region consists of entities for which a clear decision cannot be made with certainty of belonging to positive or negative region. The region (POS_P (X) ∪ BN_p (X)) is called the upper approximation of X denoted as $\bar{P} X$ . A set is called a Rough Set when the boundary region is non-empty otherwise the set is a crisp set and when $\underline{P} (X) = \bar{P} (X)$ , then the set X is said to be P-definable.

Mathematically, $\begin{matrix} \underline{P} X = \cup {Y \in \frac{U}{P} : Y \subseteq X} \\ \bar{P} X = \cup {Y \in \frac{U}{P} : Y \cap X \neq \emptyset} \\ {BN}_{P} (X) = \bar{P} X - \underline{P} X \end{matrix}$

The following section discuss the proposed Rough Set based uncertainty measure viz. span and spanning sets.

4 Rough set based span, spanning set and weighted rough sets

4.1 Span and spanning sets

Let (U, R) be an Information System and X be a subset of U To compute the degree of possibly included and certainly included concepts by a set X ⊆ U, we propose the notion of span. Formally, we define the span for a subset X of U as follows.

Definition 1. Let U be a non-empty universe of objects and R be set of attributes describing U. Let P be a subset of R. The span of a subset X of U w.r.t. P is defined as: $δ_{P, X} = (w_{1} * \frac{| \underline{P} X |}{| U |} + w_{2} * \frac{| {BN}_{P} (X) |}{| U |}), where$ $w_{1}, w_{2} \in [0, 1], w_{1} + w_{2} = 1$

Span is defined as the convex combination of degree of certainly covered concepts and possibly covered concepts by the set X. Convex combination is computed for a tradeoff between lower approximation and boundary region. The relative importance of certainly contained and possibly contained concepts are determined by the weights where the weights are application specific entities. We define spanning set of (U, R) as follows.

Definition 2. Let (U, R) be an Information System P ⊆ R, a subset Z of U is called a spanning set of (U, R) if Z maximizes the span.

Definition 3. A spanning set Z is called a minimal spanning set of (U, R) if Z is of minimum cardinality.

We shall now discuss some properties of span and spanning set. Before the results an important Lemma is presented.

Lemma 1. Let X ⊆ U be a subset of the universe. Further, let Q ⊆ P ⊆ R. Then, the following holds:

$\underline{P} X \supseteq \underline{Q} X$

BN_P (X) ⊆ BN_Q (X)

Proof. The proof follows from the fact that Q ⊆ P, which implies that $\frac{U}{P}$ is finer than $\frac{U}{Q}$ .□

Proposition 1 and Proposition 2 below state that the span of a subset of attributes is larger than the span with respect to the complete attribute subset, subject to some constraints.

Proposition 1. Suppose (U, R) is an Information System. Let X ⊆ U and P, Q ⊆ R, such that Q ⊆ P, then δ_P,X ≤ δ_Q,X + θ, where $θ = w_{1} * \frac{| \underline{P} X |}{| U |}$ . Also, in the case $lim_{w_{1} \to 0} θ = 0, δ_{p, X} \leq δ_{Q, X}$

Proof. We have, $\begin{matrix} δ_{P, X} = (w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |}), \\ δ_{Q, X} = (w_{1} \frac{| \underline{Q} X |}{| U |} + w_{2} \frac{| {BN}_{Q} (X) |}{| U |}) \end{matrix}$

Since Q ⊆ P ⊆ R by Lemma 1, $\underline{P} X \supseteq \underline{Q} X$ , and BN_P (X) ⊆ BN_Q (X), we have $\begin{matrix} | δ_{P, X} | = | w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |} | \\ \leq w_{1} \frac{| \underline{Q} X |}{| U |} + w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |} \end{matrix}$ $\begin{matrix} \leq w_{1} \frac{| \underline{Q} X |}{| U |} + w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |} \\ = | δ_{P, X} | + w_{1} \frac{| \underline{P} X |}{| U |} = | δ_{P, X} | + θ \end{matrix}$

Therefore, δ_P,X ≤ δ_Q,X + θ, where $θ = w_{1} \frac{| \underline{P} X |}{| U |}$ . Further, δ_P,X ≤ δ_Q,X, when θ is a small quantity which in the limit tends to 0.□

Proposition 2. Suppose (U, R) is an Information System. Let X ⊆ Uand P, Q ⊆ R, such that Q ⊆ P ⊆ R, and $| \underline{P} X | = | \underline{Q} X |$ , then δ_P,X ≤ δ_Q,X.

Then since Q ⊆ P ⊆ A, $\bar{P} X \subseteq \bar{Q} X$ Also, it is given that $| \underline{P} X | = | \underline{Q} X |$ ,

Hence, $\begin{matrix} | δ_{P, X} | = | w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |} | \leq | w_{1} \frac{| \underline{Q} X |}{| U |} \\ + w_{2} \frac{| {BN}_{Q} (X) |}{| U |} | \end{matrix}$

Hence, δ_P,X ≤ δ_Q,X

It is evident from these results that a smaller attribute subset always leads to a higher span, subject to satisfying constraints given in Propositions 1 and 2. The above knowledge helps us to identify suitable attributes for computing a spanning set. This motivated us to define the complete-span measure as follows.□

Definition 5. The complete span of a subset Xof U based on the given attribute set is given by: $δ_{R, X}^{Complete} = \frac{1}{| R |} \sum_{a_{i} \in R} δ_{a_{i}, X}$

The corresponding spanning sets obtained using complete span shall be referred to as complete spanning set. The complete spanning set of least cardinality is called minimal complete spanning set.

Proposition 3 given below follows from the definition of span.

Proposition 3. The following properties hold for any Rough Set based span:

If X = U, and w₁ = 1 then span is maximum and its value is 1.

If X = U, and w₁ = 0 then span is minimum and its value is 0.

If w₁ = w₂ = 0.5, then span is equal to $| \bar{P} X | / (2 (| U |))$ for any subset Z of U.

If BN_P (X) = U, then span is 1 if w₁ = 0 and span is 0 if w₂ = 0.

If X =∅, then span is 0 irrespective of values of w₁ and w₂.

The proofs of (i) to (v) follow from the definitions.

The following proposition proves relation that exists between two different span for a set X.

Proposition 4. Let w₁, w₂ be such that w₁ + w₂ = 1 and w₁ ≤ w₂. Let another set of weights be u₁ and u₂, such that u₁ + u₂ = 1, and u₁ ≤ u₂. Let the two span’s corresponding to the two set of weights be $δ_{P, X}^{'} = (u_{1} \frac{| \underline{P} X |}{| U |} + u_{2} \frac{| {BN}_{P} (X) |}{| U |})$ and $δ_{P, X} = (w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |})$ . If $| \underline{P} X | \leq | {BN}_{P} (X) |$ then,

δ_P,X′ ≤ δ_P,X if u₁ > w₁

δ_P,X′ ≥ δ_P,X if u₁ < w₁

Also, when $| {BN}_{P} (X) | \leq | \underline{P} X |$ the inequalities reverse. Further, equality holds for $| \underline{P} X | = | {BN}_{P} (X) |$ .

Proof. u₁ > w₁ $u_{1} - w_{1} = (1 - u_{2}) - (1 - w_{2}) = (w_{2} - u_{2}) > 0$

Given, $| \underline{P} X | \leq | {BN}_{P} (X) |$

$(u_{1} - w_{1}) | \underline{P} X | \leq (u_{1} - w_{1}) | {BN}_{P} (X) |$

$(u_{1} - w_{1}) | \underline{P} X | \leq (w_{2} - u_{2}) | {BN}_{P} (X) |$

$(u_{1} \frac{| \underline{P} X |}{| U |} +$

$u_{2} \frac{| {BN}_{P} (X) |}{| U |} \leq (w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |})$

δ_P,X′ ≤ δ_P,X

The other inequalities follow similar explanations.□

Proposition 5 provides relation between upper approximations of a spanning set and any other set.

Proposition 5. Let Z be a spanning set and X is any subset of U, then the following holds:

If w₂ ≤ w₁, then $| \overline{P} X | \leq | \bar{P} Z |$ , provided $| \underline{P} Z | \leq | \underline{P} X |$

If w₁ ≤ w₂ then $| \bar{P} X | \leq | \bar{P} Z |$ , provided $| \underline{P} X | \leq | \underline{P} Z |$

Proof. Let Z be a spanning set so Z maximizes the span i.e. $\begin{matrix} w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| \bar{P} X | - | \underline{P} X |}{| U |} \leq w_{1} \frac{| \underline{P} Z |}{| U |} \\ + w_{2} \frac{| \bar{P} Z | - | \underline{P} Z |}{| U |} \end{matrix}$

$(w_{1} - w_{2}) \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| \bar{P} X |}{| U |} \leq (w_{1} - w_{2}) \frac{| \underline{P} Z |}{| U |} + w_{2} \frac{| \bar{P} Z |}{| U |}$

$w_{2} \frac{| \bar{P} X |}{| U |} \leq (w_{1} - w_{2}) (\frac{| \underline{P} Z |}{| U |} - \frac{| \underline{P} X |}{| U |}) + w_{2} \frac{| \bar{P} Z |}{| U |}$

If w₂ ≤ w₁ $w_{2} \frac{| \bar{P} X |}{| U |} \leq w_{2} \frac{| \bar{P} Z |}{| U |} + (w_{1} - w_{2}) (\frac{| \underline{P} Z |}{| U |} - \frac{| \underline{P} X |}{| U |})$ $w_{2} \frac{| \bar{P} X |}{| U |} \leq w_{2} \frac{| \bar{P} Z |}{| U |},$ provided $| \underline{P} Z | \leq | \underline{P} X |$ $\Rightarrow | \overline{P} X | \leq | \overline{P} Z |$

Similarly, the other inequality follows.□

Proposition 6. The boundary region of a spanning set Z is largest provided $| \underline{P} Z | \leq | \underline{P} X |$ for any other subset X.

Proof. Let Z be the spanning set and X be any other subset of U. Then, $\begin{matrix} δ_{P, X} = (w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |}), \\ δ_{P, Z} = (w_{1} \frac{| \underline{P} Z |}{| U |} + w_{2} \frac{| {BN}_{P} (Z) |}{| U |}) \end{matrix}$

By definition, $(w_{2} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |}) \leq (w_{2} \frac{| \underline{P} Z |}{| U |} + w_{2} \frac{| {BN}_{P} (Z) |}{| U |})$ or $w_{2} (\frac{| \underline{P} X |}{| U |} - \frac{| \underline{P} Z |}{| U |}) \leq w_{2} (\frac{| {BN}_{P} (Z) |}{| U |} - \frac{| {BN}_{P} (X) |}{| U |})$

Given that $| \underline{P} Z | \leq | \underline{P} X |$ ,

Hence, it follows that $\frac{| {BN}_{P} (Z) |}{| U |} \geq \frac{| {BN}_{P} (X) |}{| U |}$ .□

Proposition 7. Given an Information System (U, R) Let X ⊆ U, P ⊆ R and Z be a spanning set satisfying $| \underline{P} Z | \leq | \underline{P} X |$ and w₂ ≤ w₁. Then the following holds:

The accuracy given by $α_{P} (X) = \frac{| \underline{P} X |}{| \bar{P} X |}$ , satisfies α_P (Z) ≤ α_P (X)

The roughness given by ρ_P (X) =1 - α_P (X) satisfies ρ_P (X) ≤ ρ_P (Z)

Proof. Let Z be a span and X be a subset of U. Since w₂ ≤ w₁, by Proposition 5 the following holds:

$| \bar{P} X | \leq | \bar{P} Z |$ , provided $| \bar{P} Z | \leq | \bar{P} X |$

$\frac{| \underline{P} Z |}{| \bar{P} Z |} \leq \frac{| \underline{P} X |}{| \bar{P} X |}$ , hence α_P (Z) ≤ α_P (X)

ρ_P (X) ≤ ρ_P (Z)

□

In Proposition 6 it is proved that boundary region of spanning set is largest given the condition on lower approximation cardinality. In Proposition 7 it is proved that roughness of a spanning set of given dimensions is highest provided it satisfy some criterion and the accuracy of the decision system formed with the spanning set is least. Hence, spanning set is a Rough Set with high degree of roughness.

Now, we define weighted Rough Sets as follows:

Definition 6. Let U be a non empty universe and R be set of attributes describing objects of U. Let be a subset of attributes of R. Let v_i be the weights assigned to each of the indiscernibility class Y_i of $\frac{U}{P}$ such that ∑_iv_i = 1. The measure of weighted lower and upper approximation is given as follows: $\begin{matrix} m (\underline{P} Z) = \sum {v_{i} * | Y_{i} | : Y_{i} \in \frac{U}{P} {andY}_{i} \subseteq Z} \\ m (\bar{P} Z) = \sum {v_{i} * | Y_{i} | : Y_{i} \in \frac{U}{P} {andY}_{i} \cap Z \neq \emptyset} \\ m ({BN}_{P} (Z) = \sum {v_{i} * | Y_{i} | : Y_{i} \in \frac{U}{P} {andY}_{i} \cap Z \neq \emptyset, \\ Y_{i} \subseteq Z} \end{matrix}$

Using weighted Rough Sets each class of $\frac{U}{P}$ is assigned an appropriate weight representing its importance. The idea behind weighted Rough Sets is that lower approximations and upper approximation containing higher number of important equivalence classes is considered more important that the one containing higher number of less important equivalence classes.

Definition 7. Let U be a non-empty universe and R be set of attributes describing objects of U. Let P be a subset of R. The weighted span of a subset Xof U w.r.t. Pis defined as: $δ_{P, X} = (w_{1} * \frac{| m (\underline{P} X) |}{| U |} + w_{2} \frac{| m ({BN}_{P} / X)) |}{| U |} where$ $w_{1}, w_{2} \in [0, 1], w_{1} + w_{2} = 1$

Weighted span measures the spanning capability of a subset using weighted measures of lower approximations and boundary region defined above.

Definition 8. The complete weighted span of a subset X of U based on the given attribute set is given by: $δ_{R, X}^{Complete} = \frac{1}{| R |} \sum_{a_{i} \in R} δ_{a_{i}, X}$

The corresponding spanning sets obtained using complete span shall be referred to as complete weighted spanning set. The complete spanning set of least cardinality is called minimal weighted complete spanning set.

4.2 Computing spanning sets

The following example illustrates the concept of computing complete spanning set.

Example 1. Let U = {x₀, x₁, . . . , x₆} and R = {a₁, a₂, a₃}. Consider the Information System (U, R) given in Table 1.

Table 1
Example on span and spanning set computation

a1 a2 a3

x0 3 1 2

x1 1 1 1

x2 1 2 2

x3 2 2 2

x4 2 2 3

x5 2 3 3

x6 3 3 3

	a1	a2	a3
x0	3	1	2
x1	1	1	1
x2	1	2	2
x3	2	2	2
x4	2	2	3
x5	2	3	3
x6	3	3	3

Let R = {x₁, x₂, x₅} , w₁ = 0.1 and w₂ = 0.9

$δ_{P, X} = w_{1} \frac{| \underline{P} X |}{| U |} + w_{2} \frac{| {BN}_{P} (X) |}{| U |}$ ,where P = {a_i}

We compute the span with respect to the three attributes as follows, $\begin{matrix} δ_{a_{1}, X} = 0.1 * \frac{2}{7} + 0.9 * \frac{3}{7} = 0.4142 \\ δ_{a_{2}, X} = 0.1 * \frac{0}{7} + 0.9 * \frac{7}{7} = 0.9 \\ δ_{a_{3}, X} = 0.1 * \frac{1}{7} + 0.9 * \frac{6}{7} = 0.7857 \end{matrix}$

The complete span is given by $δ_{P, X}^{Complete} = \frac{1}{| P |} \sum_{a_{i} \in P} δ_{a_{i}, X}$ $= \frac{1}{3} (0.4142 + 0.9 + 0.78578) = 0.6999$

Now, consider another set Y = {x₀, x_1,x₃} and weights being same as above.

Then, $\begin{matrix} δ_{a_{1}, Y} = 0.1 * \frac{0}{7} + 0.9 * \frac{7}{7} = 0.9 \\ δ_{a_{2}, Y} = 0.1 * \frac{2}{7} + 0.9 * \frac{3}{7} = 0.4142 \\ δ_{a_{3}, Y} = 0.1 * \frac{1}{7} + 0.9 * \frac{3}{7} = 0.4 \\ δ_{P, Y}^{Complete} = 0.5714 \end{matrix}$

The span of Y for this problem is less than span of X which means that the set X represent the universe in a better way than the set Y. It is evident from this example that different subsets of U produce different span and complete span.

Table 2 gives the complete spanning sets, minimal complete spanning sets and complete span for the Information System given in Table 1. To compute complete spanning set for the given problem, it requires computing 2⁷ viz. 128 possible subsets of universe and finding the one with maximum complete span. This grows exponentially as size of universe increase.

Table 2

Minimal Complete Spanning set for Example 1

Parameters	No. of Complete Spanning Sets	Minimal Complete Spanning Set	Maximum Span
w₁ = 0.1, w₂ = 0.9	2	{1, 3, 6}	0.8619
w₁ = 0.9, w₂ = 0.1	1	{0, 1, 2, 3, 4, 5, 6}	0.9
w₁ = 0.5, w₂ = 0.5	31	{0, 1, 2, 5}	0.5

Section 5 describes application of the concepts developed in this work for dealing with the problem of Text Summarization.

5 Weighted rough set based span for text summarization

Here, the application of Rough Set based span and spanning set to solve the problem of Extractive Text Summarization is proposed. For the task of extraction, the Information System (U, R) has to be constructed. The universe U consists of all the sentences in the given text. The set of attributes R consists of the features that describe the text.

5.1 Determining extract of text using span

The problem of Text Extraction evaluates the sentences for their salience. The extract so created includes all essential information since the span of a text document with more emphasis on boundary region shall cover as much key topics present in the text as possible. This follows from the fact that while lower approximations guarantee that certainly covered topics are included in the summary, a larger boundary region implies higher number of topics of the text will be covered in the extractive summary. Hence spanning set is the subset of all the sentences of the text that includes maximum number of concepts of the text represented as individual features. Further, concepts in different equivalence classes are uniquely distinct this reduces redundancy in the generated extract.

Computing an extract requires evaluating subsets of universe for their span and finding the one with highest value. Evaluating span of all subsets is computationally expensive. Hence, we solve it using optimization problem. In the following section, we describe the optimization problem used to compute the optimal spanning set for the problem of Text Summarization.

5.2 Optimization problem

Consider Z to be a subset of U which is the collection of sentences, i.e. Z is spanning set of U. Experiments show that spanning set for an Information System (U, R) may not be unique, hence it is paramount to add additional application specific objective to the optimization problem. For the given problem of extractive summarization, the additional objective function is span with higher similarity with the text document.

Hence, determination of Rough Set based extract for single document summarization is a multi-objective optimization problem given as follows:

maximize (δ_P,Z, similarity (Z, Document))

subject to,

length(Z) ≤p,

p is the degree of compression.

Here, notations are as discussed in Section 4 and δ_P,Z is the complete span of all the attributes under consideration.

5.3 Proposed solution for computing spanning sets of text documents

Computing a spanning set is a computationally complex problem. In this paper, we propose to use Particle Swarm Optimization [7] to compute a complete spanning set. Particle Swarm Optimization (PSO) is inspired by social behavior of birds and insects. A collection of particles participates to generate an optimal solution to a problem. Each particle has a velocity and a location. The particles move in direction simulated by the guidance of global best (GB) and local best (LB) positions. The velocity v_i and position x_i of a particle are updated as follows: $v_{i + 1} = w * v_{i} + c 1 * r 1 * (LB - x_{i}) + c 2 * r 2 * (GB - x_{i})$ $x_{i} = x_{i} + v_{i + 1}$ In the above equation c1, c2 are the cognitive parameters and r1 and r2 are two random numbers in interval [0, 1]. This collection of particles determines the optimal solution.

6 Experiments and observations

6.1 Experiments

Experiments of the proposed methodology have been conducted on benchmark DUC datasets for Single Document Summarization, viz. DUC2001, DUC2002 (http://www-nlpir.nist.-gov/projects/duc/) and Enron Email datasets [18] viz. Personal Email dataset, Corporate Email Dataset. 105-word summary is computed for both the DUC datasets for evaluations. While 50% summarization was computed for Enron dataset. The pre-processing steps followed are (i) Sentence Segmentation (ii) Removal of stop words (iii) POS tagging and (iv) Stemming.

To evaluate the summarization results, ROUGE package [17] was used. We have used the following ROUGE metrics: (i) ROUGE-1 (1-gram measure), (ii) ROUGE-2 (2-gram measure), (iii) ROUGE-L (Longest common subsequence measure), (iv) ROUGE-SU* (Skip bigram with 1-gram measure). The results were compared with abstracts created by human experts. We have experimented on several Information System and evaluated their effectiveness for Extractive Summarization. The parameters used in evaluations are w₁ = 0.1 and w₂ = 0.9. The following Rough Set based systems were evaluated:

Span: Here the universe is collection of all sentences and the features taken are nouns, adjectives, adverbs and verbs present in the pre-processed text. The Information System is the one-hot representation of the text described by these features. The extract here is a complete spanning set solved using PSO.

Span-Similarity: The Information System is the one-hot representation of the text and is created as in (i) above. The extract is a weighted Rough Set based spanning set with binary weights obtained by solving optimization problem given in Section 5.2 using PSO. This system outputs a spanning set with highest similarity with the document.

Span-Lexical: Lexical Chains [28] are collection of semantically related words present in the text. Each lexical chain describes the group of similar terms which convey same meaning. It plays a vital role in reducing the dimensionality of the problem. The Information System has top 20% lexical chains as attributes and sentences as the objects of universe. If a sentence i is related to an attribute a the value a(i) is set to one else the value is zero. Once the Information Set is formed, the extract is generated as in Span-Similarity.

Span-LSA: Latent Semantic Analysis (LSA) [10] based decomposition is performed on matrix M which is frequency-based representation of the document. The entry M[i, j] of matrix M is equal to frequency of term j in sentence i. The LSA based decomposition of M is M = USV^T. V is r x n matrix, r represents the key concepts determined by LSA and n is the number of sentences in text. The matrix V^T describe each sentence in terms of each of the key concept described by top lexical chains. The Information System obtained by discretizing the matrix V^T obtained by LSA based decomposition. It is evaluated for its use in Span based summarization. The extract is formed by solving optimization problem given in Section 5.2 using PSO.

Span-GLOVE: GLOVE [26] vectors are pre-trained vectors which represent words and sentences based on learning huge corpus of textual data. Since a sentence can be represented using GLOVE vectors, experiments are performed to evaluate its effectiveness for Span based summarization. The sentences present in text forms the universe and attributes are the GLOVE features. The Information System is obtained with discretization of GLOVE representation of 100 dimension. The summary generated is spanning set obtained by solving optimization problem given in Section 5.2 using PSO.

Baseline: The baseline summarization system developed by Yadav & Chatterjee [34].

Graph: Graph based technique for summarization using PageRank [23] is performed here.

LSA: Latent Semantic Analysis based technique for summarization [10].

PSO: Particle Swarm Optimization [7] with fitness function as similarity between document and extract.

The systems are evaluated for comparison of results in terms of ROUGE recall scores in the Tables 3 through 6. Table 3 summarizes the results for DUC2001 dataset. The best results for all the ROUGE parameters evaluated are obtained for Span-Similarity. Table 4 gives the results for DUC2002 dataset. The results for ROUGE-1 is best for Span-Similarity model while ROUGE-L, ROUGE-S and ROUGE-SU are best for Span-Lexical Chain based model. For Enron Personal Email dataset and Enron Corporate Email dataset the best results are obtained for Span similarity which is performing better than all other comparison models. The results presented in Tables 3 to 6 show that the Span-Similarity based methods performed better than all other techniques. It is evident that only spanning set is not enough for efficient summary generation. The reason as mentioned before is the fact that a spanning set is not unique for a given Information System.

Table 3
Results of Summarization for DUC2001 Single Document Dataset

Baseline Span Span-GLOVE Span-LSA Span- Lexical Chain Span-Similarity Graph LSA PSO

ROUGE-1 0.3298 0.3305 0.3248 0.3218 0.3688 0.3775 0.3706 0.3293 0.3766

ROUGE-L 0.2877 0.2847 0.2810 0.2790 0.3235 0.3297 0.3236 0.2826 0.3276

ROUGE-W 0.1491 0.1286 0.1275 0.1264 0.1474 0.1503 0.1468 0.1288 0.1491

ROUGE-S 0.1329 0.1095 0.1047 0.1029 0.1365 0.1417 0.1339 0.1023 0.1394

ROUGE-SU 0.1311 0.1170 0.1122 0.1103 0.1444 0.1498 0.1420 0.1100 0.1475

	Baseline	Span	Span-GLOVE	Span-LSA	Span- Lexical Chain	Span-Similarity	Graph	LSA	PSO
ROUGE-1	0.3298	0.3305	0.3248	0.3218	0.3688	0.3775	0.3706	0.3293	0.3766
ROUGE-L	0.2877	0.2847	0.2810	0.2790	0.3235	0.3297	0.3236	0.2826	0.3276
ROUGE-W	0.1491	0.1286	0.1275	0.1264	0.1474	0.1503	0.1468	0.1288	0.1491
ROUGE-S	0.1329	0.1095	0.1047	0.1029	0.1365	0.1417	0.1339	0.1023	0.1394
ROUGE-SU	0.1311	0.1170	0.1122	0.1103	0.1444	0.1498	0.1420	0.1100	0.1475

Table 4

Results of Summarization for DUC2002 Single Document Dataset

	Baseline	Span	Span-Glove	Span-LSA	Span-Lexical	Span-Similarity	Graph	LSA	PSO
ROUGE-1	0.4293	0.3863	0.3853	0.3863	0.4384	0.4400	0.4348	0.3722	0.4219
ROUGE-L	0.3771	0.3349	0.3408	0.3368	0.3875	0.3849	0.3802	0.3214	0.3734
ROUGE-W	0.1729	0.1529	0.1549	0.1526	0.1772	0.1774	0.1720	0.1453	0.1710
ROUGE-S	0.1689	0.1359	0.1338	0.1357	0.1749	0.1734	0.1725	0.1208	0.1623
ROUGE-SU	0.1775	0.1442	0.1421	0.1440	0.1835	0.1822	0.1811	0.1291	0.1709

Table 5

Results of Summarization for Enron Personal Single Document Dataset

	Baseline	Span	Span-GLOVE	Span-LSA	Span-Similarity	Graph	LSA	PSO
ROUGE-1	0.3743	0.5013	0.4600	0.4690	0.5546	0.4467	0.5415	0.5029
ROUGE-L	0.3387	0.4572	0.4162	0.4243	0.5060	0.4051	0.4955	0.4551
ROUGE-W	0.1401	0.1800	0.1650	0.1688	0.1991	0.1611	0.1959	0.1808
ROUGE-S	0.1462	0.2308	0.2024	0.2091	0.2899	0.1972	0.2764	0.2395
ROUGE-SU	0.1590	0.2459	0.2168	0.2236	0.3049	0.2110	0.2912	0.2544

Table 6

Results of Summarization for Enron Corporate Single Document Dataset

	Baseline	Span	Span-GLOVE	Span-LSA	Span-Similarity	Graph	LSA	PSO
ROUGE-1	0.4651	0.5147	0.5000	0.5208	0.6193	0.4912	0.5166	0.5825
ROUGE-L	0.4551	0.4559	0.4384	0.4642	0.5511	0.4325	0.4573	0.5161
ROUGE-W	0.1762	0.1863	0.1801	0.1906	0.2234	0.1798	0.1858	0.2112
ROUGE-S	0.2241	0.2587	0.2457	0.2641	0.3717	0.2429	0.2659	0.3328
ROUGE-SU	0.2375	0.2731	0.2599	0.2784	0.3858	0.2568	0.2799	0.3469

7 Conclusion and future work

In this paper, novel Rough Set based uncertainty measure called span is proposed. Further, special Rough subsets of universe called spanning sets and complete spanning sets are defined and their properties are analyzed. There are various practical applications of span and spanning set. Here, the concepts are applied to problem of Single Document Extractive Text Summarization where the task reduces to finding suitable optimal spanning sets. The results are analyzed in terms of ROUGE scores for standard datasets for single document summarization viz. DUC2001, DUC2002, Enron Corporate Email dataset and Enron Personal Email dataset. It follows from our observations that the proposed Rough Set-based Span- Similarity is performing best among all the proposed models and experimented models of Text Summarization. We are working towards the extension of this approach to Multi Document Summarization.

References

Alguliev

R.M.

, Aliguliyev

R.M.

, Hajirahimova

M.S.

and Mehdiyev

C.A.

, MCMR: Maximum Coverage and Minimum Redundant Text Summarization Model, Expert Systems with Applications 38(12) (2011), 514–522.

Canhasi

and Kononenko

, Multi-Document Summarization via Archetypal Analysis of the Content-Graph Joint model, Knowledge and Information Systems 41(3) (2014), 821–842.

Canhasi

and Kononenko

, Weighted Hierarchical Archetypal Analysis for Multi-Document Summarization, Computer Speech & Language 37 (2016), 24–46.

Chatterjee

and Mohan

, Extraction based Single-Document Summarization using Random Indexing. In 19th IEEE International Conference on Tools with Artificial Intelligence (2007), 448–455.

Chatterjee

and Sahoo

P.K.

, Random Indexing and Modified Random Indexing based Approach for Extractive Text Summarization, Computer Speech & Language 29(1) (2015), 32–44.

Cutler

and Breiman

, Archetypal analysis, Technometrics 36(4) (1994), 338–347.

Eberhart

, Kennedy

A New Optimizer Using Particle Swarm Theory. In MHS’95. Proceedings of The Sixth International Symposium on Micro Machine and Human Science IEEE (1995), pp. 39–43.

Edmundson

H.P.

, New Methods in Automatic Extracting, Journal of The ACM (JACM) 16(2) (1969), 264–285.

, Wang

and Yun

, The Rough Membership Functions on Four Types of Covering based Rough Sets and their Applications, Information Sciences 390 (2017), 1–14.

10.

Gong

and Liu

, Generic Text Summarization using Relevance Measure and Latent Semantic Analysis. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM (2001), 19–25.

11.

Grzymala-Busse

J.W.

and Ziarko

, Data Mining Based on Rough Sets. In Data Mining: Opportunities and Challenges. IGI Global. (2003), 142–173.

12.

Grzymala-Busse

J.W.

Rough Set Theory with Applications to Data Mining. In Real World Applications of Computational Intelligence. Springer, Berlin, Heidelberg (2005), 221–244.

13.

, An

, Yu

and Yu

, Robust Fuzzy Rough Classifiers, Fuzzy Sets and Systems 183(1) (2011), 26–43.

14.

Inbarani

H.H.

, Azar

A.T.

and Jothi

, Supervised Hybrid Feature Selection Based on PSO and Rough Sets for Medical Diagnosis, Computer Methods and Programs in Biomedicine 113(1) (2014), 175–185.

15.

Jensen

and Shen

, Fuzzy-Rough Sets assisted Attribute Selection, IEEE Transactions on Fuzzy Systems 15(1) (2007), 73–89.

16.

Karwa

and Chatterjee

, Discrete Differential Evolution for Text Summarization. In 2014 International Conference on Information Technology IEEE (2014), 129–133.

17.

Lin

C.Y.

, Rouge: A Package for Automatic Evaluation Of Summaries. Text Summarization Branches Out, 2004.

18.

Loza

, Lahiri

, Mihalcea

and Lai

P.H.

, Building a Dataset for Summarization and Keyword Extraction from Emails, In LREC (2014), 2441–2446.

19.

Luhn

H.P.

, The Automatic Creation of Literature Abstracts, IBM Journal of research and development 2(2) (1958), 159–165.

20.

Mani

Advances in Automatic Text Summarization, MIT Press, 1999.

21.

Mihalcea

Graph based Ranking Algorithms for Sentence Extraction, Applied to Text Summarization. In Proceedings of the ACL Interactive Poster and Demonstration Sessions 2004.

22.

Mihalcea

, Tarau

TextRank: Bringing order into Text. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing 2004.

23.

Page

, Brin

, Motwani

, Winograd

The PageRank citation ranking: Bringing order to the web, Stanford InfoLab 1999.

24.

Pawlak

Rough Sets: A Tutorial, Int Journal of Information and Computer Sciences 1982.

25.

Pawlak

Rough Sets: Theoretical Aspects of Reasoning about Data, Springer Science &Business Media 2012.

26.

Pennington

, Socher

, Manning

Glove: Global Vectors for Word Representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) 2014, pp. 1532–1543.

27.

Polkowski

, Rough

(Ed.).

Sets in Knowledge Discovery 2: Applications, Case Studies and Software Systems. Physica19 (2013).

28.

Silber

H.G.

, Mccoy

K.F.

Efficient Text Summarization using Lexical Chains. In Proceedings of the 5th International Conference on Intelligent User Interfaces, ACM (2000). pp. 252–255.

29.

Singh

and Dey

, A Rough Fuzzy Document Grading System for Customized Text Information Retrieval, Information Processing and Management 41(2) (2005), 195–216.

30.

Steinberger

and Jezek

, Using Latent Semantic Analysis in Text Summarization and Summary Evaluation, Proc ISIM 4 (2004), pp. 93–100.

31.

Srinivasan

, Ruiz

M.E.

, Kraft

D.H.

and Chen

, Vocabulary Mining for Information Retrieval: Rough Sets and Fuzzy Sets, Information Processing &Management 37(1) (2001), pp. 15–38.

32.

Tay

F.E.

and Shen

, Economic and Financial Prediction using Rough Sets Model, European Journal of Operational Research 141(3) (2002), pp. 641–659.

33.

Wang

, Yang

, Teng

, Xia

and Jensen

, Feature Selection based on Rough Sets and Particle Swarm Optimization, Pattern Recognition Letters 28(4) (2007), pp. 459–471.

34.

Yadav

and Chatterjee

, Text Summarization using Rough Sets. In International Conference on Natural Language Processing and Cognitive Processing 2014.

35.

Yadav

and Chatterjee

, A Novel Approach for Feature Selection using Rough Sets. In 2017 International Conference on Computer, Communications and Electronics (Comptelix) (2017), pp. 195–199.

36.

Yao

Y.Y.

Granular Computing using Neighborhood Systems, In Advances in Soft Computing, Springer, London. (1999), pp. 539–553.

37.

Yeh

J.Y.

, Ke

H.R.

, Yang

W.P.

and Meng

I.H.

, Text Summarization using a Trainable Summarizer and Latent Semantic Analysis, Information Processing and Management 41(1) (2005), 75–95.

38.

Zheng

and Zhu

, Uncertainty Measures of Neighborhood System based Rough Sets, Knowledge-Based Systems 86 (2015), 57–65.

39.

Zhu

and Wang

F.Y.

, On three types of Covering based Rough Sets, IEEE Transactions on Knowledge and Data Engineering 19(8) (2007), 1131–1144.

Rough sets based span and its application to extractive text summarization

Abstract

Keywords

1 Introduction

2 Previous works on text summarization

3 Rough sets

4 Rough set based span, spanning set and weighted rough sets

4.1 Span and spanning sets

4.2 Computing spanning sets

Table 1 Example on span and spanning set computation a1 a2 a3 x0 3 1 2 x1 1 1 1 x2 1 2 2 x3 2 2 2 x4 2 2 3 x5 2 3 3 x6 3 3 3

5.1 Determining extract of text using span

5.2 Optimization problem

5.3 Proposed solution for computing spanning sets of text documents

6 Experiments and observations

6.1 Experiments

References

Table 1
Example on span and spanning set computation

a1 a2 a3

x0 3 1 2

x1 1 1 1

x2 1 2 2

x3 2 2 2

x4 2 2 3

x5 2 3 3

x6 3 3 3