基于遺傳算法的詞語語義相似度計算研究

楊 泉

(北京師范大學，北京 100875)

0 引 言

語義相似度是對給定的語言對象間語義相似程度的衡量，通常用[0,1]之間的數值來表示。語義相似度計算就是計算語義相似度具體數值的過程。語義相似度計算對象的層級可分為詞、短語、句子、篇章，該文主要研究詞層級上兩個詞之間的語義相似度計算問題。

語義相似度計算目前在機器翻譯、人機問答、情感計算、信息提取等很多領域中都有著廣泛的應用[1]。語義相似度計算方法主要分為兩類：一類是在大規模語料的基礎上直接統計和計算的方法；另一類是根據某種已有知識本體(ontology)或分類體系(taxonomy)來計算的方法[2-3]。基于語料庫的方法對語料的依賴性較大，需要在大規模精確標注語料的基礎上進行，但語料的規模、內容、范圍以及標注的標準和規范難以統一，而且可解釋性較差；而基于知識本體或分類體系的方法在這些方面就顯示出了其優越性，越來越多的專家學者都進行了有效的嘗試。

用于語義相似度計算的漢語知識本體目前主要有《知網》[4]和《同義詞詞林》[5]。前人研究中有很多利用《知網》的樹狀結構或概念義原來進行語義相似度計算，如文獻[6]介紹了一種基于《知網》樹狀結構的語義相似度計算方法；文獻[7]在綜合考慮《知網》義原距離、義原深度、義原寬度、義原密度和義原重合度的基礎上，利用多特征結合的方法計算詞語相似度；文獻[8]基于對《知網》中詞語、義項和義原三個層次概念的研究，針對詞語相似度計算中結果合理性的問題，提出了一種結合信息論研究中熵的概念的新的詞語相似度計算方法。但是與《知網》相比較而言，《同義詞詞林》內部結構比較清楚，可以較為容易地轉化成樹形圖來計算詞語的深度和路徑，國內也有很多研究人員利用《同義詞詞林》計算詞語之間的語義相似度，文獻[6,9]利用《詞林》的編碼及結構特點，結合詞語的相似性和相關性，計算語義相似度。文獻[10]提出了一種綜合《知網》與《同義詞詞林》的計算方法。《詞林》部分采用以詞語距離為主要因素、分支節點數和分支間隔數為微調節參數的方法計算語義相似度。文獻[11]根據《詞林》提出了一種基于路徑與深度的算法。該方法通過兩個詞語義項之間的最短路徑以及它們的最近公共父節點在層次樹中的深度計算出兩個詞語義項之間的相似度。在計算過程中為分類樹中不同層之間的邊賦予不同的權值，同時通過兩個義項在其最近公共父節點中的分支間距動態調節詞語義項間的最短路徑。文獻[12]提出了一種基于路徑與《同義詞詞林》編碼相結合的語義相似度計算方法。該方法認為《詞林》編碼體系是按從左到右依次遞增的關系排列分支，距離越近的概念分支間隔越小，編碼距離也越近，由此根據每個分類節點下面的分支節點順序及編碼規律設計了計算模型。

以上這些模型都是根據經驗建立語義相似度的函數表達式，主要從兩個方面提高計算語義相似度的準確性：一是如何使用知識本體中的知識并進行量化；二是如何選擇更合適的函數表達式。由于《同義詞詞林》的內部結構清晰簡潔，使用深度、距離和節點分支數作為基礎知識進行相似度計算已經成為共識。因此如何突破已有經驗的局限性，尋找并建立更加合理的相似度函數表達式是進一步完善基于《同義詞詞林》的語義相似度計算方法的主要途徑。

1 《同義詞詞林》簡介

《同義詞詞林》是梅家駒等人1983年編撰的可計算漢語詞庫，后經哈工大信息檢索研究室擴展編輯為《哈工大信息檢索研究室同義詞詞林擴展版》(下文簡稱《詞林》)。經統計《詞林》共有77 456條詞語，分為12個大類；95個中類；1 428個小類；4 026個詞群和17 817個原子詞群。前面四個層級的節點都代表詞語的類別，第五層葉子節點上是原子詞群，每個原子詞群可用一個8位編碼唯一表示。表1展示了《詞林》中的義項編碼。

表1 《詞林》義項編碼

第八位編碼只有三種情況：其中“=”代表“相等、同義”關系；“#”代表“不等、同類”關系；“@”代表“唯一、獨立”關系。前七位編碼確定后就可以唯一確定一條編碼，不存在前七位編碼相同而第八位不同的情況。

