基于貝葉斯估計的概念語義相似度算法

吳 奎,周獻中,王建宇,趙佳寶

(1.南京理工大學 自動化學院,江蘇 南京210094;2.南京大學 工程管理學院,江蘇 南京210093)

1 引言

領(lǐng)域本體可以有效地組織、共享、重用領(lǐng)域中的知識,在軟件工程、人工智能、信息檢索、Web服務(wù)發(fā)現(xiàn)等領(lǐng)域扮演著越來越重要的角色。概念語義相似度計算是領(lǐng)域本體應(yīng)用中的基礎(chǔ)問題,用于表示本體中兩個概念之間的語義接近程度,以便提高知識檢索、服務(wù)匹配、本體映射等過程的性能[1]。已有的各種概念語義相似度計算模型,都是為了刻畫兩個概念之間的語義相近程度,其數(shù)值大小應(yīng)盡可能地接近主觀意識和客觀因素。主觀上,由于人們對事物認識的差異,并不能給出兩個概念的相似度具體數(shù)值,但在父子概念層次結(jié)構(gòu)中,某個概念與它的子概念之間的相似度必然大于其父概念與其子概念的相似度。如“哺乳動物”和“男人”之間的語義相似度應(yīng)大于“動物”和“男人”之間的相似度,小于“哺乳動物”和“人”之間的相似度?？陀^上,任何一個概念都是對其祖先概念信息的細化。因此從信息論角度,兩個概念之間的相似度與二者共享的信息有關(guān),它們從相同祖先概念中共享的信息量越多,則二者越相似。

計算兩個概念之間的語義相似度,目前有很多種方法,Budanitsky[1]對基于WordNet的幾種方法進行了比較。李峰[2]認為這些方法可以分為兩大類：一種是基于兩個節(jié)點之間的路徑長度,即語義距離;另一種是基于兩個節(jié)點所含的共有信息大小。綜合來看,基于語義距離算法簡單,但它依賴于主觀建立好的概念層次網(wǎng)絡(luò)和各個邊的權(quán)值,因而不能保證相似度的客觀性;基于信息量的相似度計算在理論上更具有說服力,它根據(jù)信息論的方法,通過概念A(yù)、B之間的共享信息量和獨立信息量計算獲得,然而這種方法需要足夠多的領(lǐng)域資料。針對這些方法的不足,江敏等[3]以加權(quán)和的方式綜合不同方法的結(jié)果,然而這種方式的合理性值得懷疑;Anna Formica[4]提出了一種基于形式概念分析的相似度算法,基于概念的上下文計算二者的相似度。本文以Lin[5]的概念相似度算法為基礎(chǔ),提出一種基于貝葉斯估計的相似度計算方法(Bayesian Estimation Similarity,BES),通過綜合考慮主觀先驗因素和客觀統(tǒng)計樣本,以求能更好地體現(xiàn)領(lǐng)域本體中兩個概念之間的語義接近程度。

貝葉斯統(tǒng)計推斷[6]是當今統(tǒng)計學發(fā)展最快的分支之一,已成為當今統(tǒng)計學的重要組成部分。雖然這種方法曾經(jīng)有很多爭論,比如指定一種先驗分布不免帶有人為性,未必有助于問題的合理解決,但近年來這些爭論已不是主流,大多數(shù)研究人員都承認貝葉斯方法可較好的應(yīng)用于統(tǒng)計學的幾乎所有分支。本文不考慮貝葉斯方法在哲學方面的問題,而是根據(jù)貝葉斯估計計算概念出現(xiàn)概率。該方法主要思路為：考慮到Beta分布可以通過選擇合理參數(shù)適應(yīng)多種分布形狀,且容易獲得計算結(jié)果,本文假設(shè)概念出現(xiàn)概率也服從Beta分布,隨后基于語義距離的算法構(gòu)造其先驗參數(shù),并利用貝葉斯估計計算該先驗分布和統(tǒng)計樣本下的后驗概率,最后根據(jù)基于信息量的公式獲得主觀經(jīng)驗與客觀事實相結(jié)合的概念語義相似度。

本文后續(xù)內(nèi)容安排如下：第2節(jié)給出語義相似度計算的基本思想,第3節(jié)介紹本文提出的算法,第4節(jié)將本文提出的算法與現(xiàn)有的6種方法進行比較,最后在第5節(jié)總結(jié)全文。

2 基本思想

2.1 基本定義

