基于改進句子相似度算法的釋義識別研究

陳俊月,郝文寧,張紫萱,唐新德,康睿智,莫 斐

(陸軍工程大學 指揮信息系統學院,南京 210000)

0 概述

隨著計算機技術的飛速發展和互聯網的全面普及,全球數字化信息的存儲量爆發式增長。豐富的信息資源既為人們的生活和生產帶來了便利,但同時也導致了信息重復冗余的問題。因此,文本語義相似度研究應運而生,其可作為承載語義信息的一種重要方式[1]。文本語義相似度計算具有廣闊的實際應用背景,例如論文查重、搜索引擎去重等,受到研究者的廣泛關注[2-4]。

釋義識別[5-6]用于判斷任意兩個句子或短語其語義是否相同,可看作是文本語義相似度計算的子任務。目前針對句子級別的文本語義相似度即句子相似度有許多較為成熟的計算方法,例如編輯距離(Levenshtein Distance,LD)算法[7]、Jaccard系數[8]和詞頻-逆文檔頻率(Term Frequency-Inverse Document Frequency,TF-IDF)算法等,但是這些方法都有著明顯的不容忽視的局限性和缺點:編輯距離算法僅考慮兩個句子相互轉換的操作次數,忽視了操作本身引起的語義差異;基于句子間共現詞計算句子相似度的Jaccard系數只考慮句子的字面量,忽視了詞語的語義信息[9];TF-IDF算法需要一個大規模語料支撐統計運算[6],而對于某些領域(如軍事領域),這樣的大規模語料是難以獲得的。近年來,隨著深度學習技術的興起,許多基于深度學習的文本相似度算法也隨之涌現。但這些算法往往需要大量的語料作為支撐,同時由于深度神經網絡本身的特點,因此其對計算時間和計算資源的要求都很高,而深度學習本身的黑箱性質也導致模型難以解釋。

詞向量技術在自然語言處理(Natural Language Processing,NLP)領域被廣泛應用,其通過無監督學習從大規模語料中獲取詞的高維向量表示,能夠很好地捕捉詞語的語法和語義信息[9]并準確計算詞語間的語義相似度。本文基于詞向量對Levenshtein相似度算法和Jaccard系數進行改進,提出一種新的句子相似度算法。通過分析對比多種句子相似度算法的優缺點和應用場景,設計多相似度特征的組合應用模式,并使用改進后的句子相似度算法在MRPC[10]釋義識別數據集上進行釋義識別實驗。

1 相關工作

句子相似度計算可分為基于字重疊的方法、基于語言學的方法和基于語料庫的方法3類[6]。

基于字重疊的方法主要通過兩個句子共有的詞匯量來計算句子間的相似度,典型代表為Jaccard系數,其以兩個句子中詞匯交集與詞匯并集的比值作為句子相似度。基于字重疊方法的基本思想是兩個句子的構成短語或詞匯的重疊個數越多,其相似度就越大,但這類方法都是字面層次的文本比較,未考慮詞語本身含義,因而使用范圍受到一定限制(如無法解決同義詞問題)。

基于語言學的方法通過計算構成兩個句子的詞之間的語義關系和語法成分來確定句子間的相似度(如基于句法分析找到句子中各部分的依存關系或語義關系,在計算相似度的同時考慮詞語相似度和關系相似度),該方法支持較為豐富的語義,但是句子本身的復雜性為框架分析帶來較大的難度和工作量。

基于語料庫的方法將文本表示為一系列詞語的組合,把基于語料庫統計的向量的余弦相似度作為句子對的相似度,而不考慮詞語的語序和含義,典型代表為TF-IDF算法。TF-IDF的基本思想是字詞的重要性隨其在文檔中出現的次數正比增加,但同時會隨其在語料庫中出現的頻率反比下降。這類方法需要一個大的文本語料庫做統計運算,而這類語料庫在某些具體領域是難以獲得的,例如軍事領域。

隨著詞向量在自然語言學習領域的廣泛使用,出現了大量基于詞向量的句子表示學習方法,主要可分為無監督學習和有監督學習兩類。

