鈕 焱 李 星 李 軍 劉宇強 Jepkemei Judith

（湖北工業(yè)大學(xué) 武漢 430068）

1 引言

隨著人工智能技術(shù)的日益深入，自然語言處理領(lǐng)域的研究變得越來越重要。句子語義相似度的計算作為自然語言處理領(lǐng)域基本且核心的問題，在很多人工智能領(lǐng)域有著廣泛的應(yīng)用，例如，在機器翻譯、語音識別、文字情感識別、自動作文等方面，均需要用相似度模型來衡量文本中詞語的可替換程度或計算問題與答案的匹配程度。相似度計算也成為備受眾多自然語言處理研究者關(guān)注的研究課題。

目前，隨著詞向量概念的提出，很多研究學(xué)者將傳統(tǒng)的相似度算法與詞向量結(jié)合起來，在短文本相似度計算的準(zhǔn)確率上有很大的提升。田星等［2］在解決短文本相似度的問題上，將傳統(tǒng)的Jaccard算法與詞向量相結(jié)合，以語義層面的高維向量代替原來句子的字面量，通過計算詞向量間的相似度，以自設(shè)定的閾值來區(qū)分共現(xiàn)部分，在相似度的準(zhǔn)確率上有明顯的提升，但是該算法在中文文本相似度的計算上效果不盡人意。針對漢語句子，李茹等［10］提出結(jié)合漢語框架語義對句子進行框架語義分析，來達到刻畫句子語義的目的，由此計算的相似度效果傳統(tǒng)的方法更好，但是現(xiàn)有的漢語語義資源中框架的覆蓋率較低，在進行語義分析時有局限。針對基于路徑方法中普遍存在的密度不均勻性問題，郭承湘等［3］提出了融合路徑距離與信息內(nèi)容方法，通過一個平滑參數(shù)將路徑和信息內(nèi)容融合調(diào)整概念間的語義距離，使路徑方法計算的相似度值更加合理，以此方法計算句子相似度具有較強的魯棒性，但是一些詞典的特殊性使得信息內(nèi)容的方法體現(xiàn)不出任何效果。針對短文本數(shù)據(jù)稀疏和缺乏語義的問題，黃棟等［5］提出詞向量和EMD距離相結(jié)合的方法，使用Skip-gram 模型訓(xùn)練得到特征詞語義的詞向量，使用歐式距離計算特征詞相似度，使用EMD 距離計算句子相似度，與傳統(tǒng)方法相比有很大提升，但是算法中未考慮詞性和語序的影響。

針對以上研究缺點，我們提出了一種基于DTW 和改進匈牙利算法的語義句子相似度算法模型。由于中文詞語具有較為豐富的語義信息，為了更好地比對詞語間的相似度，先用神經(jīng)網(wǎng)絡(luò)訓(xùn)練語料，獲得具有200 維語義信息的特征向量，再通過DTW 將分詞模擬成空間中的點，將句子模擬成空間中的曲線，把兩個句子相似度的計算轉(zhuǎn)換為空間中兩條曲線相互變換的距離和復(fù)雜度，以此解決了漢語語義的問題，通過匈牙利算法尋找兩個句子相互轉(zhuǎn)換的最優(yōu)方案，以此解決了句子語序的問題。通過實驗測試，本文使用的方法在漢語句子相似度計算上相對于傳統(tǒng)的計算模型有較好的效果。

2 相關(guān)技術(shù)介紹

2.1 詞向量

詞向量指的是用低維實數(shù)向量表示一個詞，詞向量每一維的值代表一個具有一定語義和語法上解釋的特征。由此，可通過詞向量間的距離來從語義、語法上比較兩個詞之間的相似度。本文的詞向量是依據(jù)百度新聞?wù)Z料庫，通過Word2vec 優(yōu)化訓(xùn)練得到的。Word2vec 是Google 公司在2013 年開放的一款用于訓(xùn)練詞向量的軟件工具，其內(nèi)部轉(zhuǎn)化主要運用的是神經(jīng)網(wǎng)絡(luò)算法，因此，詞向量可以稱為將深度學(xué)習(xí)算法引入NLP 領(lǐng)域的一個核心技術(shù)。Word2vec 模型有兩種：CBOW 模型（見圖1）和Skip-gram 模型（見圖2）。CBOW 模型利用詞w（t）前后各c（c=2）個詞預(yù)測當(dāng)前詞；而Skip-gram 模型利用詞w（t）預(yù)測其前后各c 個詞。本文通過Word2vec 訓(xùn)練得到漢語詞語對應(yīng)的語義特征詞向量，再通過距離計算得到詞語相似度。由于詞向量包含語義特征，所以計算的相似度值更加可靠。

