一種基于大規(guī)模知識(shí)庫(kù)的語(yǔ)義相似性計(jì)算方法

張立波 孫一涵 羅鐵堅(jiān)

1(中國(guó)科學(xué)院軟件研究所 北京 100190) 2(中國(guó)科學(xué)院大學(xué) 北京 101408)

(zsmj@hotmail.com)

一種基于大規(guī)模知識(shí)庫(kù)的語(yǔ)義相似性計(jì)算方法

張立波1孫一涵2羅鐵堅(jiān)2

1(中國(guó)科學(xué)院軟件研究所 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 101408)

(zsmj@hotmail.com)

人類知識(shí)總量不斷增加，依靠人類產(chǎn)生的結(jié)構(gòu)化大數(shù)據(jù)進(jìn)行語(yǔ)義分析在推薦系統(tǒng)和信息檢索等領(lǐng)域都有著重要的應(yīng)用.在這些領(lǐng)域中，首要解決的問(wèn)題是語(yǔ)義相似性計(jì)算，之前的研究通過(guò)運(yùn)用以維基百科為代表的大規(guī)模知識(shí)庫(kù)取得了一定突破，但是其中的路徑并沒(méi)有被充分利用.研究基于人類思考方式的雙向最短路徑算法進(jìn)行單詞和文本的相似性評(píng)估，以充分利用知識(shí)庫(kù)中的路徑信息.提出的算法通過(guò)在維基百科中抽取出顆粒度比詞條更細(xì)密的節(jié)點(diǎn)之間的超鏈接關(guān)系，并首次驗(yàn)證了維基百科之間的普遍連通性，并對(duì)2個(gè)詞條之間的平均最短路徑長(zhǎng)度進(jìn)行評(píng)估.最后，在公開(kāi)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果顯示，算法在單詞相似度得分上明顯優(yōu)于現(xiàn)有算法，在文本相似度的得分上趨于先進(jìn)水平.

大規(guī)模知識(shí)庫(kù)；語(yǔ)義相似性；維基百科；最短距離；連通性

利用計(jì)算機(jī)進(jìn)行語(yǔ)義相似度評(píng)估是人工智能領(lǐng)域的一個(gè)瓶頸問(wèn)題，這個(gè)問(wèn)題的核心是如何讓計(jì)算機(jī)模擬人類的思考方式.然而人類思維模式復(fù)雜，難以模仿，但一個(gè)基本事實(shí)是，人類的思考模式是基于自身的經(jīng)歷和經(jīng)驗(yàn)所形成的知識(shí)來(lái)進(jìn)行推理、分析和決斷.因此，利用大規(guī)模的知識(shí)庫(kù)賦予計(jì)算機(jī)一種類似人類的知識(shí)結(jié)構(gòu)模型，是一個(gè)根本的解決途徑.人類根據(jù)自身掌握的知識(shí)進(jìn)行聯(lián)想，對(duì)2個(gè)單詞、段落或文本之間的相似性進(jìn)行判斷，本文通過(guò)提取維基百科中的雙向最短路徑來(lái)模擬人類的聯(lián)想機(jī)制進(jìn)行相似性評(píng)估.

語(yǔ)義相似度在自然語(yǔ)言處理和信息檢索領(lǐng)域中一直都有著重要的應(yīng)用，例如問(wèn)答系統(tǒng)、拼寫(xiě)檢查、文本翻譯等領(lǐng)域[1].傳統(tǒng)方法主要基于單詞重疊度來(lái)評(píng)估語(yǔ)義相關(guān)性，這在論文查重系統(tǒng)中有著廣泛應(yīng)用，但如果使用不同的單詞表示同樣的含義時(shí)，這類方法明顯無(wú)法適用，它的缺陷在于簡(jiǎn)單地將單詞作為評(píng)估對(duì)象，而沒(méi)有考慮單詞之間的內(nèi)在聯(lián)系[2].概率潛在語(yǔ)義分析等方法利用了文章中的單詞和主題的關(guān)系，但是沒(méi)有考慮到單詞在知識(shí)結(jié)構(gòu)中的關(guān)系[3].近些年來(lái)，一些新的算法考慮到可以利用包含人類知識(shí)結(jié)構(gòu)的大規(guī)模知識(shí)庫(kù)，例如百科全書(shū)和語(yǔ)料庫(kù)進(jìn)行語(yǔ)義相似性評(píng)估[4]，具體來(lái)說(shuō)，它們利用百科中2個(gè)詞條頁(yè)面中包含的文本和鏈接捕獲真實(shí)世界的知識(shí)結(jié)構(gòu)，進(jìn)而評(píng)估語(yǔ)義相似度.

