path ranking algorithm调研报告.doc

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与2010年提出。该方法将每种不同的关系路径作为一维特征，通过在知识图谱/Knowledge Base中统计大量的关系路径构建关系分类的特征向量，建立关系分类器进行关系抽取，取得不错的抽取效果，成为近年来的关系抽取的代表方法之一。但目前这种基于关系的统计的方法，只能在连通图上使用，对于那些出现频率低的关系有严重的数据稀疏问题，且代价高昂。针对这样的问题，现今也出现了许多针对该算法的改进研究。2. Path Ranking Algorithm2.1 Random Walk and RestartRandom walk with restart (RWR)是最初提出的图像分割算法，也叫Personalized Page Rank。它迭代地探讨了网络的全局结构，估计两个节点之间的接近（亲和度得分）。在一个节点上，在每个步骤中，面临两个选择：要么移动到一个随机选择的邻居，或跳回到起始节点。该算法仅包含一个固定参数R称为“重启的概率（1R移动到一个邻居的概率）。迭代后达到稳定，稳定的概率向量包含了网络中的所有节点对于起始节点的得分。这种稳定的概率向量可以被看作是“有影响力的影响”，在网络上所施加的起始节点。游走的分布满足式(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）图7Path 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是在 min thenfor each e R(e) do hi+1(e)+ = sizenew end forelsefor k=1.floor(hi(e)/min) do randomly pick e R(e) hi+1(e)+ = min end forend ifend 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的实验证明，能有效的提高查询执行效率与查询质量。具体改进的实验结果如下：图73.2 Path Finding在以往的Path Ranking Algorithm中，会规定一个最大的路径长度l。当边的类型不多时，在公式(6)的还可以被一一列举出来，但如果说有很多种关系，如在知识库的背景下，对一个节点的关系就可能有100多种，那么即使路径长度只有3，那么最终的路径数量也会达到上百万种之多。若想在这样的背景下利用Path Rank Algorithm，文献4中对Path Rank Algorithm中路径的产生过程做了相应的修改，只发现那些对查询可能有用的路径，忽略排名较低的路径。首先对于任意查询实体e有，定义一个查询s去发现一路路径P，且路径发现的过程中，创建任何一个节点都需要由一部分训练集中的查询Si支持，这个比例人工指定。其次，只有当在检索时至少有一个目标实体在训练集中时，才需要在RPA中发现路径。在上述两种约束下，经实验证明可以有效的减少需要考虑的路径数量。类似发现路径以连接节点的思想并在2002年的N-FOIL中也被使用过，但是当时使用的是一个查询去发现路径，而不是RPA中以数据驱动的多查询去发现路径，且PRA可以用于非实意动词中，而N-FOIL不能。文献4中实验证明了在发现重要路径方面RPA优于N-FOIL。3.1节所述的finger printing 与 particle filtering策略有一个缺点是，他们会减弱随机游走的多样性。比如图上只有两条路径的话，那么有50%的可能性是所有的随机游走器全部在一条路径上，而另一条路径被置空。针对这样的问题，可以采用一种叫Low-Variance Sampling(LVS)的技术，该方法于2005年由Thrun提出，广泛运用于机器人学。文献4总结了几条未来的研究方向，其一是从查询节点和目标节点同时开始做推测可能会更加有效的发现长路径，而长路径一般来说是比较好的路径，且搜索效率应当更高。其二是从目标节点开始查询去发现特殊的路径，也就是反向的随机游走算法。其三是对推测树或推测图去生成推测路径可以更好的使用随机游走推测模型。最后提出随机游走模型在大规模数据集上进行关系学习是一种很有研究价值的方向。还有相关研究表明，正向与反向的随机游走混合模型对查询效率有更好的提升。结合上述基本的PRA与其改进，比较好的算法总结可以由图8表示。图83.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来说，就可以加入潜在的去预测(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, 2010.2 Ni Lao, William W. Cohen,Fast Q