圖1 CBOW模型

圖2 Skip-gram模型

2.2 DTW距離

給定兩個時間序列X=[x1,x2,…,xnx]∈Rd×nx和Y=[y1,y2,…,yny]∈Rd×ny，DTW 是一種使式（1）平方和成本最小化的X，Y樣本最佳對齊技術(shù)：

其中m是對齊兩個序列所需的索引數(shù)量，對應(yīng)矩陣P 可以由一對路徑向量參數(shù)化，P=[px,py]T∈R2×m，其中px∈{1:nx}m×1，py∈{1:ny}m×1表示幀中對齊的組成。例如，對于一些t，如果存在pt=，則X 中第i 幀與Y 中第j 幀對齊。P必須滿足三個額外的約束：邊界條件(p1≡[1,1]T和pm≡[nx,ny]T) ，連續(xù)性(0 ≤pt-pt-1≤1) ，單調(diào)性（t1≥t2?pt1-pt2≥0）。盡管對齊X 和Y 的可能方式的數(shù)量在nx和ny中是指數(shù)的，動態(tài)編程通過使用貝爾曼等式提供了一種有效的途徑來最小化Jdtw：

成本函數(shù)值L*(pt)表示，基于最優(yōu)策略π*，從第t 步開始的剩余代價。策略π:{1:nx}×{1:ny}→{[1,0]T,[0,1]T,[1,1]T}定義了連續(xù)步驟之間的確定性轉(zhuǎn)換：pt+1=pt+π(pt)。確定了策略隊列，就可以從起始點開始遞歸地構(gòu)造對齊步驟pt=[1,1]T。

2.3 匈牙利算法

匈牙利算法的目的主要是為了尋求最大匹配或最小匹配值。給定一組成員X={x1,x2,x3,x4,x5}和一組任務(wù)Task={A,B,C,D,E}，每個成員完成任務(wù)的工時不同，求解所有任務(wù)完成所用的總工時最少的指派方案。指定kij表示成員i完成任務(wù)j的標(biāo)記值（0或1），首先確定約束條件：

改進算法實現(xiàn)步驟如下：

第一步：列出成員任務(wù)的效率矩陣T，T 中每一項的值Tij表示成員i完成任務(wù)j需要的工時。查看矩陣T中每行的最小元素的個數(shù)總和r和每列的最小元素的個數(shù)總和c，比較r 和c 的大小。當(dāng)r ≥c，則先從系數(shù)矩陣的每列減去該列的最小元素，再從所得系數(shù)矩陣的每行元素中減去該行的最小元素。反之如果當(dāng)r ≤c，則先從系數(shù)矩陣的每行中減去該行的最小元素，再從所得系數(shù)矩陣的每行元素中減去該列的最小元素。由此，使變換后的效率矩陣T1各行各列都出現(xiàn)0元素。

第二步：進行試指派，在T1中找盡可能多的獨立0 元素，若能找出n 個獨立0 元素，就以這n 個獨立0 元素對應(yīng)解矩陣T2中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟：

1）從只有一個0 元素的行（列）開始，給這個0元素加圈，記作◎。然后劃去◎所在列（行）的其它0 元素，記作? ；這表示這列所代表的任務(wù)已指派完，不必再考慮其他元素了。

2）給只有一個0 元素的列（行）中的0 元素加圈，記作◎；然后劃去◎所在行的0元素，記作?。

3）反復(fù)進行1）、2）兩步，直到盡可能多的0 元素都被圈出和劃掉為止。最后得到矩陣T3。

第三步：創(chuàng)建一個與矩陣T 同大小的零矩陣，將T3與中圈0 的位置相同的地方替換成1，得到0-1矩陣R。