在大類中A、B、C類多為名詞，D類多為數詞和量詞，E類多為形容詞，F、G、H、I、J類多為動詞，K類多為虛詞，L類是難以被分到上述類別中的一些詞語，各大類編碼具體含義如表2所示。

表2 《詞林》大類編碼含義

《詞林》結構安排中大類和中類的排序遵照從具體到抽象的原則[5]，每個大類都可以轉化為一個樹形結構圖，比如E大類下面分為6個中類，從“外形”到“境況”，詳見圖1。

圖1 《詞林》E大類語義場

通過上文對《詞林》整體架構的分析，其義項編碼可以直接映射為一個樹形結構圖，所有的詞語都可以對應到葉子節點的詞群里。實際上這個樹形結構圖就是使用的知識本體，而每個知識本體反映的都是作者對于世界知識的認識，語義相似性是世界知識很重要的一個組成部分，作者在編著《同義詞詞林》時就已經融入了語義相似信息，只是沒有把這種相似性信息數量化、數值化。因此基于《詞林》的兩個詞語之間的語義相似度計算，實際上就是解析蘊含于知識本體中的語義相似信息，將其形式化后轉化為可計算的函數表達式，最終計算出量化的數值。

2 基于遺傳算法的語義相似度計算模型

表1說明《詞林》中共有五個層級，為便于計算，該文在第一層級上面再引入一個虛擬層級，稱為第0層，對應樹形結構圖中的根節點，記為R。在此情況下《詞林》共有六層節點、五層邊，所有詞語都落在樹形結構圖最底層的葉子節點上，所有葉子節點都是一個原子詞群。在該樹形結構中將兩個節點之間最小的邊數稱為兩個節點之間的路徑長度或距離。將各非根節點到根節點R的距離稱為該節點的深度。

計算語義編碼分別對應不同的葉子節點的詞語s1與s2的語義相似度S，根據《詞林》編碼規則，這兩個詞語在其最近公共父節點處分離，分屬不同類別。將其公共父節點記為F，將F的深度記為D。從《詞林》體系中可以直觀地看出，F在《詞林》體系中所處層級越高，則D的取值越小，此時s1與s2分離得越早，相似度就低；相反F在《詞林》中所處層級越低，D的取值越大，則s1和s2分開得越晚，其相似度就高。因此D的取值與S成正比關系；而F的位置與S成反比關系。這從語言學角度也很容易理解，當兩個詞語所處的分支層的公共父節點越低，說明這兩個詞語所在的類別距離越近，兩個詞語的語義相似程度就越高；相反當兩個詞語所處的分支層的公共父節點越高，說明這兩個詞語所在的類別距離越遠，兩個詞語的語義相似程度就越低。上述分析表明在《詞林》所表示的知識本體中，兩個詞語s1與s2的最近公共父節點的深度對其相似度起決定性作用。例如“我們”的語義編碼為“Aa02B01=”，“你”的語義編碼為“Aa03A01=”，“消毒劑”的語義編碼為“Br13D04#”。“我們”與“你”的語義類別在同一個大類A中，而“我們”與“消毒劑”的語義類別分別在A和B兩個大類中，因此前兩者的語義相似度一定高于后兩者。

在樹形結構中還常用兩個節點間的路徑長度H來表示兩個節點之間的關系。任意兩個葉子節點之間的路徑長度H就是它們到其最近公共父節點路徑長度之和，根據《詞林》中樹形結構的特點：所有葉子節點到根節點R的路徑長度相同，在此記為常數C；葉子節點到其公共父節點的路徑長度也相同。而葉子節點到根節點的路徑長度等于葉子節點到其任意父節點的路徑長度與該父節點到根節點路徑長度之和。由此可以得出路徑長度與深度之間的關系式：

(1)

該結論說明路徑長度和深度是兩個能夠相互表示的量，該文在計算相似度時選擇將深度作為主要因素。文獻[2]在總結基于WordNet的英語語義相似度計算方法中有一類使用路徑和深度的計算方法，但由于WordNet與《詞林》的組織架構不同，在WordNet中不同的詞語可能具有不同的深度，這種葉子節點深度不均勻，義項遍布所有節點的組織方式與《詞林》是截然不同的。

