pathrankingalgorithm调研报告.docx

pathrankingalgorithm调研报告

34
2020年4月19日
文档仅供参考
path ranking algorithm调研报告
1. 引言
近两年来，随着Linking Open Data等项目的全面展开，语义Web数据源的数量激增，大量RDF数据被发布。互联网正从仅包含网页和网页之间超链接的文档万维网(Document Web)转变成包含大量描述各种实体和实体之间丰富关系的数据万维网(Data Web)。在这个背景下，Google、百度和搜狗等搜索引擎公司纷纷以此为基础构建知识图谱，如Knowledge Graph、知心和知立方等，用以改进搜索质量，从而拉开了语义搜索的序幕。
正如Google的辛格博士在介绍知识图谱时提到的：“The world is not made of strings , but is made of things.”，知识图谱旨在描述真实世界中存在的各种实体或概念。其中，每个实体或概念用一个全局唯一确定的ID来标识，称为它们的标识符(identifier)。每个属性-值对(attribute-value pair，又称AVP)用来刻画实体的内在特性，而关系(relation)用来连接两个实体，刻画它们之间的关联。知识图谱亦可被看作是由一张巨大的图组成，图中的节点表示实体或概念，而图中的边则由属性或关系构成，我们需要构建并使用这张图。
大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，其中主要包括：实体链指（Entity Linking）、关系抽取（Relation Extraction）、知识表示（Knowledge Representation）、知识推理（Knowledge Reasoning）等。
在知识推理方面，利用推理规则实现关系抽取的经典方法之一就是Path Ranking Algorithm算法，由Lao & Cohen与 提出。该方法将每种不同的关系路径作为一维特征，经过在知识图谱/Knowledge Base中统计大量的关系路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取效果，成为近年来的关系抽取的代表方法之一。但当前这种基于关系的统计的方法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题，且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。

2. Path Ranking Algorithm
2.1 Random Walk and Restart
Random walk with restart (RWR)是最初提出的图像分割算法，也叫Personalized Page Rank。它迭代地探讨了网络的全局结构，估计两个节点之间的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R称为“重启的概率（1−R移动到一个邻居的概率）。迭代后达到稳定，稳定的概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量能够被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足式(1):
R=(1-d)u+dWr (1)
其中，d是继续游走概率，(1-d)为重启概率，u是启动节点，Wr是网络过渡矩阵。随机游走(RWR)实际是一个简单的迭代过程：
Rt=(1-d)u+dWrt-1 （2）
式(2)表示了这样一个迭代的过程：算法从图中顶点u出发，沿图中的边随机游走。在任意点上，算法以一定的概率d随机地选择与该顶点相邻的边，沿这条边移动到下一个顶点，或以(1-d)概率直接回到出发点u，这是这个重启概率可有效的防止由于随机游走的不确定性而进入一条权值很小的路径。在第t-1步时移动带下一个顶点时，就开始了以这个点新出发点的第t步随机游走，其中Wrt-1表示的是在t-1步游走时从一个节点游走到另一个节点概率。经过若干次随机游走过程，能够到达图中每一个顶点的概率值达到平稳分布，即再次迭代也不改变图中的概率分布值时，就能够得到的R值来对所求任务进行排序。比如讲RWR运用在下图做图像分割时：

图1
假设图像最核心的部分是红色，次核心为黄色，需排除的部分为蓝色。开始游走时路径沿着最左面的蓝色路径走，每一次游走都进入了不需要的部分，直到某次重新启动成功，返回最最上角的开始节点重新游走，第二次沿着绿色的路径游走，识别到了部分次核心区域，在某一步是再次重启，沿着黑色的路径识别到了核心区域。由(2)公式就能够迭代的计算出每条路径覆盖范围的概率大小，在N次游走达到稳定后，上图的每一部分子图都会有一个确定不变的概率，结合核心、次核心与需排除部分的权重，就能够计算出每个子图的评分，从而找出评分最高的核心区域。当前已有许多关于RWR的研究，包括使用RWR进行分类，关系学习与一般化的图上的相似性度量等。

