基于遺傳算法的非監督摘要提取*

王 濤，范曉波，胥小波

（1.四川省科學技術信息研究所，四川 成都 610000；2.中國電子科技網絡信息安全有限公司，四川 成都 610000）

0 引言

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

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

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

不同于當前文獻的一般方法，本文提出一種基于遺傳算法（Genetic Algorithm，GA）的非監督摘要抽取方法。遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，發現在求解摘要提取問題中有獨特的優勢。該方法將每條候選摘要編碼成0-1 序列。除了能搜索到效益函數的最優解之外，傳統的遺傳算法在變異過程中隨機選擇某個基因進行突變?？紤]到句子位置影響句子的重要性，如出現在段首、段中和段末的句子重要性不同，在遺傳算法變異選擇過程中，將以更高的概率選擇上述特定位置的句子。

1 無監督摘要抽取模型

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

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

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

當前文獻中已經給出了幾種效益函數定義形式。

1.1 成對（Pairwise）效益函數

第一個子集評分函數是由Lin 和Bilme[11]提出的。基于成對句子相似度模型，成對效益函數使用等式（2）對摘要T進行評分：

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

1.2 覆蓋效益函數

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

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

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

2 基于改進遺傳算法的摘要抽取

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。將每個可行解編碼成染色體，染色體被表示為一組定義個體的參數（特征）。為了選擇最佳的個體，使用了一個適應度函數。適應度函數的結果是表示解的質量的適應度值。適應度值越高，解決方案的質量越高。根據質量選擇最佳個體，以產生所謂的交配池，其中質量較高的個體在交配池中被選擇的概率較高。

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

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

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

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

（4）變異。對于任意一個個體，采用隨機0/1突變的方式模擬個體變異。

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

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

1.輸入原始文檔；

2.采用編碼方案進行編碼并初始化種群；

3.采用適應度函數fs(T)+βgs(T)評估種群中個體適應度；

4.采用精英保留策略的選擇方式進行個體選擇；

5.對于選擇的個體采用交叉、變異方案進行交叉、變異操作；

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

7.輸出最后一次迭代的最佳個體，而個體中狀態為1 對應的句子集合即文檔的摘要。

3 實驗結果與分析

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

（1）去除實驗噪聲，即去除對提取摘要無明顯影響的圖片、表格、特殊符號等計算機語言不易識別的形式；

（2）文檔分割，將文檔分割為句子形成句子集合，再對這些句子進行分詞、去除停用詞，得到由詞項構成的句子集合；

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

實驗首先分析了遺傳算法的收斂速度。算法的收斂速度會影響其在實際使用中的摘要抽取速度。圖1 顯示了遺傳算法在測試集中目標函數隨迭代次數的變化趨勢。由圖1 可見，一般在迭代20 次后，算法就可達到收斂狀態。

圖1 目標函數隨迭代次數變化趨勢

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

表1 改進前和改進后的遺傳算法摘要抽取示例

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

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

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

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

1.輸入原始文檔和摘要句子長度k；

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

3.計算當前摘要的fs(T)；

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

5.重復步驟3 和步驟4 共k次；

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

實驗結果如表2 所示，展示了不同的摘要抽取算法在測試集上對應指標的平均值?？梢姡倪M后的遺傳算法的召回率、準確率和f度量均優于貪婪算法。原因在于貪婪算法只是近似求解算法，不能保證能求到極值，而采用精英保留策略的遺傳算法在理論上已經證明能收斂到目標函數的最大值。同時，對比一般的遺傳算法和改進的遺傳算法，改進遺傳算法充分考慮了中文摘要中的重點句，因而具備較高的抽取精度。

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

4 結語

本文提出了一種新的基于遺傳算法的非監督摘要提取算法，將每條候選摘要中的句子編碼成0-1 序列?？紤]到句子位置影響句子重要性，如段首、段中和段末的句子在表達意思上重要性不同，算法在目標函數中加上正則項，使得遺傳算法在變異選擇過程中將以更高的概率選擇上述特定位置的句子。實驗結果表明，相對于貪婪式非監督摘要提取算法，本文提出的方法具有較好的摘要提取性能。