一種基于事實(shí)知識的實(shí)體相關(guān)度計(jì)算方法

孫叔琦，孫珂，趙世奇，李生，王海峰，楊沐昀

(1. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)2. 百度，北京 100085)

一種基于事實(shí)知識的實(shí)體相關(guān)度計(jì)算方法

孫叔琦1，孫珂2，趙世奇2，李生1，王海峰2，楊沐昀1

(1. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)2. 百度，北京 100085)

在近來出現(xiàn)的面向?qū)嶓w的搜索服務(wù)中，準(zhǔn)確地預(yù)測實(shí)體間的相關(guān)程度是至關(guān)重要的。該文提出了一種基于實(shí)體的事實(shí)知識，即利用 “實(shí)體—屬性—屬性值”(SPO)記錄進(jìn)行實(shí)體相關(guān)度計(jì)算的方法。該文通過基于屬性和屬性值的兩步概率估計(jì)，將實(shí)體表示為一個(gè)屬性值詞的概率分布列，并通過比對兩個(gè)實(shí)體共享的屬性值詞匯得出二者的相關(guān)度。實(shí)驗(yàn)表明，在用于面向?qū)嶓w搜索的相關(guān)實(shí)體排序問題上，該文方法達(dá)到了80.9%的平均top-5準(zhǔn)確率，優(yōu)于詞袋方法和基于查詢?nèi)罩竟铂F(xiàn)的方法。此外，該文通過定量分析，考察了不同領(lǐng)域的用戶需求特性對實(shí)體相關(guān)度計(jì)算結(jié)果的影響。

實(shí)體相關(guān)度；實(shí)體—屬性—屬性值(SPO)記錄；用戶需求；面向?qū)嶓w的搜索；

1 引言

在網(wǎng)頁搜索查詢中，有超過一半的查詢包含對特定實(shí)體的信息需求[1]。為了更好地滿足這些需求，一些主流搜索引擎推出了面向?qū)嶓w的搜索(entity-oriented search)服務(wù)。以谷歌推出的“知識圖譜”為例，面向?qū)嶓w的搜索結(jié)果一般在輸入查詢?yōu)橐粋€(gè)實(shí)體名字(如人名)時(shí)觸發(fā)，其內(nèi)容主要包含與實(shí)體相關(guān)的圖片、圍繞實(shí)體的關(guān)鍵事實(shí)知識羅列(如生卒年、家庭成員、作品)，以及一個(gè)相關(guān)實(shí)體的列表。除了谷歌之外，其他主流搜索引擎，包括百度、必應(yīng)、雅虎等，也推出了類似形式的服務(wù)。

在面向?qū)嶓w的搜索結(jié)果中，根據(jù)與中心實(shí)體的相關(guān)度推薦相關(guān)實(shí)體是一個(gè)環(huán)節(jié)。既有的實(shí)體相關(guān)度計(jì)算研究工作主要使用了分類體系(taxonomy)結(jié)構(gòu)[2-5]、數(shù)據(jù)庫鏈接結(jié)構(gòu)[6-9]、在線百科正文文本[2]或關(guān)鍵短語[10]等資源。

與上述研究工作相比，本文使用了一種新的資源——實(shí)體事實(shí)知識進(jìn)行實(shí)體間的相關(guān)度計(jì)算。事實(shí)知識是指與特定實(shí)體緊密相關(guān)的事實(shí)，如“人物實(shí)體A的作品有B”，“電影實(shí)體C的導(dǎo)演是D”，等等。在常見的知識庫(如Freebase，DBpedia等)中，這些事實(shí)一般以“實(shí)體-屬性-屬性值”(subject-property-object，SPO)記錄的形式存儲(chǔ)，如“A-作品-B”或“C-導(dǎo)演-D”，而一個(gè)實(shí)體則表示為一組SPO記錄的集合。在面向?qū)嶓w的搜索服務(wù)中，事實(shí)知識是前端展現(xiàn)的核心內(nèi)容，而SPO記錄是常見的后端知識庫中實(shí)體的基本存儲(chǔ)結(jié)構(gòu)。因此，使用實(shí)體知識資源，具有表義直觀、貼近應(yīng)用、附加開銷小等優(yōu)點(diǎn)。

本文基于SPO數(shù)據(jù)，以屬性值詞匯的概率分布列表示實(shí)體，并通過比對兩個(gè)實(shí)體共享的屬性值詞匯得出二者的相關(guān)度: 1)統(tǒng)計(jì)網(wǎng)頁搜索查詢?nèi)罩局械挠脩粜枨笮畔?，并由此為?shí)體的屬性賦權(quán)。這一步的基本假設(shè)是如果用戶頻繁地將實(shí)體(實(shí)體的名字)與它的某些屬性放在一起構(gòu)成查詢，那么這些屬性就是重要的，并應(yīng)賦予更高的權(quán)重；2)屬性值中的每個(gè)詞根據(jù)一個(gè)平滑語言模型來分割屬性所獲得的權(quán)重；3)通過比較對應(yīng)模型中的屬性值詞，就可以得出兩個(gè)實(shí)體之間的相關(guān)度。

