path ranking algorithm调研报告

《path ranking algorithm调研报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、pathrankingalgorithm调研报告1.引言近两年来，随着LinkingOpenData等项目的全面展开，语义Web数据源的数量激增，大量RDF数据被发布。互联网正从仅包含网页和网页之间超链接的文档万维网(DocumentWeb)转变成包含大量描述各种实体和实体之间丰富关系的数据万维网(DataWeb)。在这个背景下，Google、百度和搜狗等搜索引擎公司纷纷以此为基础构建知识图谱，如KnowledgeGraph、知心和知立方等，用以改进搜索质量，从而拉开了语义搜索的序幕。正如Google的辛格博

2、士在介绍知识图谱时提到的：“Theworldisnotmadeofstrings,butismadeofthings.”，知识图谱旨在描述真实世界中存在的各种实体或概念。其中，每个实体或概念用一个全局唯一确定的ID来标识，称为它们的标识符(identifier)。每个属性-值对(attribute-valuepair，又称AVP)用来刻画实体的内在特性，而关系(relation)用来连接两个实体，刻画它们之间的关联。知识图谱亦可被看作是由一张巨大的图组成，图中的节点表示实体或概念，而图中的边则由属性或关系构成

3、，我们需要构建并使用这张图。大规模知识图谱的构建与应用需要多种智能信息处理技术的支持，其中主要包括：实体链指（EntityLinking）、关系抽取（RelationExtraction）、知识表示（KnowledgeRepresentation）、知识推理（KnowledgeReasoning）等。在知识推理方面，利用推理规则实现关系抽取的经典方法之一就是PathRankingAlgorithm算法，由Lao&Cohen与2010年提出。该方法将每种不同的关系路径作为一维特征，通过在知识图谱/Knowled

4、geBase中统计大量的关系路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取效果，成为近年来的关系抽取的代表方法之一。但目前这种基于关系的统计的方法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题，且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。2.PathRankingAlgorithm2.1RandomWalkandRestartRandomwalkwithrestart(RWR)是最初提出的图像分割算法，也叫PersonalizedPageRan

5、k。它迭代地探讨了网络的全局结构，估计两个节点之间的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R称为“重启的概率（1−R移动到一个邻居的概率）。迭代后达到稳定，稳定的概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足式(1):R=(1-d)u+dWr(1)其中，d是继续游走概率，(1-d)为重启概率，u是启动节点，Wr是网络过渡矩

6、阵。随机游走(RWR)实际是一个简单的迭代过程：Rt=(1-d)u+dWrt-1（2）式(2)表示了这样一个迭代的过程：算法从图中顶点u出发，沿图中的边随机游走。在任意点上，算法以一定的概率d随机地选择与该顶点相邻的边，沿这条边移动到下一个顶点，或以(1-d)概率直接回到出发点u，这是这个重启概率可有效的防止由于随机游走的不确定性而进入一条权值很小的路径。在第t-1步时移动带下一个顶点时，就开始了以这个点新出发点的第t步随机游走，其中Wrt-1表示的是在t-1步游走时从一个节点游走到另一个节点概率。经过若干次

7、随机游走过程，可以到达图中每一个顶点的概率值达到平稳分布，即再次迭代也不改变图中的概率分布值时，就可以得到的R值来对所求任务进行排序。比如讲RWR运用在下图做图像分割时：图1假设图像最核心的部分是红色，次核心为黄色，需排除的部分为蓝色。开始游走时路径沿着最左面的蓝色路径走，每一次游走都进入了不需要的部分，直到某次重新启动成功，返回最最上角的开始节点重新游走，第二次沿着绿色的路径游走，识别到了部分次核心区域，在某一步是再次重启，沿着黑色的路径识别到了核心区域。由(2)公式就可以迭代的计算出每条路径覆盖范围的概率

8、大小，在N次游走达到稳定后，上图的每一部分子图都会有一个确定不变的概率，结合核心、次核心与需排除部分的权重，就可以计算出每个子图的评分，从而找出评分最高的核心区域。目前已有许多关于RWR的研究，包括使用RWR进行分类，关系学习与一般化的图上的相似性度量等。2.2RelationalLearning要实现关系抽取，其中对关系的推导学习是很重要的一部分。在大数据的背景下，预测一个关系是否成立具有极大的研