pathrankingalgorithm調(diào)研報告

1、v1.0可編輯可修改path ranking algorithm 調(diào)研報告近兩年來，隨著Linking OpenData等項目的全面展開，語義 Web據(jù)源的數(shù)量激增，大量RD嚶?lián)话l(fā)布?；ヂ?lián)網(wǎng)正從僅包含網(wǎng)頁和網(wǎng)頁之間超鏈接的文 檔萬維網(wǎng)(Document Web)轉(zhuǎn)變成包含大量描述各種實體和實體之間豐富關(guān)系的 數(shù)據(jù)萬維網(wǎng)(Data Web在這個背景下，Google、百度和搜狗等搜索引擎公司紛 紛以此為基礎(chǔ)構(gòu)建知識圖譜，如 Knowledge Graph、知心和知立方等，用以改進(jìn) 搜索質(zhì)量，從而拉開了語義搜索的序幕。正如Google的辛格博士在介紹知識圖譜時提到的：“The world is n

2、ot madeof strings , but is made of things."，知識圖譜旨在描述真實世界中存在的各種實體或概念。其中，每個實體或概念用一個全局唯一確定的ID來標(biāo)識，稱為它們的標(biāo)識符(identifier) 。每個屬性-值對(attribute-value pair ,又稱 AVP)用來刻畫實體的內(nèi)在特性，而關(guān)系(relation) 用來連接兩個實體，刻畫它們 之間的關(guān)聯(lián)。知識圖譜亦可被看作是由一張巨大的圖組成，圖中的節(jié)點表示實體或概念，而圖中的邊則由屬性或關(guān)系構(gòu)成，我們需要構(gòu)建并使用這張圖。大規(guī)模知識圖譜的構(gòu)建與應(yīng)用需要多種智能信息處理技術(shù)的支持，其中主要包括

3、：實體鏈指(Entity Linking )、關(guān)系抽取(Relation Extraction )、知 識表示(Knowledge Representation )、知識推理(Knowledge Reasoning)等。在知識推理方面，利用推理規(guī)則實現(xiàn)關(guān)系抽取的經(jīng)典方法之一就是PathRanking Algorithm 算法，由Lao & Cohen與2010年提出。該方法將每種不同 的關(guān)系路徑作為一維特征，通過在知識圖譜 /Knowledge Base中統(tǒng)計大量的關(guān)系 路徑構(gòu)建關(guān)系分類的特征向量，建立關(guān)系分類器進(jìn)行關(guān)系抽取，取得不錯的抽取 效果，成為近年來的關(guān)系抽取的代表方法之一。但

4、目前這種基于關(guān)系的統(tǒng)計的方法，只能在連通圖上使用，對于那些出現(xiàn)頻率低的關(guān)系有嚴(yán)重的數(shù)據(jù)稀疏問題, 且代價高昂。針對這樣的問題，現(xiàn)今也出現(xiàn)了許多針對該算法的改進(jìn)研究。2. Path Ranking AlgorithmRandom Walk and RestartRandom walk with restart（RWR謖最初提 出的圖像分割算法，也叫Personalized Page Rank。它迭代地探討了網(wǎng)絡(luò)的全局結(jié)構(gòu)，估計兩個節(jié)點之間 的接近（親和度得分）。在一個節(jié)點上，在每個步驟中，面臨兩個選擇：要么移 動到一個隨機(jī)選擇的鄰居，或跳回到起始節(jié)點。該算法僅包含一個固定參數(shù)R稱為“重啟的概率（

5、1- R移動到一個鄰居的概率）。迭代后達(dá)到穩(wěn)定，穩(wěn)定的 概率向量包含了網(wǎng)絡(luò)中的所有節(jié)點對于起始節(jié)點的得分。這種穩(wěn)定的概率向量可 以被看作是“有影響力的影響”，在網(wǎng)絡(luò)上所施加的起始節(jié)點。游走的分布滿足 式：R=(1-d)u+dWr其中，d是繼續(xù)游走概率，（1-d）為重啟概率，u是啟動節(jié)點，Wr是網(wǎng)絡(luò)過 渡矩陣。隨機(jī)游走（RWR界際是一個簡單的迭代過程：Rt=（1-d）u+dWrt-1（2）式（2）表示了這樣一個迭代的過程：算法從圖中頂點u出發(fā)，沿圖中的邊隨機(jī)游走。在任意點上，算法以一定的概率d隨機(jī)地選擇與該頂點相鄰的邊，沿這 條邊移動到下一個頂點，或以（1-d）概率直接回到出發(fā)點u,這是這個重啟

6、概率 可有效的防止由于隨機(jī)游走的不確定性而進(jìn)入一條權(quán)值很小的路徑。在第t-1步時移動帶下一個頂點時，就開始了以這個點新出發(fā)點的第t步隨機(jī)游走，其中 Wr1表示的是在t-1步游走時從一個節(jié)點游走到另一個節(jié)點概率。經(jīng)過若干次隨機(jī)游走過程，可以到達(dá)圖中每一個頂點的概率值達(dá)到平穩(wěn)分布，即再次迭代也不改變圖中的概率分布值時，就可以得到的R值來對所求任務(wù)進(jìn)行排序。比如講RW期用在下圖做圖像分割時：圖1假設(shè)圖像最核心的部分是紅色，次核心為黃色，需排除的部分為藍(lán)色。開始 游走時路徑沿著最左面的藍(lán)色路徑走， 每一次游走都進(jìn)入了不需要的部分， 直到 某次重新啟動成功，返回最最上角的開始節(jié)點重新游走，第二次沿著綠色

7、的路徑 游走，識別到了部分次核心區(qū)域，在某一步是再次重啟，沿著黑色的路徑識別到 了核心區(qū)域。由（2）公式就可以迭代的計算出每條路徑覆蓋范圍的概率大小，在 N次游走達(dá)到穩(wěn)定后，上圖的每一部分子圖都會有一個確定不變的概率，結(jié)合核 心、次核心與需排除部分的權(quán)重，就可以計算出每個子圖的評分， 從而找出評分 最高的核心區(qū)域。目前已有許多關(guān)于RWR勺研究，包括使用RWR4行分類，關(guān)系 學(xué)習(xí)與一般化的圖上的相似性度量等。Relational Learning要實現(xiàn)關(guān)系抽取，其中對關(guān)系的推導(dǎo)學(xué)習(xí)是很重要的一部分。 在大數(shù)據(jù)的背 景下，預(yù)測一個關(guān)系是否成立具有極大的研究潛力。我們可以用下圖描述一個關(guān) 系學(xué)習(xí)問題

8、：7如果想要判定Char10tte是否是一個作家。最簡單的情況如圖1所示，我們 需要兩個點與一條邊來描述這個問題，我們可以通過判定這兩個點之間是否存在 這樣的一條邊，來判定這兩個點是否存在關(guān)系。而這條邊存在的概率有多大，如何定量計算，就是 Path Ranking Algorithm 可以解決的問題。而現(xiàn)實的情況必然不由簡單的圖2可以描述清楚的，如果我們在判斷Charlotte 是否是一個作家時，考慮到了他的朋友與家庭等關(guān)系時，（這可以為我們的判斷提供更多的依據(jù)），那么情況可能會是這樣：我們?nèi)砸訡harlotte為出發(fā)點，Writer為終點來判斷Charlotte是否是一個作家，但這次我們多了