針對面向?qū)嶓w的搜索服務(wù)，本文在相關(guān)實(shí)體排序問題上檢驗(yàn)了本文方法的效果。實(shí)驗(yàn)結(jié)果顯示，在人物、影視、游戲三個(gè)領(lǐng)域上，本文方法達(dá)到了80.9%的平均top-5準(zhǔn)確率，優(yōu)于詞袋方法和基于查詢共現(xiàn)的方法。此外，本文還定量分析了不同領(lǐng)域的用戶需求特性對相關(guān)度計(jì)算結(jié)果的影響。

本文剩余部分組織如下: 第二部分總結(jié)實(shí)體相關(guān)度計(jì)算的相關(guān)研究工作；第三部分提出實(shí)體的表示策略，并在此基礎(chǔ)上定義實(shí)體相關(guān)度算法；第四部分在相關(guān)實(shí)體排序問題上檢驗(yàn)實(shí)體相關(guān)度的效果，并分析實(shí)驗(yàn)結(jié)果；第五部分給出結(jié)論。

2 相關(guān)工作概述

實(shí)體相關(guān)度計(jì)算的典型方法主要分為三類。

1) 基于分類體系(taxonomy)的方法

這類方法比較兩個(gè)實(shí)體在給定分類體系中的相對位置，包括分類層次深度[3-4]、路徑長度[4-5]等。分類體系的構(gòu)建是一項(xiàng)復(fù)雜和嚴(yán)謹(jǐn)?shù)墓ぷ鳎诓煌I(lǐng)域上的豐富度與質(zhì)量也不同。領(lǐng)域上的差異影響了算法的通用性，而在真正需要特定領(lǐng)域內(nèi)的語義相關(guān)度的時(shí)候，強(qiáng)領(lǐng)域相關(guān)的知識資源又不易構(gòu)建。

2) 基于數(shù)據(jù)庫鏈接結(jié)構(gòu)的方法

這類方法使用隨機(jī)漫步算法挖掘?qū)嶓w之間的引用結(jié)構(gòu)，其優(yōu)點(diǎn)是能夠發(fā)掘出高階的相關(guān)關(guān)系。這類方法經(jīng)常使用高度互聯(lián)的數(shù)據(jù)庫資源，如維基百科[6]、IMDB、DBLP[8-9]，等等。這一類方法多使用鏈接分析算法，這一算法在新實(shí)體出現(xiàn)時(shí)的迭代更新代價(jià)較大，在快速發(fā)展變化的應(yīng)用領(lǐng)域上可用性受限。

3) 基于文本資源的方法

這類方法通過考察在實(shí)體間共享的各種文本、超文本元素來判斷實(shí)體的相關(guān)度。此時(shí)，實(shí)體一般以文本的形式，如在線百科文章([2，11]或者從文章中事先抽取的關(guān)鍵短語[10]的形式表示，而用來計(jì)算重疊的基本元素一般是詞或短語。此外，計(jì)算百科文章中的超鏈接重疊也被證明是有效的[7，11]。文本資源相對于結(jié)構(gòu)嚴(yán)整的分類體系資源，其覆蓋面更廣、構(gòu)建更為容易；而相對于基于鏈接結(jié)構(gòu)的方法，基于文本資源元素的方法靈活性更強(qiáng)，對全局范圍上的迭代更新依賴性弱。

本文首次使用了事實(shí)知識，即SPO記錄支持實(shí)體相關(guān)度計(jì)算。從某種角度上講，SPO記錄也是一種文本資源，但與既有研究工作中使用的文本資源相比，SPO記錄又有其自身的特點(diǎn)。首先，與基于在線百科文章中超鏈接重疊的方法[7，11]相比，本文中基于SPO記錄的方法考察的是兩個(gè)實(shí)體在事實(shí)知識上的重疊程度，因而能夠直接反映兩個(gè)實(shí)體所共享的特征，例如，電影《泰坦尼克號》和《終結(jié)者》的“導(dǎo)演”都是“詹姆斯·卡梅隆”；其次，SPO記錄的內(nèi)容較為精煉，從而省去了從文本中識別關(guān)鍵詞、關(guān)鍵短語的開銷[10]。

3 基于事實(shí)知識的實(shí)體相關(guān)度計(jì)算

3.1 問題定義

實(shí)體相關(guān)度計(jì)算的數(shù)學(xué)形式是一個(gè)函數(shù)，它量化了兩個(gè)實(shí)體e和e′之間的相關(guān)度，如式(1)所示。

(1)

其中，M(·)是一個(gè)實(shí)體的模型化表示，而函數(shù)f(·,·)執(zhí)行相關(guān)度計(jì)算，衡量兩個(gè)實(shí)體在事實(shí)知識上的重疊程度。

事實(shí)知識是知識庫中實(shí)體的基本存儲(chǔ)結(jié)構(gòu)，通常以一組“實(shí)體-屬性-屬性值”(SPO)記錄(subj，prop，obj)的形式存在，其中subj表示實(shí)體ID，prop表示屬性，obj表示屬性值。設(shè)實(shí)體e在知識庫中的存儲(chǔ)形式為e={(subj,prop,obj)}，則e的模型M(e)定義為所有屬性prop下的屬性值詞t的一個(gè)概率分布列{Pr(t|e)}，其中每個(gè)屬性值詞的概率按照式(2)計(jì)算。

Pr(t|e)=Pr(t|{(subj,prop,obj)})

·Pr((subj,prop,obj))

·Pr((prop,obj)|subj)·Pr(subj)

·Pr(prop|subj)

(2)

其中，第六行推導(dǎo)是基于以下事實(shí): 1)subj，即實(shí)體ID在e的所有SPO記錄中保持不變；2)SPO記錄的結(jié)構(gòu)決定了屬性值obj與屬性prop是一一對應(yīng)的。