無監督學習方法包括TF-IDF加權句向量[11]、SIF加權句向量[12]、Paragraph Vector DM/DBOM[13]、FastSent[14]、Skip-Thought Vector[15]和SDAE[14]等。TF-IDF加權句向量和SIF加權句向量是基于詞袋(Bag of Words,BOW)模型的改進方法,這類方法通過對句子中詞向量的加權組合得到句子的向量表示,忽略了詞序信息,但簡單高效,在一些任務中取得了較好的結果。Paragraph Vector DM/DBOM分別基于word2vec中的CBOW模型和skip-gram模型[16]。Skip-Thought Vector模型利用word2vec中的skip-gram模型進行從詞級別到句子級別的推廣,即對當前句子進行編碼后再對其周圍的句子進行預測。該模型采用Encoder-Decoder架構,由于使用了GRU網絡,因此模型訓練速度慢。SDAE(Sequential Denoising AutoEncoder)采用基于LSTM的Encoder-Decoder模型,包括編碼器和解碼器兩部分,輸入信息通過編碼器產生編碼信息,再通過解碼器得到輸出信息,模型的目標是使輸出信息和輸入信息越來越接近,相較于Skip-Thought Vector的優點是只需要輸入單個句子,不要求句子所在的文本是有序的,而Skip-Thought的輸入必須是3個有序的句子。FastSent利用Skip-Thought Vector的設計思想以及BOW形式的編碼方式,使得模型訓練速度得到大幅提高。此外,研究者還提出一種FastSent的變體模型FastSent+AE,其不僅預測前后兩個句子中的詞,同時還預測本身句子中的詞。

有監督學習方法包括InferSent[17]和GenSen[18]等。InferSent采用了遷移學習的方法,其從SNIL數據集[19]訓練得到Encoder,然后使用預訓練的Encoder生成句向量用于其他任務。該模型能夠獲得較優的結果,但其采用BiLSTM網絡,訓練速度較慢,而且對于數據集規模的要求較高。GenSen則是一種基于多任務學習的模型,其同時在多個任務和多個數據源上進行訓練但共享相同的Sentence Embedding,這與Skip-Thought Vector 基本一致,主要區別在于Encoder 部分使用的是Bi-GRU,因此,該模型訓練速度同樣較慢。

2 句子相似度算法

2.1 全匹配相似度

文獻[20]提出了用于機器閱讀理解的文檔-問題(QE)全匹配特征。對于文檔中的某個詞,假設該詞在問題中出現,則其QE全匹配特征為1,否則為0。該特征從詞的共現出發,一般而言,文檔中包括問題詞的部分更可能含有答案。本文基于這一思路,提出句子間的全匹配相似度指標,定義如下:

定義1給定句子T、S以及預訓練的詞向量文件emb,對于句子T中的某個詞t,其與句子T的全匹配特征為:

(1)

其中,s為句子S中的某個詞,下標emb表示取該詞的詞向量。對于句子T,該句與S的全匹配相似度如式(2)所示:

(2)

其中,‖·‖表示句子包含的詞數。

全匹配特征能夠反映句子間詞是否共現。一般而言,若句子T中的詞在句子S中出現,那么這兩個句子更可能相似。考慮到自然語言中存在大量的多詞一義現象,因此,本文不直接考察文本詞是否在查詢中出現,而是通過詞向量之間的相似度度量某個文本詞的詞義是否在查詢中出現。

2.2 Jaccard系數及其改進

2.2.1 Jaccard系數

Jaccard系數又稱為Jaccard相似系數,可用于比較有限樣本集之間的相似度與差異性,系數值越大,樣本相似度越高[9]。直觀上而言,兩個句子的相同部分越大,共現詞匯數目越多,它們的相似度應該越高。因此,可以使用Jaccard系數計算兩個句子間的相似度,如式(3)所示:

(3)

其中,Inter(S,T)表示句子S和句子T之間的詞匯交集,Union(S,T)表示句子S和句子T之間的詞匯并集。

2.2.2 改進的Jaccard系數