本體的概念起源于哲學領(lǐng)域,是關(guān)于存在的學說。1993年美國斯坦福大學的G ruber給出了第一個在信息科學領(lǐng)域中的本體的正式定義[7]：本體是一個明確的概念化共享規(guī)范。目前關(guān)于本體的形式化定義很多,這里采用W 3C給出的定義[8]。

定義1：概念,也稱為類,是指具有相似特性的實體集合的名稱;某個概念所限定的具體事物對象,稱為個體;個體之間的相互聯(lián)系稱為關(guān)系。如：“小張”是概念“學生”的個體,他與《本體論》這本“書”之間存在“借閱”關(guān)系。

定義2：本體是一種領(lǐng)域知識表示手段,可以被表示為O=(C,R,I,A),其中C表示概念集合,R表示關(guān)系集合,I表示個體集合,A表示相關(guān)公理集合。

定義3：如果概念 A具有概念B的特性,稱概念A(yù)是概念B的子概念,記為A?B。如果A?B且A、B之間不存在滿足繼承關(guān)系的其他概念,則稱概念A(yù)是概念B的直接子概念,記為A=B?;。概念B的子概念集合記為ch(B),概念B的直接子概念數(shù)稱為該概念的出度deg?(B)。相應(yīng)地,也有直接父概念B,父概念集合an(B)。

定義4：領(lǐng)域本體中的概念集在繼承關(guān)系上構(gòu)成了概念格。格的頂節(jié)點稱為頂概念T,概念C與頂概念之間最短路徑上的邊數(shù)稱為該概念的深度dep(C)。

定義5：在領(lǐng)域本體中,概念的出現(xiàn)概率記為P(C)=P(c∈C),它表示從所有個體中隨機抽取某個個體是概念C個體的可能性。統(tǒng)計上,該數(shù)值可以用相對頻率P(C)=f req(C)/N,其中 f req(C)=∑c∈C count(c)表示概念C的所有個體數(shù),N為領(lǐng)域本體中全部個體數(shù)。

定義6：在領(lǐng)域本體中,概念C1和C2之間的相似度定義為[5]

其中LCS(C1,C2)表示概念C1和C2的最小公共父概念。

2.2 相似度基本假定

從公式(1)我們可以看出概念出現(xiàn)概率是計算兩個概念語義相似度的關(guān)鍵,而它需要在大樣本空間中統(tǒng)計基礎(chǔ)上獲得,本文提出了一種基于貝葉斯估計的算法以減小這種依賴。在下文展開之前,首先給出如下兩個基本假設(shè)：

1)領(lǐng)域知識庫中,“個體a是概念C中的個體”這一命題的取值只有True和False兩種可能,即隨機變量 x：=a∈C服從0～1分布;

2)若個體a是概念C中的個體,則它必然是C的父概念的個體,因此某概念的出現(xiàn)概率必然大于其子概念的出現(xiàn)概率,小于其父概念的出現(xiàn)概率。

顯然,這兩個基本假定是可以接受的,概念語義相似度具有如下性質(zhì)[5,9]：

1)當兩個概念相同時,相似度最大,規(guī)定為1;當兩個概念沒有共性時相似度最小,規(guī)定為0,即0≤Sim(C1,C2)≤1,且Sim(C,C)=1。

2)概念間相似度與二者所處層次有關(guān),概念層次越深,對事物刻畫越細,父子概念之間的差異越小,語義越接近。即Sim(C,C)≤Sim(C,C)。

3)某個概念的直接子概念越多,則分類越細,某個子概念對父概念的修飾越少,父子概念之間相似度越大。

3 基于貝葉斯估計的概念相似度算法原理

3.1 概念出現(xiàn)概率先驗分布構(gòu)造

根據(jù)基本假設(shè),從領(lǐng)域本體中任意選取某個體ai,事件 xi：=ai∈C是獨立同分布的,且服從概率為P的0～1分布。我們利用基于語義距離的算法構(gòu)造概率P的先驗分布。概念之間的語義距離是指概念層次結(jié)構(gòu)中節(jié)點之間最短路徑的加權(quán)和,路徑的權(quán)值可按公式(2)計算：

其中經(jīng)驗參數(shù)ρ>1反映了概念層次結(jié)構(gòu)中語義距離隨著深度變化的減小程度。兩個概念之間的語義距離為：

其中min{C1;C2}是概念C1和C2之間的最短路徑,因此C1和C2的語義相似度為：

經(jīng)驗參數(shù)μ為調(diào)節(jié)參數(shù)。根據(jù)公式(4)容易驗證對于任意概念C均有

3.3 Beta分布形狀參數(shù)計算

考慮到標準Beta分布變量范圍在[0,1]之間,做線性變換將上述Beta分布化為標準形式[10]：

