一種基于神經網絡模型的句子排序方法

康世澤，馬 宏，黃瑞陽

(國家數字交換系統工程技術研究中心,河南 鄭州 450002)

一種基于神經網絡模型的句子排序方法

康世澤，馬 宏，黃瑞陽

(國家數字交換系統工程技術研究中心,河南 鄭州 450002)

句子排序是多文本摘要中的重要問題，合理地對句子進行排序對于摘要的可讀性和連貫性具有重要意義。該文首先利用神經網絡模型融合了五種前人已經提出過的標準來決定任意兩個句子之間的連接強度，這五種標準分別是時間、概率、主題相似性、預設以及繼承。其次，該文提出了一種基于馬爾科夫隨機游走模型的句子排序方法，該方法利用所有句子之間的連接強度共同決定句子的最終排序。最終，該文同時使用人工和半自動方法對句子排序的質量進行評價，實驗結果表明該文所提出方法的句子排序質量與基準算法相比具有明顯提高。

句子排序;多文本摘要;神經網絡模型;馬爾科夫隨機游走模型

1 簡介

互聯網發展至今蘊含了巨大的信息量，當計算機用戶在網絡上查詢需要的信息時往往會面臨海量的檢索結果，怎樣從中篩選出需要的答案變成了一個難題。文本摘要技術應運而生成為了從海量信息中篩選所需信息的一種途徑。文本摘要系統可以從大量的文本信息中生成可以概括原文本主要信息的簡短摘要。從一組給定的文本集合中生成的摘要被稱為多文本摘要[1-3]，從單一的文本中生成的摘要被稱為單文本摘要。

多文本摘要系統的任務通常包括句子抽取、話題檢測、句子聚類、句子排序[4]等。句子的抽取和聚類決定了生成摘要所涵蓋的信息量，而Barzilay[5]的研究表明對句子的合理排序可以顯著提升摘要的可讀性和連貫性。

相對于單文本摘要，多文本摘要的句子排序問題更加具有挑戰性，因為對于多文本摘要來說，盡管一個文本集中的文本都在討論相同或相似的話題，但是從不同的文本中摘取到的句子通常由不同的作者完成于不同的時間，具有不同的寫作風格和背景知識。因此對于多文本摘要系統來說，合理地對句子進行排序對于摘要的可讀性和連貫性意義更大，同時也更加具有難度。當然句子排序技術也不僅僅應用在摘要生成之中。在自然語言生成中[6]，系統生成的句子也需要通過科學的排序，組織成具有連貫性的摘要。

本文第二部分將介紹本文的相關工作；第三部分將詳細介紹本文提出的句子排序方法；第四部分介紹句子排序的評價方法；第五部分是實驗部分；最后是對全文的總結。

2 相關工作

目前已有很多關于句子排序的相關工作。有些將句子排序與句子選擇相互分離，僅研究句子排序的方法，而另一些工作則將選擇和排序同時進行。

對于第一類工作，Peng[7]提出了一種結合支持向量機和灰色模型的句子排序方法，該方法首先利用支持向量機對原文檔進行學習并預測句子順序，之后再利用灰色模型對句子順序進行修正。Bollegala[8]提出了一種基于偏好學習的句子排序方法。為了捕獲句間的偏好，Bollegala定義了五種偏好專家： 時序、概率、主題相似性、預設以及繼承。他們使用人工編寫的摘要作為訓練數據來學習幾種偏好專家的最佳組合。最終，學習到的最佳組合將會被用于對從多文本摘要系統抽取的句子進行排序。該工作提出的句子排序算法使用貪婪搜索方法，通過把各個句子成對比較來生成最終的排序。Sukumar[9]在Bollegala工作的基礎上考慮了句子之間的語義關系。他們提出的系統使用WordNet同義詞集考慮摘要中句間的語義關系，該系統在安排摘要中句子順序的時候構建了一個蘊含模型來對句間的邏輯關系進行推測。

對于第二類工作，Nishikawa[10]提出了一種同時考慮信息量和可讀性的情感摘要算法。該方法將句子的選擇與排序同時進行。其中信息量的分數是通過計算情感表達式個數獲得的，而可讀性的分數是通過從目標語料學習獲得的。之后Nishikawa[11]又提出了同時考慮內容和連貫性的情感摘要算法。該工作將摘要視為一個句子序列并且通過線性規劃方法，從多個文檔選擇和排序以獲得最佳的序列。他們提出的線性規劃方程是最大覆蓋問題和旅行商問題的融合。