2.2 Relational Learning
要实现关系抽取，其中对关系的推导学习是很重要的一部分。在大数据的背景下，预测一个关系是否成立具有极大的研究潜力。我们能够用下图描述一个关系学习问题：

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

图3
我们仍以Charlotte为出发点，Writer为终点来判断Charlotte是否是一个作家，但这次我们多了一条这样的判断路径：Charlotte---》Patrick Bronte---》Writer。若这三个点间的两条边存在，我们同样能够得到Charlotte是一个作家的结论。值得注意的是在判定Charlotte是否是一个作家时，Charlotte的行为无疑对判定也是有帮助的，那么我们的判定图能够表述为：

图4
如果在考虑到出版社等问题，我们还要加上这样的关系：

图5
至此我们需要考虑的关系图变了这样：

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

2.3 Path Ranking Algorithm
有一些相关研究，如Minkov, Cohen等在基于RWR的模型上使用了更加丰富的特征集合，用边上的标签对排序结果再次排序。而且她们还提出了一种加权的RWR-paths方法，提高了查询到相关实体的准确率。而Path ranking algorithm算法与之类似，能够看做是其一种改进版本，相当于沿着一组带有特定类型信息的边的序列集合上的随机游走，即限制了游走路径的RWR算法。相比于RWR无法区分边的类型，它更容易加入额外所需的类型信息，如它的query-independent experts与 popular entity experts。类似的技术还有Embedding-based techniques与Probabilistic graphical models，Path ranking algorithm 相比较前两者，具有容易推测与不需要关于网络结构先验知识的优点。
其算法核心思想是利用连接着两个实体的路径去预测她们之间是否有潜在的关系。举个例子，如图7所示，我们要判定Charlotte是不是作家，能够判定这样一组特定的关系序列是否成立： Prob（Charlotte-》Writer | InSentence, InSentence-1, IsA）

图7
Path ranking algorithm能够经过不同的边类型序列来判定一个关系是否存在，在比较复杂的图6上，我们能够看到至少有一下三种不同的边类型序列能够做出判定：

或者能够举个其它的例子，如果我需要查找一些参考文献，其中一个关键字是年份y，那么可能有这样的两种方式：一、找出所有y年出版的论文。二、出版于y年经常被引用的论文。显然第二种方法更加合理，为了更加准确的描述所需信息，定义R是一个二值关系，如果e与e’ 有关系R成立，则记作R（e，e’ ），并定义。dom(R)用来表示知识领域R，range(R)表示领域R的范围。P是一条关系路径，由一组关系R1，R2, ..., RL组成，其中对于任意的i，都满足1< i < L-1, range(Ri)=dom(Ri+1)。而且有定义, 且有。如果希望强调路径上每一步的类型信息，能够将
P = R1, R2 .... RL表示为:

其中T0=dom(R1)=dom(P), T1 = range(R1) = dom(R2)。据此定义，上述以关键字年份搜索参考文件任务的两种方法能够表示成下面这样：

其中-1表示相反的主客体关系。能够看到每条关系路径都是paper，正是查找参考文献想要的信息类型。对于任意的P=R1,R2,...RL和查询实体集合。如果P是空路径，我们定义其满足如下分布：
（3）
公式(3)主要用于在RPA开始时，计算第一步连接出发节点与第二个节点的概率计算。假设我需要购买一台PC，想知道具体买什么好。这样的任务在图8所示具体问题上可表述为：首先只有查询起点PC，没有任何一条连接到其它节点的路径，此时考虑关系R1=HaveBrand-1，假设有相关的Eq={中国，美国，老挝}，对于任意此时会以相同的概率随即游走到a1,b1,c1上来，对于牛奶Eq，则对应的h为0，即不会随机游走到d1上来。

