长沙网站建设团队,做淘客应该知道的网站,旅游网站前台怎么做,wordpress照片保护基于位置的知识图谱链接预测
人工智能技术与咨询
本文来自《中文信息学报》#xff0c;作者张宁豫等
摘 要: 链接预测是知识图谱的补全和分析的基础。由于位置相关的实体和关系本身拥有丰富的位置特征#xff0c;该文提出了一种基于位置的知识图谱链接预测方法。该方法首…基于位置的知识图谱链接预测
人工智能技术与咨询
本文来自《中文信息学报》作者张宁豫等
摘 要: 链接预测是知识图谱的补全和分析的基础。由于位置相关的实体和关系本身拥有丰富的位置特征该文提出了一种基于位置的知识图谱链接预测方法。该方法首先通过分析实体和关系的语义特征对关系进行分类然后提出了一种基于位置的实体和关系位置特征和规则的挖掘方法其次通过挖掘出的实体位置特征和规则对实体和关系的向量化方法预测结果进行约束得到最终的结果。该文通过对WikiData、FB和WN数据集的实验证明该方法针对基于位置的关系和实体链接预测拥有较好的效果。
关键词: 位置特征知识图谱链接预测
0 引言
知识图谱例如FreeBase、Yago等是很多人工智能应用的重要数据来源。它包含了海量的实体和关系并以三元组的形式进行存储。然而大多数知识库的数据都是缺失的。所以知识库补全也就是对现有的知识库进行链接预测新的关系和实体是一项重要的工作。
现有的知识图谱链接预测方法大多都是直接利用实体、关系本身或图的特征来进行链接预测。对于给定的知识图谱实体和关系通常会被映射成低维的向量。通过定义一个打分函数来对每一对实体和关系的三元组进行预测。实体和关系的向量可以通过最大化已知正确三元组的打分函数来训练获得。
然而在训练实体、关系向量与打分函数的过程中这类方法并没有利用实体和关系本身隐藏的位置特征。此外,由于实体和关系向量化方法数据驱动特点如果训练结果中某一类关系或者实体数据量很小训练出的这一关系或实体的向量针对打分函数可能会导致过拟合等问题。
事实上现有的知识库中储存着海量的位置相关的实体和关系。例如在三元组(鲁迅WasBornIn绍兴)中实体“绍兴”有明确的位置特征。利用实体“绍兴”的属性可以获得位置特征进而可以推测实体“鲁迅”隐含的位置特征利用位置的隐含特征构造规则约束。例如在判断三元组(鲁迅WasBornIn 浙江)是否成立时利用实体“鲁迅”的位置特征和空间位置的规则判断可以约束判断的最终结果。
在本文中, 我们提出了一种针对位置关系的基于向量化和规则的链接预测方法。位置相关的关系指的是三元组中至少含有一个实体,其属性或者本身含义带有位置的特点。例如至少有一个实体是一个地名、一个区域名称、一个兴趣点名称等。
首先针对基于位置的三元组我们根据其特点把基于位置的关系分成了三类: 包含关系、相邻关系和相交关系。包含关系是两个实体本身的地理坐标范围是相互包含的例如LoactedIn。相邻关系是指两个实体本身的地理坐标范围是相互分离的但在一定距离内例如NearBy。相交关系是指两个实体本身的地理坐标范围是相互交叉的例如HasSameHometown。针对不同的实体我们提取出不同的隐藏位置特征。针对不同的关系类型我们提取不同的规则。实体的隐藏位置特征主要由实体本身的位置(如经纬度或地名)和它的辐射范围组成。规则主要分成两类: 一类是通用规则。例如两个实体间拥有NearBy 关系必然会存在HasNeighbour 关系同时NearBy 关系的实体必须是属于Location 类型的。另一类是位置规则。例如实体h和实体t的隐藏位置特征是后者包含前者则两个实体间有可能存在包含这类的关系。最后我们利用规则对向量化方法结果进行约束得到最终的结果如图1所示。 图1 基于位置的向量化和规则链接预测方法
我们的方法有以下优点: (1)规则的使用降低了计算空间并提高了准确度(2)保留了向量化方法的优点同时加入了隐藏的位置信息(3)它是一个通用的框架能够适用各种通用的向量化方法和规则。
综上所述本文的贡献如下:
(1) 针对基于位置的三元组我们提出了挖掘实体和关系位置特征的方法。
(2) 提出了一种针对位置关系的基于向量化和规则的链接预测方法。
(3) 利用WikiData、FB和WN的数据集进行实验证明针对位置相关的链接预测本方法比其他方法准确度有所提高。
1 相关工作
知识图谱的链接预测通常是指给定一组三元组预测其成立的可能性。根据Nickel Maximilian[1]的研究知识图谱链接预测通常分为三大类: (1)通过实体和关系的隐含特征将其转换成低维向量的方法[2-3](2)基于图特征的方法[4-5](3) 基于马尔科夫概率图利用一阶谓词逻辑[6]或者软逻辑(probabilistic soft logic)[7]来预测。
基于向量化的知识图谱链接预测方法的核心是用向量来表达实体和关系隐藏的特征。RESCAL[2]和TransE[8]是两个典型的方法。它们通过最小化结构风险或边界误差来学习隐藏的向量。然而在学习和预测的过程中这类方法都没有利用潜在的位置特征和应用规则。TRESCAL[9]将规则和RESCAL整合在了一起但它仅能使用单一规则(例如某种关系的实体必须是特定的类型)。Rocktäschel等[10]提出了将一阶谓词逻辑映射成低维向量。但是他们的方法中规则并没有直接起到链接预测的作用也没有降低预测的复杂度。Wang Q等[11]提出了一种基于整数线性规划(ILP)的方法将向量化结果和规则整合起来进行链接预测但是他们并没有利用潜在的位置特征和基于位置的规则。基于图的方法核心是挖掘知识图谱图结构所有的特征。Lü Lin[12]挖掘节点之间的相似度来进行链接预测。Path ranking algorithm(PRA)[13]是利用节点之间不同通路包含的特征来进行预测也可以提炼出规则来约束结果。但是基于图特征的方法通常适合局部的链接预测不一定能挖掘出全局的隐藏特征。我们方法的不同点在于提供了一个通用的利用位置特征和规则的预测框架可以整合各种向量化方法和规则。
在马尔科夫网络中规则已经被大量使用代表性的研究有利用一阶谓词逻辑[6]和软逻辑(probabilistic soft logic)[7]。本文利用规则来约束向量化方法的结果将整合问题变成一个整数规划问题。此外我们挖掘出了隐藏的位置特征构造了位置特征的规则。
2 方法
2.1 定义
定义1(实体位置特征) 如果实体e能够在当前知识库或外部数据库如Yago、GeoNames、 LinkedGeoData和WikiData中匹配到相应的位置(经纬度)和大致范围或所属上级的范围则e有位置特征fe[lng,lat,D]lng是经度lat是纬度D是一个描述实体包含范围的数值通常情况由实体本身的行政地域半径或上级所属区域半径最小值确定。
定义2(位置相关三元组) 三元组(h, r, t)的实体h、t中至少有一个实体含有位置特征。
定义3(包含关系) 实体h和t的位置特征存在 则两者存在包含关系HasContain(h,t)。
定义4(相邻关系) 实体h 和t的位置特征存在 ≥|hDtD|则两者存在相邻关系HasAdjacent(h,t)。
定义5(相交关系) 实体h和t的位置特征存在|hD-tD|≤ 则两者存在相交关系HasIntersect(h,t)。
2.2 框架
如图2所示我们的系统由两部分组成(1)位置特征和规则挖掘。首先对三元组中实体进行位置特征提取然后对基于位置的三元组的关系进行自动识别或者人工标注分类最后提取出其他可能存在的位置特征和规则。(2)基于向量化和规则的链接预测。首先对三元组利用向量化方法进行训练然后利用规则对结果进行约束。 图2 框架系统的组成
2.3 隐含的位置特征和规则挖掘
给定一个基于位置的三元组(h,r,t), 首先我们需要提取出三元组中实体可以直接获得的位置特征。例如三元组(鲁迅WasBornIn, 绍兴)中通过对实体“鲁迅”和“绍兴”的类型和本地数据库以及外部数据库Yago、GeoName、LinkedGeoData和WikiData的匹配得到实体“绍兴”是一个地名。我们可以获得该实体的经纬度、面积、相邻城市等信息。通过近似计算(利用面积或相邻区域经纬度)我们可以获得实体“绍兴”的位置特征。然后我们需要获得关系“WasBornIn”的类别,即它属于包含、相邻、相交哪一类。一般地说有两种做法(1)自动识别。遍历所有三元组中两个实体都含有位置特征的三元组通过反向计算实体位置特征的差异推导出此三元组拥有的关系对常见的如LocatedIn、Nearby等关系此方法可以方便地判别(2)人工标注。事实上基于位置的关系总数并不多再者通常整个知识图谱需要预测的关系数量级也不是很大远小于实体个数数量级。所以可以采取人工标注的方法来解决额外的关系分类问题。最后我们通过已经获得的关系“WasBornIn”属于包含关系判断实体“鲁迅”隐藏位置特征该特征和实体“绍兴”的位置特征存在包含关系。这个知识可以作为规则为后续的未知链接预测做约束。
具体地说, 对于任意三元组(h,r,t), 如果只有实体t可以直接获得位置特征ft[tlng,tlat,tD]根据关系r我们可以推测实体h隐含的位置特征。如果r属于包含关系则h可能存在隐含位置特征[tlng,tlat,tD-μ]其中0μtD。如果r属于相交关系则h可能存在隐含位置特征 [hlng,hlat,hD], 其中|hD-tD|≤ |hDtD|也就说是h位于一个环状区域范围内。如果r属于相邻关系则h可能存在隐含位置特征 [hlng,hlat,hD] 其中以上变量满足条件 ≥|hDtD|。反之如果实体h含有隐藏位置特征以此来推导t也是如此。事实上对于相交和相邻关系大多数三元组的两个实体本身都可以直接获取位置关系。以上的隐藏特征都是近似特征。
由此我们可以获得海量的实体隐藏位置特征和规则。事实上可以获得以下规则:
规则1(实体类型匹配) 特定的关系拥有特定类型的实体。例如关系LocatedIn拥有的两个实体一定是Location 类型的关系WasBornIn拥有的两个实体一定是一个是Person类型一个是Location类型。
规则2(参数个数匹配) 一对多和多对一的关系中特定实体的数目有一定限制。例如CityLocatedInCountry是一个多对一的关系。给定一个城市实体在知识图谱中最多存在一个国家实体与之对应。
规则3(相似关系匹配) 如果关系r1和r2存在一定的牵连或同属于同一个类型(同是包含类型)在不违背规则1、2的前提下则拥有r1 关系的实体可能存在r2关系。例如, CityCapitalOfCountry-CityLocatedInCountry。
规则4(位置包含关系) 如果两个实体的位置特征存在包含关系则两个实体可能存在包含关系。例如实体“鲁迅”和实体“浙江”的位置关系存在包含关系则两个实体很大程度上存在包含关系。
规则5(位置相邻关系) 如果两个实体的位置特征存在相邻关系则两个实体可能存在相邻关系。例如实体“西湖”和实体“浙江大学”的位置关系存在相邻关系则两个实体很大程度上存在相邻关系。
规则6(位置相交关系) 如果两个实体的位置特征存在相交关系则两个实体可能存在相交关系。例如实体“金庸”和实体“徐志摩”的潜在的位置特征存在相交关系则两个实体可能存在相交关系。
规则7(位置包含传导) 如果实体e2的位置特征包含实体e1的位置特征实体e3的位置特征包含实体e2的位置特征则实体e3和e1存在包含关系。包含关系可以一直连续传递相邻和相交关系不能传递。例如实体“鲁迅”和实体“浙江”存在包含关系实体“浙江”和实体“中国”存在包含关系则实体“鲁迅”和实体“中国”存在包含关系。
此外如果未知的一对一关系的三元组中其中一个实体和关系存在于已知三元组正样本中那这个三元组很可能是不成立的。对于一些特殊的实体可以通过几重的关系链传递估计出位置特征的信息。例如三元组(鲁迅说中文)实体“中文”的位置特征可以通过关系如“中国人说中文”、“中国人出生在中国”、“绍兴位于浙江”、“浙江位于中国”和“绍兴位于中国”等估计得到其位置特征大致和实体“中国”的位置特征接近从而估计出实体“中文”的位置特征。
2.4 基于向量化和规则的链接预测
给定一个知识图谱其包含n个实体m个关系。我们可以获得三元组集合O{h,r,t}。向量化方法的目的在于: (1)通过隐含的特征把实体和关系映射到一个向量(2)利用训练好的向量来预测新三元组成立的可能性。本文中我们利用了三种成熟的向量化方法: RESCAL、TRESCAL、 TransE。
RESCAL将每个实体ei当成一个向量ei∈Rd每个关系rk都是一个矩阵Rk∈Rd×d。给定一个三元组(ei,rk,ej)它的打分函数如式(1)所示。
f(ei,rk, (1)
{e}和{rk}是通过最小化下面的结构损失函数来获得的如式(2)所示。 ,rk,ej))2λR
(2)
其中如果三元组(ei,rk,ej)成立则 等于1反之为0。R是正则项。λ是正则化参数控制正则化和损失函数之间的平衡。
TRESCAL是RESCAL算法的一个扩展需要对给定关系的实体类型进行约束。例如给定关系rk和分别包含特定类型的实体集合Hk,Tk则问题变成优化问题如式(3)所示。 ∑i∈ ,rk,ej))2λR
(3)
TransE将三元组(ei,rk,ej)映射成以下的三个向量ei,rk,ej∈Rd它使用以下的打分函数来计算三元组成立的可能性如式(4)所示。
f(ei,rk,ej)||eirk-ej||
(4)
其中{ei}、{rk} 是通过优化式(5)的边缘损失函数(正确样本得到更高的得分错误样本得分更低)来得到: γ-f(ei,rk, ,rk, (5)
其中t是正样本O是正样本的集合t-是负样本N是负样本的集合。在替换过程中我们未采用随机替换而是替换之后确保新的三元组在原始的数据集中存在确定的关系但关系不是rk, 这很大程度上确保了样本是负样本。我们利用随机梯度下降的方法来求解优化问题。
利用上述方法对未知的三元组打分高的一般情况下成立的可能性较高反之较低。我们将向量化方法得分的输出记为 ,rk,ej)每个实体的位置特征记为fi、fj标记相交关系集合Rintersect含三元组s 对相邻关系集合Radjacent含三元组p 对包含关系集合Rcontain含三元组q 对标记一对多、多对一、一对一关系集合R1-M,RM-1,R1-1, 标记特定关系所属实体种类的集合Hk、Tk。用逻辑变量 来标记这个三元组成立的最终可能。根据文献[11]我们把规则约束向量化结果的问题定义为一个整数规划的问题如式(6)所示①。 (6)
其中 ∈{0,1},∀i,j,kO是正样本集合。通过解答上述问题求得最终的得分 我们的方法优势如下: (1) 在向量化方法的前提下利用位置和通用规则使含有显性和隐性位置特征的三元组链接预测准确率有明显的提高(2)这是一个通用的框架向量化方法和规则都可以灵活变化。
3 实验
实验的具体流程如下: (1)位置特征和规则挖掘(2)基于向量化和规则的链接预测(3)分析位置特征和规则对结果的影响。
3.1 数据集
在实验中我们使用了三个数据集: WikiData-500K、WN-100K、FB-500K分别从WikiData[14]、WordNet[15]、FreeBase[16] 获取。WikiData是目前较大的一个开放的知识图谱。WikiData包含有human、taxon、administrative territorial、architectural structure、event、chemical compound、film、thoroughfare、astronomical object等类型的实体组成的三元组信息。据我们统计有至少19.8%的三元组中至少有一个实体含有位置信息(事件、行政区划、地点等)*,可以直接通过API获取。我们由此构建了WikiData-500K数据集。WN-100K和FB-500K都是由不同学者发布出的三元组数据集。我们从WN-100K、FB-500K筛选出位置相关的三元组来进行训练。具体地说在完整知识库中至少30%的三元组都满足条件要求。此外我们还利用Yago*、GeoNames*、LinkedGeoData*和WikiData对所有数据中的实体进行位置信息匹配以获得实体本身的位置特征。我们过滤了数据集中出现次数少于三次的实体并采用了文献[8]的方法来判断实体的关系是一对多还是多对一来制定规则。此外我们制定了一些同类匹配的规则。实验数据集如表1所示。
表1 实验数据集 3.2 特征和规则挖掘
我们的任务是提取出实体隐含的位置特征。首先对数据集中所有的实体进行位置信息匹配。利用外部数据集拥有的准确地理位置信息匹配数据集中实体大约40%的实体能匹配到准确的位置特征。然后我们对数据集中拥有的关系进行分类。
利用自动分类方法标记了约63%的关系剩下的关系采用人工标记。事实上有约5%的关系是有歧义的我们将它们默认归到包含关系类。最后利用位置特征和关系类型挖掘剩下的实体隐藏位置特征。
3.3 链接预测
我们的任务是补全位置相关的三元组(h,r,t)也就是说给定h和t预测r或者给定h和r预测t或者给定r和t预测h。本节中测试了RESCAL、TRESCAL、TransE并把利用基于位置的规则来约束向量化结果的方法命名成l-RESCAL、l-TRESCAL、l-TransE。
对每个数据集我们把基于位置的三元组按照4∶1的比例划分成训练集和测试集。对每一个实体我们都获得其所属类型。对于测试三元组通过计算命中10(正确命中结果排前十所占的比例)来衡量。在具体实验中RESCAL、TRESCAL的正则化参数λ0.1我们迭代训练了十次。在向量化训练过程中我们将维度分别设置成10,20,50,100来选择最优的参数。然后利用集成学习的方法获得三种向量化方法的最优结果。在规则约束的过程中δ10.7,δ20.6,δ30.4我们使用lp solve*来解整数规划问题。我们对规则约束重复进行了20 次取平均值以获得最优的结果。
表2展示了不同数据集下不同关系进行关系预测的结果。可以看出利用基于位置的规则方法对特定的关系有显著的提高。RESCAL和TRESCAL的提升幅度比TransE要高。
表2 位置相关关系命中10结果/% 3.4 位置特征和规则分析
我们还对不同关系类型和不同实体进行了结果的比较如表3所示。从结果可以看出对我们的方法包含关系获得的提升程度 较 高其 次 是 相邻关系和相交关系。事实上包含关系的位置隐含特征区域较为狭小因此对关系的确定限制较大可以获得较好的结果而相邻关系和相交关系(实体都可以直接获得位置特征除外)获取的隐藏位置区域较大因此限制较为不准确。对实体而言两个实体都可以直接获得位置关系的预测结果提升幅度最大其次是单一实体的结果。有趣的是对于两个都不能直接获得位置信息的实体本方法仍能获得少量的提升。事实上例如判断三元组(徐志摩HasSameHometown金庸)时实体“徐志摩”和“金庸”的隐藏位置特征是可以获得的, 利用人工标记关系“HasSameHometown”为相交关系使用我们的方法可以获得准确度的提升。
表3 不同类型关系命中10结果/% 4 结论
本文提出了一种针对位置关系的基于向量化和规则的链接预测方法。实体位置特征和规则的使用降低了计算空间提高了基于位置链接预测的准确度。我们还对位置特征和规则进行了实验分析。
实验结果证明对于特定类型的关系位置特征和规则的利用可以使链接预测的准确度得到一定程度的提高。将来我们计划(1)分布式我们的方法使得它能够适用于更大的数据集(2)加入更加复杂的空间规则(3)尝试在向量化训练的同时直接利用规则以提高准确度。
关注微信公众号人工智能技术与咨询。了解更多咨询