式(2)所示的實(shí)體模型可以看作一種混合語言模型，這種模型一直在已知項(xiàng)(known-item)檢索[12]、XML檢索[13-14]，以及實(shí)體檢索[15]等研究問題中廣泛應(yīng)用。混合語言模型的核心思想是對屬于不同數(shù)據(jù)域，或不同類型的詞賦予不同的權(quán)重。在以往的工作中，這些權(quán)重或者通過訓(xùn)練樣本得到，或者直接根據(jù)知識庫中的統(tǒng)計(jì)信息確定。相比之下，本文使用從查詢?nèi)罩局型诰虻降挠脩粜枨笮畔砉烙?jì)各個(gè)屬性、屬性值詞的權(quán)重，并且在實(shí)際問題中展示了這種策略的有效性。

3.2 知識庫及其構(gòu)建

以在線百科全書為基礎(chǔ)的知識庫(如Freebase、DBPedia)在面向?qū)嶓w的搜索等新生信息服務(wù)的推動(dòng)下，發(fā)展較為迅速。此類知識庫從廣大用戶群體共同參與編輯的在線百科全書中抽取、匯總各領(lǐng)域知識，在相當(dāng)程度上降低了知識庫對專家知識的依賴程度，而對新產(chǎn)生的實(shí)體也能較快收錄。

在大多數(shù)基于在線百科全書的知識庫中，SPO記錄是實(shí)體的基本存儲(chǔ)結(jié)構(gòu)，而其中存儲(chǔ)的屬性、屬性值等信息也是實(shí)體在線百科詞條中的核心信息。下面給出本文計(jì)算實(shí)體相關(guān)度所需的知識庫的構(gòu)建過程。知識庫根據(jù)百度百科的頁面構(gòu)建，庫中的每個(gè)實(shí)體均對應(yīng)于一組SPO記錄。具體地，本文針對每個(gè)帶有“信息卡片”(如圖1所示)的百科頁面建立一個(gè)實(shí)體、分配實(shí)體ID，并從信息卡片的三個(gè)數(shù)據(jù)域中生成SPO記錄: 1)簡述，2)屬性-屬性值列表，以及3)用戶生成的標(biāo)簽，如圖1中實(shí)線框所示。

每條SPO記錄是一個(gè)三元組，為了方便表示，將其寫作下列格式:

{實(shí)體ID}{屬性}:[屬性值]

對同一實(shí)體的所有SPO記錄，實(shí)體ID實(shí)際上是不變的。在不產(chǎn)生歧義的情況下，下文中將其省略。

以圖1為例，第一，簡述生成單獨(dú)的一條SPO記錄: {簡述}:[詹姆斯·卡梅隆即……]；第二，屬性-屬性值列表中的每對屬性、屬性值生成一條SPO記錄，如{代表作品}:[泰坦尼克號，魔鬼終結(jié)者……]；第三，用戶生成的標(biāo)簽也生成單獨(dú)的一條SPO記錄: {標(biāo)簽}:[人物，導(dǎo)演，奧斯卡金像獎(jiǎng)……]。這樣，每個(gè)實(shí)體的SPO數(shù)據(jù)都包含三種類型的記錄: 簡述、屬性，以及標(biāo)簽。其中，簡述和標(biāo)簽可以看作特殊的屬性。最后，本文使用卡片的標(biāo)題(詹姆斯·卡梅隆)作為實(shí)體的名字，如圖1中虛線框所示。

整個(gè)知識庫包含36.6萬個(gè)實(shí)體，以及369萬條SPO記錄。

3.3 概率估計(jì)

式(2)將t的概率估計(jì)過程分解為三個(gè)環(huán)節(jié)。首先，通過估計(jì)概率Pr(prop|subj)對e的每個(gè)屬性prop的賦權(quán)(subj是e在知識庫中的ID)；然后，再將屬性的權(quán)重根據(jù)概率Pr(t|prop,subj)分配到對應(yīng)的屬性值詞上；最后，遍歷所有的屬性，獲得t的概率Pr(t|e)。

3.3.1 基于用戶信息需求的屬性概率估計(jì)

