基于語義依存的漢語句子相似度改進算法

黃 洪，陳德銳

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

基于語義依存的漢語句子相似度改進算法

黃 洪，陳德銳

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

現有的基于語義依存的漢語句子相似度算法僅考慮了基于核心詞的有效搭配對，根據兩個句子有效搭配對的對應詞是否是相同詞和同義詞將匹配權重簡單地處理為0，0.5和1，而且未考慮不直接依存于核心詞的其他詞語，導致在計算句子相似度時區分度較低.改進算法通過綜合計算核心詞、關鍵詞的語義相似度來確定更為精確的匹配權重，并且將不直接依存于核心詞的其他詞語對句子的影響也納入句子相似度計算，以期達到全面刻畫句子語義、提高算法的準確率和區分度的目的.實驗結果表明改進算法比原算法具有更高的準確率以及更好的對句子的區分能力.

相似度；語義依存；詞語語義；知網

相似度計算一直是人工智能領域的研究熱點[1].句子相似度計算有著非常廣泛的應用，例如在基于實例的機器翻譯系統中，通過相似度計算匹配需要的譯文；在自動問答系統[2]中，通過相似度計算進行問句檢索；在信息檢索系統中，通過相似度計算匹配用戶所查找的內容.一般將句子相似度計算分為3個等級[3]：語法相似度、語義相似度和語用相似度，不過現階段還難以有效地計算句子的語用相似度，通常只需要計算句子的語義相似度就能夠滿足現有大多數應用的實際需求.根據對句子的分析層次，句子相似度算法分為基于詞語的方法和基于句法語義分析的方法.基于詞語的方法簡單易行，但是沒有對句子進行句法結構分析，只利用句子的表層信息如句中詞語的詞頻、詞性等，而未考慮句子結構因素，主要有基于相同詞的方法[4]、基于向量空間的方法[5]、基于語義詞典的方法[6]、基于編輯距離的方法[7]等.基于句法語義分析的方法對句子進行全面的句法語義分析，找出句中詞語的依存關系，并以此為基礎計算相似度，主要有基于語義依存的方法[8].

李彬等[8]對句子進行句法分析，通過構建依存樹，比較有效搭配對來計算相似度.該方法在比較兩個句子的搭配對時只是簡單地判斷兩個詞語是否相同，或者是否是同義詞，而且未考慮不直接依存于核心詞的其他詞語.針對這些問題提出一種改進算法，通過計算詞語相似度來匹配不同詞語，使其更好地體現句子的語義信息，并將不直接依存于核心詞的詞語納入相似度計算中，從而更加全面地比較兩個句子.

1 句子相似度計算

1.1 基于語義依存的句子相似度計算

基于語義依存的相似度算法首先要對句子進行全面的句法語義分析，選用哈工大社會計算與信息檢索研究中心研制的語言技術平臺(LTP)[9]對句子進行依存句法分析，該平臺可以同時對一個句子進行分詞、詞性標注、依存句法分析等操作，將其轉化為一棵結構化的依存句法分析樹.例如“請大家再檢查一遍是否已經填上自己的名字.”，經過依存句法分析后，句中各成分之間的關系如圖1所示.

圖1 依存句法分析Fig.1 The dependency parsing

李彬等[8]在基于語義依存進行句子相似度計算時，只考慮句子的有效搭配對，其中有效搭配對是由句子的核心詞以及直接依存于核心詞的名詞、動詞或形容詞組成的詞語對.以圖1為例，該句的核心詞是“請”，而直接依存于核心詞的詞語是“大家”和“檢查”，其中“大家”是代詞，“檢查”是動詞，所以該句的有效搭配對是“請_檢查”.相似度計算公式為

(1)

目前，一些學者提出了基于語義依存的相似度算法的改進算法，如劉寶艷等[10]提出了基于改進編輯距離和依存文法的相似度算法，先進行句法依存分析，再利用編輯距離計算相似度.王品等[11]在詞形相似度的基礎上融入語義依存相似度，分別用這兩種方法計算相似度，再進行加權求和.王宏生等[12]把語義網和詞形、語義依存相似度算法相結合，在語義網的基礎上進行相似度計算.侯麗敏等[13]提出了融合語義詞典和句法依存關系的相似度算法，也采用加權求和的方式計算相似度.考慮到劉寶艷、侯麗敏的算法沒有明確給出權重的取值，王宏生的算法需要人工構建語義網，實用性較差，實驗選用王品的算法作為對比.

