pathrankingalgorithm调研报告VIP

1、v1.0可编辑可修改path ranking algorithm 调研报告近两年来，随着Linking OpenData等项目的全面展开，语义 Web据源的数量激增，大量RD嘤据被发布。互联网正从仅包含网页和网页之间超链接的文 档万维网(Document Web)转变成包含大量描述各种实体和实体之间丰富关系的 数据万维网(Data Web在这个背景下，Google、百度和搜狗等搜索引擎公司纷 纷以此为基础构建知识图谱，如 Knowledge Graph、知心和知立方等，用以改进 搜索质量，从而拉开了语义搜索的序幕。正如Google的辛格博士在介绍知识图谱时提到的：“The world is n

2、ot madeof strings , but is made of things."，知识图谱旨在描述真实世界中存在的各种实体或概念。其中，每个实体或概念用一个全局唯一确定的ID来标识，称为它们的标识符(identifier) 。每个属性-值对(attribute-value pair ,又称 AVP)用来刻画实体的内在特性，而关系(relation) 用来连接两个实体，刻画它们 之间的关联。知识图谱亦可被看作是由一张巨大的图组成，图中的节点表示实体或概念，而图中的边则由属性或关系构成，我们需要构建并使用这张图。大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，其中主要包括

3、：实体链指(Entity Linking )、关系抽取(Relation Extraction )、知 识表示(Knowledge Representation )、知识推理(Knowledge Reasoning)等。在知识推理方面，利用推理规则实现关系抽取的经典方法之一就是PathRanking Algorithm 算法，由Lao & Cohen与2010年提出。该方法将每种不同 的关系路径作为一维特征，通过在知识图谱 /Knowledge Base中统计大量的关系 路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取 效果，成为近年来的关系抽取的代表方法之一。但

4、目前这种基于关系的统计的方法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题, 且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。2. Path Ranking AlgorithmRandom Walk and RestartRandom walk with restart（RWR谡最初提 出的图像分割算法，也叫Personalized Page Rank。它迭代地探讨了网络的全局结构，估计两个节点之间 的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移 动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R称为“重启的概率（

5、1- R移动到一个邻居的概率）。迭代后达到稳定，稳定的 概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可 以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足 式：R=(1-d)u+dWr其中，d是继续游走概率，（1-d）为重启概率，u是启动节点，Wr是网络过 渡矩阵。随机游走（RWR界际是一个简单的迭代过程：Rt=（1-d）u+dWrt-1（2）式（2）表示了这样一个迭代的过程：算法从图中顶点u出发，沿图中的边随机游走。在任意点上，算法以一定的概率d随机地选择与该顶点相邻的边，沿这 条边移动到下一个顶点，或以（1-d）概率直接回到出发点u,这是这个重启

6、概率 可有效的防止由于随机游走的不确定性而进入一条权值很小的路径。在第t-1步时移动带下一个顶点时，就开始了以这个点新出发点的第t步随机游走，其中 Wr1表示的是在t-1步游走时从一个节点游走到另一个节点概率。经过若干次随机游走过程，可以到达图中每一个顶点的概率值达到平稳分布，即再次迭代也不改变图中的概率分布值时，就可以得到的R值来对所求任务进行排序。比如讲RW期用在下图做图像分割时：图1假设图像最核心的部分是红色，次核心为黄色，需排除的部分为蓝色。开始 游走时路径沿着最左面的蓝色路径走， 每一次游走都进入了不需要的部分， 直到 某次重新启动成功，返回最最上角的开始节点重新游走，第二次沿着绿色

7、的路径 游走，识别到了部分次核心区域，在某一步是再次重启，沿着黑色的路径识别到 了核心区域。由（2）公式就可以迭代的计算出每条路径覆盖范围的概率大小，在 N次游走达到稳定后，上图的每一部分子图都会有一个确定不变的概率，结合核 心、次核心与需排除部分的权重，就可以计算出每个子图的评分， 从而找出评分 最高的核心区域。目前已有许多关于RWR勺研究，包括使用RWR4行分类，关系 学习与一般化的图上的相似性度量等。Relational Learning要实现关系抽取，其中对关系的推导学习是很重要的一部分。 在大数据的背 景下，预测一个关系是否成立具有极大的研究潜力。我们可以用下图描述一个关 系学习问题

8、：7如果想要判定Char10tte是否是一个作家。最简单的情况如图1所示，我们 需要两个点与一条边来描述这个问题，我们可以通过判定这两个点之间是否存在 这样的一条边，来判定这两个点是否存在关系。而这条边存在的概率有多大，如何定量计算，就是 Path Ranking Algorithm 可以解决的问题。而现实的情况必然不由简单的图2可以描述清楚的，如果我们在判断Charlotte 是否是一个作家时，考虑到了他的朋友与家庭等关系时，（这可以为我们的判断提供更多的依据），那么情况可能会是这样：我们仍以Charlotte为出发点，Writer为终点来判断Charlotte是否是一个作家，但这次我们多了

9、一条这样的判断路径：Charlotte- »Patrick Bronte- »Writer。若这三个点间的两条边存在，我们同样可以得到Charlotte是一个作家的结论。值得注意的是在判定Charlotte是否是一个作家时，Charlotte的行为无疑对判定也是有帮助的，那么我们的判定图可以表述为：IsA1 is the reverse of 15A relationWrote*1 is the reverse of Wrote relation如果在考虑到出版社等问题，我们还要加上这样的关系:至此我们需要考虑的关系图变了这样:Prn hChrir oTtp 今 WritT

10、er)ProbfChariotte T Painter)图5可以看到这已经是一个很复杂的图了，而实际上我们在做判断的时候，可能考虑的远比这还要复杂，其计算复杂度主要体现在它有指数级增长的路径类型和 指数级增长的路径实例。图中每两个点之间存在的边，对应着我们需要学习到的 关系，可以发现不同的点之间关系的种类并不相同，如 Charlotte与Jane Eyre 之间，是 wrote的关系，而Jane Eyre与Novel之间，是IsA的关系。而 RWR 并不能有效的区分这样的区别，前面的类型信息会被后面的类型信息覆盖，而下面提到的Path Ranking Algorithm可以很好的解决这样的问题