傳統的Jaccard系數未考慮詞的語義,只是單純地基于共現詞計算句子的相似度,無法處理多詞一義的情況,如“I hava a computer.”和“I have a PC.”,顯然兩句在語義上是相等的,而傳統Jaccard系數在計算過程中卻無法識別“computer”和“PC”為語義一致,所得到的Jaccard系數僅為0.6。

詞向量是每個詞語在語義層面的高維向量表示,本文結合詞向量對傳統的Jaccard系數進行改進。改進后的Jaccard系數定義如下:

定義2給定句子T、S、預訓練詞向量文件emb以及詞向量相似度閾值α(α≥0)。T和S間的改進Jaccard系數如式(4)所示:

(4)

其中,下標emb代表取該詞的詞向量,‖T‖·‖S‖表示句子T和S的長度乘積。

在改進的Jaccard系數定義式中,分子部分代表句子T和S中詞向量的相似度之和,相較于傳統的Jaccard系數方法,改進后的Jaccard詞向量匹配特征由于引入了詞向量,不僅能夠反映句子間詞的共現情況,而且還能反映詞向量的共現值。分母部分實際上包括了分子部分以及句子T和S中詞向量的不共現度,因此,0≤Jaccard(T,S)≤1。

2.3 Levenshtein相似度算法

2.3.1 Levenshtein距離及相似度算法

Levenshtein距離是指兩個字符串之間由原字符串S轉換為新字符串T所需要的最少編輯次數,允許的編輯操作包括插入、替換、刪除[21]。

基于Levenshtein距離能夠計算字符串間的相似度,如式(5)所示:

(5)

其中,l為字符串S與T間的Levenshtein距離。Lsim值越大,表示兩個字符串相似度越高;Lsim值越小,表示兩個字符串相似度越低。同樣,對于句子而言,以詞為單位進行插入、刪除和替換操作即可得到句子級別的Levenshtein相似度。

2.3.2 基于編輯操作排序的路徑回溯算法

目前對于Levenshtein相似度的求解一般使用動態規劃算法。假設有兩個字符串S和T,S={s1,s2,…,sN},T={t1,t2,…,tM},建立S與T的(N+1)(M+1)階LD矩陣,如式(6)所示:

(6)

在LD矩陣中,第1列代表字符串S,第1行代表字符串T,dij表示從字符串{s1,s2,…,si}到字符串{t1,t2,…,tj}所需的最少編輯次數。矩陣填充公式如下:

其中,i=1,2,…,N,j=1,2,…,M,矩陣右下角元素dNM為字符串S和T之間的Levenshtein距離,記為ld。

在LD矩陣基礎上,可以回溯得到編輯路徑。需要注意的是,在編輯路徑回溯時可能產生多條編輯路徑[16],而通過實驗可以發現,不同編輯路徑計算得到的Levenshtein詞向量距離是不同的。為避免回溯路徑對相似度造成影響,本文設計基于LD矩陣的編輯路徑回溯算法,通過對編輯操作的優先級排序得到唯一的回溯路徑。算法描述如下:

算法基于編輯操作排序的編輯路徑回溯

1.Input S,T,operation_rank

//輸入源字符串、目標字符串和編輯操作排序

2.Initialize LD matrix,i=len(S),j=len(T),list_operation=[]

//初始化LD矩陣、回溯指針及回溯路徑

3.While i>= 0 and j>=0://編輯路徑回溯

{

coordinate=[i,j]//記錄當前編輯操作發生的位置

If i==0:operation=“insert”;

elif j==0:operation = “delete”;

Else://根據編輯距離和編輯操作排序選擇編輯操作

{

candidate_operation={“replace”:LD(i-1,j-1),“insert”:

LD(i,j-1),“delete”:LD(i-1,j)}

sorted_operation=sort(candidate_operation,by={value,operation_rank},descending=False)

operation=sorted_operation[0]

}//更新回溯指針

If operation==“delete”:j=j-1;

elif operation==“insert”:i=i-1;

else:i=i-1,j=j-1;

list_operation.append([operation,coordinate])//更新回//溯路徑

}