1.2 基于知網的詞語相似度計算

詞語相似度[14]指出現在文章不同位置的兩個詞語可以互相替換而不改變文章句法語義結構的程度，詞語相似度計算通常需要使用諸如知網等特定的語義資源.知網是一個描述概念與概念之間以及概念所具有的屬性之間的關系的知識系統.知網使用概念來描述詞語，一個詞語可以描述為多個概念，每個概念都用義原來描述，義原是知網中最小的意義單位.

義原之間一共有8種關系：上下位關系、同義關系、對義關系、反義關系、部件整體關系、材料成品關系、屬性宿主關系以及事件角色關系.其中上下位關系最為重要，義原按照上下位關系組成一個樹狀的層次體系，也是目前大多數基于知網的詞語相似度計算方法[15-17]的基礎.實驗選用劉群的方法進行詞語相似度計算，公式為

(2)

其中：W1和W2分別為兩個詞語；C1i和C2j分別為W1和W2中的概念，兩個詞語的相似度是各個概念的相似度的最大值.

1.3 對基于語義依存的相似度算法的改進

基于語義依存的相似度算法[8]體現了句中詞語之間的相互關系，但在匹配有效搭配對時只是簡單地判斷兩個詞語是否相同，或者是否是同義詞，然后取0，0.5或1的匹配權重，對不同搭配對的區分程度較低.當句子比較短的時候，搭配對的數量也相應較少，由于匹配權重只有3個可能取值，根據式(1)可以看出句子相似度的可能取值也比較少，即該方法對不同短句子的區分能力較差.另外，只是區分相同詞、同義詞和不同詞也丟掉了詞語的語義信息，從而影響計算結果的準確率.在匹配不同詞語或搭配對時，可以深入挖掘詞語的語義信息，即通過計算兩個詞語的相似度并將其作為它們的匹配權重.當兩個詞語的相似度越大，它們的匹配權重也就越大，基于此得到的句子相似度也相應越大，即兩個句子所含詞語的相似度越大，它們之間的相似度也就越大.考慮到詞語相似度可以取0～1之間的任何值，這樣既能加大不同詞語或搭配對的區分度，又能充分利用詞語的語義信息以提高句子相似度計算的準確性.

此外，基于語義依存的相似度算法未考慮不直接依存于核心詞的詞語的相似度，丟失了一部分句子信息，實際上這些詞語對句子也有一定的影響，如果忽略它們，將無法區分那些搭配對相同但其他詞語不同的句子.例如句子“他常常懷念從前在家鄉的日子.”和“我很懷念大家一起奮斗的日子.”，它們的有效搭配對均為“懷念_日子”，如果不考慮其他詞語，它們的相似度就是1，明顯與實際情況不符.改進算法將會把這些詞語也納入句子相似度計算中，使得句子的信息更加完整.

將經過依存句法分析后的句中詞語分為3類：核心詞、關鍵詞和其他詞，其中核心詞定義為依存句法分析后句子的核心詞，關鍵詞定義為直接依存于核心詞的名詞、動詞和形容詞，余下的其他詞語定義為其他詞.繼續以圖1為例，該句的核心詞是“請”，關鍵詞是“檢查”，其他詞是“大家”“再”“一”“遍”“是否”“已經”“填”“上”“自己”“的”“名字”.計算句子相似度時分為兩部分：核心詞和關鍵詞的相似度、其他詞的相似度，然后再對兩部分進行加權求和.

假設句子S1，S2經過依存句法分析后得到句中詞語集合{Wcore1,Wkey11,Wkey12,…,Wkey1m,Wother11,Wother12,…,Wother1p}，{Wcore2,Wkey21,Wkey22,…,Wkey2n,Wother21,Wother22,…,Wother2q}，核心詞和關鍵詞的相似度Spart1的計算公式為

Spart1=Sword(Wcore1,Wcore2)·Skeyword

(3)

其中Skeyword為兩個句子關鍵詞的相似度，計算公式為

(4)

其中ki為第i次計算時關鍵詞相似矩陣的最大值.關鍵詞相似矩陣分別以兩個句子的關鍵詞為行和列，矩陣元素為該行和該列對應的兩個詞語的相似度值，每次計算遍歷整個矩陣，取出相似度最大值，再將其所在的行和列刪除，繼續下一次計算直到矩陣為空.類似的，其他詞的相似度Spart2的計算公式為

