基于遺傳算法的非監(jiān)督摘要提取*

王 濤，范曉波，胥小波

（1.四川省科學(xué)技術(shù)信息研究所，四川 成都 610000；2.中國(guó)電子科技網(wǎng)絡(luò)信息安全有限公司，四川 成都 610000）

0 引言

自動(dòng)生成文本摘要是自然語(yǔ)言處理（Natural Language Processing）領(lǐng)域中一項(xiàng)比較復(fù)雜但意義重大的工作。所謂生成文本摘要就是指利用計(jì)算機(jī)自動(dòng)地從原始文獻(xiàn)中提取重要句子組成文章摘要的過(guò)程。隨著Web 2.0 的迅猛發(fā)展，各種用戶原創(chuàng)內(nèi)容爆炸式增長(zhǎng)，使得有價(jià)值信息的獲取愈發(fā)困難。自動(dòng)生成文本摘要從海量文本中抽取出最重要的語(yǔ)句，可以有效幫助用戶花很少的代價(jià)獲取文檔的主要信息。

大體而言，自動(dòng)摘要可分為基于抽取的自動(dòng)摘要和基于抽象的自動(dòng)摘要?；诔槿〉淖詣?dòng)摘要是指選擇輸入文檔的相關(guān)句子并將它們連接起來(lái)形成摘要。而基于抽象的方法是指采用新的句子來(lái)生成保持原文意思的摘要?；诔橄蟮淖詣?dòng)摘要受制于自然語(yǔ)言處理技術(shù)的瓶頸，實(shí)現(xiàn)相對(duì)困難，因此目前主要的研究和應(yīng)用集中在基于抽取的自動(dòng)摘要[1]。根據(jù)摘要提取的技術(shù)途徑不同，抽取的自動(dòng)摘要可分為基于特征的方法[2-3]、基于圖的方法[4-5]和基于神經(jīng)網(wǎng)絡(luò)的方法[6-9]?；谔卣鞯姆椒丛u(píng)估每個(gè)句子的特征，然后評(píng)價(jià)它的重要性，并輸出重要性靠前的句子；基于圖的方法（如TextRank[5]）從文檔中構(gòu)建圖形，其中圖的節(jié)點(diǎn)為文檔中的句子，而邊為句子之間的相似度，然后通過(guò)考慮節(jié)點(diǎn)之間的關(guān)系選取圖中重要的節(jié)點(diǎn)（句子）。受益于深度學(xué)習(xí)在自然語(yǔ)言處理領(lǐng)域的廣泛運(yùn)用，近年來(lái)提出一些基于深度學(xué)習(xí)的摘要提取方法，如seq2seq網(wǎng)絡(luò)[8]、pointer-generator 網(wǎng)絡(luò)[9]等。然而，基于深度學(xué)習(xí)的方法需要大量有監(jiān)督的訓(xùn)練數(shù)據(jù)，在實(shí)際運(yùn)用中依賴人工構(gòu)建的訓(xùn)練樣本。

子集選擇算法是無(wú)監(jiān)督自動(dòng)文檔摘要的有效方法，首先將摘要抽取建模成子集選擇問(wèn)題，即將原文看成一個(gè)由句子構(gòu)成的集合，而摘要為從集合中精心挑選的子集。特別地，選擇的摘要子集應(yīng)使得某個(gè)效益函數(shù)最大化。然而，子集選擇是非確定性多項(xiàng)式（Nondeterministic Polynomial，NP）完全的[10]。當(dāng)前文獻(xiàn)普遍采用貪婪式算法求解。