9、一條這樣的判斷路徑：Charlotte- »Patrick Bronte- »Writer。若這三個點間的兩條邊存在，我們同樣可以得到Charlotte是一個作家的結(jié)論。值得注意的是在判定Charlotte是否是一個作家時，Charlotte的行為無疑對判定也是有幫助的，那么我們的判定圖可以表述為：IsA1 is the reverse of 15A relationWrote*1 is the reverse of Wrote relation如果在考慮到出版社等問題，我們還要加上這樣的關(guān)系:至此我們需要考慮的關(guān)系圖變了這樣:Prn hChrir oTtp 今 WritT

10、er)ProbfChariotte T Painter)圖5可以看到這已經(jīng)是一個很復(fù)雜的圖了，而實際上我們在做判斷的時候，可能考慮的遠(yuǎn)比這還要復(fù)雜，其計算復(fù)雜度主要體現(xiàn)在它有指數(shù)級增長的路徑類型和 指數(shù)級增長的路徑實例。圖中每兩個點之間存在的邊，對應(yīng)著我們需要學(xué)習(xí)到的 關(guān)系，可以發(fā)現(xiàn)不同的點之間關(guān)系的種類并不相同，如 Charlotte與Jane Eyre 之間，是 wrote的關(guān)系，而Jane Eyre與Novel之間，是IsA的關(guān)系。而 RWR 并不能有效的區(qū)分這樣的區(qū)別，前面的類型信息會被后面的類型信息覆蓋，而下面提到的Path Ranking Algorithm可以很好的解決這樣的問題

11、。Path Ranking Algorithm有一些相關(guān)研究，如Minkov, Cohen等在基于RWR勺模型上使用了更加豐富 的特征集合，用邊上的標(biāo)簽對排序結(jié)果再次排序。并且他們還提出了一種加權(quán)的RWR-paths方法，提高了查詢到相關(guān)實體的準(zhǔn)確率。而 Path ranking algorithm 算法與之類似，可以看做是其一種改進(jìn)版本，相當(dāng)于沿著一組帶有特定類型信息 的邊的序列集合上的隨機(jī)游走，即限制了游走路徑的RWRT法。相比于RWR£法 區(qū)分邊的類型，它更容易加入額外所需的類型信息，如它的 query-independent experts 與 popular entity

12、experts 。 類彳以的技術(shù)還有 Embedding-based techniques 與 Probabilistic graphical models , Path ranking algorithm 相 比較前兩者，具有容易推測與不需要關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)先驗知識的優(yōu)點。其算法核心思想是利用連接著兩個實體的路徑去預(yù)測他們之間是否有潛在 的關(guān)系。舉個例子，如圖7所示，我彳門要判定Charlotte是不是作家，可以判定 這樣一組特定的關(guān)系序列是否成立：Prob (Charlotte- » Writer | InSentence,InSentence-1, IsA )圖7Path rank

13、ing algorithm可以通過不同的邊類型序列來判定一個關(guān)系是否存在，在比較復(fù)雜的圖6上，我們可以看到至少有一下三種不同的邊類型序列可 以做出判定：Prob (Charlotte Writer |HasFather,IsA)Prob (Charlotte Writer | Write, IsA, IsA-1, Write, IsA) Prob (Charlotte Writer |InSentence InSentence-1, IsA)或者可以舉個其他的例子，如果我需要查找一些參考文獻(xiàn)，其中一個關(guān)鍵字 是年份y,那么可能有這樣的兩種方式：一、找出所有y年出版的論文。二、出版于y年經(jīng)常被引