在《詞林》體系中，詞語按照類別逐級細分，在同一個類別中的排序遵照從具體到抽象的原則進行排列(如圖1所示)。這說明在同一個類別層級中，意思接近的兩個分類其排列的位置也會接近，對應到樹形結構中，就是在同一個節點上排列的分支中，離得越近的分支其代表的意思也越接近。因此詞語s1與s2的語義相似度除由其最近公共父節點的深度決定外，也會受到該父節點處兩個葉子節點所在分支的位置關系以及最小公共父節點處分支總數的影響。將最近公共父節點所含分支總數記為N，將s1與s2所在分支的間隔數記為K。在《詞林》框架體系下，對s1與s2兩個待計算相似度的詞語，根據前面分析和相關文獻中的研究結果，整合為如下相似度關鍵信息x：

x=D+K/N

(2)

其中，D為最近公共父節點深度；N為最近公共父節點處分支總數；K為詞語所在分支間隔數。則s1與s2之間的語義相似度y可以表示為關鍵信息x的函數：

y=F(x)

(3)

目前所有基于《詞林》的語義相似度計算模型都屬于這個框架，只不過不同模型使用了不同的函數。如果把一些計算語義相似度的函數放在一起，然后再制定一個評價這些相似度計算函數的規則來評價，則這些函數就可以看成是一個具有不同競爭優勢的種群。借鑒遺傳算法的思想，對由相似度函數構成種群進行生物進化方面的選擇、交叉和變異等操作來使種群進行不斷繁衍，從而得到新的種群即新的相似度計算函數。根據自然選擇優勝劣汰的規律，有理由相信能夠找到比單純通過經驗建立的更好的相似度計算函數。為實現這個目標，執行以下操作：

(1)函數編碼。

首先需要將函數映射為便于使用遺傳算法的表示形式。該文將函數用樹的形式進行編碼，目的是把函數轉化為利于計算機操作的形式。這種方法將函數中包含的四則運算、復合運算作為樹的中間節點，將自變量x作為樹的葉子節點。例如對于具有如下形式的相似度計算函數：

y=F(x)=w1x2+w2R+w3ex+w4sinx

本文的驗證問題可描述為：給定系統狀態轉換模型TS，系統安全屬性φsafe以及系統運行時的觀測序列o1,…,ot，目標是 (1)計算在t時刻系統滿足安全屬性的概率Prt(TS φsafe|o1,…,ot;TS)，(2)當系統違背安全屬性時，求解系統最大可能的執行路徑作為系統違背安全屬性的反例.針對該問題，圖1給出了本文驗證方法的框架.

(4)

其中，w1,w2,R,w3,w4為常數，則可以表示為圖2所示的樹狀結構。

圖2 函數編碼的樹狀結構

根據這種思想，語義相似度計算函數的自變量就是上面的《詞林》信息x，將基本初等函數作為基本的函數集F={x,sinx,lnx,ex,arcsinx}，取四則運算為運算集H={+,-,×,÷}。在生成函數種群時，只需從不同集合中選取元素填入相應節點，就可以生成不同的函數，反復操作2M次即可生成一個含有2M個函數的初始種群。

(2)適應度函數。

(5)

顯然R(F)越小，相似度函數F的計算結果與標準結果就越接近，該個體在種群中就越優秀，具有更強的競爭力。

(3)選擇。

要完成種群的更新需要從父代群體中選取部分個體，以便生存和繁衍產生下一代群體，這種操作稱為選擇。該文采取優者勝出的選擇方法，將當前種群中的2M個函數按照適應度R(F)從小到大進行排序，然后將適應度最好的M個函數保留，將較差的M個函數淘汰，以保留下來的M個函數為基礎進行下面的操作形成下一代種群。

在遺傳算法中交叉是利用父代個體形成子代個體的過程，該文研究的個體是函數，在將函數編碼后，隨機設置交叉點，然后在交叉點處進行斷開和重組，完成基因交換，生成新的個體。具體過程如圖3所示，左邊為選擇的兩個個體，圖中方框處為選擇作為斷點的節點位置，然后分別交換和重組后，得到右側兩個新生成的個體。

圖3 交叉生成新的個體

(5)變異。

遺傳算法中的變異，是指將個體編碼串中的某些基因用其他等位基因來替換，從而形成新個體的過程。例如圖4中，左側為選中的變異個體，其中方框處為選擇的變異位置，右側為該位置變異后生成的新個體。

圖4 變異生成新的個體

以上過程描述了一種基于遺傳算法的相似度函數構建模型，該方法使用遺傳算法的思想，隨機生成一系列函數個體組成初始的“種群”，然后根據適應度函數來評價個體的適應度。若當前種群中的函數所計算的語義相似度都不能滿足要求，則模擬生物進化中的基因變異、復制、刪除等行為，繁衍生成新一代種群，經過不斷迭代，尋找更好的語義相似度計算函數。下面根據遺傳算法的思想為《詞林》建立語義相似度計算模型，具體算法描述如下：

