融合决策蕴涵的知识图谱推理方法

翟岩慧，何 煦，李德玉,2，张 超,2

1.山西大学 计算机与信息技术学院，太原 030006

2.山西大学 计算智能与中文信息处理教育部重点实验室，太原 030006

形式概念分析（formal concept analysis，FCA）是进行数据分析和规则提取的强有力工具[1-2]。其中，形式概念分析对知识获取的研究就是对蕴涵的研究。由于形式背景中得到的蕴涵数量过于庞大，Qu等[3]提出了决策蕴涵。研究者[4-6]从逻辑角度对决策蕴涵进行描述，给出了决策蕴涵的语义结论和语构结论，比较了决策蕴涵相对于概念规则和粒规则[7]的优势[8]。

上述研究目前被广泛应用在文本挖掘[9]、冲突分析[10]、推荐系统[11]、属性约简[12-17]及基于概念的认知学习[18-21]等相关领域中。随着对形式概念分析研究[22-23]的深入，发现它在基于知识图谱的关系补全推理上也有一定的应用价值。

关系补全是知识图谱补全的任务之一[24]，最先进的关系补全方法[25]主要是基于知识嵌入的模型，包括翻译模型和基于卷积神经网络（convolutional neural network，CNN）的模型。

早期的翻译模型是Bordes等人[26]于2013年提出的TransE模型，文献[26]将知识图谱中的实体与关系映射到低维向量空间中，得到实体与关系的向量表示，并使用向量差来进行关系预测。由于该模型在处理多对一等关系上存在一定的局限性，一些研究者相继提出TransH[27]、TransR[28]、TransD[29]等模型来解决该问题。文献[27-29]提出的超平面空间向量可以很好地支持复杂关系预测，但模型复杂，参数也较多。

基于卷积神经网络的模型是由Dettmers 等人[30]提出的，文献[30]将卷积引入知识图谱嵌入（knowledge graph embedding，KGE）中，但只考虑了头实体和关系的卷积。文献[31]对文献[30]进行改进，提出将三元组的三个元素都进行卷积，由于三元组表现为三列，卷积时三列相同维度被一起提取特征。

上述知识嵌入模型都继承了表示学习[32-33]的强大能力，在关系预测任务中表现优异。然而，这些知识图谱嵌入模型都独立地处理三元组，无法封装知识图谱中给定实体附近固有或潜在的关系，较少关注知识图谱的网状结构和三元组之间的逻辑关系，存在可解释性弱等问题。

本文从形式概念分析角度解决关系推理预测问题。首先，从理论上证明基于形式概念分析的蕴涵及决策蕴涵可以表示知识推理中相应的规则。其次，为了快速挖掘决策蕴涵，对复杂背景不断约简，并证明约简后的背景可以挖掘到与原背景等价的决策蕴涵。最后，以具体示例和实验验证了该方法的可行性。

相比知识嵌入模型，基于蕴涵及决策蕴涵的关系补全方法不仅可以在构建背景的过程中引入先验知识辅助推理，而且注重不同三元组之间的关联关系，不需要把实体关系向量化后进行推理，有良好的可解释性。

1 知识图谱基本概念

知识图谱是结构化的语义知识库，以符号形式描述物理世界的概念及相互联系；其基本组成单位是（实体，关系，实体）三元组，也称为知识或事实。

定义1[34]知识图谱为二元组G=(E,R)，其中E为实体集合，R为E上的关系集合。对于r∈R，(x,y)∈r称为事实，记为(x,r,y)，x和y分别称为该事实的头实体和尾实体。

目前存在的知识图谱都存在一定的不完整性。例如，在Freebase[35]中，三百万人物实体中大约75%都遗漏了国籍信息，仅有4%的人物实体有兄弟姊妹信息，仅32%的人物实体有职业信息。在Dbpedia[35]中，有60%的人物实体没有出生地信息。

知识推理就是为了补全缺失的实体和关系。基于符号的规则推理常考虑两种规则[34]：一对一关联规则和N对一关联规则（目前只考虑N=2）。

定义2[34]令G=(E,R)为知识图谱，ri,rj∈R，称ri和rj具有ri→rj关系，若