根據(jù)Beta分布形狀參數(shù)計算公式[10]有：

其中,期望E=(?PM+4?P+?PN)/6,方差D=(?PN-?PM)2/36。

3.4 后驗出現(xiàn)概率

根據(jù)統(tǒng)計樣本在n個個體中有k個個體屬于概念C,下面根據(jù)最小貝葉斯風險估計計算θ的估計值。

設(shè)損失函數(shù)為 L(θ,δ),則統(tǒng)計判決 δ(X)的貝葉斯風險函數(shù)為

其中 f(X,θ)為 X在θ估計下的聯(lián)合分布,根據(jù)貝葉斯定理,可得：

其中c(X)是歸一化常數(shù)保證該分布是一個概率分布,將公式(10)代入公式(9)并交換積分次序后可得：

把損失函數(shù) L(θ,δ(X))關(guān)于后驗分布 π(θ|x)的加權(quán)平均稱為后驗風險,即

可以看出若某個 δ(X)使得后驗風險 Rπ(δ|x)達到最小,則它也使貝葉斯風險 Rπ(δ)達到最小。取損失函數(shù) L(θ,δ(X))=(δ(X)-θ)2代入公式(11)后得

其中：

因此當δ=-b/2a時,Rπ(δ|x)取得最小值。根據(jù)公式(10),有：

可以看出 π(θ|x)也服從 Beta分布,其超參數(shù)為k+α和n-k+β,即

因此使得Rπ(δ|x)取得最小值的δ為：

最后根據(jù)線性變換公式(6),有

這樣,我們便通過貝葉斯估計計算出概念出現(xiàn)概率P的后驗估計值。從公式(16)看出P為概念出現(xiàn)概率的主觀經(jīng)驗值根據(jù)統(tǒng)計特性的修正,當有大樣本時δ趨向于k/n體現(xiàn)了統(tǒng)計特性。當樣本很少,特別是k=0時并不能說某概念不可能出現(xiàn),仍然具有一定的出現(xiàn)可能,可通過主觀經(jīng)驗算法計算獲得。

4 算法實現(xiàn)及結(jié)果分析

4.1 算法實現(xiàn)過程

基于上面介紹的概念相似度BES算法原理,我們實現(xiàn)了本算法,并與其他幾種方法比較。在算法實驗中以WordNet[11]作為數(shù)據(jù)源,首先利用JAWS開發(fā)包,以entity為根節(jié)點,通過函數(shù)getSynsets獲得單詞的義元,通過函數(shù)getTagCount獲得該義元的出現(xiàn)次數(shù),通過函數(shù)getHyponyms獲得該義元的子概念。采用寬度優(yōu)先的方式逐層訪問各個概念節(jié)點信息,獲得其出現(xiàn)次數(shù)統(tǒng)計值,并保存到自定義的數(shù)據(jù)庫中。隨后根據(jù)提取出的概念層次結(jié)構(gòu),遍歷各個節(jié)點,依次計算各自的出現(xiàn)概率先驗分布參數(shù)和后驗估計值,由于這些數(shù)據(jù)的計算為實數(shù)運算,故算法復(fù)雜度取決于所采用的遍歷策略,可以證明為O(n)[12]。概念出現(xiàn)概率的貝葉斯估計算法過程如下：

算法CalcValues(C)過程如下：

4.2 算法實驗結(jié)果分析

由于不同的算法原理不同,計算結(jié)果也有較大差異,我們參考文獻[1]的做法：以M iller和Charles統(tǒng)計的30對概念間的主觀相似度數(shù)值作為參考標準,并與 Ted Pedersen 實現(xiàn)的 Wordnet：：Similarity[13]中其他相似度算法結(jié)果對比。實驗中取ρ=1.1,μ=0.5(x)=x,實驗結(jié)果見表1,表中BES為本算法結(jié)果,HSO 、LCH、WUP、RES、JCN 、LIN分別表示 Hirst&St-Onge方法,Leacock&Chodorow方法,Wu&Palmer方法,Resnik方法,Jiang&Conrath方法和Lin方法。

為了比較不同相似度算法的差異,我們參考文獻[1],計算各組數(shù)據(jù)與Human結(jié)果的相關(guān)系數(shù),以此作為衡量各種算法優(yōu)劣的指標,結(jié)果如表2所示,可以看出本文算法的相關(guān)系數(shù)稍高于其他算法。

表1 相似度數(shù)值對比計算結(jié)果

表2 相似度相關(guān)系數(shù)對比