图8
若P=R1...RL非空，则令P’=R1...RL-1,则：
（4）
其中I(R(e’,e))/|R1(e’)|表示沿着边Ɩ从节点e一步随机游走到e’的概率，I(R(e’,e))表示在e与e’到底有没有关系R存在。在e'与e满足关系R时取值1，否则取值0。以路径长度Ɩ=2举例，即P’为关系边R1，R2构成的路径。

图9
若R1为HaveBrand-1关系，R2为inWhichCountry-1关系。具体PC推荐任务图9上可表示为：首先P为空，以式2所述概率随机游走，假设选择a1，此时会进行第二步游走，引入新的查询实体，rang(R2)={联想}, 如果此时有联想，香蕉两个新实体e’与P相连接，首先指示器函数判定e’于e是否存在关系R2，即这样两个三元组(中国，inWhichCountry-1，联想)与(中国，inWhichCountry-1，香蕉)是否成立。显然(中国，inWhichCountry-1，香蕉)不成立，则I(R(e’,e))=0，使得路径P1=这条路径的中的第二步游走分布的h值为0，即关系inWhichCountry-1的h值为0，从而整条路径的h值变小。而其中当三元组关系(中国,inWhichCountry-1，联想)存在时，I(R(e’,e))=1时，再递归的以中国为出发节点，利用公式(3)计算一个h值，这个h乘上一个不为0的从e到e'一步随机游走的概率，最终整体路径P2=的h值肯定会明显大于P1。
至此就能够对查询所需的结果进行排名：
（5）
如图10，假设有一条路径P=，路径长度为n，最终结果为型号为Y450-tis的PC。由公式(4)计算出每一步游走的h值，也就是每一个连接2个节点的关系R的h值，最终将这些h值求和，利用公式(5)就能够得到路径P的最终排名得分，可是需要注意到的是，在这条路径中，每一步的的权重可能并不相同，这也是会影响最终得分的重要因素之一。比如在在图10的a1,b1,c1均成立的条件下，考虑到中国美国的PC水平会明显高于老挝，人们都不会倾向于购买老挝的PC产品，那么此时虽然、、均成立，却需要去调整根据公式(3)的计算出的均为1/3的概率得分，经过，应使得、的得分明显高于老挝的得分。

图10
假设如图11所示，有abc三条不同路径指向统同一款PC型号Y450-tsi，那么每条路径都会有一个对应的概率，分别能够表示为：

图11
根据公式(5)我们能够分别求得上述Pa、Pb、Pc的值，但最终我们需要的是Y450这款PC的推荐评分到底是多少，而不是具体每一条路径的评分。因此应当将所有指向这同一结果的各个概率评分求和，能够用公式(6)表示：
（6）
具体对于图11而言， P是在Ɩ<4的情况下，结果都指向Y450这个查询结果的任意一条路径。对于Y450这个查询，它的评分=score(pa)+score(pb)+score(pc)
Pa、Pb、Pc均由公式(5)计算可得。
公式(6)以更好理解的形式能够表示为：
（7）
其中Q是长度为n的查询起点s到查询终点n之间的可能路径，θp是经过训练获得的路径权重。p为具体的一条起点s到终点n的路径，若有P=π+RL+1，其中π=R1，R2... RL, 则满足：
(8)
剩下的问题就是对参数θ的估计，有许多方法能够使用，最常见的如逻辑回归分类模型、BLMVM、L-BFGS等。我们能够用关系R和（起点si，终点ti）的集合来构造所需的训练集，最终经过分类器得到所需的权重。