4.Output list_operation//輸出回溯路徑

由于算法指定了編輯操作的優先級排序,因此在進行LD矩陣回溯時,每一步的回溯操作都是唯一的,即能夠得到唯一的回溯路徑。根據分析可知,該算法的空間復雜度和時間復雜度僅與2個字符串的長度有關,其中空間開銷即LD矩陣的存儲開銷為O(MN),時間開銷即回溯的次數,若M>N,則時間復雜度為O(M),否則為O(N)。需要注意的是,“replace”本質上并不是Levenshtein算法規定的替換操作,而是指在進行字符串轉換時直接從原字符串復制字符到目標字符串中,但是為了統一符號,本文將其看作一種特殊的待替換字符與替換字符執行相同的替換操作。

2.3.3 改進的Levenshtein相似度算法

傳統的Levenshtein相似度算法從字符串互相轉換的角度出發計算需要的最少編輯操作次數,能夠從一定層面上反映句子間的相似性。但是僅考慮所需編輯操作次數而不考慮編輯操作本身引起的語義差異是不夠的。假設有句子S、T和Q,分別為“I have a computer.”“I have a PC.”和“I have a TV.”,根據傳統的Levenshtein相似度算法,3個句子兩兩之間都只需要一次替換操作即可完成轉換。實際上句子S與T的語義一致,而S與Q、T與Q的語義差異更大,這是因為不同的編輯操作對句子語義的改變是不同的,將“computer”替換為“PC”并未對語義造成影響,因為“computer”與“PC”是等價的,而將其替換為“TV”則會引起較大的語義改變。

針對上述問題,本文通過引入詞向量對Levenshtein距離算法進行改進。改進算法的具體步驟如下:

步驟1給定句子T和S,l=max(‖T‖,‖S‖),計算兩者間的LD矩陣。

步驟2通過LD矩陣回溯編輯路徑并記錄路徑。

步驟3對于編輯路徑中的刪除和插入操作,將其轉換為特殊的替換操作,即刪除操作等價于將待刪除字符替換為空字符,插入操作等價于將空字符替換為待插入字符。

步驟4對于編輯路徑中的所有操作,通過詞向量計算替換操作兩個字符的相似度并累加,將得到結果記為Lemb,即Levenshtein詞向量距離。

步驟5輸出改進的Levenshtein相似度1-Lemb/l,記為Lsim′。

根據改進的Levenshtein相似度算法對例句S、T和Q計算,從S轉換到T和從S轉換到Q都只需要一次替換操作,但由于“computer”與“PC”的語義相近,“computer”與“TV”的語義相差較大,因此有:Lemb(S,T)Lsim′(S,Q)。

可以看出,改進后的Levenshtein相似度算法相較于傳統Levenshtein相似度算法能夠更準確地刻畫句子之間的語義相關性。

2.4 多相似度特征組合分析

Jaccard系數和Levenshtein相似度是目前常用的句子相似度計算方法,兩者從不同的角度刻畫了句子間的相似度。Jaccard系數從集合論的思想出發,利用句子間共現詞占全部詞的比例反映句子的相似度,但忽視了句子語序的影響,而Levenshtein相似度則通過句子間相互轉換所需操作次數來衡量句子相似度,一定程度上考慮了句子間的語序。兩種方法本質上都是基于字面量的匹配方法,雖然取得了一定的效果,但都無法解決多詞一義問題。因此,本文引入詞向量這一詞語語義的高維表示方法對上述算法進行改進,提出一種新的相似度算法。改進后的Jaccard系數和Levenshtein相似度不僅能夠反映句子間字面量的相似性,而且能夠應對多詞一義的情況。然而需要指出的是,改進后的Jaccard系數和Levenshtein相似度由于使用了詞向量作為支撐,因此詞向量的質量對于算法性能有較大影響,而對于一些專有名詞如人名、地名或專業領域(如醫學、生物、建筑等)詞匯,這些詞匯往往不可替代且出現次數較少。因此,詞向量無法完全反映其語義信息甚至難以獲得這類詞的詞向量,而傳統Jaccard系數和Levenshtein相似度在面對此類句子時則較為有效。

