吳仁守，劉 凱，王紅玲

(蘇州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

0 引言

隨著大數(shù)據(jù)時代的到來，互聯(lián)網(wǎng)逐漸成為了人們獲取和發(fā)布信息的主要渠道，互聯(lián)網(wǎng)上關(guān)于熱點(diǎn)新聞事件的報道與日劇增。當(dāng)人們想要了解某一新聞事件時(例如，Egyptian Crisis)，可以輕易在互聯(lián)網(wǎng)上搜索到大量相關(guān)的報道，但是這些報道通常只是報道了這個新聞事件在某一時間段內(nèi)的信息，且各個報道之間會有大量重復(fù)信息。面對海量的信息，人工逐一瀏覽歸納是非常耗時耗力的，為方便用戶快速、全面地了解事件的發(fā)展，自動文摘成為一個有效手段。

傳統(tǒng)多文檔自動文摘把與事件相關(guān)的文檔作為一個文檔集合并為之生成摘要，集合中文檔數(shù)目通常較少。面對互聯(lián)網(wǎng)中大量相關(guān)且相似的文檔，傳統(tǒng)多文檔自動文摘無法很好地工作。而且，由于傳統(tǒng)多文檔自動文摘沒有考慮各個文檔之間的時間和主題關(guān)系，很難讓用戶了解該事件的演化發(fā)展過程。與之相比，帶有時間標(biāo)志的演化式文摘(evolutionary timeline summarization，ETS)可以針對互聯(lián)網(wǎng)上新聞事件的報道文檔，按時間順序抽取出演化式摘要，為用戶提供該事件全部發(fā)展過程，方便用戶全面了解事件的前因后果和發(fā)展脈絡(luò)，如表1所示。

隨著時間推移，新聞話題的內(nèi)容往往會發(fā)生變化，如何有效地組織這些大規(guī)模文檔，生成主題在不同發(fā)展階段的局部摘要，使其既能夠提煉出主題的局部摘要信息，又能體現(xiàn)相鄰時間段的主題演化，同時避免引入上一階段的冗余信息，是演化式摘要面臨的一個主要難題。由此，本文提出了一種基于局部—全局主題關(guān)系的演化式摘要方法，該方法將新聞標(biāo)題作為文摘的候選句子，大大降低了數(shù)據(jù)量，并對事件進(jìn)行主題分割，在考慮時間演化的基礎(chǔ)上同時考慮子主題間的主題演化，最后通過一種改進(jìn)的PageRank[1]算法將子主題和大主題相關(guān)聯(lián)。該方法與以往方法的不同之處在于： 以往方法通常通過抽取命名實(shí)體來追蹤事件的演化，并且只考慮了時間維度或主題維度上的演化。本文除了考慮不同時間段的演化關(guān)系，還引入了子主題間的演化關(guān)系，并對傳統(tǒng)的PageRank進(jìn)行了拓展，利用句子、時間和主題三者相互強(qiáng)化來對句子打分排序。

表1 Wikipedia中關(guān)于Egyptian Crisis的部分帶時間標(biāo)簽摘要

1 相關(guān)工作

傳統(tǒng)多文檔自動文摘(multi-document summarization，MDS)[2]是將同一主題下多個文本描述的主要信息按壓縮比提煉出一個文本摘要的自然語言處理技術(shù)。根據(jù)文摘句選取方式的不同主要可分為兩種： 抽取型(extraction)文摘[3]和理解型(abstraction)文摘[4]。

作為多文檔自動文摘的一種，演化式摘要為每個文檔做上時間標(biāo)記，然后按時間序列構(gòu)成一個摘要，它的一個重要屬性是動態(tài)演化性[5]。演化式摘要的動態(tài)演化性與話題檢測與跟蹤(TDT)任務(wù)中的話題演化研究類似，但又有所不同。TDT衡量的是同一個話題隨時間推移表現(xiàn)出的動態(tài)性、發(fā)展性和差異性。演化式文摘通常針對單個新聞事件(或話題)，重點(diǎn)考慮內(nèi)容演化，忽略強(qiáng)度演化。同時，不需要根據(jù)演化趨勢做出預(yù)測，而需要根據(jù)演化趨勢抽取代表句子生成摘要。

與時間有關(guān)的文摘技術(shù)最早由Allan[6]提出，通過抽取關(guān)鍵名詞短語和命名實(shí)體來實(shí)現(xiàn)。Tran[7]也是通過抽取命名實(shí)體來追蹤事件演化的，但是和上述方法不同的是，他利用了維基百科關(guān)于該事件的詞條中實(shí)體的分布，并且綜合考慮了實(shí)體在當(dāng)前日期文檔集合中的顯著性(salience)和該實(shí)體在所有文檔集中的信息性(informativeness)，據(jù)此抽取實(shí)體和它的上下文。Chieu[8]通過計算句子的新奇性(interest)和爆發(fā)性(burstiness)來抽取得分較高且日期不相連的句子作為摘要。不過這些方法都沒有考慮新聞事件所特有的演化特性。Yan[9-10]使用基于圖的方法，根據(jù)時間將句子映射到同一個平面，然后創(chuàng)建演化性文摘。其認(rèn)為各個摘要組件既相互獨(dú)立又相互聯(lián)系，強(qiáng)調(diào)相關(guān)性、范圍性、一致性和跨日期多樣性，并通過構(gòu)造一個最優(yōu)化框架來平衡局部和全局的關(guān)系。其中Yan[10]通過將當(dāng)前時間段文檔集合附近的文檔集，根據(jù)時間的間隔投影到當(dāng)前文檔集中來考慮文檔集合之間的聯(lián)系。該方法與本文提出的方法相似，但是它只考慮了時間的演化而忽略了主題的演化。Li[11]把演化摘要任務(wù)看作主題演化的過程，利用層次狄利克雷過程為每一個日期文檔集抽取出主題，捕捉主題演化的模式，通過考慮主題相關(guān)性、覆蓋率和一致性等不同方面，抽取句子作為摘要。William[12]使用表示學(xué)習(xí)的方法把這個問題作為一個句子推薦任務(wù)。在純文本語料庫的基礎(chǔ)上，利用了來自網(wǎng)絡(luò)上排名最高的相關(guān)圖像，使用卷積神經(jīng)網(wǎng)絡(luò)對圖像進(jìn)行建模,并提出了一種可擴(kuò)展的低秩近似方法來學(xué)習(xí)新聞故事和圖像的聯(lián)合嵌入。Meena[13]使用與自然演化過程類似的遺傳算法來優(yōu)化線性搜索問題。

在中文方面，與Tran[7]類似，宋俊等[14]提出面向?qū)嶓w的演化式多文檔摘要生成方法，利用一個概率主題模型聯(lián)合建模文檔主題的演化和實(shí)體的參與情況,然后結(jié)合實(shí)體對句子進(jìn)行評分和選擇。徐偉等[15]利用詞項強(qiáng)度和熵來確定代表性詞項，然后基于內(nèi)容覆蓋性、時間分布性和傳播影響力等三種指標(biāo)構(gòu)建出評價時間線摘要的綜合評價指標(biāo)，最后采用滑動窗口的方法，遍歷時間軸上的微博消息序列，生成微博時間線摘要。