2.4 Path Ranking Algorithm的扩展
2.4.1 Query Independent Paths
对于描述一个实体的特征取决于这些特征在图中相对查询实体的位置，而对于一个实体的关联关系可能还取决于一些独立于查询的特性。对于推荐参考文献这一项任务来说，其最近的出版商，引用数量，和作者曾经在哪里发表过文章都会有影响。考虑到查询实体这些复杂的特点，我们能够将我们的查询Eq做扩展，让每个查询Eq都包含一个特殊的实体e*。这样做之后，对于每一种类型信息T，都有关系AnyT使得AnyT（e*,e）对于所有属于T的E都成立。如关系AnyPaper将映射e*为每个paper，关系AnyYearr将映射e*为每个year。
举个例子，如果有这样的路径：，这代表着我们以相等的概率随机选择任何一个paper作为开始节点，然后游走到它的一篇参考文献上。这样最后得到的结果有很大的概率会是一个有高引用量的paper。一条以AnyPaper作为开始节点的路径，随后沿着两条引用关系的边去分配权重给那些经常被高引用量文章引用的paper，随着路径的不断增长，这种结合了多种独立于查询路径的算法，开始类似于在引用量构成的图上使用PageRank算法。
这种情况，称其为Query Independent Paths（RPA-qip），依然是以式（2）来计算评分，但其好处是因为这些路径都是独立于查询的，我们能够经过提前计算它们的值来改进整体Path Ranking Algorithm的效率。

2.4.2 Popular Entity Biases
对于一些特定的查询检索任务，用户可能感兴趣的是一些计算出的排名相对低但被点击次数很多的查询结果，这是主要是因为有一些特征不能很好的被排名系统识别。在这种情况下，如果能将这些点击次数大的查询结果或文档给以较高的排名，就能够给用户更好的体验。对于个性化的搜索，不同的用户在同一个查询下可能需要的是不同的结果，比如单词“mouse”，对于一个生物学家来说她需要的是老鼠的相关信息，而对于一个程序员来说，更加可能的是代表鼠标的意思。因此，我们对查询者与查询目标建立一个联系，对上述这种情况可能会有一定的帮助。
Popular Entity Biases是一种简单而又适用性广的方法。它经过对查询目标添加一个查询偏好来建立对查询实体的流行度。对于一个查询任务，有查询类型T0，查询目标类型Tq，Popular Entity Biases会对每一个查询目标增加一个流行实体偏好，并对每一对查询实体（e'，e）引入条件流行实体偏好，其中。在这种情况下，对于RPA与RPA-qip的排名计算公式6就不在适用了，能够将公式2扩展为：
（8）
或者以矩阵形式表示为：
（9）
其中用于连接所有偏好参数，一个条件偏好参数构成的矩阵，q是一个二值指示器（0 or 1），用于表示每个实体是否包含在查询中。能够看出在式8中参数的取值可能会非常大的，的长度相当于所有查询目标实体的总数，也是一个很大的矩阵，行数为目标实体的数，列数等于查询中所有的实体类型数。
举个列子，比如Apple这个查询词，其可能对应查询实体有苹果(水果)，或Apple Compute(苹果公司)，如果在最近苹果刚刚发布了iPhone7的背景下，有用户查询了Apple这个关键词，更应当出现的查询结果是Apple Compute，而不是水果。此时就能够经过设置公式8中的不同的流行偏好来调节查询结果。同理，对于查询关键词e苹果，设e’为实体手机，实体对(苹果，手机)在公式8中的会相对于实体对(苹果，水果)在上述背景下应当更大。结合两个针对流行度的计算参数， Popular Entity Biases能够使RPA更加准确的对查询结果评分排名。
Path Ranking Algorithm较之前的各算法，具有表示能力强，鲁棒性高，适用与大规模数据的优点。