本文将G 中的ri→rj关系称为1→1型关系。

定义3[34]令G=(E,R)为知识图谱，rj,rk∈R，称rj和rk具有rj↪rk关系，若

本文将G 中的rj↪rk关系称为1↪1型关系。

例1给定3个关系capital、belong_to、contains，其中(x,capital,y)表示x是y的首都，(x,belong_to,y)表示x属于y，(y,contains,x)表示y包含x。因为∀x,y∈E:(x,capital,y)⇒(x,belong_to,y)，所以capital和belong_to有capital→belong_to关系。又因为∀x,y∈E:(x,belong_to,y)⇒(y,contains,x)，所以belong_to和contains有belong_to↪contains关系。

定义4[34]令G=(E,R)为知识图谱，ri,rj,rk∈R，称ri和rj与rk具有rirj→rk关系，若

定义4表明，如果实体x和y具有关系ri且y和z具有关系rj，则x和z具有关系rk。本文将G 中的rirj→rk关系称为2→1型关系。

例2给定3 个关系ri、rj和rk，令ri=place_of_birth，rj=belong_to，rk=nationality，其中，(x,ri,y)表示x出生于y，(y,rj,z)表示y属于z，(x,rk,z)表示x的国籍是z。因为∀x,y,z∈E:(x,ri,y)∧(y,rj,z)⇒(x,rk,z)，所以belong_to、place_of_birth和nationality具有rirj→rk关系。

2 FCA基本概念

本章主要介绍FCA和决策蕴涵的一些基本概念和性质。

2.1 FCA

定义5[5]形式背景是一个三元组K=(G,M,I),其中G是对象集，M是属性集，I⊆G×M是对象和属性之间的二元关系。对于g∈G,m∈M,(g,m)∈I表示“对象g具有属性m”。

定义6[5]设K=(G,M,I)为形式背景，A,B⊆M。如果每一个具有属性集A的对象也同时具有属性集B，则A→B叫作K的一个蕴涵。

定义7[5]设K为形式背景，对于A⊆G，记：

为对象集A所共有的属性集。对于B⊆M，记：

为具有B中所有属性的对象集。对于g∈G，为了简单起见，将{g}I记为gI。

2.2 决策背景上的决策蕴涵

定义8[5]决策背景是一个三元组K=(G,C∪D,IC∪ID)，其中，G是对象集，C是条件属性集，D是决策属性集，IC⊆G×C是条件关联关系，ID⊆G×D是决策关联关系。对于g∈G,m∈C∪D,(g,m)∈IC或(g,m)∈ID表示对象g具有属性m。

由此可见，决策背景由两个子形式背景构成，KC=(G,C,IC)和KD=(G,C,ID)，对于A⊆C和B⊆D，符号AIC、BID简记为AC、BD。

定义9[5]设K=(G,C∪D,IC∪ID) 是一个决策背景。若A⊆C且B⊆D，K上成立的蕴涵A→B被称为K的决策蕴涵。此时，A为该决策蕴涵的前提，B为该决策蕴涵的结论。

定理1[5]设K=(G,C∪D,IC∪ID) 是一个决策背景，A⊆C，B⊆D，则A→B为K的决策蕴涵当且仅当AC⊆BD，当且仅当B⊆ACD。

3 基于形式概念分析的知识图谱推理研究

基于规则的知识推理无论依靠人工构建规则还是采用自适应规则挖掘算法，代价都非常高。本章研究知识图谱中1→1 型、1↪1 型和2→1 型关系在形式背景中的蕴涵表示和知识推理。

3.1 1→1 型关系对应蕴涵

定义10知识图谱G=(E,R)对应的(1,1)型关系形式背景是一个三元组=(G,M,I)，其中G=E×E，M=R，I满足对于任意的(x,y)∈G，r∈M，

对于(x,y)∈G,r∈M,(x,y)Ir或者((x,y),r)∈I表示(x,y)具有关系r。

例3由例1 生成的(1,1)型关系形式背景如表1所示。

表1 (1,1)型关系形式背景Table 1 Formal context of (1,1) relationship

表1 (1,1)型关系形式背景Table 1 Formal context of (1,1) relationship