2 基于主題關(guān)系的演化式摘要方法

一個新聞事件通常包含了多個子主題[16]，每個子主題表現(xiàn)了這個新聞事件的某一個點(diǎn)。這些子主題往往是相互關(guān)聯(lián)的，但是在一定程度上也是相互獨(dú)立的，并不是所有子主題都和某個特定的子主題緊密關(guān)聯(lián)。為了更好地刻畫事件演化過程，我們分別從兩種角度對事件主題進(jìn)行建模： 一種是局部的，基于子主題內(nèi)部時間演化；另一種是全局的，基于子主題間主題演化。

如圖1所示，我們將新聞標(biāo)題集合C劃分為k個子主題集{T1,T2,T3,…,Tk}。對于各個子主題ti，分別計算其對應(yīng)的子主題內(nèi)得分[Local(i)]與子主題間得分[Global(i)]，并生成子主題摘要。

圖1 系統(tǒng)框架圖

2.1 子主題內(nèi)得分

在計算子主題內(nèi)得分時，我們認(rèn)為各個子主題是相互獨(dú)立的。對于任意子主題ti，對應(yīng)的標(biāo)題集Ti中標(biāo)題的主題基本相似，標(biāo)題之間主題演化不明顯，因此在計算子主題內(nèi)得分時不考慮標(biāo)題間的主題演化，而僅僅考慮其時間演化。