在人類編撰形成的知識(shí)庫(kù)中，大英百科全書(shū)和維基百科全書(shū)最具有代表性，它們經(jīng)過(guò)人工的梳理和編輯，構(gòu)成以詞條為單位的人類知識(shí)寶庫(kù).相比大英百科，維基百科在保證了同等正確率的同時(shí)，包含了更多的詞條量.我們將維基百科詞條中含有鏈接的單詞稱為節(jié)點(diǎn)，節(jié)點(diǎn)之間的最短路徑能夠反映出人類聯(lián)想機(jī)制，為了驗(yàn)證這一點(diǎn)，我們提出了一種基于最短路徑對(duì)語(yǔ)義相關(guān)性進(jìn)行評(píng)估的算法.與之前的算法不同，本文第1次對(duì)維基百科中詞條之間的連通性進(jìn)行驗(yàn)證，證明了維基百科中的詞條具有普遍聯(lián)系，2個(gè)節(jié)點(diǎn)之間一定存在一條通路，即從一個(gè)概念出發(fā)，經(jīng)過(guò)有限次數(shù)的跳轉(zhuǎn)鏈接可以到達(dá)另一個(gè)任意節(jié)點(diǎn).在相關(guān)的研究論文中，研究者假設(shè)任意2個(gè)詞條之間都可以建立路徑關(guān)系，但是缺乏證明；最新的一些論文使用隨機(jī)游走算法尋找路徑，而我們使用了最短路徑.傳統(tǒng)的有關(guān)最短路徑的算法是基于詞條所屬分類間的最短路徑，而我們使用了更細(xì)密的節(jié)點(diǎn)；大部分對(duì)維基進(jìn)行的研究都將其限定在100萬(wàn)節(jié)點(diǎn)左右，而我們使用了1 200萬(wàn)節(jié)點(diǎn)進(jìn)行更加細(xì)致的探究.本文提出了一種基于維基百科節(jié)點(diǎn)的最短路徑進(jìn)行語(yǔ)義相似性分析的算法，并驗(yàn)證了通過(guò)最短路徑能夠模擬人類的聯(lián)想機(jī)制對(duì)語(yǔ)義相似性進(jìn)行評(píng)估.

1 相關(guān)工作

傳統(tǒng)語(yǔ)義關(guān)系的分析需要依靠人類自身知識(shí)和經(jīng)驗(yàn)的背景進(jìn)行推理和聯(lián)想，而這對(duì)計(jì)算機(jī)一直是難以克服的障礙.為了探索2個(gè)詞條之間的關(guān)系，計(jì)算機(jī)必須獲取大量相關(guān)領(lǐng)域的背景知識(shí)，而之前的相關(guān)工作更多地依靠統(tǒng)計(jì)而忽略了背景知識(shí)；另外一些基于背景知識(shí)進(jìn)行語(yǔ)義相關(guān)的研究由于知識(shí)總量的限制無(wú)法取得很好的效果；一些論文基于網(wǎng)頁(yè)鏈接對(duì)語(yǔ)義進(jìn)行分析，取得了一定的突破，但是由于網(wǎng)頁(yè)中的知識(shí)顆粒度較粗，并且知識(shí)含量較為稀疏，因此不能夠反映出某個(gè)知識(shí)點(diǎn)的全貌.2005年，Giles[5]指出，維基百科的廣度和深度都值得信任，從此之后，開(kāi)啟了基于維基百科進(jìn)行語(yǔ)義分析的熱潮.

本文系統(tǒng)地收集了在維基百科的基礎(chǔ)上提出的利用人類知識(shí)庫(kù)進(jìn)行語(yǔ)義分析的方法，如表1所示.傳統(tǒng)的方法主要有2類：1)基于內(nèi)容的方法；2)基于鏈接的方法.Gabrilovich等人[6]提出一種名為顯示語(yǔ)言分析的方法，這種方法通過(guò)維基百科收集概念，將文本中的內(nèi)容與收集的概念建立矩陣關(guān)系，但缺乏對(duì)人類知識(shí)體系的使用.Zesch等人[7]證明了使用維基百科能夠提高之前方法的效果，但性能的提升受到制約.Hassan等人[8]衡量2個(gè)概念之間的跨越關(guān)系，并通過(guò)顯示語(yǔ)言分析來(lái)建立概念的矢量表述.Syed等人[9]將維基百科詞條作為本體，使用3種方式將關(guān)鍵詞、主題與文本結(jié)合，但是缺乏對(duì)詞條路徑關(guān)系的考慮.Coursey等人[10]建立了概念和分類關(guān)系圖，提出了一個(gè)自動(dòng)化的主題分類方法，但是無(wú)法解決分類數(shù)量有限和概念從屬多種分類的問(wèn)題.Gabrilovich等人[11]通過(guò)建立一個(gè)語(yǔ)義轉(zhuǎn)換器對(duì)概念建立權(quán)重矢量，并通過(guò)矢量之間的比較進(jìn)行語(yǔ)義相關(guān)性評(píng)估，這種方法僅基于文本內(nèi)容，在概念之間的關(guān)系上只考慮了所屬分類之間的關(guān)系，而忽視了超鏈接形成的路徑.

另外一些研究，利用路徑信息進(jìn)行語(yǔ)義相似度評(píng)估，例如Ponzetto等人[12]將概念映射到所屬的分類中，通過(guò)2個(gè)分類之間的路徑長(zhǎng)度對(duì)2個(gè)概念的相關(guān)性進(jìn)行評(píng)估，但是分類之間的路徑關(guān)系僅僅是簡(jiǎn)單的樹(shù)形結(jié)構(gòu).Milne等人[13-16]通過(guò)計(jì)算詞條所包含鏈接的重復(fù)率進(jìn)行相關(guān)性評(píng)估，這種方法無(wú)法對(duì)概念之間的關(guān)系進(jìn)行精確計(jì)算.與Yeh等人[14]的方法類似，有研究者提出了一種基于維基漫步方法, Yazdani等人[4]提出一種訪問(wèn)概率的方法來(lái)計(jì)算節(jié)點(diǎn)之間的距離，這種方法僅僅基于概念所屬分類的路徑關(guān)系，或者是特定2個(gè)詞條包含超鏈接的重疊性.劉均等人[17]設(shè)計(jì)了一種利用維基百科鏈接關(guān)系的13維特征適量來(lái)進(jìn)行關(guān)系抽取，但是缺乏對(duì)節(jié)點(diǎn)之間通路的考慮.Singer等人[18]使用了一種維基游戲，通過(guò)人們的點(diǎn)擊來(lái)尋找2個(gè)詞條之間的路徑關(guān)系，然而由于游戲的特殊性質(zhì)，會(huì)對(duì)參與測(cè)試的人們?cè)斐蓵r(shí)間壓力，因此無(wú)法準(zhǔn)確模擬人類的思考模式.Niebler等人[19]注意到了無(wú)約束航行數(shù)據(jù)，維基百科點(diǎn)擊流數(shù)據(jù)[20]記錄了人們?cè)谝粋€(gè)維基詞條中如何進(jìn)行下一次鏈接點(diǎn)擊.Dallmann等人[15]基于這個(gè)數(shù)據(jù)集，使用隨機(jī)游走的算法模擬了人類的超鏈接點(diǎn)擊行為，但是隨機(jī)游走往往無(wú)法獲取最佳路徑，而最短路徑才對(duì)人類的決策最有意義.