多種句子相似度指標的組合能夠有效結合各類指標的優點。傳統的Jaccard系數和Levenshtein相似度對于專有名詞表現更好,而改進的Jaccard系數和Levenshtein相似度則對通用詞匯間的多詞一義現象更具優勢。全匹配特征類似于Jaccard系數,其直接通過詞的共現判斷句子相似度,但沒有采用集合論方法,因此能夠反映詞頻信息。本文將句子對的Jaccard系數、Levenshtein相似度、全匹配相似度、改進后的Jaccard系數與Levenshtein相似度共5種相似度指標相結合作為特征向量,共同描述句子對間的相似度關系,然后根據這一特征向量判斷句子間的語義等價關系,從而避免信息的遺漏和丟失,增強算法的健壯性。

3 實驗

3.1 數據集與評價指標

本文選用微軟發布的通用語料集MRPC進行實驗。MRPC數據集是一個用于釋義識別任務的數據集,包含取自互聯網新聞文章的4 076對訓練句子和1 725對測試句子,每個句子對由兩位評估人員判斷其語義是否等價,該數據集樣本分布如表1所示。

表1 MRPC數據集樣本分布

給出如下數據集示例,其中,“#1 String”和“#2 String”是被測試的句子對,Quality表示句子對是否語義等價,取值為{0,1}。

Quality#1 ID#2 ID#1 String#2 String

1702876702977Amrozi accused his brother,whom he called "the witness",of deliberately distorting his evidence.Referring to him as only "the witness",Amrozi accused his brother of deliberately distorting his evidence.

021087052108831Yucaipa owned Dominick′s before selling the chain to Safeway in 1998 for $2.5 billion.Yucaipa bought Dominick′s in 1995 for $693 million and sold it to Safeway for $1.8 billion in 1998.

MRPC數據集以準確率(accuracy)和F1值作為評價指標,其定義如下:

其中:TP為預測為等價并且實際上等價的樣本數量;TN為預測為不等價并且實際上不等價的樣本數量;FP為預測為等價但實際上不等價的樣本數量;FN為預測為不等價但實際上等價的樣本數量[6]。

3.2 相似度計算與模型訓練

首先對句子進行預處理,然后計算句子對的Jaccard系數、Levenshtein相似度、全匹配相似度、改進后的Jaccard系數與Levenshtein相似度5種相似度指標。其中,分詞方法選用python的spacy包,詞向量選用300維的谷歌預訓練詞向量[22](下載地址為nlp.stanford.edu/data/glove.840B.300d.zip),改進Jaccard系數算法的參數,并將Levenshtein距離計算中路徑回溯算法的編輯操作優先級排序為[replace,delete,insert]。

由于各類相似度取值都較為接近,簡單的特征加權算法會丟失大量信息,因此在完成各類相似度計算后,采用分類模型進行釋義識別。以5種相似度指標值為樣本特征,以句子對是否語義等價為類別標簽,選用多種常用機器學習分類算法對訓練數據進行訓練,包括梯度提升樹(Gradient Boosting Decision Tree,GBDT)、支持向量機(Support Vector Machine,SVM)、樸素貝葉斯(Na?ve Bayes,NB)、K近鄰分類(K-Nearest Neighbor algorithm,KNN)、決策樹(Decision Tree,DT)、隨機森林(Random Forest,RF)和邏輯回歸分類(Logistic Regression,LR)。

3.3 實驗結果與分析

3.3.1 分類算法對比實驗