第1步：給定m組詞語的《詞林》信息{x1,x2,…,xm}和標準相似度結果{y1,y2,…,ym}，基本函數集F={x,sinx,lnx,ex,arcsinx}，運算符號集H={+,-,×,÷}，最大進化代數T。

第2步：隨機生成包含2M個計算語義相似度的函數初始種群：{F1,F2,…,F2M}。

第3步：當進化代數小于最大進化代數時，生成新的計算語義相似度函數種群，完成種群繁衍迭代。具體方法如下：

①選擇：計算種群內全部語義相似度函數個體{F1,F2,…,F2M}的適應度，保留M個適應度最好的語義相似度函數個體；

②交叉：隨機選擇兩個語義相似度函數，通過交叉生成新的函數，重復四分之三M次，生成復四分之三M個新的語義相似度函數；

③變異：隨機選取四分之一M個語義相似度函數，然后隨機選取節點進行變異，生成四分之一M個新的語義相似度函數；

第4步：回到第3步繼續進化，直到達到最大進化代數；

第5步：計算最終得到的種群中M個語義相似度函數的適應度，并將最優個體作為最終相似度計算函數。

該方法中采取了優者勝出的選擇方法，每一代中的最優個體會保留到下一代中，隨著種群的繁衍，該方法會得到越來越優秀的個體，即越來越好的相似度計算函數。如果達到最大繁衍代數后，得到的相似度計算函數還不夠理想，可以適當增加種群大小，即增加迭代次數，甚至反復執行該方法，直到得到滿意的相似度計算函數為止。

3 實驗及結果分析

目前國際上對語義相似度算法的評價標準普遍采用Miller & Charles發布的30組英語詞對集(簡稱MC30)的人工判定值作為比較或學習的標準[14-15]。該文首先根據《詞林》提供的關于這30組詞對的信息計算其相應的詞對信息值x；然后使用遺傳算法模型尋找關于x的相似度函數表達式；最后，使用新找到的模型重新計算詞對相似度并與標準結果和相關結果進行對比。在試驗中設定函數構成分量的長度為3；此時函數關系式可表示為：

F(x)=w1f1(x)+w2f2(x)+w3f3(x)

(6)

初始種群的數量為50，在遺傳算法開始時隨機產生50個函數{Fi(x),I=1,2,…,50}；此后每代種群的最大數量為100，即有100個候選函數；種群的最大進化代數為1 000代。若達到最大進化代數，則選取最后一代中最優的函數作為相似度計算模型。經過運行模型算法，最終選定的函數模型為：

(7)

利用式(7)計算得到的語義相似度結果如表3所示。

表3 語義相似度計算結果

續表3

遺傳算法模型對MC30語義相似度的具體計算結果如表3所示，該文計算結果與皮爾遜相關系數為r=0.864 5。在實際應用中一般認為：當r≥0.8時，兩個變量間高度相關；當0.5≤r<0.8時，兩個變量中度相關。以上結果說明，該文提出的語義相似度計算模型能夠表達《詞林》中包含的詞語相似度關系，與人工值有較強的相關性。從表3中的相似度計算值中可以看出，仍然存在該文計算結果與MC30的人工判定值有較大差異的詞對，比如第10個詞對“食物(Br03A01=)”與“水果(Bh07A01=)”；第14個詞對“兄弟(Aa02A07=)”與“和尚(Am01B04=)”。其差異的深層次主要原因是《詞林》中對該詞對的相似度判斷標準與MC30的判斷標準在語言學認識上的差異。這種差異既有不同判定者主觀因素，也有不同語言之間在翻譯時所帶來的差異。

4 結束語

該文所提出的語義相似度計算方法是在《詞林》體系中詞語的深度、路徑和分支節點信息基礎上進行的，充分利用了人工智能遺傳算法強大的搜索能力，所得相似度計算模型更為準確合理。在此研究過程中發現，已有的模型中有一些詞語無論使用哪種方法，其計算結果均不理想，這種情況一般既有知識本體中義項定義或者詞語分類不合理的原因，也有相似度計算模型不夠完善的原因。為了克服前人研究中的不足，在知識方面充分利用《詞林》已有的詞語信息；在算法方面利用遺傳算法從更大更廣的函數空間中尋找函數模型，因此所得結論中既能得到較為理想的計算結果，也能更好地反映出語言知識層面的關系。