不同于當(dāng)前文獻(xiàn)的一般方法，本文提出一種基于遺傳算法（Genetic Algorithm，GA）的非監(jiān)督摘要抽取方法。遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，發(fā)現(xiàn)在求解摘要提取問(wèn)題中有獨(dú)特的優(yōu)勢(shì)。該方法將每條候選摘要編碼成0-1 序列。除了能搜索到效益函數(shù)的最優(yōu)解之外，傳統(tǒng)的遺傳算法在變異過(guò)程中隨機(jī)選擇某個(gè)基因進(jìn)行突變。考慮到句子位置影響句子的重要性，如出現(xiàn)在段首、段中和段末的句子重要性不同，在遺傳算法變異選擇過(guò)程中，將以更高的概率選擇上述特定位置的句子。

1 無(wú)監(jiān)督摘要抽取模型

本節(jié)將說(shuō)明如何使用子集選擇模型來(lái)定義自動(dòng)文檔摘要。為了便于描述，本文將一篇特定文檔定義為句子的有序集合。不失一般性，假設(shè)原文共有n條句子，記si表示第i條句子，摘要提取可以視為從集合S={s1,…,sn}中提取子集T?S來(lái)作為原文的摘要。給定某個(gè)效益函數(shù)，子集T的選取應(yīng)該使得效益函數(shù)最大化。令fs表示定義在集合S上的效益函數(shù)，則摘要抽取模型可表示為求解如下優(yōu)化表達(dá)式：

式中，優(yōu)化條件|T|≤k表示最多從原文中抽取k條句子作為摘要。

怎么選取效益函數(shù)呢？一種直觀的理解是給定|T|≤k約束下，子集中蘊(yùn)含的“信息”應(yīng)越多越好。通常來(lái)說(shuō)，一段話包含的信息量要多于其段落中某些句子組成的子集的信息量。令T1、T2均為T的子集且T1?T2，則應(yīng)有fs(T1)＜fs(T2)，即集合的效益函數(shù)值應(yīng)大于其子集的效益函數(shù)值。

當(dāng)前文獻(xiàn)中已經(jīng)給出了幾種效益函數(shù)定義形式。

1.1 成對(duì)（Pairwise）效益函數(shù)

第一個(gè)子集評(píng)分函數(shù)是由Lin 和Bilme[11]提出的?；诔蓪?duì)句子相似度模型，成對(duì)效益函數(shù)使用等式（2）對(duì)摘要T進(jìn)行評(píng)分：

式中，σ(i,j)≥0 表示句子i和j之間的相似性度量（如句子TFIDF 的余弦相似性）。式（2）中，等式右邊的第一項(xiàng)是衡量摘要T中的句子與S中的其他句子的相似程度；第二項(xiàng)為T內(nèi)部的各個(gè)句子之間的相似程度。λ≥0 是一個(gè)標(biāo)量參數(shù)，用來(lái)權(quán)衡第一項(xiàng)和第二項(xiàng)。最大化上述效益函數(shù)可以使得T中的句子與S中的其他句子相似度較高，而其內(nèi)部相似度較低，即增加所選摘要與其他句子的相似性，同時(shí)最小化摘要中蘊(yùn)含的重復(fù)信息，從而實(shí)現(xiàn)有效的信息抽取。

1.2 覆蓋效益函數(shù)

覆蓋效益函數(shù)基于詞覆蓋[12]的概念。該概念首先被提出用于多文檔檢索，隨后被引入用來(lái)衡量自動(dòng)文檔摘要的質(zhì)量。在詞覆蓋的定義中，文檔中的每個(gè)詞v都具備一個(gè)權(quán)重ω(v)用來(lái)表示該詞在文檔中的重要程度。給定一個(gè)摘要T，如果T中某條句子含有詞v，則稱摘要T覆蓋詞v，而摘要的得分就是其覆蓋的所有詞的權(quán)重之和：

式中，U(T)表示T中所有詞的并集。最大化該效益函數(shù)屬于著名的最大覆蓋問(wèn)題，即選擇摘要使得其能最大化覆蓋原文檔中所有重要的詞。在簡(jiǎn)單情況下，類似成對(duì)效益函數(shù)，式（3）中的權(quán)重函數(shù)ω(v)可以為詞語(yǔ)的TFIDF 值。