注：表中x表示相应的对象具有相应的属性。

表1中的实体x和y分别为Beijing和China，属性ri、rj和rk表示关系“capital”“belong_to”和“contains”。因为在知识图谱中有(x,y)∈ri，所以在形式背景中有((x,y),ri)∈I，即((Beijing,China),capital)∈I，同理，((Beijing,China),belong_to)∈I，((China,Beijing),contains)∈I。

定理2令G=(E,R)为一知识图谱，ri,rj∈R，则ri和rj具有1→1 型关系当且仅当ri→rj在中成立。

证明由于ri和rj具有1→1 型关系，有∀x,y∈E:(x,ri,y)⇒(x,rj,y)，由定义10，上式等价于∀x,y∈E:((x,y),ri)∈I⇒((x,y),rj)∈I，即有∀(x,y)∈G:((x,y),ri)∈I⇒((x,y),rj)∈I，因此ri→rj。

定理2表明，对知识图谱中ri→rj关系的研究可等价转化为对(1,1)型关系形式背景上特定蕴涵的研究。

结合定理2可知，例3的实际意义在于，当x和y分别为城市和国家实体类别时，由(1,1)型关系形式背景可知，对于任意的(x,y)∈G，若((x,y),ri)∈I，则((x,y),rj)∈I，即若x是y的首都，则x隶属于y。在知识问答系统中，对于(x,y)∈G，当查询某城市x的隶属情况时，若只有信息((x,y),ri)∈I，则由定理2可得((x,y),rj)∈I，即在已知首都信息的情况下通过蕴涵可推理得到隶属信息，同时也满足G 中的1→1 型关系。

3.2 1↪1 型关系对应蕴涵

3.3 2→1 型关系对应决策蕴涵

知识图谱中的2→1 型关系rirj→rk可以补全图谱中缺失的知识。例如，在开源知识库Freebase 中，有超过70%的人条目中都没有国籍相关信息。如果将rk定义为国籍关系，并可以从具有国籍信息的知识库中识别出与国籍信息相关的ri和rj，则可将识别出的2→1 型关系rirj→rk应用于缺失知识补全。为此，本节由G 构建的(2,1)型关系形式背景，并将2→1型关系转换为形式背景中的蕴涵。

3.3.1 2→1 型关系的基本概念

定义12令G=(E,R)为一知识图谱，G 对应的(2,1)型关系形式背景是一个三元组=(G,M,I)，其中G=E×E×E，M=R×{1,2,3}，I为G和M之间的二元关系，且满足对于任意的(x,y,z)∈G，(ri,1),(rj,2),(rk,3)∈M，有：

例4一个(2,1)型关系形式背景可以用一个二维表表示。从知识图谱G 中任选3 个关联实体和3 个关联关系均可以构建一个(2,1)型关系形式背景，如表2所示。

表2 (2,1)型关系形式背景Table 2 Formal context of (2,1) relationship

表2 (2,1)型关系形式背景Table 2 Formal context of (2,1) relationship

注：表中x表示相应的对象具有相应的属性。

表3 决策背景Table 3 Decision context

表3 决策背景Table 3 Decision context

注：表中x表示相应的对象具有相应的属性。

表4 决策背景Table 4 Decision context

注：表中x表示相应的对象具有相应的属性。

下面将知识图谱中的2→1 型关系转换为形式背景中的蕴涵。

定理4令G=(E,R)为一知识图谱，ri,rj,rk∈R，则ri和rj与rk具有2→1型关系当且仅当(ri,1)(rj,2)→(rk,3)在中成立。

证明由于ri和rj与rk具有2→1型关系，因此有：

由定义12，上式等价于：

由定理4 可知，2→1 型关系成立的充要条件是特定的蕴涵在(2,1)型关系形式背景中成立，因此，只需在中找出相应的蕴涵即可生成知识图谱中所有的2→1型关系。

3.3.2 对象约简