在上述三個(gè)環(huán)節(jié)中，Pr(prop|subj)的估計(jì)對基于事實(shí)知識的實(shí)體相關(guān)度計(jì)算是至關(guān)重要的。一個(gè)實(shí)體具有多方面的事實(shí)知識，這些事實(shí)知識的重要性不同，而屬性對事實(shí)知識起著提綱挈領(lǐng)的作用。例如，判斷兩個(gè)電影實(shí)體間的相關(guān)度時(shí)，“導(dǎo)演”屬性顯然比由 “上映時(shí)間”屬性更加可靠。

但是，從知識庫本身出發(fā)，難以找到有效的統(tǒng)計(jì)方式來預(yù)測這樣的重要度差異。這是因?yàn)橹R庫有自身的設(shè)計(jì)需求，屬性在知識庫中出現(xiàn)的概率有時(shí)不能代表其重要性。例如，如果知識庫從設(shè)計(jì)完備性考慮，那么應(yīng)該對同一類型的所有實(shí)體設(shè)置相同的屬性集合，即使對應(yīng)的屬性值并不存在。于是，如果按照屬性在實(shí)體中出現(xiàn)的概率估計(jì)Pr(prop|subj)，則所有屬性的概率均相等，這是不合理的。因此，需要挖掘知識庫以外的數(shù)據(jù)源，以實(shí)現(xiàn)對Pr(prop|subj)的合理估計(jì)。

圖1 百度百科中電影導(dǎo)演詹姆斯·卡梅隆的“信息卡片”示例

搜索引擎的查詢?nèi)罩局苯芋w現(xiàn)了用戶的信息需求，而用戶對實(shí)體的某種事實(shí)知識的需求強(qiáng)度是一個(gè)自然的重要性判斷依據(jù)。因此，本文首先從查詢?nèi)罩局型诰蛴脩粜枨笮畔?，以確定e的每個(gè)屬性prop的權(quán)重。具體地，本文假設(shè):

如果prop是e的重要屬性，那么人們會(huì)頻繁地把prop和e(的名字*實(shí)體的名字在常見的知識庫(如Freebase，DBpedia)中是一個(gè)特殊的數(shù)據(jù)域，與實(shí)體的SPO記錄獨(dú)立。在本文使用的知識庫中，也沿用了這樣的實(shí)現(xiàn)方式。)放在一起搜索。

“把prop與實(shí)體e的名字(記作Ne)放在一起搜索”包括兩種情況: 第一，直接將Ne與prop拼接成查詢；第二，將Ne與prop所對應(yīng)的屬性值objprop，subj*這里的obj用下標(biāo)修飾，是為了區(qū)分不同實(shí)體、不同屬性所對應(yīng)的屬性值。中的詞匯拼接成查詢。例如，“泰坦尼克號 導(dǎo)演”和“泰坦尼克號 卡梅隆”都反映出用戶對“導(dǎo)演”這一屬性的興趣。

對應(yīng)上面的兩種情況，本文按照下面的方式為屬性prop賦權(quán)。首先，將objprop，subj分詞并進(jìn)行詞性標(biāo)注與名實(shí)體識別，然后，分別考察“實(shí)體名+屬性”以及“實(shí)體名+屬性值詞”形式的查詢在查詢?nèi)罩局械念l率，計(jì)算prop關(guān)于e(即subj)的搜索頻率分?jǐn)?shù)sf(prop，subj)，如式(3)所示。

sf(prop,subj)=ln(#(Ne+prop))

(3)

其中，#(Ne+x)表示查詢“Nex”在查詢?nèi)罩局?如“泰坦尼克號 導(dǎo)演”、“泰坦尼克號 卡梅隆”)的頻率，集合T(objprop，subj)包含屬性值objprop，subj中所有的名詞(包括名實(shí)體)和動(dòng)詞。只考慮名詞、動(dòng)詞與實(shí)體名Ne的共現(xiàn)，是因?yàn)槠渌~性的屬性值詞與Ne的共現(xiàn)不能明顯反映用戶對prop的興趣。

統(tǒng)計(jì)共現(xiàn)所用的查詢?nèi)罩臼侨齻€(gè)月的百度搜索日志。在共現(xiàn)頻率上取自然對數(shù)，是為了降低極高頻查詢的影響。特別地，每個(gè)詞t的共現(xiàn)頻率被平均分配到所有在屬性值中含有t的屬性(即{prop′:t∈T(objprop′,subj)})上。例如，電影《泰坦尼克號》的導(dǎo)演和編劇均為卡梅隆，如果查詢“泰坦尼克號 卡梅隆”在日志中出現(xiàn)了N次，那么導(dǎo)演、編劇兩個(gè)屬性將分別獲得ln(N)/2的搜索頻率分?jǐn)?shù)加成。此外，本文對“實(shí)體名+屬性值詞”型查詢的頻率使用T(objprop，subj)的基數(shù)(即屬性值包含的詞數(shù))進(jìn)行了歸一化，以避免長屬性值的影響。

最后，根據(jù)sf(prop，subj)，Pr(prop|subj)以一個(gè)帶全局平滑項(xiàng)的概率形式計(jì)算，如式(4)所示。

