Using Context Inference to Improve Sentence Ordering for Multi-document Summarization

In this paper, we propose a novel context inference-based approach for sentences ordering in mult i-document summarization application. Our method first detects whether or not two summarizat ion sentences should be adjacent according to the similarity between one summarizat ion sentence and the context of the other one, and then it co mputes the reliability of the adjacent summarization sentences based on the similarity and their relative position. To be specific, the first sentence will be selected according to features of sentence, and the second sentence will be selected if and only if it has the maximu m reliability with previous sentence. Evaluation result shows that our method outperforms the state-of-the-art ones on DUC2004 corpus.


Introduction
Multi-document summarization is an automatic procedure aimed at extraction of information from multiple texts written about the same topic. Whereas, sentence ordering, the last task of multi-document summarization, will finally affect the quality of summarization. Furthermore, the task of sentence ordering in multi-document summarization is harder than that in single document summarization because multiple documents are created by different authors who have different writing styles and backgrounds. Therefore, no natural order of texts can be extracted as the basis of sentence ordering judgment. How to conduct an efficient and effective method for sentences ordering is a difficult but important task for both multidocument summarization and other text processing job, e.g. Question Answering.
Currently, a variety of studies have been reported on sentence ordering. Some methods adopted chronological information (McKeown et al., 1999;Lin et al., 2001;Barzilay et al., 2002;Okazaki et al., 2004) while others learned the natural order of sentences from source documents or large corpus (Lapata, 2003;Barzilay and Lee, 2004;Nie et al., 2006;Ji and Nie, 2008). However, chronological information cannot be easily extracted from those non-news documents and constructing a large corpus also is not so easy. Furthermore, those results of all above methods are far from satisfactory. Therefore, how to achieve coherent summarization still is an issue for us. This paper proposes a novel method to infer the order of summarization sentences for multidocument summarization according to their context. We first judge whether or not two summarization sentences should be adjacent based on the similarity between one summarization sentence and the context of the other one, and then compute the reliability based on the similarity and relative position of the adjacent summarization. To be specific, the first sentence will be selected based on its features, and the second sentence will be selected if and only if it has the maximum adjacency reliability with previous sentence. The experimental results on DUC2004 corpus show that our method outperforms state-of-the-art ones.
The reminder of this paper is organized as follows. In Section 2, the related work is introduced. The motivation of our method is discussed in Section 3. In Section 4, the context inference-based sentence ordering algorithm is described. In Section 5, the experiments and evaluation are presented. Conclusions and future work are given in Section 6.

Related Work
So far many studies on sentence ordering have been proposed. They can be divided into two categories: chronology-based method and natural order-based method. To be specific, chronologybased methods determine sentence ordering according to the chronological order of events while natural order-based methods infer sentence ordering according to some cues that are learned from source documents and corpus. Barzilay et al. (2002) proposed a chronologybased method to sort sentence, they assumed the theme of sentences were the cues of sentence ordering. Based on it, they presented a strategy according to the first published date of the theme; then sorted sentences based on their order of presentation in the same article. Okazaki et al. (2004) proposed an approach to improve the chronological sentence ordering method by using precedence relation technology. They assumed the presupposed information should be transferred to reader in advance before the sentence was interpreted. They first arranged sentences in a chronological order and then estimated the presupposed information for each sentence by using the content of the sentences located in before each sentence in its original article.
Generally speaking, the articles in news domain usually contain descriptions of date and events accompanying the publication sequences. Therefore, chronology-based method is practical for news domain. However, chronological information is not ubiquitous in a large number of multi-document summarization tasks. So, some studies began to focus on general domain, and they sorted sentences according to the source documents and corpus. McKeown et al. (2001) and  presented a majority ordering algorithm to sort sentences. They classified sentences of source documents into different themes or topics using summarization sentences. If sentences from theme 1 preceded sentences from theme 2 when they appeared in same text, then putted theme 1 was preceding theme 2. The order of summarization sentences was determined by the order of themes. However, there were some potential issues in this kind of method. Firstly, it was not easy to correctly cluster sentences into topics. Secondly, some summarization sentences may belong to a same topic. Finally, the relative order between two topics may be not steady. Lapata (2003) provided an unsupervised probabilistic model for sentence ordering. The model assumed that sentences were represented as a set of features that could be automatically extracted from the corpus without manual annotation. The conditional probability of sentence pairs can be learned from a training corpus. By computing conditional probability of each sentence pairs, the approximate optimal global sentence ordering can be achieved using a simple greedy algorithm. Bollegala et al. (2005) combined three ordering methods together, said chronological ordering, probabilistic ordering and topic relatedness ordering, and adopted a machine learning approach for sentence ordering. The mixed system can achieve better performance than any of the three individual one. To be extended, they also proposed a bottom-up approach for sentence ordering (Bollegala et al., 2010). They defined four criteria (chronology, topical-closeness, precedence and succession) between two textual segments, and adopted SVM classifier to learn the relative order of them. They repeatedly concatenated two textual segments into one segment based on the relative order until all sentences were arranged. Nie et al. (2006) adopted adjacency of sentence pairs to sort sentences. Sentence adjacency was calculated based on adjacency of features of each sentence pairs. Adjacency between two sentences represented how closely they should be putted together in a set of summarization sentences. Ji et al. (2008) extended the above adjacency model. They proposed a cluster-adjacency based method to map each sentence of source documents to a theme by using semi-supervised classification method. The adjacency of sentences pair was learned from source documents according to adjacency of clusters they belonged to.
Our method is different from above ones in two aspects. First, we try to find the indirect relations of summarization sentences according to source documents. Second, the source documents are topic-related and most summarization sentences or their similar ones appear in more than one source document. Meanwhile, there are more than two summarization sentences or their similar ones may co-occur in a source document. Therefore, we can infer the order of summarization sentences by using the indirect relation between summarization sentences.

