pathrankingalgorithm调研分析报告.docx

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 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-1h值为0，从而整条路径h值变小。而其中当三元组关系(中国,inWhichCountry-1，联想)存在时，I(R(e,e)=1时，再递归以中国为出发节点，利用公式(3)计算一个h值，这个h乘上一个不为0从e到e一步随机游走概率，最终整体路径P2=h值肯定会显著大于P1。至此就能够对查询所需结果进行排名： （5）图10，假设有一条路径P=，路径长度为n，最终止果为型号为Y450-tisPC。由公式(4)计算出每一步游走h值，也就是每一个连接2个节点关系Rh值，最终将这些h值求和，利用公式(5)就能够得到路径P最终排名得分，不过需要注意到是，在这条路径中，每一步权重可能并不相同，这也是会影响最终得分关键原因之一。比如在在图10a1,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中发觉路径。在上述两种约束下，经试验证实能够有效降低需要考虑路径数量。类似发觉路径以连接节点思想并在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表示。图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, .2 Ni Lao, William W. Cohen,Fast Query Execution for Retrieval Models based on Path Constrained Random Walks. KDD, 3 D. Fogaras and B. Racz. Towards fully personalizing PageRank. In Proceedings of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW), in conjunction with FOCS .4 Ni Lao, Tom Mitchell, William W. Cohen,Random Walk Inference and Learning in A Large Scale Knowledge Base. EMNLP, slidesposterAMT labels of 16 relationsDistant Supervision labels of 96 relations5 Ni Lao, Amarnag Subramanya, Fernando Pereira, William W. CohenReading The Web with Learned Syntactic-Semantic Inference Rules. EMNLP, 6 Matt Gardner, Partha Talukda