值得注意的是，不管是哪一種效益函數(shù)，其本質(zhì)都是以盡可能少的文本涵蓋文檔信息，區(qū)別僅是信息的描述角度不同。本文提出的遺傳算法抽取文本摘要方法可適用于以上任何一種效益函數(shù)。

2 基于改進(jìn)遺傳算法的摘要抽取

遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。將每個(gè)可行解編碼成染色體，染色體被表示為一組定義個(gè)體的參數(shù)（特征）。為了選擇最佳的個(gè)體，使用了一個(gè)適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的結(jié)果是表示解的質(zhì)量的適應(yīng)度值。適應(yīng)度值越高，解決方案的質(zhì)量越高。根據(jù)質(zhì)量選擇最佳個(gè)體，以產(chǎn)生所謂的交配池，其中質(zhì)量較高的個(gè)體在交配池中被選擇的概率較高。

遺傳算法的一般流程是模擬自然進(jìn)化過(guò)程進(jìn)行循環(huán)迭代，直至收斂或滿足最大迭代次數(shù)。每一次循環(huán)包括：評(píng)估每條染色體所對(duì)應(yīng)個(gè)體的適應(yīng)度；遵照“適應(yīng)度越高，選擇概率越大”的原則，從種群中選擇兩個(gè)個(gè)體作為父方和母方（精英保留策略）；抽取父母雙方的染色體進(jìn)行交叉，產(chǎn)生子代；對(duì)子代的染色體進(jìn)行變異。為了將遺傳算法應(yīng)用于文本摘要，本文從如下幾個(gè)方面進(jìn)行闡述。

（1）候選解編碼。在基于遺傳算法進(jìn)行摘要抽取時(shí)，由于其本質(zhì)是從集合S={s1,…,sn}中提取子集T?S作為原文的摘要，因此將每一個(gè)可行解編碼成n維的0/1 向量，其中1 代表選中對(duì)應(yīng)位置的句子作為摘要，而0 表示未選中。

（2）適應(yīng)度函數(shù)。適應(yīng)度函數(shù)表達(dá)一個(gè)候選解的好壞，其中好的解應(yīng)該以較大的概率在下一次迭代中保存。特別地，最好的精英解應(yīng)保證能進(jìn)入下一代；相反，較差的解會(huì)以較大的概率淘汰。由于摘要提取的目的是使fs(T)最大化，因此可以簡(jiǎn)單地將目標(biāo)函數(shù)fs(T)設(shè)為適應(yīng)度函數(shù)。

（3）交叉算子。交叉算子根據(jù)交叉率將種群中的兩個(gè)個(gè)體（即父方和母方）隨機(jī)地交換某些基因并產(chǎn)生新的基因組合，期望將有益基因組合在一起。由于將個(gè)體編碼成n維的0/1 向量，通常分別從父方的位字符串和母方對(duì)應(yīng)的位字符串進(jìn)行隨機(jī)交換。在摘要提取中，摘要長(zhǎng)度遠(yuǎn)小于原文，即在個(gè)體編碼中1 的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于0 的個(gè)數(shù)。為了加快算法的收斂速度，本文只在父母雙方基因的“差異處”進(jìn)行隨機(jī)交換。這里的差異處指的是父母在該位置的編碼不一樣，對(duì)于父母雙方a、b，其差異處為集合{i,ai,xor bi=1}，其中xor表示異或操作。

（4）變異。對(duì)于任意一個(gè)個(gè)體，采用隨機(jī)0/1突變的方式模擬個(gè)體變異。