2.1.1 標(biāo)題間時間距離

一般來說，如果兩個標(biāo)題之間的時間間隔越長，兩個標(biāo)題之間的聯(lián)系就越弱，因此標(biāo)題間的時間差異可以通過標(biāo)題間時間距離來衡量。Rui Yan[10]利用高斯核函數(shù)將不同時間集中的句子映射到當(dāng)前時間集來計算句子間的轉(zhuǎn)移概率。與其類似但又有所不同，我們沒有將不同時段的標(biāo)題映射到同一時間段上，而是通過圓核函數(shù)來計算兩個標(biāo)題之間的時間距離。圓核公式如式(1)所示。

(1)

其中ts表示時間戳，σ為最大時間間隔。一般來說，σ的最優(yōu)設(shè)置可以根據(jù)新聞集而變化，因?yàn)榫渥涌赡茉谀承┬侣勚黝}中具有更廣泛的語義范圍，因此需要更高的σ值，反之亦然。

2.1.2 子主題內(nèi)標(biāo)題排序模型

通過對子主題ti對應(yīng)的標(biāo)題集Ti構(gòu)建有向圖，可以使用普通的隨機(jī)游走模型來計算子主題內(nèi)各標(biāo)題得分。設(shè)Ti={h1,h2,…,hn}，構(gòu)建一個有向圖G=(V，E)，V中的結(jié)點(diǎn)由Ti中的標(biāo)題構(gòu)成，結(jié)點(diǎn)vi到vj的邊eij的權(quán)重由vi到vj的轉(zhuǎn)移概率pij決定，如式(2)所示。

(2)

其中，fij表示標(biāo)題hi和hj對應(yīng)的TF-ISF特征向量的余弦距離。

標(biāo)題hj得分通過模型中隨機(jī)游走的訪問概率來估計，該概率使用下列等式迭代計算，如式(3)所示。

(3)

其中轉(zhuǎn)移概率pij在計算時已經(jīng)歸一化以滿足馬爾科夫?qū)傩?，阻尼因子d=0.85。當(dāng)相鄰兩次迭代后，各個標(biāo)題的得分差異小于0.000 1時，迭代停止。

2.2 子主題間得分

在計算子主題間得分時，我們認(rèn)為各個子主題是相互關(guān)聯(lián)的。因此，不僅要考慮各個標(biāo)題之間的時間距離，還需要考慮各子主題間的主題差異。

2.2.1 子主題距離

(4)

(5)

2.2.1 子主題間標(biāo)題排序模型

在為子主題ti對應(yīng)的標(biāo)題集進(jìn)行排序時，我們將其余子主題根據(jù)其與子主題ti的距離映射到當(dāng)前子主題中，并利用之前計算的子主題ti內(nèi)部排序結(jié)果為子主題ti內(nèi)的標(biāo)題設(shè)置偏好。如圖1所示，在計算Global(i)時，實(shí)線圓代表當(dāng)前計算的子主題ti，虛線圓代表映射到子主題ti的其他子主題。為滿足需求，我們對傳統(tǒng)的PageRank算法進(jìn)行了改變。

傳統(tǒng)的PageRank算法表示如式(6)、式(7)所示。

其中Rank為PageRank值，M為N×N的轉(zhuǎn)移概率矩陣。Taher H[17]通過使用非均勻個性化向量p來增加某些類別的頁面的影響，從而創(chuàng)建主題敏感的PageRank。他認(rèn)為偏置p涉及在計算的每次迭代中向適當(dāng)?shù)墓?jié)點(diǎn)引入額外的等級，而不僅僅是在標(biāo)準(zhǔn)PageRank向量上執(zhí)行的后處理步驟。與其類似，我們利用計算子主題內(nèi)得分時得到的標(biāo)題得分來修改p，將子主題ti內(nèi)的局部特征融入到子主題間標(biāo)題排序的全局建模中。