第二類方法由于還要兼顧句子選擇，在進行句子排序時考慮的因素相對較少，因此本文舍去了句子選擇的部分。

3 本文方法

3.1 文本片段間關系

本文引入判斷函數f(a→b)來表示句子a和b之間的連接強度和方向，如式(1)所示。

(1)

其中p表示兩個句子a和b之間的連接強度。

(1) 時間標準

時間標準反應了兩個句子在語料中出現的時間先后。本文定義了將b排列在a后的時間標準函數如式(2)所示。

(2)

其中，T(a)為句子a的發布時間，D(a)表示句子a所屬文檔，N(a)表示句子a在所處文檔中所處的行數。當句子a在發布時間上先于b時f(a→b)會被賦予值1，如果兩個句子在同一文檔中，句子a相對句子b位置靠前時f(a→b)會被賦予值1；當兩個句子不在同一文檔卻有相同的發布時間時會被賦予值0.5，表示兩個句子的順序無法判斷。

(2) 概率標準

概率標準反應了兩個句子在語料中相鄰出現的概率。本文利用Lapata[12]提出的概率模型來計算兩個句子相鄰的概率。

Lapata的模型定義一個摘要T是由句子序列{s1,s2,…,sn}按序列內部順序構成的，觀察到該序列的概率P(T)如式(3)所示。

(3)

基于馬爾科夫假設可以認為一個句子出現的概率僅和與它直接相鄰的前一個句子相關，由此式(3)可以改寫為式(4)。

(4)

Lapata把名詞、動詞和依存結構作為特征來表示句子，假設這些特征彼此獨立，并且用相鄰句子笛卡爾乘積特征組中的特征對P(si|si-1)進行估計，如式(5)所示。

(5)

a是句子si中的第j個特征，其中P(a|a)可以通過式(6)估計。

(6)

其中d(a,a)表明在語料中特征a在特征a前的次數，而分母中的式子表示在語料中a在任意特征前的次數。經過以上的推導定義了如式(7)的概率判斷函數來計算兩個片段的關系。

(7)

(3) 主題相似性標準

Barzilay[5]提出利用兩個句子所涉及的主題來對它們的相似性進行衡量的方法。對于摘要中的任意句子l，首先定義主題相似性函數如式(8)所示。

(8)

其中Q表示已經排序完畢的句子組，q是Q中的一個子句。sim(l,q)表明兩個句子向量的相似性。為了計算句子的相似性首先需要將句子轉化為向量。為了將句子轉化為向量需要做停用詞去除和詞型轉換的預處理。Barzilay使用的句子向量將向量的每個元素對應于原句的一個名詞或動詞，并使用余弦相似性對兩個向量的相似性進行計算。

使用以上定義的主題相似性函數，本文定義如式(9)所示的主題相似性標準函數。

(9)

其中，?代表空集，a、b代表正在被考慮的兩個句子，Q為已經排序完畢的句子集合。主題相似性標準函數的值在兩個句子的主題相似性相同或還沒有開始進行句子排序時取值為0.5，表示兩個句子的排序無法決斷。

(4) 預設標準

一個被抽取式摘要算法抽取的句子可能包含一些預設信息，這些信息可能包含在原文位于該句子前面的一組句子中，而這組句子沒有被摘要算法摘取。預設標準衡量了一個句子是否可以替代另一個文本片段的預設信息。該想法是由Okazaki[13]提出的句子排序算法提煉的。首先定義預設函數如式(10)所示。

(10)

其中Q表示已經排序完畢的句子組，q是Q中的一個子句。Pq是在原文中位于句子q之前的句子組，從中選擇可以使sim(p,l)最大的句子來計算預設函數的值。

最終可以定義預設標準函數如式(11)所示。

(11)

其中，?代表空集，a、b代表正在被考慮的兩個句子，Q為已經排序完畢的句子集合。預設標準函數的值在兩個句子的預設函數值相同或還沒有開始進行句子排序時取值為0.5，表示兩個句子的排序無法決斷。

(5) 繼承標準

繼承標準是和預設標準相對的，對于一個被抽取式摘要算法抽取的句子，在原文位于該句子后的句子組可能和其構成邏輯上的因果關系或包含該句子的一些繼承信息。繼承標準衡量了一個句子b是否可以替代另一個文本片段的繼承信息。首先定義繼承函數如式(12)所示。

(12)

其中，Sq是在原文中位于句子q之前的句子組，從中選擇可以使sim(p,l)最大的句子來計算繼承函數的值。