以上是采用一般流程的遺傳算法進(jìn)行非監(jiān)督摘要提取。然而，在算法迭代產(chǎn)生新種群的過(guò)程中，候選個(gè)體從父母雙方隨機(jī)選擇基因，且變異位置隨機(jī)，忽略了中文寫作習(xí)慣的影響，如起始句、點(diǎn)題句等句子的重要性比其他句子高，本文稱之為重點(diǎn)句子。研究表明，在人工摘要中，選取段首句作為摘要的比例高達(dá)85%，而選取段尾句作為摘要的比例接近7%[13]。針對(duì)該問(wèn)題，本文對(duì)上述通用的遺傳算法進(jìn)行改進(jìn)，以更適用于非監(jiān)督摘要提取。充分考慮句子位置、點(diǎn)題句等情況對(duì)節(jié)點(diǎn)權(quán)重的影響，將適應(yīng)度函數(shù)修改為fs(T)+βgs(T)。其中，gs(T)衡量段首句和段尾句的重要性，一種最簡(jiǎn)單的方式是令段首和段尾為1，其他為0；β用來(lái)控制gs(T)在適應(yīng)度函數(shù)中的權(quán)重。同時(shí)，為了加快遺傳算法的收斂速度，在交叉操作中以更高的概率選擇父母雙方中處于重點(diǎn)句位置的句子。

綜上所述，本文提出的基于改進(jìn)遺傳算法的摘要抽取算法流程如下：

1.輸入原始文檔；

2.采用編碼方案進(jìn)行編碼并初始化種群；

3.采用適應(yīng)度函數(shù)fs(T)+βgs(T)評(píng)估種群中個(gè)體適應(yīng)度；

4.采用精英保留策略的選擇方式進(jìn)行個(gè)體選擇；

5.對(duì)于選擇的個(gè)體采用交叉、變異方案進(jìn)行交叉、變異操作；

6.重復(fù)步驟3～步驟5，直到滿足最大迭代次數(shù)；

7.輸出最后一次迭代的最佳個(gè)體，而個(gè)體中狀態(tài)為1 對(duì)應(yīng)的句子集合即文檔的摘要。

3 實(shí)驗(yàn)結(jié)果與分析

采用公開(kāi)的中文短文本摘要數(shù)據(jù)集（https://www.jianshu.com/p/f98deb85e0ff）驗(yàn)證自動(dòng)摘要算法的性能。該數(shù)據(jù)集來(lái)源于新浪微博主流媒體發(fā)布的微博，共679 898 條數(shù)據(jù)，每條數(shù)據(jù)均包含源博文和參考摘要。為了采用算法進(jìn)行摘要提取，首先進(jìn)行數(shù)據(jù)預(yù)處理。具體步驟為：

（1）去除實(shí)驗(yàn)噪聲，即去除對(duì)提取摘要無(wú)明顯影響的圖片、表格、特殊符號(hào)等計(jì)算機(jī)語(yǔ)言不易識(shí)別的形式；

（2）文檔分割，將文檔分割為句子形成句子集合，再對(duì)這些句子進(jìn)行分詞、去除停用詞，得到由詞項(xiàng)構(gòu)成的句子集合；

（3）向量化，本文的摘要提取框架可適用于不同的效益函數(shù)fs，不失一般性，考慮式（2）所示的成對(duì)效益函數(shù)。

實(shí)驗(yàn)首先分析了遺傳算法的收斂速度。算法的收斂速度會(huì)影響其在實(shí)際使用中的摘要抽取速度。圖1 顯示了遺傳算法在測(cè)試集中目標(biāo)函數(shù)隨迭代次數(shù)的變化趨勢(shì)。由圖1 可見(jiàn)，一般在迭代20 次后，算法就可達(dá)到收斂狀態(tài)。

圖1 目標(biāo)函數(shù)隨迭代次數(shù)變化趨勢(shì)

如前所述，本文在一般的遺傳算法的基礎(chǔ)上對(duì)中文語(yǔ)言的特點(diǎn)進(jìn)行一些改進(jìn)。由于起始句、點(diǎn)題句等句子的重要性比其他句子高，在種群迭代過(guò)程中需充分考慮段首句和段尾句對(duì)節(jié)點(diǎn)權(quán)重的影響。表1 展示了改進(jìn)前和改進(jìn)后的遺傳算法摘要抽取的一個(gè)示例，顯然該示例中改進(jìn)后抽取的摘要更接近參考摘要。

