{'fraction_non_alphanumeric': 0.025513033832501388, 'fraction_numerical': 0.010229863807234856, 'mean_word_length': 4.5651577503429355, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Update Summarization Based on Co-Ranking with Constraints

Update summarization is an emerging summarization task of creating a short summary of a set of news articles, under the assumption that the user has already read a given set of earlier articles. In this paper, we propose a new co-ranking method to address the update summarization task. The proposed method integrates two co-ranking processes by adding strict constraints. In comparison with the original co-ranking method, the proposed method can compute more accurate scores of sentences for the purpose of update summarization. Evaluation results on the most recent TAC2011 dataset demonstrate that our proposed method can outperform the original co-ranking method and other baselines.


Introduction
Update summarization is an emerging new summarization task of creating a short summary of a set of news articles, under the assumption that the user has already read a given set of earlier articles. The purpose of update summarization is to inform the reader of new information about a particular topic. Update summary is very useful for the user to know about a chronic topic. For example, given a topic of "Haiti earthquake", the earlier articles mainly talk about the occurrence of the earthquake and the consequence of the earthquake, and the later articles talk about the consequence of the earthquake and the rescue issues. In this case, the reader will read the later articles to know about the rescue issues after he/she has read the earlier articles. Therefore, an update summary of the later articles may facilitate the reader to grasp the "update" information in a very convenient way.
The update summarization task can be formulated as follows: Given an earlier document set D A and a later document set D B about a topic q, the sentence set for D A is denoted as S A and the sentence set for D B is denoted as S B . The update summary with a predefined length for D B after reading D A is denoted as SUM B , where the sentences in SUM B must meet the following requirements: 1) The summary sentences must be representative of D B , i.e., the summary sentences in SUM B must reflect important information in D B . Moreover, the sentences must be biased to the topic q.
2) The summary sentences must be the least redundant with the sentences in D A , i.e., the summary must not contain important information in D A .
The task of update summarization was piloted in DUC2007, and it has been the fundamental task through TAC2008~TAC2011. The "update" characteristic makes the task more challenging than traditional document summarization tasks. Till now, most existing update summarization methods are adaptations of multi-document summarization methods by considering the redundancy information between the earlier and later document sets (Boudin et al. 2008;Fisher and Roark 2008;Nastase et al. 2008 ). In addition, several new methods have been proposed for addressing this task (Du et al. 2010;Wang and Li 2010;Li et al. 2008), and graph-based coranking is a typical one, where the sentences in the two document sets are ranked simultaneously by considering the sentence relationships across the document sets. Based on the co-ranking framework, Li et al. (2008) propose a graph-based sentence ranking algorithm named PNR 2 for update summarization, and it models both the positive and negative mutual reinforcement between sentences in the ranking process. In addition, Wan et al. (2011) apply the co-ranking algorithm for multilingual news summarization.
In this study, we propose a new co-ranking method, which is inspired by (Wan et al. 2011), to address the update summarization task. The proposed method integrates two co-ranking processes by adding strict constraints. In comparison with the original co-ranking method, the proposed method can compute more accurate scores of sentences for the purpose of update summarization. We perform experiments on the most recent TAC2011 dataset, and the evaluation results demonstrate that out proposed method can outperform the original co-ranking method and a few other baselines.