3. Path Ranking Algorithm的发展与应用
3.1 Efficient Inference
Path Ranking Algorithm能够看做是基于路径限制的一种随机游走算法，它在关系学习方面有良好的表现，可是这种算法的代价高昂，在推测路径中会产生大量概率非零的中间节点，但实际上我们并不需要很多的随机游走就能够将查询目标从噪声节点中区分出来。文献[2]采用稀疏化策略fingerprinting, particle filtering, fixed truncation与beam truncation针对对此问题对Path Ranking Algorithm算法进行了改进，达到了更加高效的关系推测学习。
有文献[3]提出了一种近似于personalized PageRank的蒙特卡罗算法，这种算法描述了从查询节点出发，产生k条独立的随机游走，节点的概率由它被随机游走到的被归一化后的次数来确定，并指出这样就能够由K的大小来轻易的控制计算量的大小，且只需要相对比较少的随机游走器就能够区分出高、中、低排名的查询结果节点。这样虽然会对低排名节点的计算精度有影响，可是查询结果是否符合人们的要求，主要是由那些高质量的查询结果决定的，低排名的结果的精度对于整体查询并不会有很大的影响。根据这样的结论，文献[2]在Path Ranking Algorithm算法的基础上提出了The Fingerprinting Strategy的稀疏化抽样策略，将Path Ranking Algorithm算法中每一步的h计算方法替换为：
（10）
这种抽样策略，仅仅是用公式(10)替换公式(3)，依然服从公式(4)所描述的分布。h值的确定不再像公式(3)中对所有包含在查询集合中的实体数量等概率确定，而是随机游走器与被游走到的次数来确定概率大小。比如能够设置10个随即游走器，如果一个节点总共被这10个随即游走器游走到了10次，那么这个节点的h值就是1，而不是由具体的查询相关的实体数量决定。这样做的好处是能够经过控制随机游走器的数量，来灵活的控制计算量的大小。
而上述The Fingerprinting Strategy在随机游走器的数量远大于链路数量时，可能会引起很大的计算浪费。比如有3万个随机游走器，却只存在3条路径时，The Fingerprinting Strategy依然需要产生3万个随机数并对每一个随机游走器分配一条特殊的路径，以概率学的角度来说，这样一路路径上就有1万个随机游走器在工作。对于这样的问题，Particle Filtering Strategy被提出，可表示如下：
Input: distribution hi(e), relation R, threshold εmin
Output: hi+1(e)
Set hi+1(e) = 0 (should not take any time)
for each e with hi(e) != 0 do
sizenew = hi(e)/|R(e)|
if sizenew > εmin then
for each e′ ∈ R(e) do
hi+1(e′)+ = sizenew
end for
else
for k=1..floor(hi(e)/εmin) do
randomly pick e′ ∈ R(e)
hi+1(e′)+ = εmin
end for
end if
end for
其核心思想是刚开始将所有游走器看做一个整体大粒子，在接下来的游走过程中将粒子不断分割成几个等大小的小粒子再重复随机游走，直到粒子大小被分割小于实现设置好的阈值时，再将算法转化为之前公式2描述的精确计算。
在文献[2]中指出，随机游走会产生一种不平衡的分布，小部分节点有高评分，而大部分节点是低评分(即符合幂率分布)。因此，能够做出这样的假设：将那些低评分的节点忽视掉，不但不会影响随机游走鉴别重要实体的能力，反而还能极大的减少所需的时间和计算内存耗费。此假设已有相关文献证明。Truncation Strategies据此能够表示为：
(11)
其中为在hi+1中排名第W的概率，W是自定义参数，用来控制截断的程度。这种截断抽样策略，同样是用公式(11)替换公式(3)，依然服从公式(4)所描述的分布。如果一个低概率节点的h值非常小，我们就用0来代替那个非常小的h值，而不再用本身的h值。这个临界值能够有在hi+1分布中的第W高的概率决定。换句话说，就是在hi+1分布中，有很多个按概率大小排好的节点，我们计算概率从前w个开始的节点的h值，在第W个后的节点，全部令它们的h值为0，即在w位置进行截断。这种截断策略还是鉴于将低评分的节点忽视掉，不但不会影响随机游走鉴别重要实体的能力，反而还能极大的减少所需的时间和计算内存耗费来设计的。
上述几种稀疏策略已经经过文献[2]的实验证明，能有效的提高查询执行效率与查询质量。具体改进的实验结果如下：