(5)

其中oi為第i次計算時其他詞相似矩陣的最大值.綜上，整個句子的相似度計算公式為

Ssen(S1,S2)=αSpart1+βSpart2

α+β=1，0<β<α<1

(6)

改進算法在依存句法分析的基礎上融入了詞語語義相似度計算，能夠從語義層面更加深入地比較兩個句子，而且還考慮到了不直接依存于核心詞的詞語的相似度，對句子的理解更加充分.但是在時間復雜度方面，因為改進算法考慮了句子中的所有詞語，所以它的時間復雜度O(mn+pq)要高于原算法的時間復雜度O(mn).

2 實 驗

2.1 確定權重

改進算法的句子相似度由兩部分組成，為了確定每部分的權重，針對性地構建了40對句子進行測試.這些句子分為4種類型：A類中每對句子的核心詞和關鍵詞基本相同，而且其他詞也基本相同；B類中每對句子的核心詞和關鍵詞基本相同，但是其他詞基本不同；C類中每對句子的核心詞和關鍵詞基本不同，但是其他詞基本相同；D類中每對句子的核心詞和關鍵詞基本不同，而且其他詞也基本不同.

由式(6)中的條件α+β=1，0<β<α<1可得α=1-β，0<β<0.5，然后聯合式(3)和式(5)，得出的結果代入式(6)中，就可以得到Ssen關于β的形如Ssen=aβ+b的一元二次方程.因為每一類句子都包含10對測試句，所以利用它們的平均值求解β，測試結果如圖2所示.

圖2 β取值對句子相似度的影響Fig.2 The influence of β values on sentence similarity

根據測試句的構建規則，4類句子的相似度應滿足SA>SB>SC>SD.假設直線A和直線B的交點為O，O點對應的β=0.12，那么β應滿足0.12<β<0.5.再在該區間內以0.05為步長取值，并使用下一節的方法依次進行實驗，實驗結果表明，β=0.5時，準確率達到最高，所以最終的權重取值為α=0.5，β=0.5.

2.2 實驗方法

現階段漢語句子相似度計算還沒有可用的公共測試集，一般需要人工構建測試語料.實驗所用語料主要來自《漢語動詞用法詞典》和互聯網，經過人工篩選后獲得.最終構建的實驗語料包含330條句子，這些句子分為標準集和測試集[18]：標準集含33條句子，測試集包括含99條句子的匹配集和含198條句子的噪聲集.其中，匹配集含33×3條與標準集中對應句子相似的句子，噪聲集中的所有句子均包含標準集中句子的關鍵詞語，以起到噪聲作用.

具體實驗方法為：從標準集中依次抽取第i(1≤i≤33)條句子，與測試集中的所有句子計算相似度，選取相似度最大的3條句子，記這3條句子和匹配集中對應的3條句子相同的句子數量為ri，即找到的正確句子數量.因此，準確率P的計算公式為

(7)

2.3 實驗結果

分別用3種不同的句子相似度算法對實驗語料進行了5次實驗，每次實驗都將匹配句和噪聲句隨機打亂以測試算法對不同句子的區分能力，其他設置保持不變.實驗結果如表1所示，其中方法1是李彬等的算法[8]，方法2是王品等的算法[11]，方法3是筆者的算法.從表1中可以看出：方法2和方法3都優于方法1，主要是因為它們在語義依存的基礎上考慮了其他因素，而且方法3的準確率更高，說明句中詞語的語義比詞頻(詞形)包含更多的句子信息.

表1 實驗結果

另外，方法1的實驗結果略有波動，原因是該方法對不同句子的區分能力較差，可能會出現標準句、匹配句的相似度與標準句、噪聲句的相似度相同的情況，因為每次實驗都將匹配句和噪聲句隨機打亂，所以在選取相似度最大的3條句子時(相似度相同時取靠前的句子)匹配句和噪聲句都有可能被選中.

3 結 論

對基于語義依存的句子相似度算法進行改進，通過對兩個句子的核心詞和關鍵詞進行語義相似度計算來確定更加精確的匹配權重，而不是簡單地根據是否是相同詞或同義詞而取0，0.5或1，并將不直接依存于核心詞的其他詞語也納入相似度計算，從而更加完整地反映句子的含義.實驗結果表明：改進算法在計算句子相似度時比原算法具有更高的準確率，而且正確句子的數量并未像原算法一樣出現波動，即改進算法對不同句子的區分能力更強.

