pathrankingalgorithm調(diào)研報(bào)告

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

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

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

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

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

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

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

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

9、一條這樣的判斷路徑：Charlotte- »Patrick Bronte- »Writer。若這三個(gè)點(diǎn)間的兩條邊存在，我們同樣可以得到Charlotte是一個(gè)作家的結(jié)論。值得注意的是在判定Charlotte是否是一個(gè)作家時(shí)，Charlotte的行為無疑對(duì)判定也是有幫助的，那么我們的判定圖可以表述為：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)是一個(gè)很復(fù)雜的圖了，而實(shí)際上我們?cè)谧雠袛嗟臅r(shí)候，可能考慮的遠(yuǎn)比這還要復(fù)雜，其計(jì)算復(fù)雜度主要體現(xiàn)在它有指數(shù)級(jí)增長(zhǎng)的路徑類型和 指數(shù)級(jí)增長(zhǎng)的路徑實(shí)例。圖中每?jī)蓚€(gè)點(diǎn)之間存在的邊，對(duì)應(yīng)著我們需要學(xué)習(xí)到的 關(guān)系，可以發(fā)現(xiàn)不同的點(diǎn)之間關(guān)系的種類并不相同，如 Charlotte與Jane Eyre 之間，是 wrote的關(guān)系，而Jane Eyre與Novel之間，是IsA的關(guān)系。而 RWR 并不能有效的區(qū)分這樣的區(qū)別，前面的類型信息會(huì)被后面的類型信息覆蓋，而下面提到的Path Ranking Algorithm可以很好的解決這樣的問題

11、。Path Ranking Algorithm有一些相關(guān)研究，如Minkov, Cohen等在基于RWR勺模型上使用了更加豐富 的特征集合，用邊上的標(biāo)簽對(duì)排序結(jié)果再次排序。并且他們還提出了一種加權(quán)的RWR-paths方法，提高了查詢到相關(guān)實(shí)體的準(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 相 比較前兩者，具有容易推測(cè)與不需要關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)先驗(yàn)知識(shí)的優(yōu)點(diǎn)。其算法核心思想是利用連接著兩個(gè)實(shí)體的路徑去預(yù)測(cè)他們之間是否有潛在 的關(guān)系。舉個(gè)例子，如圖7所示，我彳門要判定Charlotte是不是作家，可以判定 這樣一組特定的關(guān)系序列是否成立：Prob (Charlotte- » Writer | InSentence,InSentence-1, IsA )圖7Path rank

13、ing algorithm可以通過不同的邊類型序列來判定一個(gè)關(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)或者可以舉個(gè)其他的例子，如果我需要查找一些參考文獻(xiàn)，其中一個(gè)關(guān)鍵字 是年份y,那么可能有這樣的兩種方式：一、找出所有y年出版的論文。二、出版于y年經(jīng)常被引