最終可以定義繼承標準函數如下式(13)所示。

(13)

繼承標準函數的值在兩個句子的繼承函數值相同或還沒有開始進行句子排序時取值為0.5，表示兩個句子的排序無法決斷。

3.2 句子間分數計算

(14)

如圖1所示為該模型的隱含層含有五個節點即n=5時的示例。

圖1 隱含層有五個節點的神經網絡示例

(15)

(16)

其中m是用于訓練的對數，上標k代表第k對文本片段組。

本文設置K=13，在對語料進行標注時，句子a排在句子b之前的分數如式(17)所示。

(17)

其中n(a)為句子a在文檔中的位置。當兩個句子的位置差距大于14時相互之間的影響會比較小，因此分數本文將其分數設為0。

3.3 句子排序

算法1

本文基于馬爾科夫隨機游走模型對句子進行排序。馬爾科夫隨機游走模型(MRW)可以通過從全圖遞歸得到的全局信息決定圖內任一頂點的重要性。定義圖G=(V,E)如圖2所示。V是頂點集，任一頂點vi∈V是待排序句子序列中的一員。E是邊的集合，任意兩個頂點vi和vj的判斷函數值如果存在(大于0)都會存在一條邊eij∈E。每條邊都對應著句間的連接權重，該權重就是兩個句子間的判斷函數值f(i→j)。

圖2 馬爾科夫隨機游走模型

通過歸一化相應權重可以得到從頂點vi到vj的過渡概率如式(18)所示。

(18)

(19)

(20)

它的矩陣形式為式(21)。

(21)

在執行階段，所有句子的初始分數都設為1并利用公式(20)來迭代計算各個句子的分數。通常連續兩次迭代各個句子的差值都小于一個固定閾值時算法收斂。

當圖G按照公式(20)執行至收斂后從X中選取排序分數最高的句子加入句子組Q，剩下的句子組成新圖并按照(20)執行至收斂，按照算法1中的步驟執行到X中沒有句子為止，Q中的句子順序就是最終的排序結果。

4 實驗結果與分析

本文收集了2012年六大門戶網站(網易、新浪、騰訊、搜狐、新華網、中華網)的新聞數據，共分為國內、國際、體育、社會、娛樂等18個類別，其中每條新聞數據都標注了發布的時間。

本文使用MEAD[14]從每個類別中抽取句子。MEAD是一種基于質心的多文本摘要算法，對于一系列相關文檔中的每個句子，MEAD使用三種特征并利用它們的線性結合判斷哪些句子最有突顯性。這三種特征分別是質心分數、位置以及最短句長。最終，本文利用MEAD從每個類別之中抽取了15個句子。

為了進行比較，本文使用了六種方法。

隨機排序(RO) 此種方法就是指對句子進行隨機排序，它代表了性能較低的基準算法。

概率排序(PO) 此種方法就是指利用概率標準函數對句子進行排序。使用此種方法的前提是訓練語言模型。本文將18個類別的所有語料作為訓練語料，利用fudannlp對語料進行分詞和提取依存結構并將它們作為特征。

時間排序(CO) 此種方法就是指利用時間標準函數對句子進行排序。

支持向量機監督方法(SVM) 本文所使用的神經網絡主要起到分類器作用，因此將其替換為支持向量機分類器作為對比。

貝葉斯分類器監督方法(Na?ve Bayes) 將本文所使用的神經網絡模型替換為樸素貝葉斯分類器作為對比。

本文提出方法(LO) 即為本文所使用的方法。

本文并未使用主題相似性標準、預設標準和繼承標準，因為這幾種標準都無法在句子排序沒有進行初始化的情況下使用，當然它們都融入了本文所提出的方法。

4.1 人工評價

可以使用人工評價的方法評價句子順序的質量。評價人在對一個摘要進行評價時通常從以下四個指標中選擇一種作為該摘要的評價結果。

完美 完美摘要是指無法通過重新排序進一步改進的摘要。

可接受 可接受摘要是指可以理解并且無需修改，但在可讀性上仍然需要提高的摘要。

一般 一般摘要是指丟失了某些故事主線，并需要少量修改使其可以提升到可接受級別的摘要。

不可接受 無法接受的摘要是指需要較大的改進并且需要從整體上調整結構的摘要。