Motivation
Different documents have different writing styles and backgrounds. Besides, sentences that used to describe a same topic may have different forms. Therefore, source documents maybe cannot provide the direct information for sentence ordering. However, they still provide some indirect information which can be used to infer the order of summarization sentences.
Each source document for multi-document summarization is not an information island. They may have some overlapped information. For example, there are three documents to report a same news event. The first document describes its background and cause. The second one describes the origin, process and result. The third one describes the effect and comment. Each document has its own key point, but they have some overlapped information. The first and the second one report the cause in both while the second and the third one report the effect in both.
Each summarization sentence is extracted from a source document even though it is created or rewritten manually, it also can link to one or more sentences in source documents. Therefore, each summarization sentence is also not isolated and there are many sentences surrounding them in the source document. We call these sentences as the context of the summarization sentence. Furthermore, the source documents are in same topic and most of summarization sentences are presented in more than one document. In a word, a summarization sentence may have some similar sentences in source documents.
Accordingly, we provide a method to infer the order of summarization sentences by using their context. Let us consider an example: there are two documents, d 1 and d 2 , sketched in Figure 1, where ss 1 and ss 2 are two summarization sentences or their similar ones in source documents, s1 i and s2 i are the context sentence of ss 1 and ss 2 respectively. If ss 2 is similar to s1 1 , we have reason to believe that ss 2 and ss 1 should be adjacent and ss 2 should be in front of ss 1 because s1 1 is front of ss 1 . The highly similarity between ss 2 and s1 1 , the highly probability that ss 2 is in front of ss 1 .
If ss 2 is not similar to s1 1 , but it is similar to s1 2 , we also consider ss 2 should be in front of ss 1 , but the probability will higher because s1 2 is closer to ss 1 than s1 1 . Similarly, if ss 2 is similar to s1 3 , ss 1 should be in front of ss 2 .

Context Inference-based Sentence Orde ring Algorithm
From the analysis in section 3, we can infer the order of sentence by using the similarity between summarization sentences and their context. We compute the adjacent credibility of two sentences and then use a directed graph with weight to represent the order of summarization sentences. A vertex denotes a sentence. If two sentences are adjacent then an edge exists of them. The weight of edge is the adjacency credibility of two sentences. Figure 2 shows the order relation among summarization sentences, there is an edge from s 1 to s 3 and the weight is 0.5, which means s 1 and s 3 are adjacent, and the credibility of them is 0.5. From figure 2, we can find a path contained all vertexes, which has the maximum weight. The order of the path is considered as the best logical order of summarization sentences. Due to finding an optimal path in a graph is a typical NP problem; we will use an algorithm to find an approximate optimal path. We assume that the document set D= {d 1 , d 2 ... d n }, a document d j = {s j,1 , s j,2 , …, s j,m } where s j,i is the ith sentence in d j , the summarization sentences set SS= {ss 1 , ss 2 , ..., ss k }, the Graph G=NULL. For a sentence ss i in d j , its context sentence set is {d j -ss i }. The algorithm is described as follows. Input: D, SS and G Output: P, an ordered list that contains all summarization sentences.