與傳統(tǒng)方法中利用詞條中的鏈接關(guān)系不同，我們通過(guò)尋找2個(gè)節(jié)點(diǎn)之間的鏈接通路，來(lái)描述它們之間的關(guān)系.本文提出一種新的方法，通過(guò)結(jié)構(gòu)化的維基百科節(jié)點(diǎn)中的最短路徑關(guān)系，對(duì)2個(gè)詞條之間的關(guān)系進(jìn)行刻畫(huà).

2 主要工作

2.1預(yù)處理

互聯(lián)網(wǎng)百科全書(shū)是當(dāng)前能夠隨意查閱的最大的、最完整的人類知識(shí)庫(kù)，其中維基百科是人類共同參與編撰的規(guī)模最大的互聯(lián)網(wǎng)多語(yǔ)言百科全書(shū)，其與專業(yè)人士編撰的大英百科全書(shū)具有相近的正確率，但由于編撰自由，發(fā)展更加迅速.截至2016年7月25日，英文維基百科總計(jì)擁有5 201 640篇文章、39 827 021個(gè)頁(yè)面，覆蓋了人類的大部分知識(shí)領(lǐng)域,詞條為最小知識(shí)單元，以鏈接跳轉(zhuǎn)表現(xiàn)知識(shí)之間的聯(lián)系.維基百科本身的鏈接結(jié)構(gòu)是人類經(jīng)過(guò)時(shí)間積累的智慧結(jié)晶，編撰結(jié)構(gòu)和人類的思考方式高度吻合，因此本文選取維基百科作為基本數(shù)據(jù)集.我們使用原始數(shù)據(jù)集是完整的維基百科版本(2016-06-01)，解壓后得到一個(gè)53.4 GB的XML文件.這個(gè)XML文件包含了所有的詞條，而每個(gè)詞條中都包含了指向其他詞條的超鏈接.傳統(tǒng)的算法主要關(guān)注詞條之間的關(guān)系，而我們希望能從更小的維度進(jìn)行觀察，本文將每個(gè)詞條中的超鏈接對(duì)應(yīng)的單詞作為研究對(duì)象，稱之為節(jié)點(diǎn), 該數(shù)據(jù)集包含了所有節(jié)點(diǎn)之間的鏈接關(guān)系.我們處理后所使用的節(jié)點(diǎn)數(shù)量為1 200萬(wàn)，這是傳統(tǒng)算法中研究對(duì)象數(shù)量的5～10倍.

本文的預(yù)處理工作主要包括5個(gè)步驟：

1) 在原始XML文件中，先抽取詞條本身和其文本中超鏈接對(duì)應(yīng)的單詞.這個(gè)數(shù)量遠(yuǎn)大于詞條, 我們稱之為節(jié)點(diǎn).

2) 規(guī)整詞條格式，在節(jié)點(diǎn)中去除不合法的鏈接和詞條，例如詞條包含的錨鏈接等.

3) 刪除空指向的詞條.

4) 因?yàn)槲募杏行┕?jié)點(diǎn)首字母為小寫(xiě)，而在維基百科網(wǎng)頁(yè)中，全部詞條的首字母均為大寫(xiě)，因此將文檔中節(jié)點(diǎn)的小寫(xiě)首字母轉(zhuǎn)化為大寫(xiě).

5) 在節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)中，用Hadoop集群將單項(xiàng)鏈接轉(zhuǎn)化為雙向鏈接，即把鏈接構(gòu)成的有向圖轉(zhuǎn)化為無(wú)向圖.

2.2節(jié)點(diǎn)普遍聯(lián)系的驗(yàn)證

在基于路徑的語(yǔ)義分析的研究中，利用超鏈接尋找從一個(gè)詞條到另一個(gè)詞條的通路，都是建立在存在通路的假設(shè)前提下.雖然根據(jù)經(jīng)驗(yàn)可以基本判斷維基百科的詞條間應(yīng)該是普遍連通的，但是缺乏有力驗(yàn)證.我們?cè)陬A(yù)處理的基礎(chǔ)上對(duì)維基百科中節(jié)點(diǎn)的普遍聯(lián)系進(jìn)行驗(yàn)證，利用廣度優(yōu)先搜索算法在節(jié)點(diǎn)構(gòu)成的無(wú)向圖中生成連通分量.

