01
知识图谱中的链接预测
知识图谱以形式化、规范化的方法表示知识，将知识表示为三元组(triple)进行存储。三元组包含主语（头实体）、宾语（尾实体）和二者之间的关系，通常表示为(h,r,t)，在计算机中可以用一个有向图表示。知识图谱的完整性和准确性是影响其可用性的主要因素，目前已有的知识图谱多数存在数据不完整的问题，链接预测技术能够自动知识图谱进行补全，提高知识图谱的质量，是一个非常有意义的研究问题。
上次介绍中作者对已有的链接预测方法进行梳理，重点介绍模型构建的思想，在全局层面介绍了链接预测任务的研究进展。本次介绍将聚焦于使用张量分解技术完成知识图谱链接预测任务的若干代表性工作，深入其技术细节进行讨论。
02
基于张量分解的链接预测模型基本概念
在本次介绍中，我们使用G(E,R)表示知识图谱,其中E表示实体的集合，R表示关系的集合，|E|和|R|分别表示集合E和集合R中元素的个数。(h,r,t)表示知识图谱中的三元组，其中h,t∈N,r∈E分别表示主语、关系和宾语。知识图谱中的数据被存储为三元组的形式，在任意两个实体之间，是否存在某种关系只存在两种可能，该事实成立/不成立。我们可以使用一个|E|×|E|×|R|的三维二值张量(3D binary tensor)表示一个知识图谱中的全部事实。如果我们用A表示该张量，则A_ikj=1表示第i个实体和第j个实体具有关系k，在本文中表示为(i,k,j)∈G。
基于张量分解的模型共学习三个函数：1.实体表示函数，通常将实体表示为向量；2.关系表示函数，通常将关系表示为矩阵；3.评分函数，根据实体和关系的表示得到三维二值张量中某个值的预测值。在本文中，使用EMBE作为实体表示函数，输入为该实体的id以及在三元组中所处的位置，第i个实体作为主语的表示在本文表示为EMBE(i,h)=e_(i,h)。使用EMBR作为关系表示函数，输入为该关系的id，第k个关系的表示在本文表示为EMBR(k)=M_k。使用f作为关系表示函数，输入为三元组中实体和关系的表示，输出为该三元组的预测值，A_ikj=f(e_(i,h),M_k,e_(j,t))。图1为一个基于张量分解模型的典型示意图，四个矩阵从左到右分别为：实体作为主语的embedding矩阵，关系k的embedding矩阵，实体作为宾语的embedding矩阵，三维二值张量A的一个切片A_(:k:)。
图1
除了通过实验评价一个基于张量分解的链接预测模型外，通常需要在理论上分析模型性能的上界。如果对于任意的三维二值张量A，模型都能够在某种参数设置下正确地拟合该张量而不存在任何误差，我们称模型具有完全表达能力。证明模型具有完全表达能力通常需要提供一种构造算法，通过该构造算法能够实现拟合任意的三维张量。
03
基于张量分解的链接预测模型代表性工作
1. RESCAL[1]模型年发表于2011年ICML，首先提出基于张量分解的方法对关系数据建模，完成知识图谱中链接预测的任务。对于每个实体，RASCAL模型不区分实体作为主语还是宾语，即EMBE(i,h)=EMBE(i,t)=e_i。RASCAL模型对于一个知识图谱中存在的多种关系共享实体的表示，除此之外并不显式学习任何关系间的相关性，将|E|×|E|×|R|的三维二值张量视为|R|个|E|×|E|的二维二值张量切片的简单堆叠，EMBR(k)=M_k。如果实体的embedding的维度为r，则每个关系被表示为r×r的二维矩阵，最终得到的张量分解的表达式为A_ikj=e_i^T M_k e_j。RASCAL模型的参数量为O(|E|×r |R|×r^2)。RASCAL模型具有完全表达能力，在实体和关系的表示维度r足够大的时候都能够正确的拟合该张量而不存在任何误差。一个简单的构造方法为：设置表示维度r=|E|，第i个实体的表示为e_i [i]=1， e_i [i^' ]≠1 for i^'≠i（即实体的表示构成的矩阵为单位矩阵I）。对于A_ikj=1，关系表示函数将M_k [i,j]表示为1，对于A_ikj=0，关系表示函数将M_k [i,j]表示为0（即关系k的表示M_k=A_(:k:)），显然IA_(:k:) I=A_(:k:)，即对于任意的三维二值张量A，在上述构造下RASCAL模型都可以正确地拟合。从这个构造中我们可以看出，虽然RESCAL模型在理论上具有完全的表达能力，但是由于模型没有对信息进行任何的抽取和压缩损失了泛化性，极易出现模型过拟合的现象，因此在实验中表现并不好。RASCAL模型示意图如图1所示，是最基础的基于张量分解的链接预测模型。
2. DistMult [2]模型年发表于2015年ICLR，考虑到RESCAL模型由于参数过多导致的过拟合问题，DistMult模型沿用了RESCAL模型的框架，不区分其在三元组中处于主语还是宾语的位置，获得相同的向量表示，即EMBE(i,h)=EMBE(i,t)=e_i。对关系表示函数进行修改，将关系表示为对角矩阵，EMBR(k)=Ʌ_k ，最终得到的张量分解的表达式为A_ijk=e_i^T Ʌ_k e_j。如果使用和RESCAL模型同样的embedding的维度r，DistMult将模型的参数量减少为O(|E|×r |R|×r)。虽然DistMult模型通过减少参数数量缓解了过拟合的问题，但使用对角矩阵表示关系带来了新的问题。由于对角矩阵是对称矩阵，且DistMult模型的实体表示函数在表示实体时不区分主语和宾语，因此模型只能表示对称关系，e_j^T Ʌ_k e_i=e_i^T Ʌ_k e_j。假设(i,k,j)∈G，训练中DistMult需要e_i^T Ʌ_k e_j=1，则e_j^T Ʌ_k e_i=1，(j,k,i)∈G。无论怎样设置embedding的维度r，模型都不具有完全的表现能力，这是DistMult模型结构中固有的缺陷。即使如此，DistMult模型在实验中性能仍然远超过RASCAL模型。DistMult模型示意图如图2所示，可以看到关系k的embedding矩阵只在对角线有参数。
图2
3. ComplEx [3]模型年发表于2016年ICML，考虑到DistMult模型只能解决对称关系的问题，ComplEx模型沿用了DistMult模型中关系表示函数输出为对角矩阵的限制，但是将实体和关系的向量表示从实数域拓展到复数域。修改了实体表示函数，同一个实体作为主语和宾语时的表示不同，如果用¯e表示e的共轭复数，则实体表示函数为EMBE(i,h)=e_(i,h)，EMBE(i,t)=e_(i,t)，(e_(i,h) ) ̅=e_(i,t)，关系表示函数为EMBR(k)=Ʌ_k，最终得到的张量分解的表达式为A_ikj=Re(e_(i,h)^T Ʌ_k e_(j,t))，其中Re表示最终结果取实数部分。通过使用一对共轭复数分别作为一个实体作为主语和宾语的表示，ComplEx模型不但可以表示对称关系，还可以表示反对称关系。容易证明，实体表示中的实数部分能够建模实体属性中属于对称关系的特征，虚数部分能够建模实体属性中属于反对称关系的特征。事实上，ComplEx模型也可以不使用虚数，将实数部分和虚数部分级联，同一实体在作为主语和宾语时实数部分表示相同，虚数部分表示互为相反数，并且将矩阵视为2×2的分块矩阵，每个分块矩阵都是对角矩阵，即可实现同样的效果。与DistMult模型相比，ComplEx模型的参数量在数量级上并没有变化，从实质上看，是在DistMult模型之上增加了适用于反对称关系的特征表示。同一实体在作为主语和宾语时的表示并不是相互独立的，这种依存关系对于反对称关系的表示非常有意义，其作者证明了ComplEx模型具有完全表示能力，具体构造可以参考[4]。DistMult模型示意图如图3所示，可以看到实体的表示被分为两个部分，在作为主语和宾语时一部分相同，一部分互为相反数，关系k的embedding矩阵只在为2×2的分块矩阵对角线有参数。
图3
4. SimplE [5]模型年发表于2018年NIPS，沿用了DistMult模型中关系表示函数输出为对角矩阵的限制，但是同一实体作为主语和宾语时表示不同，即EMBE(i,h)≠EMBE(i,t)。SimplE模型基于CP分解，基础的CP分解算法中实体作为主语和宾语的表示是单独学习的，二者没有相关性，这样独立学习的过程会带来一定的问题。基于此，SimplE首先为每个关系r增加一个逆关系r^(-1)，对于每一个知识图谱中存储的三元组(h,r,t)，我们都知道存在另一个对应的三元组(t,r^(-1),h)，SimplE模型通过同时优化两个三元组的预测值，同步更新同一个实体的两个表示。EMBE(i,h)=e_(i,h)，EMBE(i,t)=e_(i,t)，关系表示函数为EMBR(k)=Ʌ_k，最终得到的张量分解的表达式为A_ikj=1/2(e_(i,h)^T Ʌ_k e_(j,t) e_(j,h)^T Ʌ_(k^(-1) ) e_(i,t))。SimplE模型具有完全的表示能力，与ComplEx模型相比，SimplE中实体的两个表示并没有在数据上直接相关，而是在训练的过程中通过联合优化的方式使得其学习过程产生相关性。实验结果表明，SimplE比ComplEx在性能上的提升并不明显，因此难以直接从实验结果中得出这两种学习方式究竟哪一个更加有利于知识图谱中链接预测任务的结论。SimplE的分解方式中两个表示的关联更加自由，如果面对更复杂的场景，拥有更多的训练数据， SimplE模型在性能上可能会体现出一定的优势。但是ComplEx模型中将实体的特征分为两部分，分别表示实体属性中对称属性和反对称属性，在结果的可解释性上要略胜一筹。DistMult模型示意图如图4所示，可以看到实体主语和宾语表示并没有任何相关性，一部分互为相反数，关系k的embedding矩阵只在对角线有参数。
图4
5. 张量分析第二版电子书籍Tucker[6]模型于2019年被发表于EMNLP，与上述所有模型不同，Tucker并不将知识图谱的三维张量表示看作独立的针对每个关系的二维向量的堆叠，采用二维张量分解的方式进行处理。相反的，对于一个知识图谱中存在的多种关系，Tucker采用三维张量分解的算法直接分解为一个核张量（三维张量）和三个二维张量在其对应维度的乘积。即除了需要训练实体表示函数、关系表示函数和评分函数，Tucker模型需要训练一个针对整个知识图谱的核张量。Tucker的实体表示函数不区分实体作为主语还是宾语，即EMBE(i,h)=EMBE(i,t)=e_i，embedding尺寸为r_entity，关系表示函数为EMBR(k)=e_k，embedding尺寸为r_relation假设习得的核张量表示为W，则W尺寸为r_entity×r_entity×r_relation，最终得到的张量分解的表达式为A_ikj=W×_1 e_i ×_2 e_j ×_3 e_k，其中×_i表示在张量的第i维做矩阵乘法。通过合理设置核张量，前文所述的四个模型都可以看作Tucker模型某种特殊的实现方式，因此，Tucker模型也具有完全表示能力。从直觉上看，前文所述的模型都是直接对每一个关系学习一个二维张量表示，而Tucker模型其实可以看作学习了r_entity个二维张量基，然后每一个关系的二维张量由这些二维张量基通过线性组合而成，通过这样的操作，模型学到一些跨关系的通用模式，从而在实验中体现了更好地效果。Tucker模型示意图如图5所示，可以看到核张量本质上是一组二维张量基，关系k的embedding是该张量基下的一个组合参数，首先得到关系k的embedding矩阵，后续操作同最初的RASCAL模型。
图5
上述五个模型的总结如表1所示：
表1 基于张量分解的链接预测模型总结
04
总结
本文较为细致地分析了基于张量分解完成知识图谱中链接预测任务的五个模型，按照时间顺序进行介绍。经验性的结论为，好的模型必须在理论上具有较强的表达能力，但在训练中应该增加合适的约束，引导模型学习跨样本的通用的知识而非针对每个样本去拟合其独有的性质。