[1] 徐彩虹,劉志,潘翔,等.一種基于實例學習的三維模型檢索匹配方法[J].浙江工業大學學報,2012,40(3):326-330.

[2] 周永梅,陶紅,陳姣姣,等.自動問答系統中的句子相似度算法的研究[J].計算機技術與發展,2012,40(5):75-78.

[3] CHATTERJEE N. A statistical approach for similarity measurement between sentences for EBMT[C]//Proceedings of Symposium on Translation Support Systems STRANS. Kanpur: Indian Institute of Technology,2001:122-131.

[4] 秦元巧,孫國強.改進的句子相似度計算在問答系統中的應用[J].微計算機信息,2011,27(8):206-208.

[5] 鄭誠,李清,劉福君.改進的VSM算法及其在FAQ中的應用[J].計算機工程,2012,38(17):201-204.

[6] 程傳鵬,吳志剛.一種基于知網的句子相似度計算方法[J].計算機工程與科學,2012,34(2):172-175.

[7] 葉煥倬,吳迪.基于改進編輯距離的相似重復記錄清理算法[J].現代圖書情報技術,2011,7(8):82-90.

[8] 李彬,劉挺,秦兵,等.基于語義依存的漢語句子相似度計算[J].計算機應用研究,2003,20(12):15-17.

[9] CHE Wanxiang, LI Zhenghua, LIU Ting. LTP: a Chinese language technology platform[C]//23rd International Conference on Computational Linguistics. Beijing: Tsinghua University Press,2010:13-16.

[10] 劉寶艷,林鴻飛,趙晶.基于改進編輯距離和依存文法的漢語句子相似度計算[J].計算機應用與軟件,2008,25(7):33-34.

[11] 王品,黃廣君.信息檢索中的句子相似度計算[J].計算機工程,2011,37(12):38-40.

[12] 王宏生,張敏.一種基于語義網的相似度計算模型[J].微計算機信息,2011,27(7):227-228.

[13] 侯麗敏,張永強.面向課程的中文FAQ自動問答系統模型[J].計算機與現代化,2014(10):20-24.

[14] 劉端陽,王良芳.基于語義詞典和詞匯鏈的關鍵詞提取算法[J].浙江工業大學學報,2013,41(5):545-551.

[15] 劉群,李素建.基于《知網》的詞匯語義相似度計算[J].中文計算語言學,2002,7(2):59-76.

[16] 黃洪,豐旭.涉及地名的句子相似度計算方法的改進[J].浙江工業大學學報,2015,43(6):624-629.

[17] 劉杰,郭宇,湯世平,等.基于《知網》2008的詞語相似度計算[J].小型微型計算機系統,2015,36(8):1728-1733.

[18] 李茹,王智強,李雙紅,等.基于框架語義分析的漢語句子相似度計算[J].計算機研究與發展,2013,50(8):1728-1736.

An improved Chinese sentence similarity algorithm based on semantic dependency

HUANG Hong, CHEN Derui

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

The existing Chinese sentence similarity algorithms based on semantic dependency only consider the effective word pairs based on the core word. Depending on whether or not the words in the effective word pairs of two sentences are same words or synonyms, it simply sets the matching weight to 0, 0.5 or 1. Those words which are not depended on the core word directly are not considered. This results in a bad discrimination in sentence similarity computing. In order to get a comprehensive characterization of sentence semantics and improve the accuracy and discrimination of the algorithm, the improved algorithm sets a more precise matching weight by computing the similarity of the core words and the key words, those words which are not depended on the core word directly are taken into the sentence similarity computation as well. The experimental results show that the improved algorithm has better accuracy and better discrimination than the original algorithms.

similarity; semantic dependency; word semantics; HowNet

(責任編輯：劉 巖)

2016-03-23

國家自然科學基金資助項目(61202202)；浙江省人社廳錢江人才項目(QJ01302010)

黃 洪(1964—)，男，江西豐城人，教授，研究方向為軟件開發方法、智能電子商務和自然語言處理，E-mail：huanghong@zjut.edu.cn.

TP391

A

1006-4303(2017)01-0006-04