我們獲得了節(jié)點(diǎn)中連通分量的分布，如表2所示，維基百科中節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)中，一共包含10 441個(gè)連通分量，這些連通分量一共含有12 280 497個(gè)節(jié)點(diǎn).其中最大聯(lián)通分量中含有12 269 222個(gè)節(jié)點(diǎn),可以清楚地看出，99.91%的節(jié)點(diǎn)都包含在最大聯(lián)通分量中.經(jīng)過(guò)觀察，其他聯(lián)通分量包含的節(jié)點(diǎn)是一些特殊字符，因此我們將最大聯(lián)通分量視為研究對(duì)象.這就意味著，如果我們將整個(gè)維基百科網(wǎng)絡(luò)視為無(wú)向圖，任意2個(gè)節(jié)點(diǎn)之間都存在著通路.

Table 2 Connected Component Number and the

2.3維基百科節(jié)點(diǎn)間的最短路徑

維基百科是由詞條構(gòu)成，詞條文本中含有節(jié)點(diǎn)間的鏈接關(guān)系.每一個(gè)維基百科詞條的頁(yè)面中，都包含了與之相關(guān)的其他詞條，通過(guò)這些詞條對(duì)其進(jìn)行解釋，因此我們可以直接使用維基百科而無(wú)需對(duì)文本做深層次的語(yǔ)義理解.圖1顯示了維基百科詞條間的鏈接關(guān)系，圓點(diǎn)代表詞條，顏色代表詞條距離選定詞條的不同層級(jí)，虛線圓代表處于同一層級(jí)的詞條，紅色箭頭代表詞條間通過(guò)超鏈接的跳轉(zhuǎn).具體來(lái)說(shuō)，紅色圓圈代表選定的初始節(jié)點(diǎn);綠色圓圈代表與初始節(jié)點(diǎn)存在直接鏈接關(guān)系的詞條，也就是從初始節(jié)點(diǎn)出發(fā)，可以通過(guò)一次鏈接到達(dá)綠色節(jié)點(diǎn)，我們把這些綠色節(jié)點(diǎn)定義為第1層節(jié)點(diǎn).

Fig. 1 The hyperlink relationship in Wikipedia nodes圖1 維基百科中節(jié)點(diǎn)的鏈接關(guān)系

類似地，從綠色節(jié)點(diǎn)詞條經(jīng)過(guò)一次跳轉(zhuǎn)，可以到達(dá)紫色節(jié)點(diǎn)，我們把紫色節(jié)點(diǎn)定義為初始節(jié)點(diǎn)的第2層節(jié)點(diǎn).以此類推，我們把藍(lán)色節(jié)點(diǎn)定義為初始節(jié)點(diǎn)的第3層節(jié)點(diǎn).需要額外說(shuō)明的是，在計(jì)算第n層節(jié)點(diǎn)的詞條時(shí)，先排除處于n層中但與n層之前重復(fù)的部分詞條.我們認(rèn)為2個(gè)節(jié)點(diǎn)之間的最短路徑越短，表明他們之間的關(guān)系越密切；2個(gè)節(jié)點(diǎn)之間的路徑越長(zhǎng)，則表明他們之間的關(guān)系越遙遠(yuǎn).這個(gè)觀點(diǎn)也與人類的思維模式相同，面對(duì)一個(gè)具體問(wèn)題，人類首先會(huì)聯(lián)想到與這個(gè)問(wèn)題最相關(guān)的因素，之后再深入到每個(gè)因素之中.舉個(gè)例子，當(dāng)提到“Milk”時(shí)，人們首先會(huì)想到有關(guān)的產(chǎn)品，例如“Cheese”等；通過(guò)“Cheese”會(huì)深入聯(lián)想到制作所需的材料，例如“Pepper”等.而這和維基百科的構(gòu)建方式剛好吻合，在維基百科中，詞條“Cheese”和“Pepper”，分別是詞條“Milk”的第1層和第2層上的節(jié)點(diǎn).

2.4基于雙向最短路徑的語(yǔ)義相似性算法

在使用維基百科評(píng)估語(yǔ)義相似度的方法中，大多都利用了2個(gè)單詞之間超鏈接所構(gòu)建的路徑[18].傳統(tǒng)算法將單詞A到單詞B的路徑長(zhǎng)度和單詞B到單詞A的路徑長(zhǎng)度看作是等同的，并隨機(jī)地從單詞A和單詞B中選取一個(gè)單詞作為起始點(diǎn)，然后在這種模式下探尋到達(dá)另一個(gè)單詞的超鏈接路徑.但是這種路徑方式有很大的局限性，因?yàn)榇蟛糠智闆r下，2種方向的路徑長(zhǎng)度并不相同，可以通過(guò)一個(gè)顯而易見(jiàn)的例子進(jìn)行說(shuō)明：當(dāng)提到單詞“成都”時(shí)，人們會(huì)自然地想到“中國(guó)”；但是當(dāng)提到“中國(guó)”時(shí)，卻很難想到成都.從這個(gè)例子可以明顯看出，從“成都”到“中國(guó)”和從“中國(guó)”到“成都”的距離(聯(lián)想難度)明顯不同.我們進(jìn)一步通過(guò)維基百科的鏈接結(jié)構(gòu)進(jìn)行解釋，如圖2所示為傳統(tǒng)算法考慮路徑時(shí)鏈接路徑的模式，給定的2個(gè)單詞“Night”和“System”，可以通過(guò)一個(gè)“Energy”頁(yè)面進(jìn)行中轉(zhuǎn)，于是這2個(gè)單詞的最短距離是2.傳統(tǒng)算法的思考模式將整個(gè)維基的鏈接網(wǎng)絡(luò)看成一個(gè)無(wú)向圖，任選一個(gè)單詞作為起點(diǎn)并不會(huì)影響最短路徑的長(zhǎng)度.本文算法的靈感來(lái)自于對(duì)人類思維模式的思考：當(dāng)人類考慮單詞A和單詞B相似性時(shí)，不會(huì)采用單方向的思考方式，而是采用雙向的思考模式，正向距離和反向距離都會(huì)影響思考過(guò)程.我們將整個(gè)維基鏈接結(jié)構(gòu)視為有向圖，在有向圖中尋找最短路徑.