表2記錄了基于多相似度特征不同分類算法在MRPC數據集上的表現,其中黑體表示最優結果。可以看出,表現最好的是SVM算法和LR算法。SVM算法的F1值達到83.69%,準確率為73.62%。LR算法雖然在F1值上略遜色于SVM算法,為82.12%,但準確率的表現更好,達到了74.14%。KNN算法、DT算法和RF算法整體表現較差,筆者認為這與數據中類別不平衡和特征相關性有關。由表1可見:MRPC數據存在一定的類別不平衡現象,其語義等價樣本數和語義不等價樣本數的比值約為2∶1,同時作為樣本特征的5類相似度指標存在一定的相關性;KNN算法容易受到類別不平衡影響,決策樹算法不僅受類別不平衡影響較大,而且還容易過擬合,因此,兩者表現較差,而基于決策樹的隨機森林算法同樣無法避免這個問題;SVM算法基于結構風險最小化原則,能夠避免過擬合問題,泛化能力強,并且SVM是一個凸優化問題,其局部最優解必定為全局最優解,而LR算法不容易受到特征間相關性的影響,因此,這兩種算法取得了較好的實驗結果。

表2 不同分類算法在MRPC數據集上的準確率和F1值

由于表2所示的實驗結果是在未做進一步模型調參下獲得的,即使是表現最差的決策樹算法也依然取得了準確率63.48%和F1值72.30%的結果,表明輸入特征能夠有效區分句子間的語義相似度。

3.3.2 本文算法與其他算法的對比實驗

根據表2不同分類算法的表現結果,本文選擇SVM算法訓練分類模型,同時應用超參數搜索和交叉檢驗等方法提升模型表現,其與現有其他模型的準確率和F1值比較如表3所示,其中黑體表示最優結果,?表示在文獻[20]基礎上通過遷移學習得到的新模型。可以看出,本文模型準確率為74.4%,F1值為82.6%,位居第三,并且與前兩名實驗結果差距較小。

表3 使用不同句子相似度算法的釋義識別模型性能對比Table 3 Performance comparison of paraphrase recognition models using different sentence similarity algorithms %

表3中的模型都需要大規模語料庫或深度學習模型進行支撐。如第1組和第2組中的Unigram-TFIDF、Paragraph Vec和SDAE、FastSent、Skip Thought等無監督表示學習方法都是在Toronto book corpus (該語料庫大小約70 MB,由來自7 000多本書的有序句子組成)上訓練得到,并且這兩組模型最好的實驗結果分別為準確率73.9%、F1值82.0%和準確率73.0%、F1值82.0%,相較本文模型的實驗結果仍有一定差距。第3組中的方法通過有監督訓練學習得到句子表示,然后基于句子的表示進行釋義識別,僅有InferSent和GenSen兩種模型比本文模型表現得更好。但是InferSent模型的結果是基于SNLI和MultiGenre NLI(該數據集是SNLI的增強版本,包括433k個句子對)兩個數據集[23]訓練得到的,而當InferSent模型在SST數據集[24](該數據集僅包括12k個樣本)上進行訓練時僅能得到準確率72.7%和F1值80.9%的實驗結果,相較于本文模型的實驗結果低了2個百分點,說明該模型的表現受到語料數量的限制。此外,InferSent模型使用了BiLSTM-Maxpooling作為編碼器,這導致其訓練時長和計算資源需求都十分巨大,根據官方代碼,該模型的參數量約為47 MB。GenSen模型基于GRU的Encoder-Decoder架構,同時使用了多任務學習,這種方法同樣對于計算資源和語料的要求都十分巨大,而在不進行多任務學習的情況下其表現為準確率72.4%、F1值81.6%,與本文模型相比仍略有差距。

相比上述模型,本文基于改進文本相似度的釋義識別模型僅使用了通用的預訓練詞向量,計算過程也只包括相似度指標計算和簡單的機器學習分類模型訓練兩部分,因而實驗結果較優,證明了本文對文本相似度算法的改進是有效的,并且可將該算法作為一種簡單但優秀的基線模型用于后續的釋義識別任務研究。

4 結束語

本文針對現有句子相似度算法存在的不足,結合詞向量技術對傳統的Levenshtein相似度算法和Jaccard系數進行改進,提出一種新的句子相似度算法。在通用MRPC數據集上的實驗結果表明,該算法能夠提高準確率和F1值,可作為一種簡單有效的基線模型用于后續的釋義識別任務。下一步將拓展更多的句子相似度度量指標,同時加快算法的計算速度。