本文安排了兩名評價員按照上文所提到的四種評價指標對各種方法生成的摘要進行評價。兩名評價員都已經閱讀了摘要的源文檔，并被告知使用各種方法生成的摘要只有內部句子順序不同。每種句子排序方法一共有18×2=36組評價結果，分別累加各方法所獲得四種評價的數量并計算比例，最終的評價結果如圖3所示。

圖3 人工評價結果

從圖3的實驗結果可以看出，本文所提出方法的實驗效果是最好的。雖然利用時間排序方法生成的一般質量摘要比例高于本文所提出方法，但是本文提出方法生成的一般以上(完美、可接受)質量摘要所占的比例要高于利用時間排序方法生成的摘要，而且時間排序方法效果較好的原因主要是新聞語料實時性強。另外使用SVM和Na?ve Bayes方法所取得的結果整體不如本文所提出方法，主要表現在它們生成的不可接受摘要比例較高。

4.2 半自動評價

人工評價的方法工作量太大，需要消耗大量的時間，因此本文又使用了Kendall等級相關系數、Spearman等級相關系數以及平均連續性(Average Continuity，AC)[16]等半自動方法對句子順序進行評價。評價結果如表1所示。

表1 語料1半自動評價結果

從表1的結果可以看出，本文所提出方法的性能在六種方法中是最好的。其中隨機排序方法和概率排序方法的實驗效果較差。概率排序方法效果較差的原因是本文在訓練概率模型時使用的是新聞語料，新聞語料是用于描述新事件的，因此在舊新聞中在相鄰句子中共現的詞語很少在需要排序的兩個句子中共現。時間排序方法相對概率排序方法效果較好，原因也是由于本文采用的訓練語料是新聞語料，語料中本身包含了時間信息。效果最好的是本文所提出的方法，因為它同時綜合了多種因素對句子進行排序。Na?ve Bayes方法效果與時間排序方法相近，都差于本文所提出方法，而SVM方法效果稍差于Na?ve Bayes方法。在將神經網絡模型作為監督分類器的其他一些工作中，其性能也好于SVM和Na?ve Bayes[17-18]。

4.3 圖排序算法性能對比

本文提出了一種基于馬爾科夫隨機游走模型的方法對句子進行排序，為了驗證該方法的性能，本文將其與其他幾種常用的圖排序算法進行了對比。這幾種基準算法分別是PageRank[19]算法、HITS算法[20]以及傳統的馬爾科夫隨機游走模型(MRW)[21]。將從每個新聞類別選取的15個句子分別利用基準算法進行排序，由于人工評價方法比較費時，因此本文利用半自動評價方法將各基準算法排序的結果與本文提出方法獲得的結果進行對比，評價結果如表2所示。

表2 語料1半自動評價結果

從實驗結果可以看出，本文所提出的方法性能最好。PageRank算法和傳統的馬爾科夫隨機游走模型表現接近而且和本文所提出方法的差距不大。HITS算法相對其他幾種算法表現最差。本文提出方法效果更好的原因是本文在圖排序算法的基礎上又提出了算法1所示的句子排序方法。

5 結論

本文利用神經網絡將幾種前人提出的句子排序方法融合，并在此基礎上提出了一種基于馬爾科夫隨機游走模型的句子排序算法。經過實驗驗證，利用本文所提出的方法對句子進行排序相對基準算法可以取得更好的效果。接下來的工作主要集中在進一步提高摘要的可讀性上，例如，利用句子壓縮的方法進行摘要潤色。

[1] 韓永峰, 許旭陽, 李弼程, 等. 基于事件抽取的網絡新聞多文檔自動摘要[J]. 中文信息學報, 2012, 26(1): 58-66.

[2] 劉平安. 基于HLDA模型的中文多文檔摘要技術研究[D]. 北京郵電大學, 2013.

[3] Wang L,Raghavan H, Castelli V, et al. A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization[C]//Proceedings of ACL, 2013.

[4] Ferreira R, Cabral L D S, Freitas F, et al. A multi-document summarization system based on statistics and linguistic treatment[J]. Expert Systems with Applications, 2014, 41(13): 5780-5787.

[5] R Barzilay, N Elhadad, K McKeown. Inferring strategies for sentence ordering in multidocument news summarization[J]. Journal of Artificial Intelligence Research，2002，17： 35-55.

[6] Banik E, Kow E, Chaudhri V. User-Controlled, Robust Natural Language Generation from an Evolving Knowledge Base[J]. Enlg, 2013.

[7] Peng G, He Y, Zhang W, et al. A Study for Sentence Ordering Based on Grey Model[C]//Proceedings of Services Computing Conference (APSCC) IEEE, 2010: 567-572.