Fig. 2 The representation of traditional shortest link path圖2 傳統(tǒng)鏈接最短路徑表示

Fig. 3 The representation of bidirectional shortest link path圖3 雙向鏈接最短路徑表示

如圖3所示，人類聯(lián)想2個(gè)單詞相關(guān)性的最優(yōu)解法是通過(guò)雙向最短路徑(我們稱之為前向路徑和反向路徑)，這是因?yàn)榫S基百科中2個(gè)單詞會(huì)因?yàn)槠瘘c(diǎn)和終點(diǎn)的轉(zhuǎn)換引起最短路徑的長(zhǎng)度不同.具體來(lái)說(shuō)，前向路徑中從“Night”出發(fā)，經(jīng)過(guò)“Energy”1次跳轉(zhuǎn)后到達(dá)“System”；反向路徑中從“System”出發(fā)，依次經(jīng)過(guò)“Interaction”，“Action”，“Time”3次跳轉(zhuǎn)后到達(dá)“Night”.由此看出，“Night”和“System”中的前向最短路徑長(zhǎng)度為2，反向最短距離為4.

我們使用維基百科有2個(gè)原因：

1) 維基百科包含多種語(yǔ)言，其中英文版本約有500萬(wàn)的詞條和1 000萬(wàn)的標(biāo)題，是現(xiàn)今人類在網(wǎng)絡(luò)中最大的知識(shí)倉(cāng)庫(kù)，它由人類經(jīng)過(guò)結(jié)構(gòu)化編撰而成，正確率和權(quán)威性已經(jīng)得到了普遍認(rèn)可;

2) 維基百科具有良好的成長(zhǎng)性，在每個(gè)知識(shí)的寬度和深度上，隨著時(shí)間穩(wěn)步增長(zhǎng).

我們定義2個(gè)單詞之間的最短路徑長(zhǎng)度：

其中,LF為前向最短路徑長(zhǎng)度，LB為反向最短路徑長(zhǎng)度.在通過(guò)雙向最短路徑進(jìn)行語(yǔ)義相似性評(píng)估時(shí)，有一個(gè)需要解決的核心問(wèn)題：如何設(shè)定最短路徑的步長(zhǎng)上限.因?yàn)楸M管在我們驗(yàn)證了節(jié)點(diǎn)的普遍聯(lián)通性，但是尋找2個(gè)節(jié)點(diǎn)間的最短路徑時(shí)，仍會(huì)遇到路徑過(guò)長(zhǎng)的問(wèn)題.為了解決這個(gè)問(wèn)題，我們?cè)O(shè)計(jì)了一個(gè)實(shí)驗(yàn)：隨機(jī)選取300 000個(gè)單詞對(duì)，用廣度優(yōu)先搜索算法找到每對(duì)單詞的前向最短路徑長(zhǎng)度，最后求得2個(gè)節(jié)點(diǎn)間的平均最短路徑長(zhǎng)度值E(L)=3.84，標(biāo)準(zhǔn)偏差σ=1.73.根據(jù)切比雪夫不等式：

令k=3可得平均路徑長(zhǎng)度L≥9.03的概率小于19，因此我們將最短路徑的步長(zhǎng)上限設(shè)置為8，即超過(guò)8步就認(rèn)為2個(gè)單詞不存在相似性.

Fig. 4 The similarity evaluation of texts based on bidirectional shortest path圖4 基于雙向最短路徑的文本相似性算法

下面我們通過(guò)矩陣分塊來(lái)計(jì)算Text1文本和Text2文本的相關(guān)性：

1) 我們對(duì)矩陣進(jìn)行重排，假設(shè)|A∩B|=p，重排元組A和B使得：

這是將A和B中共有的單詞排列于各自元組的前端，并保證下標(biāo)相同.

Fig. 5 Matrix partitioning圖5 矩陣分塊

3) 對(duì)子矩陣進(jìn)行重排，使得：

?(p+1)≤r≤s≤m，tr≥ts，

4) 令q=min(m,n)，?。?/p>

我們進(jìn)一步得到一個(gè)q×q的方陣.

即相互匹配的元素下標(biāo)相同.

3 實(shí)驗(yàn)評(píng)估

3.1WS-353Ex數(shù)據(jù)集

在語(yǔ)義相關(guān)性評(píng)估中，研究者通常會(huì)使用標(biāo)準(zhǔn)的黃金數(shù)據(jù)集WS-353[21](WordSimilarity-353).WS-353中包含了353對(duì)英語(yǔ)單詞，每一對(duì)都用一個(gè)范圍在0～10的分?jǐn)?shù)來(lái)表示它們的相關(guān)程度.每個(gè)分?jǐn)?shù)都是由16個(gè)人分別打出，最后取平均值而得到.WS-353是根據(jù)人類的聯(lián)想和判斷，確定對(duì)語(yǔ)義相似度的評(píng)估標(biāo)準(zhǔn).因此，我們可以通過(guò)與其結(jié)果的對(duì)比，判斷本文提出的算法能否與人類的聯(lián)想機(jī)制契合.

