基于DTW 和改進(jìn)匈牙利算法的句子語義相似度研究?

鈕 焱 李 星 李 軍 劉宇強(qiáng) Jepkemei Judith

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

1 引言

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

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

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

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

2.1 詞向量

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

圖1 CBOW模型

圖2 Skip-gram模型

2.2 DTW距離

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

其中m是對齊兩個(gè)序列所需的索引數(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必須滿足三個(gè)額外的約束：邊界條件(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 步開始的剩余代價(jià)。策略π:{1:nx}×{1:ny}→{[1,0]T,[0,1]T,[1,1]T}定義了連續(xù)步驟之間的確定性轉(zhuǎn)換：pt+1=pt+π(pt)。確定了策略隊(duì)列，就可以從起始點(diǎn)開始遞歸地構(gòu)造對齊步驟pt=[1,1]T。

2.3 匈牙利算法

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

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

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

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

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

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

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

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

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

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

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

3.1 詞向量的計(jì)算

本文研究用到的數(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 個(gè)漢字的幾個(gè)句子。通過檢索詞向量庫得到每個(gè)句子對應(yīng)的詞向量數(shù)組。

3.2 DTW矩陣的計(jì)算

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

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

圖3 矩陣M1

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

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

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

圖4 矩陣M2

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

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

4.1 實(shí)驗(yàn)流程及結(jié)果

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

表2 實(shí)驗(yàn)中計(jì)算相似度的句子

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

5 結(jié)語

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