對于子主題ti，我們使用不均勻的p=vji，如式(8)所示。

(8)

其中β為阻尼系數(shù)，設(shè)置為0.8，S(hi)為標(biāo)題hi在主題內(nèi)的得分，N為所有新聞標(biāo)題的數(shù)目。

對于標(biāo)題集C的所有標(biāo)題，我們構(gòu)建轉(zhuǎn)移概率矩陣M，pij表示標(biāo)題i到標(biāo)題j的轉(zhuǎn)移概率,如式(9)所示。

(9)

有了轉(zhuǎn)移矩陣M和偏置p，就可以利用傳統(tǒng)PageRank算法的求解過程進(jìn)行求解。

2.3 摘要生成

根據(jù)各子主題對應(yīng)的子主題間排序結(jié)果，分別從各個子主題中抽取一定數(shù)目的標(biāo)題，并按照時間順序輸出作為摘要。各個子主題抽取的標(biāo)題數(shù)目η由該子主題包含的標(biāo)題數(shù)目|Ti|以及總的標(biāo)題數(shù)目|C|來決定，具體計算如式(10)所示，最終生成摘要包含標(biāo)題數(shù)目n如式(11)所示。

其中k為子主題數(shù)目，偏置b用于對最終生成摘要數(shù)目進(jìn)行調(diào)整。當(dāng)給定最終生成摘要包含標(biāo)題數(shù)目n時，可以通過調(diào)整b的值進(jìn)行控制。

一般的，子主題包含的標(biāo)題數(shù)目越多，該子主題越重要，因此抽取的標(biāo)題越多。當(dāng)η小于1時，可以認(rèn)為該子主題重要性較弱，不對其生成摘要。在冗余控制方面，利用最大邊緣相關(guān)(MMR)[18]算法來去除冗余的句子。

3 實(shí)驗(yàn)與評價

3.1 數(shù)據(jù)集

我們利用Giang Tran[19]論文中的數(shù)據(jù)集[注]Available at http: //www.l3s.de/*gtran/timeline/，其中包含了埃及革命、敘利亞戰(zhàn)爭、也門危機(jī)和利比亞戰(zhàn)爭的四個長期事件。

數(shù)據(jù)集中的文章主要來源于Google搜索，針對用于創(chuàng)建參考摘要的新聞機(jī)構(gòu)，構(gòu)建了例如“埃及(革命或危機(jī)或起義或內(nèi)戰(zhàn))”等問題，利用Google進(jìn)行查詢，并收集前300個答案。數(shù)據(jù)集中的參考摘要來源于包含BBC、CNN和Reuters等在內(nèi)的多家知名通訊社出版的，由專業(yè)記者手動創(chuàng)建的對應(yīng)事件的時間表。具體信息見表2。

表2 參考摘要概述