我們對(duì)WS-353進(jìn)行了改進(jìn)，稱之為WS-353Ex(WS-353 extend version)，這是因?yàn)槠渲幸恍﹩卧~無(wú)法映射到維基百科的詞條中.之前的研究中一些研究者也發(fā)現(xiàn)了這一問(wèn)題，但是一直沒(méi)有得到有效的解決.Milne等人[13]選擇直接刪除60個(gè)不合適的單詞.Singer 等人[18]也發(fā)現(xiàn)了這個(gè)問(wèn)題，并給出了改進(jìn)版的數(shù)據(jù)集WikipediaSimilarity-353，將單詞對(duì)刪減到308個(gè),但是Singer等人忽視了引起這個(gè)問(wèn)題的真正原因.我們發(fā)現(xiàn)，自從2002年WS-353提出之后，維基百科經(jīng)過(guò)14年的發(fā)展和變化，在數(shù)量級(jí)上發(fā)生了數(shù)十倍的增長(zhǎng)，導(dǎo)致部分單詞無(wú)法映射到維基百科中進(jìn)行路徑探索的原因是WS-353中的一些單詞出現(xiàn)在重定向頁(yè)面和消歧義頁(yè)面.為了解決這個(gè)問(wèn)題，我們做了2項(xiàng)工作：

1) 將重定向的單詞進(jìn)行替換，例如 “Diego Maradona”更換為“Maradona”，“theater”更換為“theatre”；

2) 將維基百科中無(wú)法查到的單詞刪除，例如“defeating”.

我們對(duì)2002年的數(shù)據(jù)集WS-353進(jìn)行了改進(jìn)和修正，形成WS-353Ex，最后保留了344對(duì)單詞.如表3所示，WS-353在最初的3個(gè)維度(Word1，Word2，human mean)的基礎(chǔ)上，增加了3個(gè)新的維度：前向最短路徑長(zhǎng)度f(wàn)、反向最短路徑長(zhǎng)度b和平均最短路徑長(zhǎng)度a.以“tiger”和“cat”舉例，人類對(duì)2個(gè)單詞相似性的打分是7.35，從“tiger”出發(fā)經(jīng)過(guò)2步能夠鏈接到“cat”，從“cat”出發(fā)經(jīng)過(guò)3步能夠鏈接到“tiger”， “tiger” 與“cat”的平均最短路徑為2.5.

Table 3 Demonstration of WS-353Ex Dataset表3 WS-353Ex數(shù)據(jù)集樣例

3.2語(yǔ)義相似性評(píng)估

在本節(jié)中，我們分別使用WS-353Ex和Lee[22]數(shù)據(jù)集來(lái)驗(yàn)證算法在單詞和文本相似度評(píng)估的有效性.首先使用WS-353Ex數(shù)據(jù)集進(jìn)行單詞相似度評(píng)估，具體步驟如下：

1) 基于在3.1節(jié)中相關(guān)方法所計(jì)算出的WS-353Ex中每對(duì)單詞之間的f和b，求出：

2) 采用嶺回歸方法，分別使用單詞對(duì)的f，b，a與對(duì)應(yīng)的人類打分進(jìn)行擬合：

其中，h代表人類的打分，w=(w1,w2,…, wp) 代表系數(shù)，w0代表截?cái)辔覀兪褂脦X回求解：

其中，α是復(fù)雜性系數(shù)，α的值越大, 收縮性越好，也就使得系數(shù)擁有更強(qiáng)的魯棒性.

3) 我們采用斯皮爾曼等級(jí)相關(guān)系數(shù)、皮爾遜相關(guān)系數(shù)和谷本系數(shù)[1,4]來(lái)評(píng)價(jià)預(yù)測(cè)擬合模型的正確性，評(píng)估的分?jǐn)?shù)區(qū)間為0～1，越趨近于1說(shuō)明該方法的準(zhǔn)確度越高.實(shí)驗(yàn)結(jié)果驗(yàn)證了通過(guò)最短路徑算法進(jìn)行相似性評(píng)估的準(zhǔn)確性.

本文設(shè)計(jì)了3組實(shí)驗(yàn)，分別使用f，b，a與人類打分值進(jìn)行組合預(yù)測(cè)：實(shí)驗(yàn)隨機(jī)選取了測(cè)試集和驗(yàn)證集(分別采用3:7，5:5，7:3的比例)，重復(fù)500次取平均值.實(shí)驗(yàn)結(jié)果如表4所示，單獨(dú)使用f和b最高只能達(dá)到0.51和0.53的分?jǐn)?shù)，而使用a能夠?qū)⒎謹(jǐn)?shù)穩(wěn)定在0.84.為了進(jìn)一步的評(píng)估，我們將本文的算法與之前的一些重要相關(guān)研究結(jié)果作了比較，如表5顯示，Milne等人[13]所提出的一種基于超鏈接相似度的方法可以將分?jǐn)?shù)提高到0.78.在本文基本方法的基礎(chǔ)上，我們觀察到在WS-353Ex數(shù)據(jù)集中有一些明顯錯(cuò)誤樣本數(shù)據(jù)，人工刪除這些誤差樣本后重新進(jìn)行評(píng)估，能夠?qū)?zhǔn)確率提高到0.90.從表5中可以看出，通過(guò)本文提出的算法與8種傳統(tǒng)算法的比較，驗(yàn)證了所述算法在單詞相似度計(jì)算的有效性上明顯超越現(xiàn)有算法.