(4)

其中，第二項(xiàng)表示prop在整個(gè)SPO數(shù)據(jù)庫中的全局重要程度，并根據(jù)參數(shù)λprop與第一項(xiàng)擬合。根據(jù)本文實(shí)驗(yàn)數(shù)據(jù)上的實(shí)驗(yàn)分析，我們發(fā)現(xiàn)全局項(xiàng)的權(quán)重較大時(shí)，計(jì)算效果較好。在實(shí)驗(yàn)中，設(shè)置λprop=0.1。

3.3.2 基于平滑語言模型的屬性值詞概率估計(jì)

在獲得屬性的權(quán)重之后，本文使用一個(gè)相對簡單的策略將該權(quán)重根據(jù)概率Pr(t|prop,subj)分配到對應(yīng)的屬性值詞上。為了增強(qiáng)表義能力，排除通用詞的干擾，本文在實(shí)體模型M(e)中只引入了屬性值中的名詞、名實(shí)體、數(shù)量值以及動(dòng)詞。

與屬性相對于實(shí)體的分布不同，屬性值詞在給定一條屬性值上的概率分布是有意義的，尤其是將屬性值詞限定到上述范圍之后。但是，由于屬性值一般比較短，為了得到有意義的概率分布，需要對其進(jìn)行平滑。因此，對實(shí)體e的每條SPO記錄(subj，porp，objprop，subj)，本文使用一個(gè)平滑語言模型[15]獲得t在該記錄上的分布Pr(t|prop,subj)，如式(5)所示。

(5)

其中tf(t，objprop，subj)表示objprop，subj中t的頻率，|objprop，subj|表示objprop，subj包含的詞數(shù)。沿用文獻(xiàn)[15]的配置，插值參數(shù)λobj=0.5。θsubj是e的一個(gè)Dirichlet平滑的語言模型，如式(6)所示。

(6)

其中Pr(t|θDB)是t在整個(gè)知識庫中的概率，平滑參數(shù)μ設(shè)定為一個(gè)實(shí)體的所有SPO記錄所包含的平均詞匯數(shù)[15]。

3.4 實(shí)體相關(guān)度計(jì)算

在得到屬性值詞t的概率分布列之后，兩個(gè)實(shí)體e、e′的相關(guān)度按照式(7)計(jì)算。

(7)

4 實(shí)驗(yàn)與分析

4.1 應(yīng)用場景

實(shí)體相關(guān)度有著廣泛的應(yīng)用，本文以相關(guān)實(shí)體推薦這一典型應(yīng)用場景為例，來驗(yàn)證本文方法的效果。相關(guān)實(shí)體是面向?qū)嶓w的搜索結(jié)果中的一項(xiàng)重要內(nèi)容。在傳統(tǒng)的推薦服務(wù)中，一種常見的方法是通過統(tǒng)計(jì)與原始查詢的字面共現(xiàn)頻率，從查詢文本和用戶會(huì)話中挖掘相關(guān)查詢。該方法在原始查詢是一個(gè)實(shí)體名字的時(shí)候同樣有效。給定中心實(shí)體ec和一個(gè)候選相關(guān)實(shí)體集合R(ec)={r1(ec),r2(ec),…,rn(ec)}，通過統(tǒng)計(jì)與中心實(shí)體名Nec和Nri(ec)在查詢?nèi)罩局械墓铂F(xiàn)，可以將R(ec)排序。但是，查詢?nèi)罩竟铂F(xiàn)所反映出的趨勢可能會(huì)偏離相關(guān)實(shí)體推薦的初始預(yù)期。例如，同期上映的電影可能在查詢中高頻共現(xiàn)，盡管它們的演員、類型可能很不一致。

相比之下，本文使用基于SPO記錄的實(shí)體相關(guān)度對候選相關(guān)實(shí)體進(jìn)行排序，即根據(jù)實(shí)體相關(guān)度rel(ec,ri(ec))從高到低的順序，對R(ec)排序?；赟PO記錄的相關(guān)度計(jì)算算法考察的是實(shí)體內(nèi)在屬性上的一致性，而這些內(nèi)在屬性來自人們根據(jù)自身常識編纂的在線百科詞條。人的常識是一種較為穩(wěn)定的知識，受暫時(shí)性事件的影響較小，舉例來說，電影的“導(dǎo)演”是一個(gè)事實(shí)性的信息，不因一部電影是否與其他電影同期上映而改變。因此，基于此類事實(shí)知識的實(shí)體相關(guān)度計(jì)算結(jié)果能夠糾正由暫時(shí)性的事件導(dǎo)致的計(jì)算錯(cuò)誤。

4.2 實(shí)驗(yàn)設(shè)置

4.2.1 數(shù)據(jù)準(zhǔn)備與標(biāo)注

實(shí)驗(yàn)數(shù)據(jù)分為三個(gè)領(lǐng)域: 人物、影視和游戲。這三個(gè)領(lǐng)域既是用戶高度關(guān)注的領(lǐng)域，同時(shí)也是主流的面向?qū)嶓w搜索服務(wù)的覆蓋范圍。

