《pathrankingalgorithm调研报告》由会员分享，可在线阅读，更多相关《pathrankingalgorithm调研报告（24页珍藏版）》请在金锄头文库上搜索。
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称为“重启的概率（1- R移动到一个邻
5、居的概率）。迭代后达到稳定，稳定的 概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可 以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足 式：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要实现关系抽取，其中对关系的推导学习是很重要的一部分。 在大数据的背 景下，预测一个关系是否成立具有极大的研究潜力。我们可以用下图描述一个关 系学习问题：#如果想要判定Ch
8、ar10tte是否是一个作家。最简单的情况如图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 今 WritTer)ProbfChariotte T Pa
10、inter)图5可以看到这已经是一个很复杂的图了，而实际上我们在做判断的时候，可能考虑的远比这还要复杂，其计算复杂度主要体现在它有指数级增长的路径类型和 指数级增长的路径实例。图中每两个点之间存在的边，对应着我们需要学习到的 关系，可以发现不同的点之间关系的种类并不相同，如 Charlotte与Jane Eyre 之间，是 wrote的关系，而Jane Eyre与Novel之间，是IsA的关系。而 RWR 并不能有效的区分这样的区别，前面的类型信息会被后面的类型信息覆盖，而下面提到的Path Ranking Algorithm可以很好的解决这样的问题。Path Ranking Algorith
11、m有一些相关研究，如Minkov, Cohen等在基于RWR勺模型上使用了更加丰富 的特征集合，用边上的标签对排序结果再次排序。并且他们还提出了一种加权的RWR-paths方法，提高了查询到相关实体的准确率。而 Path ranking algorithm 算法与之类似，可以看做是其一种改进版本，相当于沿着一组带有特定类型信息 的边的序列集合上的随机游走，即限制了游走路径的RWRT法。相比于RWR法 区分边的类型，它更容易加入额外所需的类型信息，如它的 query-independent experts 与 popular entity experts 。 类彳以的技术还有 Embedding
12、-based techniques 与 Probabilistic graphical models , Path ranking algorithm 相 比较前两者，具有容易推测与不需要关于网络结构先验知识的优点。其算法核心思想是利用连接着两个实体的路径去预测他们之间是否有潜在 的关系。举个例子，如图7所示，我彳门要判定Charlotte是不是作家，可以判定 这样一组特定的关系序列是否成立：Prob (Charlotte- Writer | InSentence,InSentence-1, IsA )图7Path ranking algorithm可以通过不同的边类型序列来判定一个关系是否存
13、在，在比较复杂的图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年经常被引用的论文。显然第二种方法更加合理，为了更加准确的描述所 需信息，定义R
14、是一个二值关系，如果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 表示为：RiRlTo .其中 T(=dom(R)=dom(P), T1 = range(R1) = dom(R2) 。据
15、此定义，上述以 关键字年份搜索参考文件任务的两种方法可以表示成下面这样: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)hEq, 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