14、用的論文。顯然第二種方法更加合理，為了更加準(zhǔn)確的描述所 需信息，定義R是一個二值關(guān)系，如果e與e'有關(guān)系R成立，則記作Re, e'), 并定義R(e) e:R(e,e')。dom(R)用來表示知識領(lǐng)域 R, range(R)表示領(lǐng)域R的 范圍。P是一條關(guān)系路徑，由一組關(guān)系R, R, ., R l組成，其中對于任意的i,都滿足 1< i < L-1, range(Ri)=dom(R+1)。并且有定義 dom(R1 .RL) dom(R1),且有range(R.R) range(R)。如果希望強調(diào)路徑上每一步的類型信息，可以將P = Ri, R 2. R L 表

15、示為：RiRlTo .其中 T(=dom(R)=dom(P), T1 = range(R1) = dom(R2) 。據(jù)此定義，上述以 關(guān)鍵字年份搜索參考文件任務(wù)的兩種方法可以表示成下面這樣:v1.0可編輯可修改TrtPublis h edfn -i111 : yearpaperH 2 : 4/rarPubtinhrdlnJCitr* paperpaper其中-1表示相反的主客體關(guān)系?？梢钥吹矫織l關(guān)系路徑都是paper,正是查找參考 文獻(xiàn)想要的信息類型。對于任意的P=R,R2,.R l和查詢實體 集合Eq dom(P)。如果P是空路徑，我們定義其滿足如下分布：.1/Eq,if e Eq(3)hE

16、q, p(e)0, otherwise公式(3)主要用于在RPA開始時，計算第一步連接出發(fā)節(jié)點與第二個節(jié)點的概率計算。假設(shè)我需要購買一臺PC,想知道具體買什么好。這樣的任務(wù)在圖 8所示具體問題上可表述為：首先只有查詢起點PC,沒有任何一條連接到其他節(jié)點的路徑，此時考慮關(guān)系R=HaveBrand1,假設(shè)有相關(guān)的Eq=中國，美國，老撾,對于任意e Eq此時會以相同的概率hEqp(e) 1/3隨即游走到a1,b1,c1上來，對 q q, p于牛奶 Eq,則對應(yīng)的h為0,即不會隨機(jī)游走到d1上來。圖8若 P=R.R l非空，則令 P' =R.R l-i,WJ:hEq, p(e)hEq,p

17、9;(e') * e' range(P')I(R(ee)R(e')(4)其中I(R(e ' ,e)/|R 1(e ' )|表示沿著邊？從節(jié)點e 一步隨機(jī)游走到e'的 概率，I(R(e ' ,e)表示在e與e'到底有沒有關(guān)系R存在。在e'與e滿足關(guān)系 R時取值1,否則取值00以路徑長度？ =2舉例，即P'為關(guān)系邊R, R2構(gòu)成的 8v1.0可編輯可修改路徑圖9若R1為HaveBrand1關(guān)系，R2為inWhichCountry -1關(guān)系。具體PC推薦任務(wù) 圖9上可表示為：首先P為空，以式2所述概率隨機(jī)游走，假

18、設(shè)選擇 a1,此時 會進(jìn)行第二步游走，引入新的查詢實體，rang(Rz)=聯(lián)想,如果此時有聯(lián)想， 香蕉兩個新實體e'與P相連接，首先指示器函數(shù)判定e'于e是否存在關(guān)系R, 即這樣兩個三元組(中國，inWhichCountry-1,聯(lián)想)與(中國，inWhichCountry -1, 香蕉)是否成立。顯然(中國，inWhichCountry -1,香蕉)不成立，則I(R(e ' ,e)=0 ,HaveBrand-1 inWhichCou ntry -1使得路徑 P1=PC中國香蕉 這條路徑的中的第二步游走分布inWhichCou ntry-1中國香蕉的h值為0,即關(guān)系in

19、WhichCountry ”的h值為0,從而整條路徑的h值變小。而其中當(dāng)三元組關(guān)系(中國,inWhichCountry -1,聯(lián)想)存在時， I(R(e ' ,e)=1時，再遞歸的以中國為出發(fā)節(jié)點，利用公式(3)計算一個h值， 這個h乘上一個不為 0的從e到e' 一步隨機(jī)游走的概率，最終整體路徑 -1 HaveBrandinWhichCou ntry-1P2=PC中國聯(lián)想的h值肯定會明顯大于P10至此就可以對查詢所需的結(jié)果進(jìn)行排名：1hEq,R(e)2hEq,P2(e) nhEq,Pn(e)(5)-1HaveBrandinWhichCou ntry-1如圖10,假設(shè)有一條路徑

20、P=PC中國聯(lián)想 .Y450-tsi,路徑長度為n,最終結(jié)果為型號為Y450-tis的PG由公式(4)計算出每一步游走的h值，也就是每一個連接2個節(jié)點的關(guān)系R的h值，最終將這些h值求和，利 用公式(5)就可以得到路徑P的最終排名得分，但是需要注意到的是，在這條路 徑中，每一步的的權(quán)重也許并不相同，這也是會影響最終得分的重要因素之一。比如在在圖10的a1,b1,c1均成立的條件下，考慮到中國美國的PC水平會明顯1HaveBrand高于老撾，人們都不會傾向于購買老撾的PC產(chǎn)品，那么此時雖然PC 中國、 11HaveBrandHaveBrandPC 美國、PC 老撾均成立，卻需要去調(diào)整根據(jù)公式(3)

21、的計算11HaveBrand 1HaveBrand 1出的均為1/3的概率得分，通過 ，應(yīng)使得PC 中國、PC 美國的 得分明顯高于老撾的得分。圖10假設(shè)如圖11所示，有abc三條不同路徑指向統(tǒng)同一款 PC型號Y450-tsi ,那么每條路徑都會有一個對應(yīng)的概率，分別可以表示為：Pa( PC Y450| whichCountry, whichBrand, choosePb( PC Y4501 whichYear, choos8Pc(PC Y4501choosR圖11根據(jù)公式(5)我們可以分別求得上述Pa、Pb、Pc的值，但最終我們需要的是Y450這款PC的推薦評分到底是多少，而不是具體每一條路

22、徑的評分。所以應(yīng)當(dāng)將所有指向這同一結(jié)果的各個概率評分求和，可以用公式(6)表示：score(e, )hEq,p(e)p(6)P (q,l)具體對于圖11而言，P是在？ <4的情況下，結(jié)果都指向Y450這個查詢結(jié)果的任意一條路徑。對于 Y450這個查詢，它的評分=score(p a)+score(p b)+score(p c)Pa、R、Pc均由公式(5)計算可得。公式(6)以更好理解的形式可以表示為：score(s,t) P(s t; ) p(7)p Q其中Q是長度為n的查詢起點s到查詢終點n之間的可能路徑，9 p是通過 訓(xùn)練獲得的路徑權(quán)重。p為具體的一條起點s到終點n的路徑，若有Pf+R

23、+i, 其中兀=R, R. R l,則滿足：p(s t; ) P(s z; ')P(z t;R) (8)剩下的問題就是對參數(shù) 9的估計，有許多方法可以使用，最常用的如邏輯 回歸分類模型、BLMVML-BFG胡。我們可以用關(guān)系R和(起點si,終點ti )的 集合來構(gòu)造所需的訓(xùn)練集，最終通過分類器得到所需的權(quán)重。Path Ranking Algorithm 的擴(kuò)展Query Independent Paths對于描述一個實體的特征取決于這些特征在圖中相對查詢實體的位置，而對于一個實體的關(guān)聯(lián)關(guān)系可能還取決于一些獨立于查詢的特性。對于推薦參考文獻(xiàn)這一項任務(wù)來說，其最近的出版商，引用數(shù)量，和作者

24、曾經(jīng)在哪里發(fā)表過文章都 會有影響?？紤]到查詢實體這些復(fù)雜的特點，我們可以將我們的查詢Eq做擴(kuò)展， 讓每個查詢Eq都包含一個特殊的實體e*。這樣做之后，對于每一種類型信息T, 都有關(guān)系A(chǔ)nyT使得AnyT (e*,e )對于所有屬于T的E都成立。如關(guān)系A(chǔ)nyPaper 將映射e*為每個paper,關(guān)系A(chǔ)nyYearr將映射e*為每個year。AnyPaperCite舉個例子，如果有這樣的路徑：e paper paper,這代表著我們以相等的概率隨機(jī)選擇任何一個paper作為開始節(jié)點，然后游走到它的一篇參考文獻(xiàn) 上。這樣最后得到的結(jié)果有很大的概率會是一個有高引用量的paper。一條以AnyPape

25、r作為開始節(jié)點的路徑，隨后沿著兩條引用關(guān)系的邊去分配權(quán)重給那些 經(jīng)常被高引用量文章引用的paper,隨著路徑的不斷增長，這種結(jié)合了多種獨立 于查詢路徑的算法，開始類似于在引用量構(gòu)成的圖上使用PageRank算法。這種情況，稱其為 Query Independent Paths (RPA-qip),仍然是以式(2) 來計算評分，但其好處是因為這些路徑都是獨立于查詢的，我們可以通過提前計算它們的值來改善整體 Path Ranking Algorithm的效率。Popular Entity Biases對于一些特定的查詢檢索任務(wù)，用戶可能感興趣的是一些計算出的排名相對 低但被點擊次數(shù)很多的查詢結(jié)果，

26、這是主要是因為有一些特征不能很好的被排名 系統(tǒng)識別。在這種情況下，如果能將這些點擊次數(shù)大的查詢結(jié)果或文檔給以較高 的排名，就可以給用戶更好的體驗。對于個性化的搜索，不同的用戶在同一個查12v1.0可編輯可修改詢下可能需要的是不同的結(jié)果，比如單詞“ mouse',對于一個生物學(xué)家來說他 需要的是老鼠的相關(guān)信息，而對于一個程序員來說，更加可能的是代表鼠標(biāo)的意 思。所以，我們對查詢者與查詢目標(biāo)建立一個聯(lián)系， 對上述這種情況可能會有一 定的幫助。Popular Entity Biases是一種簡單而又適用性廣的方法。它通過對查詢目標(biāo)添加一個查詢偏好來建立對查詢實體的流行度。對于一個查詢?nèi)蝿?wù)，有

27、查詢類型Tc，查詢目標(biāo)類型 Tq, Popular Entity Biases會對每一個查詢目標(biāo)e Tq增e' , e）引入條件流行實體偏RPA與RPA-qip的排名計算公加一個流行實體偏好epop ,并對每一對查詢實體（ 好e, e,其中e' T°,e Tq。在這種情況下，對于式6就不在適用了，可以將公式2擴(kuò)展為:s(e；)hEq,p(e) pP (q.l)popepope,ee, Eq(8)或者以矩陣形式表示為:(9)popq其中pop用于連接所有偏好參數(shù)，一個條件偏好參數(shù)構(gòu)成的矩陣，q是一個二值指示器（0 or 1）,用于表示每個實體是否包含在查詢中。可以看出在

28、式8中參數(shù)的取值可能會非常大的，pop的長度相當(dāng)于所有查詢目標(biāo)實體的總數(shù)，也是一個很大的矩陣，行數(shù)為目標(biāo)實體的數(shù)，列數(shù)等于查詢中所有的實體類型 數(shù)。舉個列子，比如 Apple這個查詢詞，其可能對應(yīng)查詢實體有蘋果（水果），或Apple Compute評果公司），如果在最近蘋果剛剛發(fā)布了 iPhone7的背景下，有 用戶查詢了 Apple這個關(guān)鍵詞，更應(yīng)當(dāng)出現(xiàn)的查詢結(jié)果是 Apple Compute,而 pop不是水果。此時就可以通過設(shè)置公式8中的不同的流行偏好來調(diào)節(jié)查詢結(jié)果。同理，對于查詢關(guān)鍵詞e蘋果，設(shè)e'為實體手機(jī)，實體對（蘋果，手機(jī)）在公式 13v1.0可編輯可修改8中的 epOp

29、會相對于實體對（蘋果，水果）在上述背景下應(yīng)當(dāng)更大。結(jié)合兩個針 e' Eq對流行度的計算參數(shù)，Popular Entity Biases 可以使RPA更加準(zhǔn)確的對查詢結(jié)果評分排名。Path Ranking Algorithm較之前的各算法，具有表示能力強，魯棒性高，適用與大規(guī)模數(shù)據(jù)的優(yōu)點。3. Path Ranking Algorithm的發(fā)展與應(yīng)用Efficient InferencePath Ranking Algorithm 可以看做是基于路徑限制的一種隨機(jī)游走算法，它 在關(guān)系學(xué)習(xí)方面有良好的表現(xiàn)，但是這種算法的代價高昂，在推測路徑中會產(chǎn)生 大量概率非零的中間節(jié)點，但實際上我們并不

30、需要很多的隨機(jī)游走就可以將查詢 目標(biāo)從噪聲節(jié)點中區(qū)分出來。文獻(xiàn)2采用稀疏化策略fingerprinting, particle filtering, fixed truncation與 beam truncation 針對對止匕問題對Path Ranking Algorithm算法進(jìn)行了改進(jìn)，達(dá)到了更加高效的關(guān)系推測學(xué)習(xí)。有文獻(xiàn)3提出了一種近似于personalized PageRank的蒙特卡羅算法，這 種算法描述了從查詢節(jié)點出發(fā)，產(chǎn)生k條獨立的隨機(jī)游走，節(jié)點的概率由它被隨 機(jī)游走到的被歸一化后的次數(shù)來確定，并指出這樣就可以由K的大小來輕易的控 制計算量的大小，且只需要相對比較少的隨機(jī)游走器

31、就可以區(qū)分出高、中、低排名的查詢結(jié)果節(jié)點。這樣雖然會對低排名節(jié)點的計算精度有影響，但是查詢結(jié)果是否符合人們的要求，主要是由那些高質(zhì)量的查詢結(jié)果決定的，低排名的結(jié)果的精度對于整體查詢并不會有很大的影響。根據(jù)這樣的結(jié)論，文獻(xiàn) 2在Path Ranking Algorithm 算法的基礎(chǔ)上提出了 The Fingerprinting Strategy 的稀疏 化抽樣策略，將Path Ranking Algorithm算法中每一步的h計算方法替換為：#wal kers visting e hi i(e)#wal kers(10)這種抽樣策略，僅僅是用公式(10)替換公式(3),仍然服從公式(4)所描述

32、的 分布。h值的確定不再像公式(3)中對所有包含在查詢集合中的實體數(shù)量等概率 確定，而是隨機(jī)游走器與被游走到的次數(shù)來確定概率大小。比如可以設(shè)置 10個 隨即游走器，如果一個節(jié)點總共被這10個隨即游走器游走到了10次，那么這個節(jié)點的h值就是1,而不是由具體的查詢相關(guān)的實體數(shù)量決定。這樣做的好處是 可以通過控制隨機(jī)游走器的數(shù)量，來靈活的控制計算量的大小。而上述The Fingerprinting Strategy在隨機(jī)游走器的數(shù)量遠(yuǎn)大于鏈路數(shù)量時，可能會引起很大的計算浪費。比如有3萬個隨機(jī)游走器，卻只存在3條路徑 時，The Fingerprinting Strategy 仍然需要產(chǎn)生3萬個隨機(jī)數(shù)

33、并對每一個隨機(jī) 游走器分配一條特殊的路徑，以概率學(xué)的角度來說，這樣一路路徑上就有1萬個 隨機(jī)游走器在工作。對于這樣的問題，Particle Filtering Strategy被提出，可表小如下：Input: distribution hi(e), relation R, threshold& minOutput: h i+1 (e)Set h i+1 (e) = 0 (should not take any time)for each e with h i(e) != 0 dosize new= hi (e)/|R(e)|if size new > £ min the

34、nfor each e ' G R(e) dohi+1 (e ' )+ = size newend forelsefor k=1.floor(hi(e)/e mm) dorandomly pick ee R(e)hi+1(e ' )+ = e min end forend ifend for其核心思想是剛開始將所有游走器看做一個整體大粒子， 在接下來的游走過 程中將粒子不斷分割成幾個等大小的小粒子再重復(fù)隨機(jī)游走，直到粒子大小被分 割小于實現(xiàn)設(shè)置好的閾值時，再將算法轉(zhuǎn)化為之前公式 2描述的精確計算。在文獻(xiàn)2中指出，隨機(jī)游走會產(chǎn)生一種不平衡的分布，小部分節(jié)點有高評 分，而大

35、部分節(jié)點是低評分(即符合幕率分布)。因此，可以做出這樣的假設(shè)：將 那些低評分的節(jié)點忽視掉，不但不會影響隨機(jī)游走鑒別重要實體的能力，反而還能極大的減少所需的時間和 計算內(nèi)存 耗費。此假 設(shè)已有相關(guān)文獻(xiàn)證 明。Truncation Strategies據(jù)此可以表示為：hi i(e) max(0,hi1(e)w(41)(11)其中亞(兀J為在hi+1中排名第 W勺概率，W是自定義參數(shù)，用來控制截斷的程度。這種截斷抽樣策略，同樣是用公式(11)替換公式(3),仍然服從公式(4)所描述的分布。如果一個低概率節(jié)點的h值非常小，我們就用0來代替那個非常 小的h值，而不再用本身的h值。這個臨界值可以有在hi+

36、1分布中的第W高的概 率決定。換句話說，就是在hi+1分布中，有很多個按概率大小排好的節(jié)點，我們 計算概率從前w個開始的節(jié)點的h值，在第W個后的節(jié)點，全部令它們的h值為 0,即在w位置進(jìn)行截斷。這種截斷策略還是鑒于將低評分的節(jié)點忽視掉，不但 不會影響隨機(jī)游走鑒別重要實體的能力，反而還能極大的減少所需的時間和計算 內(nèi)存耗費來設(shè)計的。上述幾種稀疏策略已經(jīng)通過文獻(xiàn)2的實驗證明，能有效的提高查詢執(zhí)行效 率與查詢質(zhì)量。具體改進(jìn)的實驗結(jié)果如下：24圖7Path Finding在以往的Path Ranking Algorithm 中，會規(guī)定一個最大的路徑長度 1。當(dāng)邊 的類型不多時，在公式(6)的P(q,1

37、)還可以被一一列舉出來，但如果說有很多種關(guān)系，如在知識庫的背景下，對一個節(jié)點的關(guān)系就可能有100多種，那么即使 路徑長度只有3,那么最終的路徑數(shù)量也會達(dá)到上百萬種之多。若想在這樣的背 景下利用 Path Rank Algorithm ,文獻(xiàn)4中對 Path Rank Algorithm 中路徑的 產(chǎn)生過程做了相應(yīng)的修改，只發(fā)現(xiàn)那些對查詢可能有用的路徑，忽略排名較低的 路徑。首先對于任意查詢實體e有hs p(e) 0 ,定義一個查詢s去發(fā)現(xiàn)一路路徑P, ,且路徑發(fā)現(xiàn)的過程中，創(chuàng)建任何一個節(jié)點都需要由一部分訓(xùn)練集中的查詢S支持，這個比例 人工指定。其次，只有當(dāng)在檢索時至少有一個目標(biāo)實體在訓(xùn)練集 中

38、時，才需要在RPA中發(fā)現(xiàn)路徑。在上述兩種約束下，經(jīng)實驗證明可以有效的減 少需要考慮的路徑數(shù)量。類似發(fā)現(xiàn)路徑以連接節(jié)點的思想并在 2002年的N-FOIL 中也被使用過，但是當(dāng)時使用的是一個查詢?nèi)グl(fā)現(xiàn)路徑，而不是RPA中以數(shù)據(jù)驅(qū)動的多查詢?nèi)グl(fā)現(xiàn)路徑，且 PRA可以用于非實意動詞中，而 N-FOIL不能。文獻(xiàn) 4中實驗證明了在發(fā)現(xiàn)重要路徑方面 RPA優(yōu)于N-FOIL。節(jié)所述的finger printing 與 particle filtering策略有個缺點是，他們會減弱隨機(jī)游走的多樣性。比如圖上只有兩條路徑的話，那么有50%勺可能性是所有的隨機(jī)游走器全部在一條路徑上，而另一條路徑被置空。針對這樣

39、的問題， 可以采用一種叫Low-Variance Sampling(LVS)的技術(shù)，該方法于2005年由Thrun 提出，廣泛運用于機(jī)器人學(xué)。文獻(xiàn)4總結(jié)了幾條未來的研究方向，其一是從查詢節(jié)點和目標(biāo)節(jié)點同時開 始做推測可能會更加有效的發(fā)現(xiàn)長路徑，而長路徑一般來說是比較好的路徑，且搜索效率應(yīng)當(dāng)更高。其二是從目標(biāo)節(jié)點開始查詢?nèi)グl(fā)現(xiàn)特殊的路徑，也就是反向的隨機(jī)游走算法。其三是對推測樹或推測圖去生成推測路徑可以更好的使用隨機(jī) 游走推測模型。最后提出隨機(jī)游走模型在大規(guī)模數(shù)據(jù)集上進(jìn)行關(guān)系學(xué)習(xí)是一種很 有研究價值的方向。還有相關(guān)研究表明，正向與反向的隨機(jī)游走混合模型對查詢效率有更好的提 開。結(jié)合上述基本的PR

40、A與其改進(jìn)，比較好的算法總結(jié)可以由圖8表示。StageComputationPath Discoverygiven (si/ GJ,find f;3cc(f)>=3, hits二hGenerate Training Samples generate (卻，tj and 卜，yjSgistic Regression Training產(chǎn)博”,海Predictionapply model to nodes s in domainrKnowledge Base Inference and Extension知識庫(KB)/知識圖譜經(jīng)常是不完整的，這就讓完善知識庫成為必需。Pathranking

41、algorithm 是完成這項任務(wù)的最有希望的方法，目前關(guān)于使用RPAS行知識庫的推斷與補全是一項研究熱點，近年來有許多在Freebase, DBPedia,NELL, YAGO? KB上的研究。上述文獻(xiàn)4則是首先提出了在大規(guī)模 KB上使用RPA 進(jìn)行關(guān)系學(xué)習(xí)的研究方向。文獻(xiàn)5提出，KB中會存在一些潛在的關(guān)系，這些關(guān)系對關(guān)系抽取有很大的 幫助，而傳統(tǒng)的基于文本的關(guān)系抽取模型并不能利用這些潛在的關(guān)系。使用 RPA 去學(xué)習(xí)結(jié)合了語義語法的規(guī)則，可以輕松在提取任務(wù)中融入現(xiàn)有的知識，并首次成功的嘗試了對大規(guī)模異構(gòu)數(shù)據(jù)運用關(guān)系學(xué)習(xí)方法。文獻(xiàn)5從兩方面對Pathranking algorithm 進(jìn)行了擴(kuò)

42、展：結(jié)合在KB中已有文本知識的語法與語義線索； 在web級規(guī)模的數(shù)據(jù)上分布式的實現(xiàn)了學(xué)習(xí)與推導(dǎo)算法。這使得在KB上學(xué)習(xí)語義語法規(guī)則成為了可能。如果RPA真型用從KB中生成的查詢正例與反例去訓(xùn)練， 那就要考慮到像Freebase中有上百萬條的概念與邊，而且還要在Freebase上擴(kuò) 展帶語法關(guān)系的話，這樣訓(xùn)練的話計算量將會非常大。況且用 Freebase生成的 查詢本身會偏向于Freebase本身的那些概念，而很難反映出文本數(shù)據(jù)上出現(xiàn)的 潛在概念，若果要學(xué)習(xí)Freebase本身沒有的概念的話，就必須解決這樣的問題。 針對這樣的問題，文獻(xiàn)5從三方面對 RPA做了擴(kuò)展：Scaling Up 、Sam

43、pling Training Data 、Text Graph Construction 。文獻(xiàn)6證明了在大規(guī)模語料庫上加入標(biāo)記了潛在特征的邊能有效的提升 RPAfi KB推測補全任務(wù)上的表現(xiàn)，可以看做是針對文獻(xiàn)5研究的改進(jìn)。由于文 獻(xiàn)5中使用的語法標(biāo)簽集合是非詞匯化依賴于角色標(biāo)簽 （沒有對應(yīng)的實詞），使 得其不能完全表達(dá)學(xué)習(xí)到的推理規(guī)則。為了克服這個問題，文獻(xiàn) 6在每條邊上 加入了更加詞匯化的語義標(biāo)簽（標(biāo)簽都是相互獨立的實詞）。這些邊都是以主題- 動詞-對象這種形式的三元組表示的。通過學(xué)習(xí)潛在加入的詞匯化的邊去得到需 要的標(biāo)簽，也可以避免傳統(tǒng) RPA特征過多與數(shù)據(jù)稀疏的問題。舉例如圖 9?？?/p>

44、以看到圖9本身是一個非連通圖，所以想通過傳統(tǒng)RPA學(xué)習(xí)到AlexRodriguez與World Series的關(guān)系是不可能的。如果說加上虛線所示的兩條潛 在的詞匯化的邊(Alex Rodriguez, play for, NY Yankees) 與(Alex Rodriguez, bats for, NY Yankees),這種關(guān)系就有可能被學(xué)習(xí)到。具體對于RPA說，就可以加入潛在的 <plays for,teamPlayIn> 去預(yù)測(Alex Rodriguez, atheteWonChampionship,World Series) 這個關(guān)系是否成立。經(jīng)文獻(xiàn) 6實驗所 述，這

45、種加入潛在邊的策略能有效提高在大規(guī)模KB上關(guān)系學(xué)習(xí)的效率。文獻(xiàn)7就在大規(guī)模KB上使用RPA!推測的任務(wù)，給出了 2種如何更好的使 用文本語料庫的方法。其一是提出了在一種結(jié)合KB上的關(guān)系與文本語料的技術(shù)， 使得它們比之前的研究結(jié)合的更加緊密，在一臺計算機(jī)上就可以實現(xiàn)相對大規(guī)模 的關(guān)系計算。其二是闡述了如何將空間向量的相似性加入在KB上的隨機(jī)游走推測，以減少RPA*身帶來的數(shù)據(jù)稀疏問題，具體描述為當(dāng)沿著邊類型的序列進(jìn)行 隨機(jī)游走時，同時允許沿著那些在語義上也相似的邊進(jìn)行游走。舉個列子，比如說一種邊叫作“ flows through "，那我們同時也以一定的概率接受類似“ run thro

46、ugh ”這樣的邊，這種概率由歐式空間相似度為度量。這兩種改進(jìn)都是在RPA選擇好特征路徑后，進(jìn)行概率計算時的改進(jìn)。具體計算公式如式(12)所示。其中 v()是以向量形式返回一條類型邊的函數(shù)，是調(diào)節(jié)空間相似性所占權(quán)重的比例系數(shù)。pg | i) exp(v(ej) v( J), j,1 j m(12)其中冗是各個邊類型的集合序列，即兀=ei,e2, . , e ? ,i代表在這個集合中的第i條邊類型，在傳統(tǒng)RPA中，當(dāng)隨機(jī)游走到一個出度為 m的節(jié)點時， 會選擇符合i的那些邊類型，再隨機(jī)的在這些符合條件的邊中選擇一條游走，公式(12)則表述了另一種選擇哪一條邊概率計算方法。當(dāng)隨機(jī)游走到一個出度為 m

47、的節(jié)點時，不去找符合i的那些邊類型了，而是選擇所有符合一定相似性的所有 邊。比如三元關(guān)系組(Tom, visiting, Beijing)這樣的關(guān)系，我們選擇visiting 這個邊的時候，如(Tom, touring, Beijing) 、(Tom, going, Beijing)這樣的關(guān)系也認(rèn)為成立，關(guān)系touring與going的邊也放在選擇列表中。公式(12)中的0 可以控制具體這樣的擴(kuò)展范圍有多大，比如B =1時，認(rèn)為 visiting=touring=going , 0=10 時，貝U visiting=touring going ,再擴(kuò)大 0 =100 時，visiting to

48、uring going ,即隨著 0 的增 大，文獻(xiàn)7描述的方法向傳統(tǒng)的RPAB近。文獻(xiàn)8指出由于RPA是一種2階段算法，即先找出連接各個節(jié)點的路徑集 合，還要在特征矩陣中計算這些路徑的概率，因而計算量較大，特別是運用于大規(guī)模KB補全任務(wù)上時耗時過長，因此提出了一種名為subgraph featureextraction(SFE)的更加簡單高效的算法去生成知識圖的特征矩陣。SFE與只作第一步的RPAf目似，對給定圖上的節(jié)點集合，先本地搜索去標(biāo)記這對節(jié)點周圍的 節(jié)點作為子圖，接下來去在這些子圖上進(jìn)行特征提取，去獲得每一組節(jié)點對的特 征向量。這樣就可以不必計算特征矩陣的每一種路徑組合的隨機(jī)游走概率

49、，可以抽取更加有表現(xiàn)力的特征，甚至包括那些不以路徑形式表現(xiàn)出來的關(guān)系，還可以以廣度優(yōu)先搜索代替隨機(jī)游走，以更加詳細(xì)標(biāo)記本地節(jié)點構(gòu)成的圖。文獻(xiàn)9指出前對PRA的研究一般是遵循單任務(wù)學(xué)習(xí)范式，為它們及其訓(xùn)練 數(shù)據(jù)的每個獨立關(guān)系構(gòu)建一個預(yù)測模型。它忽略了某些關(guān)系中有意義的聯(lián)系，而且因為更低頻的聯(lián)系而得不到足夠的訓(xùn)練數(shù)據(jù)。因此文獻(xiàn)9為RPA提出了一個新穎的多任務(wù)學(xué)習(xí)框架，稱之為緊密耦合的 PRA (CPRA)。它首先設(shè)計一個凝聚 式聚類策略，自動發(fā)現(xiàn)高度相關(guān)的關(guān)系，然后利用多任務(wù)學(xué)習(xí)策略有效地結(jié)合對 這種關(guān)系的預(yù)測。CPRA將這些關(guān)系都考慮進(jìn)來，使得內(nèi)隱數(shù)據(jù)在它們之間分享。CPRA等KB補全任務(wù)看作是

50、一個二值分類的問題，就是說給定一個關(guān)系r,。是KB上的三元組關(guān)系，對于任意實體對(h, t)有(h,r,t),就去判斷h和t是否 被r連接。R R代表著要被預(yù)測到關(guān)系，則對于每一個關(guān)系 r R都有一個對 應(yīng)的訓(xùn)練實例集合。對于每一對實體對，路徑特征用傳統(tǒng)的RPAtt取計算，對于 抽取到的關(guān)系r的路徑特征集合以表示，訓(xùn)練集合被定義為,(Xir,yir), Xir是實體對的特征向量，對應(yīng)所有屬于的路徑。yir是取值為1的標(biāo)簽。CPRA 用多任務(wù)學(xué)習(xí)策略進(jìn)行KB補全任務(wù)，具包含兩個方面：關(guān)系聚類與關(guān)系耦合。 關(guān)系聚類用以自動發(fā)現(xiàn)高相關(guān)度的關(guān)系，關(guān)系耦合去學(xué)習(xí)這些關(guān)系。在關(guān)系聚類方面，需要發(fā)現(xiàn)那個高相

51、關(guān)度的關(guān)系才能聚類，具體的，以網(wǎng)為起點聚類，每個聚類只含有一個關(guān)系r R,| |是基數(shù)的集合。然后遍歷的合并最相似的聚類， 相關(guān)度以公式(13)計算。Sim(Ci, Cj)CiCj|min( C ,| Cj )(13)公式(13)表示了發(fā)現(xiàn)這些高相關(guān)度關(guān)系方法的核心思想： 如果兩個關(guān)系，他們之 間的共享路徑或共享特征越多，他們就越相似，即相關(guān)度高。其中Ci是與聚類C關(guān)聯(lián)的特征集合。即在兩個需要聚類的 C與C間，找出他們共同的特征來作 為分子，并以其中一個小的聚類中的特征為分子， 計算出它們的相關(guān)度來。舉例: 一個聚類蘋果，其特征集合為水果，甜的，圓形,另一個聚類菠蘿，其特征集 合為水果，甜的，

52、柱狀，有刺。則他們之間的相關(guān)度以公式13計算為：Sim（蘋果，菠蘿）|水果，甜的|2min（|水果，甜的,圓形|） 3可以看到蘋果和菠蘿的相似性比較的高了， 在用戶搜索蘋果的時候，就可以考慮 將菠蘿作為查詢實體進(jìn)行排名評分。在聚類之后，CRPA下一步將對于每一個聚類中不同關(guān)系的路徑排序進(jìn)行耦合以同時學(xué)習(xí)分類任務(wù)。在一個包含K個關(guān)系的聚類C二，.，rk中，有 c % b.0。對于關(guān)系K的的訓(xùn)練 實例，使用共享的特征集合，使得所有的訓(xùn)練數(shù)據(jù)在同一個空間內(nèi)， 與改進(jìn)后的 第k個關(guān)系相關(guān)的訓(xùn)練數(shù)據(jù)以Tk = （x ik,yik）Nk表示，然后一起學(xué)習(xí)K個分類器 fi, f2, . , fk以達(dá)到最終的補全任務(wù)。驗結(jié)果表明， CPRA能有效地確認(rèn)出有 邏輯關(guān)聯(lián)的集群，它們彼此是高度相關(guān)的。就預(yù)測的準(zhǔn)確率和模型的可解釋性而 言，通過進(jìn)一步結(jié)合這種關(guān)系，CPRA