第四步：將1的位置同原矩陣T映射的值相加，即得到最少總工時，最優(yōu)指派方案即為1 對應(yīng)的橫縱坐標(biāo)（成員與任務(wù)）的匹配。

通過上述的步驟可以看出，尋找獨立零元素的位置即尋找最優(yōu)匹配，這就是匈牙利算法的本質(zhì)。

3 基于DTW 和匈牙利算法的語義句子相似度計算方法

3.1 詞向量的計算

本文研究用到的數(shù)據(jù)為2016 年～2018 年百度新聞?wù)Z料數(shù)據(jù)。通過Word2vec 結(jié)合神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的方法訓(xùn)練出6萬條具有200維特征的詞向量數(shù)據(jù)形成詞向量庫，經(jīng)過此方法獲取的詞向量包含了漢字的語義信息。從語料庫中選著或人工組合出長度小于30 個漢字的幾個句子。通過檢索詞向量庫得到每個句子對應(yīng)的詞向量數(shù)組。

3.2 DTW矩陣的計算

針對實驗中兩個需要計算相似度的漢語句子S1和S2，通過jieba 分詞將其劃分成長度分別為m和n 的詞組，從詞向量庫中檢索出對應(yīng)的詞向量，得到句子S1和S2對應(yīng)的詞向量數(shù)組Vec1和Vec2。將詞向量數(shù)組Vec1和Vec2中每個分量相互求DTW 距離，最終得到一個大小為m×n 的DTW 矩陣Ddtw。本文在DTW 定義的基礎(chǔ)上做了一定的調(diào)整，使計算的流程更加簡潔，計算兩個向量V 和U間DTW距離的方法如下。

第一步：確定初始向量V=｛v1,v2,v3,v4｝，U=｛u1,u2,u3,u4,u5｝，約束條件為向量V 和U 的分量維度相同。計算V 中每個分量與U 中每個分量的歐氏距離，得到矩陣M1（如圖3）。

圖3 矩陣M1

第二步：由于向量V 和U 的分量在矩陣中是按照一定順序排列的，所以我們計算向量V 和U的DTW 距離即找到一條從矩陣M1左下角到右上角的最短動態(tài)規(guī)劃距離。設(shè)定當(dāng)從一個方格（（i-1，j-1）或者（i-1，j）或者（i，j-1））到下一個方格（i，j），如果是橫著或者豎著的話其距離為d（i，j），如果是斜著對角線過來的則是2d（i，j）。其中約束條件函數(shù)如式（6）和式（7）：

式（6）中d(i,j) 表示矩陣M1第i 行第j 列的值；g(i,j)表示兩個向量從起始分量開始逐次匹配，已經(jīng)到達V 的i 分量，U 的j 分量的距離。每一步的計算遵循約束式（6），如：

第三步：按照第二步的計算方法計算矩陣M1中每一處的g(i,j)值，將其寫入矩陣值的右上角并用紅色標(biāo)記，結(jié)果為矩陣M2（如圖4）。

圖4 矩陣M2

第四步：由第三步計算結(jié)果可得出，向量V 和U 的DTW 距離為18，即到達矩陣右上角的最短動態(tài)規(guī)劃路徑距離值。并且可以通過回溯得到最短規(guī)劃路徑，如圖4中箭頭標(biāo)出。

通過上述步驟可以總結(jié)出動態(tài)規(guī)劃的思路為

3.3 匈牙利算法求解句子相似度

將上一步求得的DTW 矩陣作為初始矩陣進行匈牙利算法計算，由于匈牙利算法要求的是一對一匹配，但是DTW 矩陣可能行列數(shù)不等。這里我們進行了填補處理。嘗試以向量最大值填補時，發(fā)現(xiàn)在求取獨立0 元素時會有很大誤差，導(dǎo)致最終相似度結(jié)果與實際偏差過大。于是以行列中最大值為基準(zhǔn)，缺失的部分補0。經(jīng)過多次測試，行列值均為0 時，在計算的過程中不會對選取獨立零元素造成太大影響。填補之后得到一個行列數(shù)相等的初始矩陣，按照匈牙利算法的步驟先比較行列最小值數(shù)目的總和進行比較，判定先從行開始處理還是先從列開始處理；處理后得到行列均有0 元素的矩陣；接著選取獨立0 元素進行位置標(biāo)記，選擇完所有的獨立0 元素之后將其位置與初始矩陣映射的值相加得到最短距離值d12（句子S1變換到S2所需的最小距離值），我們將一個詞與另一個詞的相似度以空間中的距離變化來衡量。由于匈牙利算法計算出獨立0 元素的個數(shù)count(0)對結(jié)果均有影響，延伸出句子相似度的計算公式：