首先，由定理4可以看出，为了挖掘2→1型关系对应的决策蕴涵，可将属性集M分为两部分，即条件属性集C=R×{1,2}和决策属性集D=R×{3}，而相应的蕴涵必然具有A→B的形式，其中A⊆C，B⊆D。具体来说，可将关系形式背景=(G,M,I)转化为决策背景=(G,C∪D,IC∪ID)，其中C=R×{1,2}，D=R×{3}，IC⊆G×C，ID⊆G×D且IC∪ID=I。

定理5令G=(E,R)为一知识图谱，ri,rj,rk∈R，则ri和rj与rk具有2→1型关系当且仅当(ri,1)(rj,2)→(rk,3)在中成立。

定理7令G=(E,R)为一知识图谱，ri,rj,rk∈R，则ri和rj与rk具有2→1 型关系当且仅当(ri,1)(rj,2)→(rk,3)在中成立。

表5 决策背景Table 5 Decision context

表5 决策背景Table 5 Decision context

注：表中x表示相应的对象具有相应的属性。

为简化2→1型关系对应决策蕴涵的生成，本小节对相应的决策背景进行了对象约简。与李金海等[36-37]所提的约简方法相比：一方面，本小节所提约简方法是为了保持决策蕴涵即知识的不变性，而文献[36-37]是为了保存代数结构的不变性；另一方面，本小节所提方法进行了对象约简，而文献[36-37]进行了属性约简。事实上，本节所提约简方法只能保持2→1 型关系对应决策蕴涵，并不是一种通用的约简方法。

4 实验和分析

本章通过实验验证基于形式概念分析的知识图谱推理方法的可行性和有效性。本文在FB15k-237数据集上选取某一关系作为决策属性，对知识图谱中缺失的关系进行补全，并与基于翻译模型的关系预测方法进行对比分析。

4.1 数据集

本例在FB15k-237数据集上进行验证，该数据集是Freebase的子集。如表6所示，本实验选用了38 001个元组构建该知识图谱对应的决策背景（具体构建方法见4.2 节），并进行决策蕴涵挖掘，随后在8 130个元组上测试所得决策蕴涵在关系预测任务中的准确性。其中，训练集含有237个关系和4 421个人物实体，测试集含有1个待预测关系和4 533个人物实体。

表6 FB15k-237实验数据Table 6 FB15k-237 experimental data

4.2 决策蕴涵挖掘及推理

通常情况下，可以根据定义12 对训练集中相应实体及其N跳范围内的邻居关系和实体构建形式背景，并视其复杂程度决定是否转化为决策背景。为了减少构建决策背景的复杂度，可以根据具体的应用场景对决策背景进行简化。以Freebase为例，首先可以通过问题分析确定决策属性，如Freebase 中“nationality”的信息缺失高达一半，为了补全该信息，以“nationality”作为决策属性(rk,3)；进一步，因为需要推理人物实体的国籍信息，所以可确定人物为头实体。基于此，可以通过以下“直接构建法”来建立决策背景。

以人物实体作为头实体h出发寻找中间实体e，按照每个实体平均包含3个关系，理论上可以找到大约1.4万个中间实体e，其对应的关系设为(ri,1)。再以e为出发点去寻找尾实体t，此时分两种情况进行讨论：若存在t与之相连，连接关系记为(rj,2)，对应(h,e,t)∈G作为决策背景的对象；若中间实体e无后续关系(rj,2)，也找不到对应尾实体t，该情况符合第3.3.2 小节中对“可约对象”和“冗余对象”的定义，即有且仅有一个条件属性时，无论其是否具有决策属性，该对象都应该被约简，因此可以不考虑该情况。

上述直接构建法可以在构建过程中对满足对象约简定义的对象直接约简，并对条件属性1和2加以区分，在实现行最简的同时实现列最简，使最终的列规模仅为原有背景的1/2。

表7 为按照上述方法构建的决策背景子图，其中各属性的含义为：1.acquire，2.executive_produce，3.education_of，4.artist_of，5.award_of，6.place_lived，7.place_of_birth，8.actor_of，9.nominate，10.nominated_for，11.produced_of，12.currency，13.has student，14.child_of，15.has artist，16.award_winner，17.sports_team_location，18.government，19.category，20.actor，21.film_subject，22.belong_to，23.capital，24.nationality。

表7 FB15k-237子集对应的决策背景Table 7 Decision context for subset of FB15k-237