11、。Path Ranking Algorithm有一些相关研究，如Minkov, Cohen等在基于RWR勺模型上使用了更加丰富 的特征集合，用边上的标签对排序结果再次排序。并且他们还提出了一种加权的RWR-paths方法，提高了查询到相关实体的准确率。而 Path ranking algorithm 算法与之类似，可以看做是其一种改进版本，相当于沿着一组带有特定类型信息 的边的序列集合上的随机游走，即限制了游走路径的RWRT法。相比于RWR£法 区分边的类型，它更容易加入额外所需的类型信息，如它的 query-independent experts 与 popular entity

12、experts 。 类彳以的技术还有 Embedding-based techniques 与 Probabilistic graphical models , Path ranking algorithm 相 比较前两者，具有容易推测与不需要关于网络结构先验知识的优点。其算法核心思想是利用连接着两个实体的路径去预测他们之间是否有潜在 的关系。举个例子，如图7所示，我彳门要判定Charlotte是不是作家，可以判定 这样一组特定的关系序列是否成立：Prob (Charlotte- » Writer | InSentence,InSentence-1, IsA )图7Path rank

13、ing algorithm可以通过不同的边类型序列来判定一个关系是否存在，在比较复杂的图6上，我们可以看到至少有一下三种不同的边类型序列可 以做出判定：Prob (Charlotte Writer |HasFather,IsA)Prob (Charlotte Writer | Write, IsA, IsA-1, Write, IsA) Prob (Charlotte Writer |InSentence InSentence-1, IsA)或者可以举个其他的例子，如果我需要查找一些参考文献，其中一个关键字 是年份y,那么可能有这样的两种方式：一、找出所有y年出版的论文。二、出版于y年经常被引