[8] Bollegala D, Okazaki N, Ishizuka M. A preference learning approach to sentence ordering for multi-document summarization[J]. Information Sciences, 2012, 217: 78-95.

[9] Sukumar P, Gayathri K S. Semantic based Sentence Ordering Approach for Multi-Document Summarization[J]. International Journal of Recent Technology and Engineering (IJRTE), 2014, 3(2): 71-76.

[10] Nishikawa H, Hasegawa T, Matsuo Y, et al. Optimizing informativeness and readability for sentiment summarization[C]//Proceedings of the ACL 2010 Conference Short Papers. Association for Computational Linguistics, 2010: 325-330.

[11] Nishikawa H, Hasegawa T, Matsuo Y, et al. Opinion summarization with integer linear programming formulation for sentence extraction and ordering[C]//Proceedings of the 23rd International Conference on Computational Linguistics: Posters. Association for Computational Linguistics, 2010: 910-918.

[12] M Lapata,Probabilistic text structuring: Experiments with sentence ordering[C]//Proceedings of the annual meeting of ACL, 2003: 545-552.

[13] Naoaki Okazaki, Yutaka Matsuo, and Mitsuru Ishizuka. Improving chronological sentence ordering by precedence relation[C]//Proceedings of 20th International Conference on Computational Linguistics (COLING 04), 2004： 750-756.

[14] Dragomir R Radev, Hongyan Jing, and Malgorzata Budzikowska. Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies[J]. ANLP/NAACL Workshop on Summarization, Seattle, WA, April 2000.

[15] Hinton G E. A Practical Guide to Training Restricted Boltzmann Machines[M]. Neural Networks: Tricks of the Trade. Springer Berlin Heidelberg, 2012: 599-619.

[16] D Bollegala, N Okazaki, M Ishizuka, A bottom-up approach to sentence ordering for multi-document summarization[J]. Information Processing and Management,2010,46(1): 89-109.

[17] Sharma A K, Prajapat S K, Aslam M. A Comparative Study Between Naive Bayes and Neural Network (MLP) Classifier for Spam Email Detection[C]//IJCA Proceedings on National Seminar on Recent Advances in Wireless Networks and Communications. Foundation of Computer Science (FCS), 2014,(2): 12-16.

[18] Gharaviri A, Dehghan F, Teshnelab M, et al. Comparison of neural network, ANFIS, and SVM classifiers for PVC arrhythmia detection[C]//Proceedings of Machine Learning and Cybernetics, International Conference on. IEEE, 2008, 2: 750-755.

[19] 林莉媛, 王中卿, 李壽山, 等. 基于 PageRank 的中文多文檔文本情感摘要[J]. 中文信息學報, 2014, 28(2): 85-90.

[20] 苗家, 馬軍, 陳竹敏. 一種基于 HITS 算法的 Blog 文摘方法[J]. 中文信息學報, 2011, 25(1): 104-109.

[21] Wan X, Yang J. Multi-document summarization using cluster-based link analysis[C]//Proceedings of the 31st annual international ACM SIGIR conference on research and development in information retrieval. ACM, 2008: 299-306.

A Neural Network Model Based Sentence Ordering Method for Multi-document Summarization

KANG Shize,MA Hong,HUANG Ruiyang

(National Digital Switching System Engineering & Technological R&D Center, Zhengzhou,Henan 450002, China)

Sentence ordering is an important task in multi-document summarization. For this purpose, we first use neural network model to incorporate five proposed criteria for sentence connection, namely chronology, probabilistic, topical-closeness, precedence, and succession. Then, a sentence ordering method based on Markov random walk model is proposed, which determines the final ordering of the sentences based on the strength of connection between them. Examined by the semi-automatic and a subjective measures, the proposed method achieves obviously better sentence order compared with the baseline algorithms in the experiments.

sentence ordering;multi-document summarization;neural network model;Markov Random Walk Model

康世澤(1991—)，碩士研究生，主要研究領域為數據挖掘、自然語言處理。E?mail：xdkangshze@163．com馬宏(1968—)，碩士，研究員，主要研究領域為數據挖掘、電信網信息關防。E?mail：13838175769@139．com黃瑞陽(1986—)，博士，助理研究員，主要研究領域為文本挖掘、圖挖掘。E?mail：277433109@qq．com

1003-0077(2016)05-0195-08

2015-10-15 定稿日期： 2016-04-15

TP391

A