对于生成的决策背景，可以使用算法1生成候选决策蕴涵，然后使用算法2生成决策蕴涵。

算法1候选决策蕴涵生成

算法1根据决策属性是否为空将所有的对象（步骤2～26）分为两个类别（步骤3～14 和步骤16～25）。若该对象k拥有决策属性（步骤3），则该对象拥有的条件属性和决策属性可能建立相应的决策蕴涵联系。为此，将该对象拥有的(ri,1) 类属性添加到attri[k]，拥有的(rj,2)类属性添加到attrj[k]。显然，对于任意的i∈attri[k]和j∈attrj[k]，可生成候选决策蕴涵(ri,1)(rj,2)→(rk,3)，因为对象k拥有条件属性(ri,1)和(rj,2)的同时也拥有决策属性(r,3)。为了方便，也可以认为对象k可生成决策蕴涵集attri[k]×attrj[k]→(r,3)。然而，这样的候选决策蕴涵并不一定成立，还需有不拥有决策蕴涵的对象进行验证。为此，对于所有不拥有决策蕴涵的对象（步骤15），算法1将其拥有的条件属性和决策属性分别保存到resti[k]和restj[k]中，然后使用算法2 对候选决策蕴涵进行排除，以生成最终的决策蕴涵。

算法2决策蕴涵挖掘

为了减少生成决策蕴涵的复杂度，算法2 首先对算法1 生成的attri、attrj和resti、restj去除重复（步骤1）；在此过程中，只有attri和attrj均重复的行才能被去除，类似地，只有resti和restj均重复的行才能被去除。显然，这种去除方式相当于去除原决策背景中的重复行，并不会对决策蕴涵的生成产生任何影响。

算法2 根据没有决策属性的对象对候选决策蕴涵进行验证，去除不成立的决策蕴涵（步骤2～11）。对于没有决策属性的对象s，若其所拥有的(ri,1)类属性resti[k]和(rj,2)类属性restj[k]与已生成的候选决策蕴涵的交集都不为空（步骤4），这表明交集内的候选决策蕴涵不成立。例如，对于含有决策属性的对象l，可生成候选决策蕴涵集attri[l]×attrj[l]→(r,3)；此时，对于不含有决策属性的对象s，可以生成条件属性集resti[s]和restj[s]，对任意的i∈resti[s]和j∈restj[s]，决策蕴涵(ri,1)(rj,2)→(r,3)均不成立；换言之，对象s否认决策蕴涵集resti[s]×resti[s]→(r,3)的成立性。因此，对象s就可以对对象l生成的候选决策蕴涵进行修正，去除不成立的候选决策蕴涵。此时，记inseti=resti[s]∩attri[l]和insetj=restj[s]∩attrj[l]分别为对象l和对象s在(ri,1)和(rj,2)两类属性上的交集，若inseti和insetj均不为空（步骤5），即使resti[s]和restj[s]可以否认决策蕴涵集resti[s]×restj[s]→(r,3)的成立性，但无法否认决策蕴涵集attri[l]inseti×attrj[l]→(r,3)和attri[l]×attrj[l]insetj→(r,3)的成立性。因此，步骤7 和步骤8 将这些候选决策蕴涵加入到attri和attrj，以便于后续检验。容易验证，所有经过检验的决策蕴涵均为决策背景上成立的决策蕴涵，因此，算法2在步骤9～16生成待挖掘的决策蕴涵。

对于表7，通过算法1和算法2可得决策蕴涵：

（1）place_of_birth∧belong_to→nationality

（2）place_of_birth∧capital→nationality

由G 转化的决策背景中挖掘到的决策蕴涵是进行知识补全的依据。以“nationality”为例，可以从知识图谱G 中拥有决策蕴涵条件属性的实体对出发，选择与决策蕴涵前件匹配的部分进行推理。例如，若某个对象同时具有条件属性“contains”（即belong_to）和“place_of_birth”，则可以为该对象补全相应的“nationality”关系。