14、用的论文。显然第二种方法更加合理，为了更加准确的描述所 需信息，定义R是一个二值关系，如果e与e'有关系R成立，则记作Re, e'), 并定义R(e) e:R(e,e')。dom(R)用来表示知识领域 R, range(R)表示领域R的 范围。P是一条关系路径，由一组关系R, R, ., R l组成，其中对于任意的i,都满足 1< i < L-1, range(Ri)=dom(R+1)。并且有定义 dom(R1 .RL) dom(R1),且有range(R.R) range(R)。如果希望强调路径上每一步的类型信息，可以将P = Ri, R 2. R L 表

15、示为：RiRlTo .其中 T(=dom(R)=dom(P), T1 = range(R1) = dom(R2) 。据此定义，上述以 关键字年份搜索参考文件任务的两种方法可以表示成下面这样:v1.0可编辑可修改TrtPublis h edfn -i111 : yearpaperH 2 : 4/rarPubtinhrdlnJCitr* paperpaper其中-1表示相反的主客体关系。可以看到每条关系路径都是paper,正是查找参考 文献想要的信息类型。对于任意的P=R,R2,.R l和查询实体 集合Eq dom(P)。如果P是空路径，我们定义其满足如下分布：.1/Eq,if e Eq(3)hE

16、q, p(e)0, otherwise公式(3)主要用于在RPA开始时，计算第一步连接出发节点与第二个节点的概率计算。假设我需要购买一台PC,想知道具体买什么好。这样的任务在图 8所示具体问题上可表述为：首先只有查询起点PC,没有任何一条连接到其他节点的路径，此时考虑关系R=HaveBrand1,假设有相关的Eq=中国，美国，老挝,对于任意e Eq此时会以相同的概率hEqp(e) 1/3随即游走到a1,b1,c1上来，对 q q, p于牛奶 Eq,则对应的h为0,即不会随机游走到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 ' )|表示沿着边？从节点e 一步随机游走到e'的 概率，I(R(e ' ,e)表示在e与e'到底有没有关系R存在。在e'与e满足关系 R时取值1,否则取值00以路径长度？ =2举例，即P'为关系边R, R2构成的 8v1.0可编辑可修改路径图9若R1为HaveBrand1关系，R2为inWhichCountry -1关系。具体PC推荐任务 图9上可表示为：首先P为空，以式2所述概率随机游走，假

18、设选择 a1,此时 会进行第二步游走，引入新的查询实体，rang(Rz)=联想,如果此时有联想， 香蕉两个新实体e'与P相连接，首先指示器函数判定e'于e是否存在关系R, 即这样两个三元组(中国，inWhichCountry-1,联想)与(中国，inWhichCountry -1, 香蕉)是否成立。显然(中国，inWhichCountry -1,香蕉)不成立，则I(R(e ' ,e)=0 ,HaveBrand-1 inWhichCou ntry -1使得路径 P1=PC中国香蕉 这条路径的中的第二步游走分布inWhichCou ntry-1中国香蕉的h值为0,即关系in

19、WhichCountry ”的h值为0,从而整条路径的h值变小。而其中当三元组关系(中国,inWhichCountry -1,联想)存在时， I(R(e ' ,e)=1时，再递归的以中国为出发节点，利用公式(3)计算一个h值， 这个h乘上一个不为 0的从e到e' 一步随机游走的概率，最终整体路径 -1 HaveBrandinWhichCou ntry-1P2=PC中国联想的h值肯定会明显大于P10至此就可以对查询所需的结果进行排名：1hEq,R(e)2hEq,P2(e) nhEq,Pn(e)(5)-1HaveBrandinWhichCou ntry-1如图10,假设有一条路径

20、P=PC中国联想 .Y450-tsi,路径长度为n,最终结果为型号为Y450-tis的PG由公式(4)计算出每一步游走的h值，也就是每一个连接2个节点的关系R的h值，最终将这些h值求和，利 用公式(5)就可以得到路径P的最终排名得分，但是需要注意到的是，在这条路 径中，每一步的的权重也许并不相同，这也是会影响最终得分的重要因素之一。比如在在图10的a1,b1,c1均成立的条件下，考虑到中国美国的PC水平会明显1HaveBrand高于老挝，人们都不会倾向于购买老挝的PC产品，那么此时虽然PC 中国、 11HaveBrandHaveBrandPC 美国、PC 老挝均成立，却需要去调整根据公式(3)

21、的计算11HaveBrand 1HaveBrand 1出的均为1/3的概率得分，通过 ，应使得PC 中国、PC 美国的 得分明显高于老挝的得分。图10假设如图11所示，有abc三条不同路径指向统同一款 PC型号Y450-tsi ,那么每条路径都会有一个对应的概率，分别可以表示为：Pa( PC Y450| whichCountry, whichBrand, choosePb( PC Y4501 whichYear, choos8Pc(PC Y4501choosR图11根据公式(5)我们可以分别求得上述Pa、Pb、Pc的值，但最终我们需要的是Y450这款PC的推荐评分到底是多少，而不是具体每一条路

22、径的评分。所以应当将所有指向这同一结果的各个概率评分求和，可以用公式(6)表示：score(e, )hEq,p(e)p(6)P (q,l)具体对于图11而言，P是在？ <4的情况下，结果都指向Y450这个查询结果的任意一条路径。对于 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是通过 训练获得的路径权重。p为具体的一条起点s到终点n的路径，若有Pf+R

23、+i, 其中兀=R, R. R l,则满足：p(s t; ) P(s z; ')P(z t;R) (8)剩下的问题就是对参数 9的估计，有许多方法可以使用，最常用的如逻辑 回归分类模型、BLMVML-BFG胡。我们可以用关系R和(起点si,终点ti )的 集合来构造所需的训练集，最终通过分类器得到所需的权重。Path Ranking Algorithm 的扩展Query Independent Paths对于描述一个实体的特征取决于这些特征在图中相对查询实体的位置，而对于一个实体的关联关系可能还取决于一些独立于查询的特性。对于推荐参考文献这一项任务来说，其最近的出版商，引用数量，和作者

24、曾经在哪里发表过文章都 会有影响。考虑到查询实体这些复杂的特点，我们可以将我们的查询Eq做扩展， 让每个查询Eq都包含一个特殊的实体e*。这样做之后，对于每一种类型信息T, 都有关系AnyT使得AnyT (e*,e )对于所有属于T的E都成立。如关系AnyPaper 将映射e*为每个paper,关系AnyYearr将映射e*为每个year。AnyPaperCite举个例子，如果有这样的路径：e paper paper,这代表着我们以相等的概率随机选择任何一个paper作为开始节点，然后游走到它的一篇参考文献 上。这样最后得到的结果有很大的概率会是一个有高引用量的paper。一条以AnyPape

25、r作为开始节点的路径，随后沿着两条引用关系的边去分配权重给那些 经常被高引用量文章引用的paper,随着路径的不断增长，这种结合了多种独立 于查询路径的算法，开始类似于在引用量构成的图上使用PageRank算法。这种情况，称其为 Query Independent Paths (RPA-qip),仍然是以式(2) 来计算评分，但其好处是因为这些路径都是独立于查询的，我们可以通过提前计算它们的值来改善整体 Path Ranking Algorithm的效率。Popular Entity Biases对于一些特定的查询检索任务，用户可能感兴趣的是一些计算出的排名相对 低但被点击次数很多的查询结果，

26、这是主要是因为有一些特征不能很好的被排名 系统识别。在这种情况下，如果能将这些点击次数大的查询结果或文档给以较高 的排名，就可以给用户更好的体验。对于个性化的搜索，不同的用户在同一个查12v1.0可编辑可修改询下可能需要的是不同的结果，比如单词“ mouse',对于一个生物学家来说他 需要的是老鼠的相关信息，而对于一个程序员来说，更加可能的是代表鼠标的意 思。所以，我们对查询者与查询目标建立一个联系， 对上述这种情况可能会有一 定的帮助。Popular Entity Biases是一种简单而又适用性广的方法。它通过对查询目标添加一个查询偏好来建立对查询实体的流行度。对于一个查询任务，有

27、查询类型Tc，查询目标类型 Tq, Popular Entity Biases会对每一个查询目标e Tq增e' , e）引入条件流行实体偏RPA与RPA-qip的排名计算公加一个流行实体偏好epop ,并对每一对查询实体（ 好e, e,其中e' T°,e Tq。在这种情况下，对于式6就不在适用了，可以将公式2扩展为:s(e；)hEq,p(e) pP (q.l)popepope,ee, Eq(8)或者以矩阵形式表示为:(9)popq其中pop用于连接所有偏好参数，一个条件偏好参数构成的矩阵，q是一个二值指示器（0 or 1）,用于表示每个实体是否包含在查询中。可以看出在

28、式8中参数的取值可能会非常大的，pop的长度相当于所有查询目标实体的总数，也是一个很大的矩阵，行数为目标实体的数，列数等于查询中所有的实体类型 数。举个列子，比如 Apple这个查询词，其可能对应查询实体有苹果（水果），或Apple Compute评果公司），如果在最近苹果刚刚发布了 iPhone7的背景下，有 用户查询了 Apple这个关键词，更应当出现的查询结果是 Apple Compute,而 pop不是水果。此时就可以通过设置公式8中的不同的流行偏好来调节查询结果。同理，对于查询关键词e苹果，设e'为实体手机，实体对（苹果，手机）在公式 13v1.0可编辑可修改8中的 epOp

29、会相对于实体对（苹果，水果）在上述背景下应当更大。结合两个针 e' Eq对流行度的计算参数，Popular Entity Biases 可以使RPA更加准确的对查询结果评分排名。Path Ranking Algorithm较之前的各算法，具有表示能力强，鲁棒性高，适用与大规模数据的优点。3. Path Ranking Algorithm的发展与应用Efficient InferencePath Ranking Algorithm 可以看做是基于路径限制的一种随机游走算法，它 在关系学习方面有良好的表现，但是这种算法的代价高昂，在推测路径中会产生 大量概率非零的中间节点，但实际上我们并不

30、需要很多的随机游走就可以将查询 目标从噪声节点中区分出来。文献2采用稀疏化策略fingerprinting, particle filtering, fixed truncation与 beam truncation 针对对止匕问题对Path Ranking Algorithm算法进行了改进，达到了更加高效的关系推测学习。有文献3提出了一种近似于personalized PageRank的蒙特卡罗算法，这 种算法描述了从查询节点出发，产生k条独立的随机游走，节点的概率由它被随 机游走到的被归一化后的次数来确定，并指出这样就可以由K的大小来轻易的控 制计算量的大小，且只需要相对比较少的随机游走器

31、就可以区分出高、中、低排名的查询结果节点。这样虽然会对低排名节点的计算精度有影响，但是查询结果是否符合人们的要求，主要是由那些高质量的查询结果决定的，低排名的结果的精度对于整体查询并不会有很大的影响。根据这样的结论，文献 2在Path Ranking Algorithm 算法的基础上提出了 The Fingerprinting Strategy 的稀疏 化抽样策略，将Path Ranking Algorithm算法中每一步的h计算方法替换为：#wal kers visting e hi i(e)#wal kers(10)这种抽样策略，仅仅是用公式(10)替换公式(3),仍然服从公式(4)所描述

32、的 分布。h值的确定不再像公式(3)中对所有包含在查询集合中的实体数量等概率 确定，而是随机游走器与被游走到的次数来确定概率大小。比如可以设置 10个 随即游走器，如果一个节点总共被这10个随即游走器游走到了10次，那么这个节点的h值就是1,而不是由具体的查询相关的实体数量决定。这样做的好处是 可以通过控制随机游走器的数量，来灵活的控制计算量的大小。而上述The Fingerprinting Strategy在随机游走器的数量远大于链路数量时，可能会引起很大的计算浪费。比如有3万个随机游走器，却只存在3条路径 时，The Fingerprinting Strategy 仍然需要产生3万个随机数

33、并对每一个随机 游走器分配一条特殊的路径，以概率学的角度来说，这样一路路径上就有1万个 随机游走器在工作。对于这样的问题，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其核心思想是刚开始将所有游走器看做一个整体大粒子， 在接下来的游走过 程中将粒子不断分割成几个等大小的小粒子再重复随机游走，直到粒子大小被分 割小于实现设置好的阈值时，再将算法转化为之前公式 2描述的精确计算。在文献2中指出，随机游走会产生一种不平衡的分布，小部分节点有高评 分，而大

35、部分节点是低评分(即符合幕率分布)。因此，可以做出这样的假设：将 那些低评分的节点忽视掉，不但不会影响随机游走鉴别重要实体的能力，反而还能极大的减少所需的时间和 计算内存 耗费。此假 设已有相关文献证 明。Truncation Strategies据此可以表示为：hi i(e) max(0,hi1(e)w(41)(11)其中亚(兀J为在hi+1中排名第 W勺概率，W是自定义参数，用来控制截断的程度。这种截断抽样策略，同样是用公式(11)替换公式(3),仍然服从公式(4)所描述的分布。如果一个低概率节点的h值非常小，我们就用0来代替那个非常 小的h值，而不再用本身的h值。这个临界值可以有在hi+

36、1分布中的第W高的概 率决定。换句话说，就是在hi+1分布中，有很多个按概率大小排好的节点，我们 计算概率从前w个开始的节点的h值，在第W个后的节点，全部令它们的h值为 0,即在w位置进行截断。这种截断策略还是鉴于将低评分的节点忽视掉，不但 不会影响随机游走鉴别重要实体的能力，反而还能极大的减少所需的时间和计算 内存耗费来设计的。上述几种稀疏策略已经通过文献2的实验证明，能有效的提高查询执行效 率与查询质量。具体改进的实验结果如下：24图7Path Finding在以往的Path Ranking Algorithm 中，会规定一个最大的路径长度 1。当边 的类型不多时，在公式(6)的P(q,1

37、)还可以被一一列举出来，但如果说有很多种关系，如在知识库的背景下，对一个节点的关系就可能有100多种，那么即使 路径长度只有3,那么最终的路径数量也会达到上百万种之多。若想在这样的背 景下利用 Path Rank Algorithm ,文献4中对 Path Rank Algorithm 中路径的 产生过程做了相应的修改，只发现那些对查询可能有用的路径，忽略排名较低的 路径。首先对于任意查询实体e有hs p(e) 0 ,定义一个查询s去发现一路路径P, ,且路径发现的过程中，创建任何一个节点都需要由一部分训练集中的查询S支持，这个比例 人工指定。其次，只有当在检索时至少有一个目标实体在训练集 中

38、时，才需要在RPA中发现路径。在上述两种约束下，经实验证明可以有效的减 少需要考虑的路径数量。类似发现路径以连接节点的思想并在 2002年的N-FOIL 中也被使用过，但是当时使用的是一个查询去发现路径，而不是RPA中以数据驱动的多查询去发现路径，且 PRA可以用于非实意动词中，而 N-FOIL不能。文献 4中实验证明了在发现重要路径方面 RPA优于N-FOIL。节所述的finger printing 与 particle filtering策略有个缺点是，他们会减弱随机游走的多样性。比如图上只有两条路径的话，那么有50%勺可能性是所有的随机游走器全部在一条路径上，而另一条路径被置空。针对这样

39、的问题， 可以采用一种叫Low-Variance Sampling(LVS)的技术，该方法于2005年由Thrun 提出，广泛运用于机器人学。文献4总结了几条未来的研究方向，其一是从查询节点和目标节点同时开 始做推测可能会更加有效的发现长路径，而长路径一般来说是比较好的路径，且搜索效率应当更高。其二是从目标节点开始查询去发现特殊的路径，也就是反向的随机游走算法。其三是对推测树或推测图去生成推测路径可以更好的使用随机 游走推测模型。最后提出随机游走模型在大规模数据集上进行关系学习是一种很 有研究价值的方向。还有相关研究表明，正向与反向的随机游走混合模型对查询效率有更好的提 开。结合上述基本的PR

40、A与其改进，比较好的算法总结可以由图8表示。StageComputationPath Discoverygiven (si/ GJ,find f;3cc(f)>=3, hits二hGenerate Training Samples generate (却，tj and 卜，yjSgistic Regression Training产博”,海Predictionapply model to nodes s in domainrKnowledge Base Inference and Extension知识库(KB)/知识图谱经常是不完整的，这就让完善知识库成为必需。Pathranking

41、algorithm 是完成这项任务的最有希望的方法，目前关于使用RPAS行知识库的推断与补全是一项研究热点，近年来有许多在Freebase, DBPedia,NELL, YAGO? KB上的研究。上述文献4则是首先提出了在大规模 KB上使用RPA 进行关系学习的研究方向。文献5提出，KB中会存在一些潜在的关系，这些关系对关系抽取有很大的 帮助，而传统的基于文本的关系抽取模型并不能利用这些潜在的关系。使用 RPA 去学习结合了语义语法的规则，可以轻松在提取任务中融入现有的知识，并首次成功的尝试了对大规模异构数据运用关系学习方法。文献5从两方面对Pathranking algorithm 进行了扩

42、展：结合在KB中已有文本知识的语法与语义线索； 在web级规模的数据上分布式的实现了学习与推导算法。这使得在KB上学习语义语法规则成为了可能。如果RPA真型用从KB中生成的查询正例与反例去训练， 那就要考虑到像Freebase中有上百万条的概念与边，而且还要在Freebase上扩 展带语法关系的话，这样训练的话计算量将会非常大。况且用 Freebase生成的 查询本身会偏向于Freebase本身的那些概念，而很难反映出文本数据上出现的 潜在概念，若果要学习Freebase本身没有的概念的话，就必须解决这样的问题。 针对这样的问题，文献5从三方面对 RPA做了扩展：Scaling Up 、Sam

43、pling Training Data 、Text Graph Construction 。文献6证明了在大规模语料库上加入标记了潜在特征的边能有效的提升 RPAfi KB推测补全任务上的表现，可以看做是针对文献5研究的改进。由于文 献5中使用的语法标签集合是非词汇化依赖于角色标签 （没有对应的实词），使 得其不能完全表达学习到的推理规则。为了克服这个问题，文献 6在每条边上 加入了更加词汇化的语义标签（标签都是相互独立的实词）。这些边都是以主题- 动词-对象这种形式的三元组表示的。通过学习潜在加入的词汇化的边去得到需 要的标签，也可以避免传统 RPA特征过多与数据稀疏的问题。举例如图 9。可

44、以看到图9本身是一个非连通图，所以想通过传统RPA学习到AlexRodriguez与World Series的关系是不可能的。如果说加上虚线所示的两条潜 在的词汇化的边(Alex Rodriguez, play for, NY Yankees) 与(Alex Rodriguez, bats for, NY Yankees),这种关系就有可能被学习到。具体对于RPA说，就可以加入潜在的 <plays for,teamPlayIn> 去预测(Alex Rodriguez, atheteWonChampionship,World Series) 这个关系是否成立。经文献 6实验所 述，这

45、种加入潜在边的策略能有效提高在大规模KB上关系学习的效率。文献7就在大规模KB上使用RPA!推测的任务，给出了 2种如何更好的使 用文本语料库的方法。其一是提出了在一种结合KB上的关系与文本语料的技术， 使得它们比之前的研究结合的更加紧密，在一台计算机上就可以实现相对大规模 的关系计算。其二是阐述了如何将空间向量的相似性加入在KB上的随机游走推测，以减少RPA*身带来的数据稀疏问题，具体描述为当沿着边类型的序列进行 随机游走时，同时允许沿着那些在语义上也相似的边进行游走。举个列子，比如说一种边叫作“ flows through "，那我们同时也以一定的概率接受类似“ run thro

46、ugh ”这样的边，这种概率由欧式空间相似度为度量。这两种改进都是在RPA选择好特征路径后，进行概率计算时的改进。具体计算公式如式(12)所示。其中 v()是以向量形式返回一条类型边的函数，是调节空间相似性所占权重的比例系数。pg | i) exp(v(ej) v( J), j,1 j m(12)其中冗是各个边类型的集合序列，即兀=ei,e2, . , e ? ,i代表在这个集合中的第i条边类型，在传统RPA中，当随机游走到一个出度为 m的节点时， 会选择符合i的那些边类型，再随机的在这些符合条件的边中选择一条游走，公式(12)则表述了另一种选择哪一条边概率计算方法。当随机游走到一个出度为 m

47、的节点时，不去找符合i的那些边类型了，而是选择所有符合一定相似性的所有 边。比如三元关系组(Tom, visiting, Beijing)这样的关系，我们选择visiting 这个边的时候，如(Tom, touring, Beijing) 、(Tom, going, Beijing)这样的关系也认为成立，关系touring与going的边也放在选择列表中。公式(12)中的0 可以控制具体这样的扩展范围有多大，比如B =1时，认为 visiting=touring=going , 0=10 时，贝U visiting=touring going ,再扩大 0 =100 时，visiting to

48、uring going ,即随着 0 的增 大，文献7描述的方法向传统的RPAB近。文献8指出由于RPA是一种2阶段算法，即先找出连接各个节点的路径集 合，还要在特征矩阵中计算这些路径的概率，因而计算量较大，特别是运用于大规模KB补全任务上时耗时过长，因此提出了一种名为subgraph featureextraction(SFE)的更加简单高效的算法去生成知识图的特征矩阵。SFE与只作第一步的RPAf目似，对给定图上的节点集合，先本地搜索去标记这对节点周围的 节点作为子图，接下来去在这些子图上进行特征提取，去获得每一组节点对的特 征向量。这样就可以不必计算特征矩阵的每一种路径组合的随机游走概率

49、，可以抽取更加有表现力的特征，甚至包括那些不以路径形式表现出来的关系，还可以以广度优先搜索代替随机游走，以更加详细标记本地节点构成的图。文献9指出前对PRA的研究一般是遵循单任务学习范式，为它们及其训练 数据的每个独立关系构建一个预测模型。它忽略了某些关系中有意义的联系，而且因为更低频的联系而得不到足够的训练数据。因此文献9为RPA提出了一个新颖的多任务学习框架，称之为紧密耦合的 PRA (CPRA)。它首先设计一个凝聚 式聚类策略，自动发现高度相关的关系，然后利用多任务学习策略有效地结合对 这种关系的预测。CPRA将这些关系都考虑进来，使得内隐数据在它们之间分享。CPRA等KB补全任务看作是

50、一个二值分类的问题，就是说给定一个关系r,。是KB上的三元组关系，对于任意实体对(h, t)有(h,r,t),就去判断h和t是否 被r连接。R R代表着要被预测到关系，则对于每一个关系 r R都有一个对 应的训练实例集合。对于每一对实体对，路径特征用传统的RPAtt取计算，对于 抽取到的关系r的路径特征集合以表示，训练集合被定义为,(Xir,yir), Xir是实体对的特征向量，对应所有属于的路径。yir是取值为1的标签。CPRA 用多任务学习策略进行KB补全任务，具包含两个方面：关系聚类与关系耦合。 关系聚类用以自动发现高相关度的关系，关系耦合去学习这些关系。在关系聚类方面，需要发现那个高相

51、关度的关系才能聚类，具体的，以网为起点聚类，每个聚类只含有一个关系r R,| |是基数的集合。然后遍历的合并最相似的聚类， 相关度以公式(13)计算。Sim(Ci, Cj)CiCj|min( C ,| Cj )(13)公式(13)表示了发现这些高相关度关系方法的核心思想： 如果两个关系，他们之 间的共享路径或共享特征越多，他们就越相似，即相关度高。其中Ci是与聚类C关联的特征集合。即在两个需要聚类的 C与C间，找出他们共同的特征来作 为分子，并以其中一个小的聚类中的特征为分子， 计算出它们的相关度来。举例: 一个聚类苹果，其特征集合为水果，甜的，圆形,另一个聚类菠萝，其特征集 合为水果，甜的，

52、柱状，有刺。则他们之间的相关度以公式13计算为：Sim（苹果，菠萝）|水果，甜的|2min（|水果，甜的,圆形|） 3可以看到苹果和菠萝的相似性比较的高了， 在用户搜索苹果的时候，就可以考虑 将菠萝作为查询实体进行排名评分。在聚类之后，CRPA下一步将对于每一个聚类中不同关系的路径排序进行耦合以同时学习分类任务。在一个包含K个关系的聚类C二，.，rk中，有 c % b.0。对于关系K的的训练 实例，使用共享的特征集合，使得所有的训练数据在同一个空间内， 与改进后的 第k个关系相关的训练数据以Tk = （x ik,yik）Nk表示，然后一起学习K个分类器 fi, f2, . , fk以达到最终的补全任务。验结果表明， CPRA能有效地确认出有 逻辑关联的集群，它们彼此是高度相关的。就预测的准确率和模型的可解释性而 言，通过进一步结合这种关系，CPRA