表1 改進(jìn)前和改進(jìn)后的遺傳算法摘要抽取示例

最后，對(duì)本文算法和其他摘要抽取算法進(jìn)行實(shí)驗(yàn)對(duì)比。摘要質(zhì)量的評(píng)價(jià)方法采用自動(dòng)摘要領(lǐng)域廣泛使用的Rouge（Recall-Oriented Understudy for Gisting Evaluation）指標(biāo)[14]。Rouge 指標(biāo)是一種基于召回率（Recall）和n元詞（n-gram）的自動(dòng)化評(píng)價(jià)方法。它的基本思想是將系統(tǒng)生成的自動(dòng)摘要與標(biāo)準(zhǔn)摘要對(duì)比，通過(guò)統(tǒng)計(jì)二者之間重疊的基本單元（n元語(yǔ)法、詞序列和詞對(duì)）的數(shù)目來(lái)評(píng)價(jià)摘要的質(zhì)量。Rouge-n指標(biāo)（n=1、2、3、4，分別代表基于1 元詞到4 元詞的模型）又分為召回率、準(zhǔn)確率和f度量，分別定義如下：

式中，Countmatch(n-gram)表示算法生成摘要和參考摘要中同時(shí)出現(xiàn)n-gram的個(gè)數(shù)；Count(n-gram)則表示參考摘要中出現(xiàn)的n-gram個(gè)數(shù)。為了簡(jiǎn)單起見(jiàn)，本文采用Rouge-1 指標(biāo)，即Rouge 中的1 元詞模型。

將本文提出的算法和文獻(xiàn)[15]中摘要抽取方法進(jìn)行比較。文獻(xiàn)[15]采用貪婪算法的方式求解效益函數(shù)的極值問(wèn)題。貪婪算法在每一次迭代中，選擇使得效益函數(shù)增長(zhǎng)最大的句子作為摘要。

貪婪式算法抽取摘要的主要流程如下：

1.輸入原始文檔和摘要句子長(zhǎng)度k；

2.設(shè)S為候選摘要并初始化為空集；

3.計(jì)算當(dāng)前摘要的fs(T)；

4.從原始文檔中選擇句子i使得fs∪i(T)-fs(T)最大化；

5.重復(fù)步驟3 和步驟4 共k次；

6.輸出選擇的句子作為原始文檔的摘要。

實(shí)驗(yàn)結(jié)果如表2 所示，展示了不同的摘要抽取算法在測(cè)試集上對(duì)應(yīng)指標(biāo)的平均值。可見(jiàn)，改進(jìn)后的遺傳算法的召回率、準(zhǔn)確率和f度量均優(yōu)于貪婪算法。原因在于貪婪算法只是近似求解算法，不能保證能求到極值，而采用精英保留策略的遺傳算法在理論上已經(jīng)證明能收斂到目標(biāo)函數(shù)的最大值。同時(shí)，對(duì)比一般的遺傳算法和改進(jìn)的遺傳算法，改進(jìn)遺傳算法充分考慮了中文摘要中的重點(diǎn)句，因而具備較高的抽取精度。

表2 不同的摘要抽取算法的性能

4 結(jié)語(yǔ)

本文提出了一種新的基于遺傳算法的非監(jiān)督摘要提取算法，將每條候選摘要中的句子編碼成0-1 序列。考慮到句子位置影響句子重要性，如段首、段中和段末的句子在表達(dá)意思上重要性不同，算法在目標(biāo)函數(shù)中加上正則項(xiàng)，使得遺傳算法在變異選擇過(guò)程中將以更高的概率選擇上述特定位置的句子。實(shí)驗(yàn)結(jié)果表明，相對(duì)于貪婪式非監(jiān)督摘要提取算法，本文提出的方法具有較好的摘要提取性能。