注： 參考摘要數(shù)量 (#TL)，所有參考摘要時間點(diǎn)個數(shù) #Timepoint，真實(shí)狀況時間點(diǎn)個數(shù)(#GT-Date)，時間范圍(#TL-Range)，每個參考摘要上每個日期的平均句子(#a.sent)，新聞文章數(shù)量 (#News)

3.2 評價方法

ROUGE[20]是Chin-Yew Lin在2004年提出的一種自動摘要評價方法，被廣泛應(yīng)用于NIST組織的自動摘要評測任務(wù)中。ROUGE基于摘要中n元詞(n-gram)的共現(xiàn)信息來評價摘要，是一種面向n元詞召回率的評價方法?；舅枷霝橛啥鄠€專家分別生成人工摘要，構(gòu)成標(biāo)準(zhǔn)摘要集，將系統(tǒng)生成的自動摘要與人工生成的標(biāo)準(zhǔn)摘要相對比，通過統(tǒng)計二者之間重疊的基本單元(n元語法、詞序列和詞對)的數(shù)目，來評價摘要的質(zhì)量。通過與標(biāo)準(zhǔn)人工摘要的對比，提高評價系統(tǒng)的穩(wěn)定性和健壯性。該方法現(xiàn)已成為自動評價技術(shù)的通用標(biāo)準(zhǔn)之一。本文采用ROUGE中ROUGE-1，ROUGE-2，ROUGE-L和ROUGE-SU4的F值來對生成的摘要進(jìn)行評價。

3.3 對照實(shí)驗(yàn)

LexPageRank[21]: 是基于圖排序的自動摘要算法，使用句子作為圖結(jié)點(diǎn)，如果兩個句子余弦相似度大于閾值則在這兩個句子之間添加無向邊，利用PageRank算法求解。其主要思想是： 若一個句子與眾多其他句子相似，那么此句話就可能是重要的。

Chieu: 提出了“interest”和“burstiness”兩種測量標(biāo)準(zhǔn)，認(rèn)為在事件發(fā)生之后的一段時間內(nèi)經(jīng)常會在許多新聞文章中重復(fù)出現(xiàn)，并且有不同的更新和評論的事件是重要的。

ETTS: 是迄今為止在新聞領(lǐng)域最好的無監(jiān)督TS系統(tǒng)之一。它利用句子中的單詞分布與整個語料庫中的單詞分布以及相鄰日期之間的相似性構(gòu)造本地和全局摘要并進(jìn)行優(yōu)化組合。

3.4 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用Java編程，運(yùn)行服務(wù)器配置為3.40GHz Inter(R) Core(TM) i7-6700 CPU和16GB內(nèi)存，使用Windows系統(tǒng)和JKD1.8.0_101環(huán)境。

我們將四個事件中的“也門危機(jī)”作為開發(fā)集，來對系統(tǒng)的各項參數(shù)進(jìn)行調(diào)整。各個對比實(shí)驗(yàn)中的超參數(shù)均按照其對應(yīng)論文中推薦的值進(jìn)行設(shè)置，并根據(jù)本文數(shù)據(jù)集的大小及時間跨度等特點(diǎn)做了輕微的調(diào)整。在其他三個事件中進(jìn)行交叉驗(yàn)證，將系統(tǒng)生成的自動摘要與人工生成的標(biāo)準(zhǔn)摘要利用ROUGE評價包(1.55版本)分別計算每次實(shí)驗(yàn)結(jié)果的ROUGE-1，ROUGE-2，ROUGE-L和ROUGE-SU4的F值，最后取平均值。

具體實(shí)驗(yàn)步驟如本文第二節(jié)。以下詳細(xì)介紹文本預(yù)處理、子主題劃分方法與參數(shù)設(shè)置。

3.4.1 文本預(yù)處理

我們對數(shù)據(jù)集中的特殊字符(例如@、#等)和長度小于4的標(biāo)題進(jìn)行過濾，并對單詞進(jìn)行詞干提取以減少詞表大小。最后，通過類似TF-IDF的TF-ISF(S為Sentences)技術(shù)將新聞標(biāo)題轉(zhuǎn)化為特征向量。

3.4.2 子主題劃分

本文利用K-means聚類方法對新聞標(biāo)題集合C進(jìn)行子主題劃分，子主題數(shù)目k值根據(jù)輪廓系數(shù)法[22]得到。通過枚舉，令k從2到10取值，在每個k值上重復(fù)運(yùn)行數(shù)次k_means，并計算當(dāng)前k的平均輪廓系數(shù)，最后選取輪廓系數(shù)最大的值對應(yīng)的k作為最終的集群數(shù)目。

3.4.3 參數(shù)設(shè)置

偏置b主要用于對生成摘要包含標(biāo)題數(shù)目進(jìn)行調(diào)整。為適應(yīng)本文所用數(shù)據(jù)集，我們控制生成摘要包含標(biāo)題數(shù)目在50個左右。因此，實(shí)驗(yàn)中b值統(tǒng)一設(shè)置為事件包含的總標(biāo)題數(shù)目|C|的二分之一。

最大時間間隔σ主要用于對超出一定時間間隔的數(shù)據(jù)進(jìn)行截斷，減少干擾。為適應(yīng)本文所用數(shù)據(jù)集，通過在“也門危機(jī)”事件數(shù)據(jù)集上對不同σ值進(jìn)行實(shí)驗(yàn)，本文實(shí)驗(yàn)中σ值統(tǒng)一設(shè)置為一個月。

3.5 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果如表3所示(其中LGT為本文方法)。結(jié)果顯示，本文提出的方法在三個事件中的各項測量指標(biāo)均高于對比實(shí)驗(yàn)方法，說明本文提出的方法是有效的。和預(yù)想的相同，由于LexPageRank并沒有考慮時間因素，所以其在三個事件中表現(xiàn)都為最差，而Chieu考慮了事件的演化性，所以效果優(yōu)于LexPageRank。出乎意料的是： ETTS三個事件中的各項測量指標(biāo)普遍高于Chieu，但是在敘利亞戰(zhàn)爭中ROUGE-2低于Chieu。通過比較兩者生成的摘要，發(fā)現(xiàn)Chieu傾向于選擇含有相似短語的標(biāo)題作為摘要。當(dāng)該短語是標(biāo)準(zhǔn)事件表中的重要短語時，Chieu獲得了更高的ROUGE-2值。我們猜測這是由于Chieu算法本身造成的。它為句子集中具有高相似度的句子賦予高權(quán)重，而其自帶的去冗余方法主要針對去除日期相近的句子。

表3 實(shí)驗(yàn)結(jié)果

針對利比亞戰(zhàn)爭，表4和表5分別列出了CNN人工編輯的部分摘要和本文方法抽取的部分摘要。結(jié)果顯示，對于延續(xù)時間較長且在主題演化主線上的子主題，例如，“對利比亞實(shí)行禁飛區(qū)”和“北約對利比亞發(fā)動軍事行動”等子主題，本文方法可以較好地識別并抽取出相關(guān)內(nèi)容，說明本文的方法是有效的。但是，對于持續(xù)時間較短、偏離主題演化主線的事件，例如，“伊曼·奧貝迪(Eman al-Obeidy)事件”等，本文方法還是無法很好地識別出來。

表5顯示，在冗余度控制方面，無論是在時間粒度上或是子主題粒度上，本文方法生成的摘要冗余度都很低。但是，本文方法生成的摘要會包含一些評論性語句，例如，“What can be done to end the crisis in Libya?”等，這些語句通常并沒有涉及具體的事件，不適合作為時間標(biāo)簽摘要。我們猜想，抽取到這些句子的原因可能是這些評論性句子中通常包含多個該事件下的主題詞，例如，“l(fā)ibya”“crisis”等，導(dǎo)致這些句子獲得了高得分。

表4 CNN針對利比亞戰(zhàn)爭人工編輯的時間標(biāo)簽摘要(節(jié)選，2011年3月)

表5 LGT生成關(guān)于Egyptian Crisis的部分帶時間標(biāo)簽摘要(節(jié)選，2011年3月)

續(xù)表

4 結(jié)束語

演化式摘要作為多文檔自動文摘的一種，它在傳統(tǒng)多文檔摘要的基礎(chǔ)上需要額外考慮事件隨時間變化的演化特性。為此，本文提出了一種基于主題和時間變化的演化式摘要方法，其分別考慮了子主題內(nèi)部和子主題間的主題和時間關(guān)系，并通過變種的PageRank算法將兩者聯(lián)系起來。實(shí)驗(yàn)結(jié)果表明，該方法與現(xiàn)有方法相比在ROUGE值上有較大提升。未來，我們將通過句法結(jié)構(gòu)分析、單詞詞性等文本特征來判斷句子是否屬于評論性句子，避免這些不涉及具體事件的句子在摘要中出現(xiàn)。另外，我們還將嘗試不同的文本表示方法，例如，LDA、Word Embedding等，并考慮將時間和主題等特征加入文本表示的向量中。