pathrankingalgorithm调研分析报告

path ranking algorithm调研汇报 1. 引言 近两年来，伴随Linking Open Data等项目标全方面展开，语义Web数据源数量激增，大量RDF数据被公布。互联网正从仅包含网页和网页之间超链接文档万维网Document Web转变成包含大量描述多种实体和实体之间丰富关系数据万维网Data Web。在这个背景下，谷歌、baidu和搜狗等搜索引擎企业纷纷以此为基础构建知识图谱，如Knowledge Graph、知心和知立方等，用以改善搜索质量，从而拉开了语义搜索序幕。 正如谷歌辛格博士在介绍知识图谱时提到“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 R1-dudWr 1 其中，d是继续游走概率，1-d为重启概率，u是开启节点，Wr是网络过渡矩阵。随机游走RWR实际是一个简单迭代过程 Rt1-dudWrt-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 ran