图7
3.2 Path Finding
在以往的Path Ranking Algorithm中，会规定一个最大的路径长度l。当边的类型不多时，在公式(6)的还能够被一一列举出来，但如果说有很多种关系，如在知识库的背景下，对一个节点的关系就可能有100多种，那么即使路径长度只有3，那么最终的路径数量也会达到上百万种之多。若想在这样的背景下利用Path Rank Algorithm，文献[4]中对Path Rank Algorithm中路径的产生过程做了相应的修改，只发现那些对查询可能有用的路径，忽略排名较低的路径。首先对于任意查询实体e有，定义一个查询s去发现一路路径P，且路径发现的过程中，创立任何一个节点都需要由一部分训练集中的查询Si支持，这个比例人工指定。其次，只有当在检索时至少有一个目标实体在训练集中时，才需要在RPA中发现路径。在上述两种约束下，经实验证明能够有效的减少需要考虑的路径数量。类似发现路径以连接节点的思想并在 的N-FOIL中也被使用过，可是当时使用的是一个查询去发现路径，而不是RPA中以数据驱动的多查询去发现路径，且PRA能够用于非实意动词中，而N-FOIL不能。文献[4]中实验证明了在发现重要路径方面RPA优于N-FOIL。
3.1节所述的finger printing 与 particle filtering策略有一个缺点是，她们会减弱随机游走的多样性。比如图上只有两条路径的话，那么有50%的可能性是所有的随机游走器全部在一条路径上，而另一条路径被置空。针对这样的问题，能够采用一种叫Low-Variance Sampling(LVS)的技术，该方法于 由Thrun提出，广泛运用于机器人学。
文献[4]总结了几条未来的研究方向，其一是从查询节点和目标节点同时开始做推测可能会更加有效的发现长路径，而长路径一般来说是比较好的路径，且搜索效率应当更高。其二是从目标节点开始查询去发现特殊的路径，也就是反向的随机游走算法。其三是对推测树或推测图去生成推测路径能够更好的使用随机游走推测模型。最后提出随机游走模型在大规模数据集上进行关系学习是一种很有研究价值的方向。
还有相关研究表明，正向与反向的随机游走混合模型对查询效率有更好的提升。结合上述基本的PRA与其改进，比较好的算法总结能够由图8表示。

图8
3.3 Knowledge Base Inference and Extension
知识库(KB)/知识图谱经常是不完整的，这就让完善知识库成为必须。Path ranking algorithm 是完成这项任务的最有希望的方法，当前关于使用RPA进行知识库的推断与补全是一项研究热点，近年来有许多在Freebase, DBPedia, NELL, YAGO等KB上的研究。上述文献[4]则是首先提出了在大规模KB上使用RPA进行关系学习的研究方向。
文献[5]提出，KB中会存在一些潜在的关系，这些关系对关系抽取有很大的帮助，而传统的基于文本的关系抽取模型并不能利用这些潜在的关系。使用RPA去学习结合了语义语法的规则，能够轻松在提取任务中融入现有的知识，并首次成功的尝试了对大规模异构数据运用关系学习方法。文献[5]从两方面对Path ranking algorithm进行了扩展：结合在KB中已有文本知识的语法与语义线索；在web级规模的数据上分布式的实现了学习与推导算法。这使得在KB上学习语义语法规则成为了可能。如果RPA模型用从KB中生成的查询正例与反例去训练，那就要考虑到像Freebase中有上百万条的概念与边，而且还要在Freebase上扩展带语法关系的话，这样训练的话计算量将会非常大。况且用Freebase生成的查询本身会偏向于Freebase本身的那些概念，而很难反映出文本数据上出现的潜在概念，若果要学习Freebase本身没有的概念的话，就必须解决这样的问题。针对这样的问题，文献[5]从三方面对RPA做了扩展：Scaling Up 、Sampling Training Data 、Text Graph Construction。
文献[6]证明了在大规模语料库上加入标记了潜在特征的边能有效的提升RPA在KB推测补全任务上的表现，能够看做是针对文献[5]研究的改进。由于文献[5]中使用的语法标签集合是非词汇化依赖于角色标签(没有对应的实词)，使得其不能完全表示学习到的推理规则。为了克服这个问题，文献[6]在每条边上加入了更加词汇化的语义标签(标签都是相互独立的实词)。这些边都是以主题-动词-对象这种形式的三元组表示的。经过学习潜在加入的词汇化的边去得到需要的标签，也能够避免传统RPA特征过多与数据稀疏的问题。举例如图9。