通過名實(shí)體識別，并對照知識庫中的實(shí)體名，本文從一個(gè)月的百度搜索查詢中抽取出所有人名、影視名和游戲名，并統(tǒng)計(jì)了同類名字在查詢文本和用戶會(huì)話中兩兩的共現(xiàn)頻率。這樣，對每個(gè)實(shí)體名，都可以獲得一個(gè)與其共現(xiàn)的實(shí)體名列表。

為了模擬“給定中心實(shí)體，對其相關(guān)實(shí)體排序”的應(yīng)用場景，我們在人物、影視和游戲領(lǐng)域，分別隨機(jī)抽樣了120個(gè)實(shí)體名，構(gòu)成集合U。其中任意u∈U都滿足: 在知識庫中只存在一個(gè)以u為名字的實(shí)體；然后，對每個(gè)u∈U，為其提取至多前10個(gè)共現(xiàn)實(shí)體名，構(gòu)成集合R(u)；最后，把每個(gè)u∈U在知識庫中對應(yīng)的實(shí)體eu作為中心實(shí)體，并將每個(gè)共現(xiàn)實(shí)體名r(u)∈R(u)通過與eu比對，對應(yīng)到知識庫的具體實(shí)體r(eu)上，形成待排序的候選相關(guān)實(shí)體集合R(eu)。

在應(yīng)用實(shí)體相關(guān)度對R(eu)排序之前，需要首先建立黃金標(biāo)準(zhǔn)。我們請兩位標(biāo)注者對eu與所有r(eu)∈R(eu)的相關(guān)程度做出0分、0.5分、1分的三檔評價(jià)。評價(jià)標(biāo)準(zhǔn)如下:

? 兩個(gè)實(shí)體是相關(guān)的(1分)，如果它們有顯著、明確的共同點(diǎn)或者確定的關(guān)系。如“瑪麗蓮·夢露-伊麗莎白·泰勒”、“阿凡達(dá)-泰坦尼克號”、“使命召喚-戰(zhàn)地”，等；

? 兩個(gè)實(shí)體是弱相關(guān)的(0.5分)，如果它們只有不太重要的共同點(diǎn)，或者在一些周邊的事件中共同出現(xiàn)。如名人在其軼事中涉及的其他人物，具有同一類型的電影等；

? 其他情況下，兩個(gè)實(shí)體是不相關(guān)的(0分)。

兩位評價(jià)者之間的Cohen’s Kappa系數(shù)在人物、影視、游戲三個(gè)領(lǐng)域上分別為0.43、0.44和0.44。在實(shí)驗(yàn)中，兩位標(biāo)注者給出的分?jǐn)?shù)取了平均值。在移除|R(eu)| < 5的中心實(shí)體eu后，用于排序?qū)嶒?yàn)的數(shù)據(jù)規(guī)模如表1所示。

表1 三個(gè)領(lǐng)域上的排序?qū)嶒?yàn)數(shù)據(jù)統(tǒng)計(jì)

4.2.2 評價(jià)指標(biāo)

為評估排序質(zhì)量，本文在每個(gè)領(lǐng)域上計(jì)算平均的Precision@k(1≤k≤5)如式(8)所示。

(8)

4.2.3 基線方法

本文方法與下列兩個(gè)方法對比。

1) 詞袋(bag-of-words)方法

所有SPO記錄，包括屬性和屬性值，被解散成詞袋。兩個(gè)實(shí)體之間的相關(guān)度定義為對應(yīng)詞袋之間的余弦相似度。

2) 查詢?nèi)罩竟铂F(xiàn)

我們有必要確認(rèn)基于實(shí)體相關(guān)度的排序結(jié)果是否好于基于查詢?nèi)罩竟铂F(xiàn)次數(shù)的結(jié)果。查詢?nèi)罩竟铂F(xiàn)方法根據(jù)實(shí)體名u和r(u)在查詢?nèi)罩?與4.3.1節(jié)相同)中的共現(xiàn)頻率對R(eu)排序。實(shí)際上，考察查詢?nèi)罩竟铂F(xiàn)在傳統(tǒng)搜索服務(wù)中也是一種典型的推薦策略。

4.2.4 均勻分布的實(shí)體模型

為了驗(yàn)證本文提出的概率估計(jì)策略的有效性，本文還嘗試將兩個(gè)概率Pr(prop|subj)、Pr(t|prop,subj)全部設(shè)為均勻分布，并考察基于這一簡化的實(shí)體模型的推薦結(jié)果質(zhì)量。

4.3 實(shí)驗(yàn)結(jié)果

總體上，本文方法取得了最好的效果。不同方法的效果對比如圖2所示。本文的方法在三個(gè)領(lǐng)域、所有1～5位置上的平均Precision@k均高于詞袋方法以及基于均勻分布實(shí)體模型的方法，其中在影視領(lǐng)域上的每個(gè)位置，以及游戲領(lǐng)域的第二位上統(tǒng)計(jì)顯著地高于后兩者。這說明本文提出的基于兩步概率估計(jì)的實(shí)體模型化表示方法以及賦權(quán)策略都是有效的。