Table 4 Comparison of Word Similarity Using Three Kinds of Shortest Path

為了探究在評(píng)估文本相似度的效果，我們基于雙向最短路徑算法在Lee數(shù)據(jù)集[26]上進(jìn)行了驗(yàn)證，這個(gè)數(shù)據(jù)集包含了50個(gè)文本，以及每一對(duì)文本對(duì)應(yīng)的人類打出的相似性分?jǐn)?shù).實(shí)驗(yàn)中隨機(jī)抽取1 000對(duì)文本進(jìn)行實(shí)驗(yàn)，得到分?jǐn)?shù)的平均值.如表6所示，Hassan等人[8]提出基于小規(guī)模語(yǔ)料庫(kù)進(jìn)行訓(xùn)練的LSA算法，能夠得到0.69的分?jǐn)?shù).Gabrilovich等人[11]提出了ESA算法，并得到0.75的分?jǐn)?shù).本文通過(guò)雙向最短路徑算法進(jìn)行文本相似性分析，能夠得到0.77的分?jǐn)?shù).基于雙向最短路徑的算法在單詞相似性的評(píng)估上取得了很好的效果，但是在文本相似度上效果與之前的算法效果相當(dāng)，我們認(rèn)為這主要因?yàn)橛?xùn)練集較小，僅基于數(shù)據(jù)集WS-353Ex，只包含344對(duì)單詞；另一個(gè)影響因素是我們僅通過(guò)文本在維基百科網(wǎng)絡(luò)中的鏈接關(guān)系進(jìn)行評(píng)估，沒(méi)有結(jié)合其他更多的屬性.

Table 5 Comparison of Word Similarity Scores with

Table 6 Comparison of Text Similarity Scores with

4 總 結(jié)

本文提出了一種基于維基百科中超鏈接結(jié)構(gòu)進(jìn)行語(yǔ)義相似性評(píng)估的方法.這是首次在論文中考慮到2個(gè)單詞之間雙向路徑的不同，并證明了維基百科中詞條的普遍連通性，發(fā)現(xiàn)了它們之間的平均最短路徑長(zhǎng)度約為3.84.考慮到人類雙向思維的方式，我們應(yīng)用雙向最短路徑長(zhǎng)度設(shè)計(jì)了一種新的算法，該算法能夠充分利用維基百科結(jié)構(gòu)中的潛在人類特性.本文使用提出的算法分析單詞相似性，取得了很好的效果，在此基礎(chǔ)上提出一種使用矩陣分解進(jìn)行文本相似性分析的方法，取得了良好的效果.另外，我們對(duì)傳統(tǒng)的WS-353進(jìn)行了修正和升級(jí).本文最大的貢獻(xiàn)在于：在僅使用維基百科中鏈接關(guān)系和數(shù)量較少的訓(xùn)練數(shù)據(jù)的情況下，取得了出色的評(píng)估效果.在未來(lái)的工作中，我們希望能夠結(jié)合其他文本特征，并增加更多訓(xùn)練數(shù)據(jù)來(lái)改進(jìn)評(píng)估模型.

[1]Zhang Libo, Zhang Fei, Luo Tiejian. Knowledge structure evolution and evaluation method in computer science[J]. Journal of University of Chinese Academy of Sciences, 2016, 33(6): 844-850 (in Chinese) (張立波, 張飛, 羅鐵堅(jiān). 計(jì)算機(jī)科學(xué)知識(shí)體系演化與評(píng)估方法[J]. 中國(guó)科學(xué)院大學(xué)學(xué)報(bào), 2016, 33(6): 844-850)

[2]Xin Yu, Yang Jing, Tang Chuheng, et al. An overlapping semantic community detection algorithm based on local semantic cluster[J]. Journal of Computer Research and Development, 2015, 52(7): 1510-1521 (in Chinese) (辛宇, 楊靜, 湯楚蘅, 等. 基于局部語(yǔ)義聚類的語(yǔ)義重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(7): 1510-1521)