图9
能够看到图9本身是一个非连通图，因此想经过传统RPA学习到Alex Rodriguez与World Series的关系是不可能的。如果说加上虚线所示的两条潜在的词汇化的边(Alex Rodriguez, play for, NY Yankees)与(Alex Rodriguez, bats for, NY Yankees)，这种关系就有可能被学习到。具体对于RPA来说，就能够加入潜在的<plays for,teamPlayIn>去预测(Alex Rodriguez, atheteWonChampionship,World Series)这个关系是否成立。经文献[6]实验所述，这种加入潜在边的策略能有效提高在大规模KB上关系学习的效率。
文献[7]就在大规模KB上使用RPA做推测的任务，给出了2种如何更好的使用文本语料库的方法。其一是提出了在一种结合KB上的关系与文本语料的技术，使得它们比之前的研究结合的更加紧密，在一台计算机上就能够实现相对大规模的关系计算。其二是阐述了如何将空间向量的相似性加入在KB上的随机游走推测，以减少RPA本身带来的数据稀疏问题，具体描述为当沿着边类型的序列进行随机游走时，同时允许沿着那些在语义上也相似的边进行游走。举个列子，比如说一种边叫作“flows through”,那我们同时也以一定的概率接受类似“run through”这样的边，这种概率由欧式空间相似度为度量。这两种改进都是在RPA选择好特征路径后，进行概率计算时的改进。具体计算公式如式(12)所示。其中是以向量形式返回一条类型边的函数，是调节空间相似性所占权重的比例系数。
（12）
其中π是各个边类型的集合序列，即π={e1,e2, ... , eƖ}，代表在这个集合中的第i条边类型，在传统RPA中，当随机游走到一个出度为m的节点时，会选择符合的那些边类型，再随机的在这些符合条件的边中选择一条游走，公式(12)则表述了另一种选择哪一条边概率计算方法。当随机游走到一个出度为m的节点时，不去找符合的那些边类型了，而是选择所有符合一定相似性的所有边。比如三元关系组(Tom, visiting, Beijing)这样的关系，我们选择visiting这个边的时候，如(Tom, touring, Beijing)、(Tom, going, Beijing)这样的关系也认为成立，关系touring与going的边也放在选择列表中。公式(12)中的β能够控制具体这样的扩展范围有多大，比如β=1时，认为visiting=touring=going，β=10时，则visiting
=touringgoing，再扩大β=100时，，即随着β的增大，文献[7]描述的方法向传统的RPA靠近。
文献[8]指出由于RPA是一种2阶段算法，即先找出连接各个节点的路径集合，还要在特征矩阵中计算这些路径的概率，因而计算量较大，特别是运用于大规模KB补全任务上时耗时过长，因此提出了一种名为subgraph feature extraction(SFE)的更加简单高效的算法去生成知识图的特征矩阵。SFE与只作第一步的RPA相似，对给定图上的节点集合，先本地搜索去标记这对节点周围的节点作为子图，接下来去在这些子图上进行特征提取，去获得每一组节点正确特征向量。这样就能够不必计算特征矩阵的每一种路径组合的随机游走概率，能够抽取更加有表现力的特征，甚至包括那些不以路径形式表现出来的关系，还能够以广度优先搜索代替随机游走，以更加详细标记本地节点构成的图。
文献[9]指出前对 PRA 的研究一般是遵循单任务学习范式，为它们及其训练数据的每个独立关系构建一个预测模型。它忽略了某些关系中有意义的联系，而且因为更低频的联系而得不到足够的训练数据。因此文献[9]为RPA提出了一个新颖的多任务学习框架，称之为紧密耦合的 PRA (CPRA)。它首先设计一个凝聚式聚类策略，自动发现高度相关的关系，然后利用多任务学习策略有效地结合对这种关系的预测。CPRA 将这些关系都考虑进来，使得内隐数据在它们之间分享。
CPRA将KB补全任务看作是一个二值分类的问题，就是说给定一个关系r，O是KB上的三元组关系，对于任意实体对(h, t)有，就去判断h和t是否被r连接。代表着要被预测到关系，则对于每一个关系都有一个对应的训练实例集合。对于每一对实体对，路径特征用传统的RPA抽取计算，对于抽取到的关系r的路径特征集合以表示，训练集合被定义为，xir是实体正确特征向量，对应所有属于的路径。yir是取值为1的标签。CPRA 用多任务学习策略进行KB补全任务，其包含两个方面：关系聚类与关系耦合。关系聚类用以自动发现高相关度的关系，关系耦合去学习这些关系。在关系聚类方面，需要发现那个高相关度的关系才能聚类，具体的，以为起点聚类，每个聚类只含有一个关系，是基数的集合。然后遍历的合并最相似的聚类，相关度以公式(13)计算。
（13）
公式(13)表示了发现这些高相关度关系方法的核心思想：如果两个关系，她们之间的共享路径或共享特征越多，她们就越相似，即相关度高。其中是与聚类Ci关联的特征集合。即在两个需要聚类的Ci与Cj间，找出她们共同的特征来作为分子，并以其中一个小的聚类中的特征为分子，计算出它们的相关度来。举例：一个聚类苹果，其特征集合为{水果，甜的，圆形}，另一个聚类菠萝，其特征集合为{水果，甜的，柱状，有刺}。则她们之间的相关度以公式13计算为：