基于查詢?nèi)罩竟铂F(xiàn)的方法效果明顯不如本文方法。從表2給出的實(shí)例來看，雖然“鞠萍”與“倪萍”均為央視的主持人，但是“董浩”才是前者在兒童節(jié)目中的搭檔；“西雅圖未眠夜”與“真愛至上”雖然題材相似，但“電子情書”不但與前者題材相似，而且其兩大主演(湯姆·漢克斯、梅格·瑞安)更與前者相同；“生化尖兵”與“生化奇兵”僅在字面上相似，而“使命召喚”則是在游戲類型(第一人稱射擊游戲)上與前者一致。這些實(shí)例表明: 網(wǎng)頁搜索用戶的興趣并非總能體現(xiàn)出實(shí)體之間的相關(guān)關(guān)系，而基于事實(shí)知識的實(shí)體相關(guān)度可以改良基于查詢?nèi)罩竟铂F(xiàn)的推薦結(jié)果。

領(lǐng)域中心實(shí)體查詢?nèi)罩竟铂F(xiàn)方法本文方法第1位結(jié)果人工評分第1位結(jié)果人工評分人物鞠萍倪萍0．75董浩1影視西雅圖夜未眠真愛至上0．25電子情書1游戲生化奇兵生化尖兵0．5使命召喚1

4.4 領(lǐng)域用戶需求特性分析

在式(4)中，屬性的權(quán)重是通過搜索引擎用戶對它的興趣確定的。根據(jù)上一節(jié)的實(shí)驗(yàn)，這樣的賦權(quán)策略的確可以導(dǎo)出比較準(zhǔn)確的實(shí)體相關(guān)度結(jié)果。但是，通過分析黃金標(biāo)準(zhǔn)數(shù)據(jù)，我們發(fā)現(xiàn): 一些被用戶的具體信息性需求提權(quán)的屬性有時(shí)并不能有效指導(dǎo)實(shí)體之間的相關(guān)度計(jì)算——這對本文工作的假設(shè)是一種擾亂。這種擾亂是影響實(shí)體相關(guān)度計(jì)算的重要因素，且在各個(gè)領(lǐng)域上的強(qiáng)弱程度不同。

表3 人們在查詢信息和判斷相關(guān)度時(shí)

5 結(jié)論

本文探究了如何使用實(shí)體-屬性-屬性值(SPO)記錄中存儲(chǔ)的事實(shí)知識計(jì)算實(shí)體之間的相關(guān)度。本文使用屬性值中詞匯的概率分布列表示一個(gè)實(shí)體，并根據(jù)網(wǎng)頁搜索用戶的需求信息，以及屬性值上的平滑語言模型，分兩步估計(jì)了屬性值詞的概率。最后，實(shí)體間的相關(guān)度由二者的模型所共享的詞匯及權(quán)重確定。在面向?qū)嶓w的搜索中的一個(gè)應(yīng)用問題: 相關(guān)實(shí)體排序上，本文提出的實(shí)體相關(guān)度達(dá)到了最高80.9%的平均top-5相關(guān)實(shí)體推薦準(zhǔn)確率。此外，本文通過定量的領(lǐng)域特性分析，發(fā)現(xiàn)了人們在“獲取信息”和“判斷相關(guān)度”時(shí)的認(rèn)知差異，這種差異是影響實(shí)體相關(guān)度計(jì)算效果的重要因素。

在未來研究工作中，我們將考慮使用短語代替詞匯作為實(shí)體的基本表示單元。這將使得兩個(gè)實(shí)體所共享的事實(shí)知識更具可讀性。我們還將嘗試直接從知識庫中推薦相關(guān)實(shí)體。這對在查詢?nèi)罩局腥狈铂F(xiàn)信息的長尾實(shí)體尤其重要。

[1]JPound,PMika,HZaragoza.Ad-hocobjectretrievalinthewebofdata[C]//Proceedingsofthe19thInternationalConferenceonWorldWideWeb,WWW’10.NewYork,NY,USA:ACM. 2010: 771-780.

[2]MStrube,SPPonzetto.Wikirelate!ComputingsemanticrelatednessusingWikipedia[C]//Proceedingsofthe21stNationalConferenceonArtificialIntelligence-Volume2,AAAI’06.AAAIPress,2006: 1419-1424.

[3]JLiu,LBirnbaum.Measuringsemanticsimilaritybetweennamedentitiesbysearchingthewebdirectory[C]//ProceedingsoftheIEEE/WIC/ACMInternationalConferenceonWebIntelligence,WI’07.Washington,DC,USA:IEEEComputerSociety,2007: 461-465.

[4]SPPonzetto,MStrube.KnowledgederivedfromWikipediaforcomputingsemanticrelatedness[J].J.Artif.Int.Res.,2007,30(1): 181-212.