4.3 參數(shù)對比實驗

為了分析統(tǒng)計數(shù)據(jù)和算法參數(shù)對相似度計算結(jié)果的影響,采用同樣的測試集做了對比實驗,實驗結(jié)果如表3所示。

表3 參數(shù)調(diào)整對比計算結(jié)果

續(xù)表

實驗中,前三組為帶有統(tǒng)計數(shù)據(jù)的結(jié)果,其中第1組ρ=1.1,μ=0.5;第2 組 ρ=1.2,μ=0.3;第3組ρ=1.4,μ=0.2。后三組為概念出現(xiàn)次數(shù)均為0時的結(jié)果,其中第4組ρ=1.1,μ=0.5;第5組ρ=1.2,μ=0.3;第 6組ρ=1.4,μ=0.2。計算各組數(shù)據(jù)與H um an結(jié)果的相關(guān)系數(shù),結(jié)果如表4所示。

表4 參數(shù)調(diào)整對比實驗相關(guān)系數(shù)

從實驗結(jié)果看出,盡管隨著統(tǒng)計數(shù)據(jù)和參數(shù)的變化,相似度結(jié)果也有所不同,但與主管經(jīng)驗的相關(guān)系數(shù)變化很小,因此本算法對數(shù)據(jù)和參數(shù)的變動不敏感。

5 結(jié)束語

概念相似度計算是本體映射、服務(wù)發(fā)現(xiàn)、語義檢索等技術(shù)的關(guān)鍵基礎(chǔ)。本文的主要貢獻如下：提出了一種基于貝葉斯估計的概念出現(xiàn)概率算法;在此基礎(chǔ)上概念相似度計算綜合考慮了人為主觀經(jīng)驗和客觀統(tǒng)計樣本,改進了傳統(tǒng)方法的不足,具有較好的實用性。結(jié)合WordNet的算法實驗表明,本算法與人為主觀經(jīng)驗之間具有最大的相關(guān)系數(shù)。

由于本算法需要首先根據(jù)當前概念層次結(jié)構(gòu)和出現(xiàn)次數(shù)計算各個概念的出現(xiàn)概率,當概念數(shù)較多,網(wǎng)絡(luò)復(fù)雜時,如使用WordNet時,它必須構(gòu)造新的數(shù)據(jù)庫以便存放每個概念的出現(xiàn)概率,需要占用額外的資源。另外,由于概念相似度大小并沒有客觀標準,僅依賴少量測試數(shù)據(jù)并不能充分說明各種方法之間的性能差異,且主觀經(jīng)驗值是否合理也有待商榷,因此如何評價各種算法的優(yōu)劣性還值得進一步研究。

[1] A lexander Budanitsky,Graeme H irst.Evaluating Word-Net-based Measures of Lexical Semantic Relatedness[J].Computational Linguistics,2006,1(32)：13-49.

[2] 李峰,李芳.中文詞語語義相似度計算——基于《知網(wǎng)》2000[J].中文信息學報,2007,21(3)：99-105.

[3] 江敏,肖詩斌,王弘蔚,等.一種改進的基于《知網(wǎng)》的詞語語義相似度計算[J].中文信息學報,2008,22(5)：84-89.

[4] Anna Form ica.Ontology-based concept similarity in Formal Concep t Analysis[J].Information Sciences,2006,176(18)：2624-2641.

[5] Dekang Lin.An in formation-theoretic definition o f similarity[C]//Proceedings of the 15thInternational Conference on M achine Learning,San Francisco：M organ Kaufmann.1998：296-304.

[6] 陳希孺.數(shù)理統(tǒng)計引論[M].北京：科學出版社,1999：131-159.

[7] Thomas R.G ruber.A translation approach to portable ontology specification[J].Know ledge Acquisition,1993,5(2)：1992-2201.

[8] W 3C.OW LW eb Ontology Language Reference[EB/OL][2009-7-8].http：//www.w3.org/TR/ow l-ref.

[9] 劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計算[C]//臺北：第三屆漢語詞匯語義學研討會論文集.2002：59-76.

[10] 方開泰,許建倫.統(tǒng)計分布[M].北京：科學出版社.,1987：246-258.

[11] Princeton University Cognitive Science Laboratory.W ordNet-a lexical database for the English language[EB/OL][2009-7-9].http：//wordnet.p rinceton.edu.

[12] Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Introduc tion to A lgorithms[M],M IT Press,2001：224-227.

[13] Ted Pedersen.W ordnet：：Sim ilarity[EB/OL][2009-7-9],http：//w nsim ilarity.sourceforge.net.