能够看到苹果和菠萝的相似性比较的高了，在用户搜索苹果的时候，就能够考虑将菠萝作为查询实体进行排名评分。在聚类之后，CRPA下一步将对于每一个聚类中不同关系的路径排序进行耦合以同时学习分类任务。在一个包含K个关系的聚类C={r1，r2，...，rk}中，有。对于关系K的的训练实例，使用共享的特征集合，使得所有的训练数据在同一个空间内，与改进后的第k个关系相关的训练数据以表示，然后一起学习K个分类器f1，f2，...，fk以达到最终的补全任务。验结果表明，CPRA 能有效地确认出有逻辑关联的集群，它们彼此是高度相关的。就预测的准确率和模型的可解释性而言，经过进一步结合这种关系，CPRA比PRA就KB补全任务来说表现的更好。

4 结语
当前RPA的研究焦点在大规模KB/知识图谱补全上。虽然RPA有计算量大，数据稀疏等问题存在，但总体来说RPA对KB补全任务表现良好。如何进一步提高算法效率与精确度仍有研究前景，如双向游走的混合模型研究，使用潜在语义关系，分布式计算与多任务计算等任然有进一步优化的空间。而在20 世纪 90 年代之后迅速发展的社会网络分析/社会计算是以社会行动者以及她们之间的关系的集合为分析对象的一种分析方法。是由点和关系两个部分组成，点与点之间存在联系则有线联系，反之，则无的一种分析方法，其核心思想与RPA类似，将此方法运用于知识图谱，也能够类似表示知识与知识、知识与学者、知识与学科这样的关联关系，应当也是一种在知识图谱方面有发展前景的方向。

参考文献：
[1] Lao, N., & Cohen, W. W. Relational retrieval using a combination of path-constrained random walks. Machine learning, 81(1), 53-67, .
[2] Ni Lao, William W. Cohen, Fast Query Execution for Retrieval Models based on Path Co