pathrankingalgorithm调研分析报告.docx
《pathrankingalgorithm调研分析报告.docx》由会员分享,可在线阅读,更多相关《pathrankingalgorithm调研分析报告.docx(23页珍藏版)》请在咨信网上搜索。
1、path ranking algorithm调研汇报1. 引言近两年来,伴随Linking Open Data等项目标全方面展开,语义Web数据源数量激增,大量RDF数据被公布。互联网正从仅包含网页和网页之间超链接文档万维网(Document Web)转变成包含大量描述多种实体和实体之间丰富关系数据万维网(Data Web)。在这个背景下,谷歌、baidu和搜狗等搜索引擎企业纷纷以此为基础构建知识图谱,如Knowledge Graph、知心和知立方等,用以改善搜索质量,从而拉开了语义搜索序幕。正如谷歌辛格博士在介绍知识图谱时提到:“The world is not made of string
2、s , but is made of things.”,知识图谱意在描述真实世界中存在多种实体或概念。其中,每个实体或概念用一个全局唯一确定ID来标识,称为它们标识符(identifier)。每个属性-值对(attribute-value pair,又称AVP)用来刻画实体内在特征,而关系(relation)用来连接两个实体,刻画它们之间关联。知识图谱亦可被看作是由一张巨大图组成,图中节点表示实体或概念,而图中边则由属性或关系组成,我们需要构建并使用这张图。大规模知识图谱构建和应用需要多个智能信息处理技术支持,其中关键包含:实体链指(Entity Linking)、关系抽取(Relation
3、Extraction)、知识表示(Knowledge Representation)、知识推理(Knowledge Reasoning)等。在知识推理方面,利用推理规则实现关系抽取经典方法之一就是Path Ranking Algorithm算法,由Lao & Cohen和提出。该方法将每种不一样关系路径作为一维特征,经过在知识图谱/Knowledge Base中统计大量关系路径构建关系分类特征向量,建立关系分类器进行关系抽取,取得不错抽取效果,成为多年来关系抽取代表方法之一。但现在这种基于关系统计方法,只能在连通图上使用,对于那些出现频率低关系有严重数据稀疏问题,且代价高昂。针对这么问题,现今
4、也出现了很多针对该算法改善研究。2. Path Ranking Algorithm2.1 Random Walk and RestartRandom walk with restart (RWR)是最初提出图像分割算法,也叫Personalized Page Rank。它迭代地探讨了网络全局结构,估量两个节点之间靠近(亲和度得分)。在一个节点上,在每个步骤中,面临两个选择:要么移动到一个随机选择邻居,或跳回到起始节点。该算法仅包含一个固定参数R称为“重启概率(1R移动到一个邻居概率)。迭代后达成稳定,稳定概率向量包含了网络中全部节点对于起始节点得分。这种稳定概率向量能够被看作是“有影响力影响”
5、,在网络上所施加起始节点。游走分充满足式(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
6、-1步游走时从一个节点游走到另一个节点概率。经过若干次随机游走过程,能够抵达图中每一个顶点概率值达成平稳分布,即再次迭代也不改变图中概率分布值时,就能够得到R值来对所求任务进行排序。比如讲RWR利用在下图做图像分割时:图1假设图像最关键部分是红色,次关键为黄色,需排除部分为蓝色。开始游走时路径沿着最左面蓝色路径走,每一次游走全部进入了不需要部分,直到某次重新开启成功,返回最最上角开始节点重新游走,第二次沿着绿色路径游走,识别到了部分次关键区域,在某一步是再次重启,沿着黑色路径识别到了关键区域。由(2)公式就能够迭代计算出每条路径覆盖范围概率大小,在N次游走达成稳定后,上图每一部分子图全部会有一
7、个确定不变概率,结合关键、次关键和需排除部分权重,就能够计算出每个子图评分,从而找出评分最高关键区域。现在已经有很多相关RWR研究,包含使用RWR进行分类,关系学习和通常化图上相同性度量等。2.2 Relational Learning要实现关系抽取,其中对关系推导学习是很关键一部分。在大数据背景下,估计一个关系是否成立含有极大研究潜力。我们能够用下图描述一个关系学习问题:图2假如想要判定Charlotte是否是一个作家。最简单情况图1所表示,我们需要两个点和一条边来描述这个问题,我们能够经过判定这两个点之间是否存在这么一条边,来判定这两个点是否存在关系。而这条边存在概率有多大,怎样定量计算,
8、就是Path Ranking Algorithm能够处理问题。而现实情况肯定不由简单图2能够描述清楚,假如我们在判定Charlotte是否是一个作家时,考虑到了她好友和家庭等关系时,(这能够为我们判定提供更多依据),那么情况可能会是这么:图3 我们仍以Charlotte为出发点,Writer为终点来判定Charlotte是否是一个作家,但这次我们多了一条这么判定路径:Charlotte-Patrick Bronte-Writer。若这三个点间两条边存在,我们一样能够得到Charlotte是一个作家结论。值得注意是在判定Charlotte是否是一个作家时,Charlotte行为无疑对判定也是有帮
9、助,那么我们判定图能够表述为:图4假如在考虑到出版社等问题,我们还要加上这么关系:图5至此我们需要考虑关系图变了这么:图5能够看到这已经是一个很复杂图了,而实际上我们在做判定时候,可能考虑远比这还要复杂,其计算复杂度关键表现在它有指数级增加路径类型和指数级增加路径实例。图中每两个点之间存在边,对应着我们需要学习到关系,能够发觉不一样点之间关系种类并不相同,如Charlotte和Jane Eyre之间,是wrote关系,而Jane Eyre和Novel之间,是IsA关系。而RWR并不能有效区分这么区分,前面类型信息会被后面类型信息覆盖,而下面提到Path Ranking Algorithm能够很
10、好处理这么问题。2.3 Path Ranking Algorithm有部分相关研究,如Minkov, Cohen等在基于RWR模型上使用了愈加丰富特征集合,用边上标签对排序结果再次排序。而且她们还提出了一个加权RWR-paths方法,提升了查询到相关实体正确率。而Path ranking algorithm算法和之类似,能够看做是其一个改善版本,相当于沿着一组带有特定类型信息边序列集合上随机游走,即限制了游走路径RWR算法。相比于RWR无法区分边类型,它更轻易加入额外所需类型信息,如它query-independent experts和 popular entity experts。类似技术还
11、有Embedding-based techniques和Probabilistic graphical models,Path ranking algorithm 相比较前二者,含有轻易推测和不需要相关网络结构先验知识优点。其算法关键思想是利用连接着两个实体路径去估计她们之间是否有潜在关系。举个例子,图7所表示,我们要判定Charlotte是不是作家,能够判定这么一组特定关系序列是否成立: Prob(Charlotte-Writer | InSentence, InSentence-1, IsA)图7Path ranking algorithm能够经过不一样边类型序列来判定一个关系是否存在,在
12、比较复杂图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)。而且有定义, 且有。假如期望强调路径上每一步
13、类型信息,能够将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,没有任何一
14、条连接到其它节点路径,此时考虑关系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上可表示
15、为:首先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,联想)存在
16、时,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水平会显著高于老挝,大家
17、全部不会倾向于购置老挝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)+ =
18、 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中指出,随机游走会产生一个不平衡分布,小部分节点有高评分,而大部分节点是低评分(即符合幂率分布)。所以,能够做出这么假设:将那些低评分节点忽略掉,不仅不会影响随机游走判别关键实体能力,反而还
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- pathrankingalgorithm 调研 分析 报告
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。