BEGIN
Step 1: For each ss i in SS, add a vertex to graph G; Step 2: For each ss i in d j , compute the similarity sim(ss k , s j,l ) between each ss k ( (1) where rank(ss i ) is the sequence of ss i in the document it belongs to (e.g. the rank of second sentence of document is 2), w is the contribution of sentence similarity to the credibility, sim(ss k , s j,l ) is the similarity between ss k and s j,l . If there is no edge from ss k to ss i in G, then add an edge to G; else if weight(ss i , ss k ) is greater than the weight of existing edge, then update the edge.

} {
If ss i is in front of s j,l , the credibility weight(ss i , ss k ) is computed as follows: (4) where sim(w, s i ) is the maximum semantic similarity between word w and sentence s i , length (s i ) is the length of sentence s i .
Step 3: We use a feature-based method to find the first sentence, assume that there is a null sentence at the beginning of each source document and it contains a null feature (Nie, 2006). The probability of a sentence ss i is the first one is defined as follow: where K is the number of features in sentence s i . freq() is the frequency function, freq(feature t ) denotes the frequency of feature t in the source documents, freq(feature t , nullfeature) denotes the frequency of feature i and the null feature cooccurring in the source documents within a limited range (one or several sentences, we assign 3 to the range). Select the sentence with the maximum probability as the first sentence. Add the first sentence to P.
Step 4: Get the trail sentence of P, select the next sentence and add it to P. Given an already ordered sentence serial P: ss 1 , ss 2 … ss i which is a subset of the summarization sentences set SS. The next sentence can be found by formula (6) Step 5: If P contains all summarization sentences then exit; otherwise go to step 4. END

Test Set and Evaluation Metrics
Due to current methods provided their experiment results using DUC04 corpus, we also use it to conduct our experiment. DUC04 provide 50 source document sets and four manual summaries for each document set in its Task2. Each document set consists of 10 documents. In the DUC04, sentences in summaries are not directly come from the source documents and they are created by manually. Therefore, we need map them back to the sentences in source documents. For each manual summarization sentence, we find a sentence in source document sets that has the maximal similarity with it as its source sentence. These source sentences of each summarization are taken as inputs to ordering model, but sequential information is neglected. The output ordering of various models are compared with the specified ones in manual summaries. A number of metrics can be used to evaluate the difference between two orderings. In this paper, we adopt Kendall's τ (Lebanon, 2002), which was defined as: where N is the number of objects to be ordered (i.e., sentences), number_of_inversions is the minimal number of interchanges of adjacent objects to transfer an ordering into another. Intuitively, τ can be considered as how easily an ordering can be transferred to another. The value of τ varies from -1 to 1, where 1 denotes the best situation where two orderings are the same, and -1 denotes the worst situation where two orderings are completely reversed. Given a standard ordering, randomly produced orderings of the same objects would get an average τ of 0. For example, Table 1 lists three numbers of sequences, their natural sequences and the corresponding τ values.

Experimental Results
In order to get the best performance, we adjusted the parameters of our approach (θ and w). We adopted DUC02 as the development set to adjust parameters θ and w. In DUC02, it provide 60 document sets of approximately 10 documents each and one manual summarization of about 100 words for each document set in Task2. Figure 3 show the experiment results, from it, we can finally get the optimal value of θ and w (0.3 and 0.6 respectively). We assume Rd, Mo, Pr, Fa and Ca to denote random ordering, majority ordering, probabilistic model, feature-adjacency based model and cluster-adjacency based model which have been mentioned in section 2 respectively. Due to other methods didn't report their results on DUC04 corpus; we do not compare our method with them in this paper. We define our Context-based approach as Co. Table 2 shows the results of different methods. The τ value of our approach reaches 0.43, which outperforms other approaches. Also, the performance of WordNetbased similarity measure is slightly better than the TF-IDF based one. The reason may be that some authors will express the same meaning by using some different but synonymous words.   Table 3. Comparison of correct sentence inference From table 3, our method has the highest correction ratio of sentence inference, which mean that our method's strategy to choose next sentence is reasonable than that of others. Probabilistic ordering, a statistical method, tries to find the ordering clue from the corpus, but they ignore the importance of source documents. Basically, we know that people can easily find the order of summarization sentences according to the source documents. But it's difficult to give the order for the sentence base on a corpus without the source documents even for a knowledgeable man. Therefore, we believe the source documents can give us some effective and efficient information. Fa and Ca models sort sentences by using sentence adjacency, which is calculated based on adjacency of feature pairs. However, how to choose effective features is a potential issue of this kind of method. Besides, it doesn't always mean two sentences are likely to be adjacent when some words of them are adjacent. Our method is different from other ones in that we find the indirect relations between summarization sentences based on the context and make full use of the information which provided by source documents. Table 4 shows a further comparison among all methods. "Positive ordering" means that the result of ordering is better than that of random ordering and "Negative ordering" denotes the output ordering which gets a negative τ. From it, we can review that our method generates the most positive orderings while with the least negative orderings. Precision of first sentence of our method is less than that of Ca. If we assume the first sentence of summarization is known in advance, experiments show that the average τ value of our method could reach 0.562.

Models
Precision of 1st sentence  Table 4. Correction ratio of 1st sentence ranking

Conclusion and Future Work
This paper presents a novel method for sentence ordering in multi-document summarization application. The proposed method first computes the similarity between summarization sentences and context of other summarization sentences, judge whether or not two sentences should be adjacent, and then compute the reliability according to the similarity. The experimental results review that our method outperforms other sentence ordering methods on DUC04 corpora. For further work, we will change the strategy to improve the accuracy of first summarization sentence; therefore, the τ value could have an obvious improvement. In addition, we will conduct more experiments to verify the effectiveness and efficient of our method using manual evaluation.