在预测过程中，并非所有的决策蕴涵均可预测得出国家实体。以决策蕴涵place_of_birth∧belong_to→nationality为例，具有“belong_to”属性的实体对并非全部具有形式“（国家，城市）”，部分实体对还包含任意非国家和城市实体的形式“（大地点，小地点）”。因此，为了进一步提高预测的准确率，本文限制预测的尾实体必须为国家实体。

4.3 实验比较

为验证上述方法的有效性，本文与TransE[26]和TransH[27]进行了比较。

TransE[26]：文献[26]提出将多元关系数据的实体和关系嵌入到低维向量空间，使用头尾实体的向量差预测关系。然而，TransE在处理一对多和多对一等特性时效果不佳。原因是该模型在训练过程中会将同一实体对的不同关系训练为相等的关系向量。如给定三元组(h1,place_lived,USA)和(h1,nationality,USA)，经训练可能会得到rplace_lived≈rnationality，这将导致关系预测出现多个关系混淆的情况，这也是关系预测任务中排名第一为正确预测关系概率较低的原因。

TransH[27]：文献[27]提出的TransH模型是对上述TransE 模型的改进，该模型放宽了h+r=t这一严格假设，利用头尾实体在关系r对应的超平面上的投影向量差预测关系。该模型复杂度与TransE 相似，且在一定程度上解决了一对多等关系特性。

采用文献[26]和文献[27]给定的实验参数，包括随机梯度下降的学习率λ、边缘γ以及维数k，其中TransE 上的参数设置为k=50，λ=0.01，γ=1.0，TransH上的参数设置为k=100，λ=0.005，γ=0.25。

4.4 评估指标与结论

为了评价nationality 关系预测的准确性，本文设置评价指标补全率（Completion）、补全准确率（C_precision）及平均准确率（average precision）来进行评估：

对于TransE 和TransH，本文使用如下方式进行评估。给定一个待预测的三元组(h,r,w)，为了使用TransE 和TransH 进行预测，通过训练集得到h对应头实体向量h和r对应的关系向量r，并计算h和r之和得到预测的尾实体向量w1，通过选择w1与所有国家向量中距离最接近的向量作为h所对应的国籍向量n1，并比较n1对应实体n1是否等于w来进行预测，若相等，则预测正确。评估结果如表8所示。

表8 不同推理方法的关系预测性能Table 8 Relationship prediction performance of different inference methods

由表8可以看出，本文所提方法只能补全与条件属性完全匹配的三元组，因此只能补全约一半（44.6%）的缺失国籍信息。比较而言，TransE 和TransH等翻译模型可以补全所有的缺失信息；然而，这些模型在补全的准确率方面有较大缺陷，所有补全的信息中只有约1/4 的信息是正确的（TransE 为23.7%，TransH 为27.5%），而本文方法的正确率可以达到72.5%。即使同时考虑补全率和正确率，本文方法也有0.725×0.446=32.3%的平均正确率，而翻译模型只有23.7%和27.5%的正确率，这说明本文方法在关系补全上具有一定的优势。

事实上，在进行补全时，因为本文方法并没有对不符合要求的元组进行预测，所以该方法可明确区分未补全元组，方便结合其他方法进行后续补全，而翻译模型对所有元组均进行了预测，但难以明确预测正确与否，因此难以与其他补全方法进行协同补全。

5 结束语

本文提出了一种新的用于知识图谱关系预测的方法，可以高效补全知识图谱中某些缺失的关系，实验说明了该方法具有较好的推理性能。

本文方法也具有一定的局限性：首先，该方法只能对缺失的关系进行推理预测，不能补全缺失的实体；其次，由于该方法挖掘出的依赖关系较为精确，对知识图谱中的噪声不具有鲁棒性，同时也会忽略一些具有高可信度的依赖关系，不足以表达现实世界所有的语义。因此，本文一方面考虑通过引入模糊性[38-39]和鲁棒性度量[40]来提升该方法的鲁棒性；另一方面计划将该方法提取的依赖关系进行嵌入表示，并结合神经网络进行关系预测。

另外，基于本文方法的特性，可考虑将该方法应用于生物医学领域，如在以疾病和基因为节点的图谱中，常需要推理基因和疾病之间的关联。由于医学研究的严谨性，研究者更加关注精确度，这恰好可体现本文方法的优势。