Our proposed method
Given the two document sets D A and D B about a topic q, we introduce two kinds of scores for each sentence: an update score and a consistency score. In our proposed method, each kind of score is computed with a co-ranking process, and the two kinds of scores are adjusted by adding strict constraints. Finally, the refined update scores are used for summary extraction.
We assign each sentence an update score to indicate how much the sentence contains significant and new information after knowing about the sentences in the other document set. The update score of each sentence relies not only on the sentences in the same document set, but also on the sentences in the other document set. In particular, the co-ranking method is based on the following assumption: The update score of a sentence is positively associated with the sentences with high update scores in the same document set, and is negatively associated with the sentences with high update scores in the other document set.
We introduce a consistency score for each sentence to indicate how much a sentence contains important and shared information in the two document sets. In particular, the consistency scores of the sentences can be computed based on the following assumption: The consistency score of a sentence is positively associated with the sentences with high consistency scores in the same document set, and is also positively associated with the sentences with high consistency scores in the other document set.
Formally, let G=(S A , S B , E A , E B , E AB ) be an undirected graph for the sentences in the two document sets D A and D B . S A ={s A i | 1≤i≤m} is the set of earlier sentences. S B ={s B j | 1≤j≤n} is the set of later sentences. m, n are the sentence numbers in the two document sets, respectively. Each sentence s A i or s B j is represented by a term vector A i s or B j s in the VSM model. E A is the edge set to reflect the similarity relationships between the sentences in the earlier document set. E B is the edge set to reflect the similarity relationships between the sentences in the later document set. E AB is the edge set to reflect the similarity or dissimilarity relationships between the sentences in the two different document sets. The following matrices are required to be computed to reflect the three kinds of sentence relationships: This matrix aims to reflect the similarity relationships between the sentences in S A . Each entry in the matrix corresponds to the cosine similarity between two sentences, and we let to make the sum of each row equal to 1.
This matrix aims to reflect the similarity relationships between the sentences in S B . Each entry in the matrix corresponds to the cosine similarity between two sentences, and we let directly embody the negative association between the sentences in the two sets.
In order to compute the query-biased scores of the sentences, the relevance values of the sentences to the query also need to be computed. We use two column vectors j ] n×1 to reflect the query-biased scores, where each entry in r A corresponds to the cosine similarity between a sentence and the given topic description. Then r A is normalized to r Ã to make the sum of all elements equal to 1. Each entry in r B is computed in the same way, and r B is normalized to r B .
After computing the above matrices and vectors, we can compute the update scores of the sentences in the two sets in a co-ranking process. We use two column vectors i ] n×1 to denote the update scores of the sentences in S A and the sentences in S B , respectively. Based on the first assumption, we can obtain the following equations: where α 1 , β 1 , γ 1 ∈ [0, 1] specify the relative contributions to the final scores from different sources and we have α 1 +β 1 +γ 1 =1. Note that since AB M and BA M contain the dissimilarity values between the two sets of sentences, the second terms in the right hands of the above equations actually embody the negative reinforcement between the two sets of sentences. Different from (Li et al. 2008), the addition of all the terms in the right hands of the equations makes the algorithm more convenient to be solved in an iterative way.
We can also compute the consistency scores of the sentences in the two sets in a co-ranking process. We use two column vectors to denote the consistency scores of the sentences in S A and the sentences in S B , respectively. Based on the second assumption, we can obtain the following equations: where α 2 , β 2 , γ 2 ∈ [0, 1] specify the relative contributions to the final scores from different sources and we have α 2 +β 2 +γ 2 =1.
Then, we interconnect the two co-ranking processes based on our key assumption that the update score and the consistency score of each sentence is mutually exclusive. If the update score of a sentence is high, then the sentence contains significant and new information, which is not contained in the other document set; but if the consistency score of a sentence is high, then the sentence contains significant and shared information with the other document set. Therefore, the update score and the consistency score of a sentence are conflicting with each other, and they cannot be high at the same time.
The sum of the update score and the consistency score of each sentence is fixed to a particular value.
This assumption can be used to adjust the inaccurately assigned scores for the sentences.
Till now, the update scores and the consistency scores are computed by using a co-ranking process separately. Based on our new assumption, we can add the following constraints to interconnect the two co-ranking processes: The values for different sentences may be different since they are unequally important in the document sets. In this study, we use the generic informativeness score of each sentence as the fixed sum value for the sentence. The generic informativeness score of a sentence is computed by using the basic graph-based ranking algorithm. Taking a sentence s B i in S B as an example, the value can be computed in a recursive form as follows: where μ is the damping factor usually set to 0.85, as in the PageRank algorithm. The generic informativeness score of a sentence in S A can be computed based on A M in the same way.
In order to add the constraints to interconnect the two co-ranking processes, the constraints are executed as a normalization step. In particular, the following steps are iteratively performed until convergence. Note that all the scores are simply initialized to 1, and (t+1), (t) means the (t+1)-th and (t)-th iterations, respectively.
1) Compute the update scores of the sentences with the following equations: Compute the consistency scores of the sentences with the following equations: 3) Add the constraints on the update scores and the consistency scores of the sentences by normalization with the following equations ( ζ A , η B are temporary vectors): Finally, we obtain the update scores u B for the sentences in the later document set D B , and we apply the simple greedy algorithm in (Wan et al. 2007) to remove redundant sentences and select summary sentences until the summary length reaches the given limit. Note that in the experiments, the iteration number of the above algorithm is mostly around10, which is very efficient.