[5]STuarob,PMitra,CLGiles.Taxonomy-basedquery-dependentschemesforprofilesimilaritymeasurement[C]//Proceedingsofthe1stJointInternationalWorkshoponEntity-OrientedandSemanticSearch,JIWES’12.NewYork,NY,USA:ACM,2012,8:1-8,6.

[6]YOllivier,PSenellart.Findingrelatedpagesusinggreenmeasures:anillustrationwithWikipedia[C]//Proceedingsofthe22ndNationalConferenceonArtificialIntelligence-Volume2,AAAI’07.AAAIPress,2007: 1427-1433.

[7]DTurdakov,PVelikhov.SemanticrelatednessmetricforWikipediaconceptsbasedonlinkanalysisanditsapplicationtowordsensedisambiguation[C]//ProceedingsoftheSYRCoDIS,2008.

[8]YSun,JHan,XYan,etal.Pathsim:Metapath-basedtop-ksimilaritysearchinheterogeneousinformationnetworks[J].PVLDB,2011,4(11): 992-1003.

[9]XYu,YSun,BNorick,etal.Userguidedentitysimilaritysearchusingmeta-pathselectioninheterogeneousinformationnetworks[C]//Proceedingsofthe21stACMInternationalConferenceonInformationandKnowledgeManagement,CIKM’12.NewYork,NY,USA:ACM. 2012: 2025-2029.

[10] J Hoffart,S Seufert,D B Nguyen,et al. Kore: Key phrase overlap relatedness for entity disambiguation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management,CIKM ’12. New York,NY,USA: ACM,2012: 545-554.

[11] D Milne,I H Witten. An effective,low-cost measure of semantic relatedness obtained from Wikipedia links[C]//Proceeding of AAAI Workshop on Wikipedia and Artificial Intelligence: an Evolving Synergy. AAAI Press,2008: 25-30.

[12] P Ogilvie,J Callan. Combining document representations for known-item search[C]//Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval,SIGIR ’03. NewYork,NY,USA: ACM,2003: 143-150.

[13] P Ogilvie,J Callan. Hierarchical language models for XML component retrieval[C]//Proceedings of the 3rd International Conference on Initiative for the Evaluation of XML Retrieval,INEX’04. Berlin,Heidelberg: Springer-Verlag,2005: 224-237.

[14] J Kim,X Xue,W B Croft. A probabilistic retrieval model for semi-structured data[C]//Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval,ECIR ’09. Berlin,Heidelberg: Springer-Verlag,2009: 228-239.

[15] R Neumayer,K Balog,K Nrv?g. On the modeling of entities for ad-hoc entity search in the web of data[C]//Proceedings of the 34th European conference on Advances in Information Retrieval,ECIR’12. Berlin,Heidelberg: Springer-Verlag,2012: 133-145.

[16] X Han,J Zhao. Structural semantic relatedness: a knowledge-based method to named entity disambiguation[C]//Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics,ACL ’10. Stroudsburg,PA,USA: Association for Computational Linguistics,2010: 50-59.

[17] Davis A Veloso,A S da Silva,W Meira,et al. Named entity disambiguation in streaming data[C]//Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1,ACL ’12. Stroudsburg,PA,USA: Association for Computational Linguistics,2012: 815-824.

[18] D Milne,I H Witten. Learning to link with Wikipedia[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management,CIKM’08. New York,NY,USA: ACM,2008: 509-518.

Entity Relatedness Calculation Based on Fact Knowledge

SUN Shuqi1, SUN Ke2, ZHAO Shiqi2, LI Sheng1, WANG Haifeng2, YANG Muyun1

(1. School of Computer Science and Technology,Harbin Institute of Technology, Harbin, Heilongjiang 150001, China;2. Baidu, Beijing 100085, China)

In the emerging entity-oriented search service, an accurate prediction of the relatedness between entities is essential. This paper proposes an approach to compute entity relatedness based on entities’ fact knowledge, i.e., subject-property-object (SPO) records. We adopt a two-step estimation based on property and object, mapping an entity to a discrete distribution of the object words, and obtained two entities’ relatedness by comparing the object words they share. On the related entity re-ranking problem in entity-oriented search, experimental results showed that our approach achieves 80.9% top-5 precision on average, outperforming the bag-of-words and query log co-occurrence based approaches. We also conducted quantitative analysis to find out how user demand in different domains affects the relatedness computation.

Entity relatedness,subject-property-object(SPO)record,user demand,entity-oriented search

孫叔琦(1985—)，博士研究生，主要研究領(lǐng)域?yàn)樾畔⒊槿?、文本挖掘。E?mail：sqsun@mtlab．hit．edu．cn孫珂(1982—)，博士，主要研究領(lǐng)域?yàn)樽匀徽Z言處理。E?mail：sunke@baidu．com趙世奇(1981—)，博士，主要研究領(lǐng)域?yàn)樽匀徽Z言處理。E?mail：zhaoshiqi@baidu．com

2014-07-28 定稿日期： 2014-12-20

國家自然科學(xué)基金項(xiàng)目(61272384,61370170,61105072)

1003-0077(2016)03-0178-09

TP391

A