[3]Wang Junhua, Zuo Wanli, Yan Zhao. Word semantic similarity measurement based on Naive Bayes model[J]. Journal of Computer Research and Development, 2015, 52(7): 1499-1509 (in Chinese) (王俊華, 左萬(wàn)利, 閆昭. 基于樸素貝葉斯模型的單詞語(yǔ)義相似度度量[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(7): 1499-1509)

[4]Yazdani M, Popescu-Belis A. Computing text semantic relatedness using the contents and links of a hypertext encyclopedia: Extended abstract[J]. Artificial Intelligence, 2013, 194: 176-202

[5]Giles J. Internet encyclopaedias go head to head[J]. Nature, 2005, 438: 900-901

[6]Gabrilovich E, Markovitch S. Computing semantic relatedness using Wikipedia-based explicit semantic analysis[C]Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2007: 1606-1611

[7]Zesch T, Müller C, Gurevych I. Using Wiktionary for computing semantic relatedness[C]Proc of AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2008: 861-866

[8]Hassan S, Mihalcea R. Cross-lingual semantic relatedness using encyclopedic knowledge[C]Proc of Conf on Empirical Methods in Natural Language Processing. New York: ACM, 2009: 1192-1201

[9]Syed Z S, Finin T, Joshi A. Wikipedia as an ontology for describing documents[C]Proc of Int Conf on Weblogs and Social Media. Menlo Park, CA: AAAI, 2008

[10]Coursey K, Mihalcea R. Topic identification using Wikipedia graph centrality[C]Proc of Conf on the North American Chapter of the Association of Computational Linguistics. New York: ACM, 2009: 117-120

[11]Gabrilovich E, Markovitch S. Wikipedia-based semantic interpretation for natural language processing[J]. Journal of Artificial Intelligence Research, 2014, 34(4): 443-498

[12]Strube M, Ponzetto S P. WikiRelate! computing semantic relatedness using Wikipedia[C]Proc of the 19th National Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2006: 1419-1424

[13]Milne D, Witten I H. An open-source toolkit for mining Wikipedia[J]. Artificial Intelligence, 2013, 194: 222-239

[14]Yeh E, Ramage D, Manning C D, et al. WikiWalk: Random walks on Wikipedia for semantic relatedness[C]Proc of Workshop on Graph-Based Methods for Natural Language Processing. New York: ACM, 2009: 41-49

[15]Dallmann A, Niebler T, Lemmerich F, et al. Extracting semantics from random walks on Wikipedia: Comparing learning and counting methods[C]Proc of the 10th Int AAAI Conf on Web and Social Media. Menlo Park, CA: AAAI, 2016: 33-40

[16]Witten I, Milne D. An effective, low-cost measure of semantic relatedness obtained from Wikipedia links[C]Proc of AAAI Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy. Menlo Park, CA: AAAI, 2008: 25-30

[17]Wei Bifan, Liu Jun, Ma Jian, et al. Motif-based hyponym relation extraction from Wikipedia hyperlinks[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(10): 2507-2519

[18]Singer P, Niebler T, Strohmaier M, et al. Computing semantic relatedness from human navigational paths: A case study on Wikipedia[J]. International Journal on Semantic Web amp; Information Systems, 2013, 9(4): 171-172

[19]Niebler T, Schl?r D, Becker M, et al. Extracting semantics from unconstrained navigation on Wikipedia[J]. Künstliche Intelligenz, 2016, 30(2): 1-6

[20]Ellery W, Dario T. Wikipedia Clickstream, v21.0[OL]. [2016-09-24]. https:meta.wikimedia.orgwikiResearch:Wikipedia_clickstream

[21]Finkelstein L, Gabrilovich E, Matias Y, et al. Placing search in context: The concept revisited[C]Proc of the 10th Int Conf on World Wide Web. New York: ACM, 2001: 406-414

[22]Lee M D. An empirical evaluation of models of text document similarity[JOL]. Cognitive Science, 2005 [2016-09-24]. https:core.ac.ukdownloadpdf22875578.pdf

[23]Jarmasz M. Roget’s thesaurus as a lexical resource for natural language processing[D]. Ottowa, Canada: University of Ottowa, 2012

[24]Hughes T, Ramage D. Lexical semantic relatedness with random graph walks[C]Proc of the 45th Conf on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Stroudsburg, PA: ACL, 2007: 581-589

[25]Agirre E, Alfonseca E, Hall K, et al. A study on similarity and relatedness using distributional and WordNet-based approaches[C]Proc of Conf on the North Americ Human Language Technologies. New York: ACM, 2013: 19-27

[26]Hoerl A E, Kennard R W. Ridge regression: Biased estimation for nonorthogonal problems[J]. Technometrics, 1970, 12(1): 55-67

SunYihan, born in 1994. PhD candidate. Her main research interests include recommendation system, information retrieval, machine learning and distributed storage system.

LuoTiejian, born in 1962. PhD, professor. Director of the Information Dynamic and Engineering Applications Laboratory. His main research interests include Web mining, large scale Web performance optimization and distributed storage systems.

CalculateSemanticSimilarityBasedonLargeScaleKnowledgeRepository

Zhang Libo1, Sun Yihan2, and Luo Tiejian2

1(Institute of Software, Chinese Academy of Sciences, Beijing 100190)2(University of Chinese Academy of Sciences, Beijing 101408)

With the continuous growth of the total of human knowledge, semantic analysis on the basis of the structured big data generated by human is becoming more and more important in the application of the fields such as recommended system and information retrieval. It is a key problem to calculate semantic similarity in these fields. Previous studies acquired certain breakthrough by applying large scale knowledge repository, which was represented by Wikipedia, but the path in Wikipedia didn’t be fully utilized. In this paper, we summarize and analyze the previous algorithms for evaluating semantic similarity based on Wikipedia. On this foundation, a bilateral shortest paths algorithm is provided, which can evaluate the similarity between words and texts on the basis of the way human beings think, so that it can take full advantage of the path information in the knowledge repository. We extract the hyperlink structure among nodes, whose granularity is finer than that of articles form Wikipedia, then verify the universal connectivity among Wikipedia and evaluate the average shortest path between any two articles. Besides, the presented algorithm evaluates word similarity and text similarity based on the public dataset respectively, and the result indicates the great effect obtained from our algorithm. In the end of the paper, the advantages and disadvantages of proposed algorithm are summed up, and the way to improve follow-up study is proposed.

large scale knowledge repository; semantic similarity; Wikipedia; shortest path; connectivity

his PhD degree in computer software and theory from the University of Chinese Academy of Sciences. Assistant research professor in the Institute of Software, Chinese Academy of Sciences. His main research interests include image processing, pattern recognition, knowledge graph and deep learning.

2016-08-10；

2017-02-20

中國(guó)科學(xué)院系統(tǒng)優(yōu)化基金項(xiàng)目(Y42901VED2，Y42901VEB1，Y42901VEB2)

This work was supported by the Foundation of System Optimization in Chinese Academy of Sciences (Y42901VED2, Y42901VEB1, Y42901VEB2).

TP391