14、用的論文。顯然第二種方法更加合理，為了更加準(zhǔn)確的描述所 需信息，定義R是一個(gè)二值關(guān)系，如果e與e'有關(guān)系R成立，則記作Re, e'), 并定義R(e) e:R(e,e')。dom(R)用來表示知識(shí)領(lǐng)域 R, range(R)表示領(lǐng)域R的 范圍。P是一條關(guān)系路徑，由一組關(guān)系R, R, ., R l組成，其中對(duì)于任意的i,都滿足 1< i < L-1, range(Ri)=dom(R+1)。并且有定義 dom(R1 .RL) dom(R1),且有range(R.R) range(R)。如果希望強(qiáng)調(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)系。可以看到每條關(guān)系路徑都是paper,正是查找參考 文獻(xiàn)想要的信息類型。對(duì)于任意的P=R,R2,.R l和查詢實(shí)體 集合Eq dom(P)。如果P是空路徑，我們定義其滿足如下分布：.1/Eq,if e Eq(3)hE

16、q, p(e)0, otherwise公式(3)主要用于在RPA開始時(shí)，計(jì)算第一步連接出發(fā)節(jié)點(diǎn)與第二個(gè)節(jié)點(diǎn)的概率計(jì)算。假設(shè)我需要購(gòu)買一臺(tái)PC,想知道具體買什么好。這樣的任務(wù)在圖 8所示具體問題上可表述為：首先只有查詢起點(diǎn)PC,沒有任何一條連接到其他節(jié)點(diǎn)的路徑，此時(shí)考慮關(guān)系R=HaveBrand1,假設(shè)有相關(guān)的Eq=中國(guó)，美國(guó)，老撾,對(duì)于任意e Eq此時(shí)會(huì)以相同的概率hEqp(e) 1/3隨即游走到a1,b1,c1上來，對(duì) q q, p于牛奶 Eq,則對(duì)應(yīng)的h為0,即不會(huì)隨機(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é)點(diǎn)e 一步隨機(jī)游走到e'的 概率，I(R(e ' ,e)表示在e與e'到底有沒有關(guān)系R存在。在e'與e滿足關(guān)系 R時(shí)取值1,否則取值00以路徑長(zhǎng)度？ =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,此時(shí) 會(huì)進(jìn)行第二步游走，引入新的查詢實(shí)體，rang(Rz)=聯(lián)想,如果此時(shí)有聯(lián)想， 香蕉兩個(gè)新實(shí)體e'與P相連接，首先指示器函數(shù)判定e'于e是否存在關(guān)系R, 即這樣兩個(gè)三元組(中國(guó)，inWhichCountry-1,聯(lián)想)與(中國(guó)，inWhichCountry -1, 香蕉)是否成立。顯然(中國(guó)，inWhichCountry -1,香蕉)不成立，則I(R(e ' ,e)=0 ,HaveBrand-1 inWhichCou ntry -1使得路徑 P1=PC中國(guó)香蕉 這條路徑的中的第二步游走分布inWhichCou ntry-1中國(guó)香蕉的h值為0,即關(guān)系in

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、并對(duì)每一個(gè)隨機(jī) 游走器分配一條特殊的路徑，以概率學(xué)的角度來說，這樣一路路徑上就有1萬個(gè) 隨機(jī)游走器在工作。對(duì)于這樣的問題，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其核心思想是剛開始將所有游走器看做一個(gè)整體大粒子， 在接下來的游走過 程中將粒子不斷分割成幾個(gè)等大小的小粒子再重復(fù)隨機(jī)游走，直到粒子大小被分 割小于實(shí)現(xiàn)設(shè)置好的閾值時(shí)，再將算法轉(zhuǎn)化為之前公式 2描述的精確計(jì)算。在文獻(xiàn)2中指出，隨機(jī)游走會(huì)產(chǎn)生一種不平衡的分布，小部分節(jié)點(diǎn)有高評(píng) 分，而大

35、部分節(jié)點(diǎn)是低評(píng)分(即符合幕率分布)。因此，可以做出這樣的假設(shè)：將 那些低評(píng)分的節(jié)點(diǎn)忽視掉，不但不會(huì)影響隨機(jī)游走鑒別重要實(shí)體的能力，反而還能極大的減少所需的時(shí)間和 計(jì)算內(nèi)存 耗費(fè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ù)，用來控制截?cái)嗟某潭取＿@種截?cái)喑闃硬呗?，同樣是用公?11)替換公式(3),仍然服從公式(4)所描述的分布。如果一個(gè)低概率節(jié)點(diǎn)的h值非常小，我們就用0來代替那個(gè)非常 小的h值，而不再用本身的h值。這個(gè)臨界值可以有在hi+

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

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

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

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

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

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

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

44、以看到圖9本身是一個(gè)非連通圖，所以想通過傳統(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í)到。具體對(duì)于RPA說，就可以加入潛在的 <plays for,teamPlayIn> 去預(yù)測(cè)(Alex Rodriguez, atheteWonChampionship,World Series) 這個(gè)關(guān)系是否成立。經(jīng)文獻(xiàn) 6實(shí)驗(yàn)所 述，這

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

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

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

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

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

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

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

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