基于語義依存的漢語句子相似度改進(jìn)算法

黃 洪，陳德銳

(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

基于語義依存的漢語句子相似度改進(jìn)算法

黃 洪，陳德銳

(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

相似度；語義依存；詞語語義；知網(wǎng)

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

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

1 句子相似度計算

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

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

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

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

(1)

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

1.2 基于知網(wǎng)的詞語相似度計算

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

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

(2)

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

1.3 對基于語義依存的相似度算法的改進(jìn)

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

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

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

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

Spart1=Sword(Wcore1,Wcore2)·Skeyword

(3)

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

(4)

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

(5)

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

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

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

(6)

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

2 實 驗

2.1 確定權(quán)重

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

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

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

根據(jù)測試句的構(gòu)建規(guī)則，4類句子的相似度應(yīng)滿足SA>SB>SC>SD.假設(shè)直線A和直線B的交點為O，O點對應(yīng)的β=0.12，那么β應(yīng)滿足0.12<β<0.5.再在該區(qū)間內(nèi)以0.05為步長取值，并使用下一節(jié)的方法依次進(jìn)行實驗，實驗結(jié)果表明，β=0.5時，準(zhǔn)確率達(dá)到最高，所以最終的權(quán)重取值為α=0.5，β=0.5.

2.2 實驗方法

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

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

(7)

2.3 實驗結(jié)果

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

表1 實驗結(jié)果

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

3 結(jié) 論

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

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

[2] 周永梅,陶紅,陳姣姣,等.自動問答系統(tǒng)中的句子相似度算法的研究[J].計算機(jī)技術(shù)與發(fā)展,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] 秦元巧,孫國強(qiáng).改進(jìn)的句子相似度計算在問答系統(tǒng)中的應(yīng)用[J].微計算機(jī)信息,2011,27(8):206-208.

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

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

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

[8] 李彬,劉挺,秦兵,等.基于語義依存的漢語句子相似度計算[J].計算機(jī)應(yīng)用研究,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ìn)編輯距離和依存文法的漢語句子相似度計算[J].計算機(jī)應(yīng)用與軟件,2008,25(7):33-34.

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

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

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

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

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

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

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

[18] 李茹,王智強(qiáng),李雙紅,等.基于框架語義分析的漢語句子相似度計算[J].計算機(jī)研究與發(fā)展,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

(責(zé)任編輯：劉 巖)

2016-03-23

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

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

TP391

A

1006-4303(2017)01-0006-04