4 實驗與結(jié)果分析

本文實驗訓(xùn)練及測評的數(shù)據(jù)是從2015 年～2018 年百度新聞?wù)Z料庫中摘錄的。使用Google 的Word2vec 模型，將語料分詞后通過神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練得到每個分詞對應(yīng)的200 維詞向量，每一維都包含分詞的某一特征語義的信息，形成一個含有6萬條詞向量數(shù)據(jù)的詞向量庫，詞向量庫數(shù)據(jù)見表1。

表1 百度新聞?wù)Z料200維詞向量部分數(shù)據(jù)

4.1 實驗流程及結(jié)果

選取詞向量庫中部分分詞組合成四條漢語句子（見表2）。

表2 實驗中計算相似度的句子

通過檢索詞向量庫，得到每條句子對應(yīng)的有序詞向量數(shù)組，以sentence1 作為待匹配句，sen?tence2，sentence3，sentence4 作為匹配句，分別計算sentence1 與sentence2，sentence3，sentence4 的DTW矩陣D1，D2，D3，D4；再將D1，D2，D3，D4作為初始矩陣通過匈牙利最優(yōu)匹配算法分別求出sentence1 與sentence2，sentence3，sentence4 的最短路徑值，最后通過式（9）分別計算sentence1 與sen?tence2，sentence3，sentence4 的相似度，實驗同時使用傳統(tǒng)的Jaccard 和TFIDF 方法計算相似度結(jié)果，用于對比，結(jié)果見表3。

4.2 實驗結(jié)果分析

首先我們通過人工評判四個句子，經(jīng)過專家分析觀察出sentence1 與sentence2，sentence3 表達的意思幾乎是一樣的，與sentence4 表達的意思不一樣。因此在相似度的比較上應(yīng)該有：

再觀察sentence2 和sentence3 表達的意思與sentence1 幾乎是一致的，但是sentence3 的語序雜亂程度要比sentence2 更嚴(yán)重，所以sentence1 變換到sentence3 所耗費的空間距離應(yīng)該比sentence1 變換到sentence2的要大，因此應(yīng)該有：

所以從人工評判的結(jié)果來看，應(yīng)該是：

從本文方法實驗結(jié)果來看：0.9279 ＞0.8961 ＞0.6926，結(jié)果與預(yù)期相符。而使用傳統(tǒng)的句子相似度計算方法Jaccard和TFIDF，得到的結(jié)果都為

原因在于兩種傳統(tǒng)的方法只考慮了兩個句子中共有詞出現(xiàn)的頻率，而沒有考慮語義信息和語序的影響，當(dāng)兩個句子的共有詞數(shù)目相等時無法做出有效的評估。由此表明通過DTW 與匈牙利算法相結(jié)合的方法計算含有語義信息和語序結(jié)構(gòu)的漢語句子相似度，具有一定的實際意義和研究價值。

5 結(jié)語

本文為了考慮漢語語義和句子語序?qū)渥酉嗨贫扔嬎愕挠绊?，提出了一種基于DTW 和匈牙利算法的語義句子相似度計算的方法。將原本應(yīng)用于語音識別和圖像識別領(lǐng)域的方法DTW 和解決最優(yōu)分配問題的匈牙利算法結(jié)合起來應(yīng)用在自然語言處理領(lǐng)域，并且在漢語句子相似度的計算上取得了不錯的效果，為自然語言處理領(lǐng)域研究提供了一種全新的方向。由于實驗環(huán)境的限制，我們還沒有進行大量語句的測試，對于不同方法對相似度的影響程度的權(quán)值設(shè)定可能還不是特別的精準(zhǔn)，但是相對于傳統(tǒng)的僅從距離的方向進行相似度計算有明顯的提高。