Evaluation setup
In this study, we used the most recent update summarization task on TAC 2011 for evaluation purpose. NIST selected 44 topics, and two sets of 10 documents (set A and set B) were provided for each topic. The update task aims to create a 100-word summary of 10 documents in set B, with the assumption that the content of the first 10 documents in set A is already know to the reader. For each document set, NIST assessors have created 4 human summaries as reference (model) summaries. The sentences have already been split for the documents.
For each topic, we only used the topic title as the topic description. As a pre-processing step, we removed the very long or very short sentences, which are usually not good summary sentences. We also polished some sentences to make them more concise by applying simple rules, e.g. removing some clauses in the sentences. The sentences in the documents were then stemmed by using Porter's stemmer. Our proposed summarization method and the baseline methods were performed on the pre-processed document sets.
We used the ROUGE-1.5.5 toolkit 1 for evaluation, which was officially adopted by DUC for automatic summarization evaluation. The toolkit measures summary quality by counting overlapping units such as the n-gram, word sequences and word pairs between the candidate summary and the reference summary. The ROUGE toolkit reports separate scores for 1, 2, 3 and 4-gram, and also for longest common subsequence co-occurrences. In this study, we show three ROUGE scores in the experimental results 2 : ROUGE-1 (unigram-based), ROUGE-2 (bigrambased), and ROUGE-SU4 (based on skip bigram with a maximum skip distance of 4).
In the experiments, our proposed method is compared with the following baseline methods: Lead: This baseline is provided by NIST, and it returns all the leading sentences (up to 100 words) in the most recent document. Baseline 1 provides a lower bound on what can be achieved with a simple fully automatic extractive summarizer.
Mead: This baseline is also provided by NIST, and it uses the MEAD automatic summarizer with all default settings, to produce summaries.

MMR:
This baseline is based on the MMR criterion for selecting summary sentences with new information.
SinkManifoldRank: This baseline is a new graph based ranking method for update summarization, which is based on manifold ranking with sink points (Du et al. 2010).
CoRank: This baseline is the basic co-ranking method for update summarization, and it directly uses the co-ranking algorithm to compute the update score for each sentence, without considering the constraints between the update score and the consistency score.

Evaluation results
First, our proposed method is compared with the baseline methods, and the comparison results are shown in Table 1. In the table, the 95% confidence interval of each ROUGE score is given in brackets, which is reported by the ROUGE toolkit.
Second, our proposed method is compared with the participating systems on TAC 2011. On TAC 2011, NIST received 48 runs from 24 participating teams. We rank the runs based on the ROUGE-2 scores, and list the top five runs for comparison. In addition, we also compute the average ROUGE scores. The comparison results are shown in Table 2.
We can see from the table that our proposed method ranks 4 th out of all the runs over the ROUGE-2 metric. The performance of our proposed method is comparable with the top run's performance. We can also see that the performance values of our proposed method are much better than the average scores. Note that the top runs have leveraged world knowledge or various features, for example, the NUS1 run has used category knowledge in a supervised machine learning approach. However, our proposed method only uses the similarity/dissimilarity relationships between sentences in an unsupervised approach. The comparison results demonstrate that our proposed method is a competitive method for the update summarization task.

Conclusion and future work
In this paper, we propose a new method for update summarization, and it improves the basic coranking method by adding strict constraints and interconnecting two co-ranking processes. Evaluation results on the most recent TAC 2011 dataset demonstrate the good effectiveness of the proposed method, which can outperform a few baseline methods, and the performance is comparable to the top participating systems on TAC 2011.
In this study, we only use the topic title as the topic description, however, the title is usually very short, and we will investigate query expansion techniques to get a clearer topic description. We will also make use of the topic category specific features (i.e. the guided information) to improve our update summarization method in future work.