Knowledge Graph Embedding: A Sur

• KG embedding研究的出发点：KG的表示一般基于三元组（head entity, relation, tail entity），尽管能够有效的表示结构化数据，但是底层的本质上是符号表示，使得KG很难操作; KG embedding将KG中的成分映射到一个连续的矢量空间中，不仅保留KG中的固有结构，同时简化了处理

• KG embedding研究主要分为两个阶段：

  • 阶段1：仅利用KG中的fact构建embedding, embedding只需要和每个单独fact匹配，对下游的一些任务not predictive enough

  • 阶段2：在阶段1的基础上，利用更多的信息形式，e.g.实体类型（entity type）、关系路径(relation path)、文本描述(textual description)、逻辑规则(logical rules)，得到more predictive embeddings

• 只基于facts的KG embedding 构建由3步组成：

  • step1: 表示entities和relations:

    • entity表示形式：

       *   矢量
      
       *   考虑entity的不确定性，利用多元高斯分布对entity进行建模
      

    • relation常被看成在矢量空间中的操作，表示形式：

       *   矢量
      
       *   矩阵
      
       *   张量
      
       *   多元高斯分布
      
       *   混合高斯（mixtures of Gaussians）
      

  • step2: 定义第一个打分函数

    • 每个fact(h,r,t)均对应一个score func f_r(h, t)，在KG中观察到的facts得分高于未观察到的，根据score function定义方式不同，这种只基于facts的KG embedding技术可被分为以下两类：

      • translational distance models：使用基于距离的score func【目标优化函数】，这些模型均包含约束（e.g.强制vector embedding至少L2范数），这些约束在优化问题中被转化为正则项【正则项】

        • TransE及其扩展，实体/关系都是矢量空间中确定的点

          *   TransE：
          
              *   简单高效，通过学习分布式的词表示来捕捉语言规律，e.g.JamesCameron + DirectorOf ≈ Avatar
          
              *   处理一对多，多对一，多对多关系时有问题，e.g.一对多为例，AlfredHitchcock + DirectorOf ≈Psycho，Rebecca，RearWindow，一个导演对应多部电影，虽然这些电影属于不同实体，但是学到的矢量表示都是非常相似的，这是有问题的
          
          *   TransE改进策略：
          
              *   引入 Relation-Specific Entity Embeddings:
          
                  *   TransH：
          
                      *   改进TransE：引入 Relation-Specific Entity Embeddings，允许实体在不同的关系中有明显不同的表示。e.g.即使Psycho，Rebecca，RearWindow在给定DirectorOf 关系时，表示很相似，但给定其他关系时，表示可能相差很大
          
                      *   引入relation-specific超平面，每个关系r用矢量r表示，在一个以w_r为法向量的超平面上，实体h,t投射到该超平面上
          
                  *   TransR：
          
                      *   引入relation-specific 空间，而不是超平面；实体表示为实体空间的向量，每个关系关联到另外的关系空间，定义投影矩阵M_r（实体空间到关系空间）
          
                      *   每个关系都需要引入投影矩阵，不如TransE,TransH简单高效
          
                  *   TransD:
          
                      *   简化TransR,比TransR更高效。将投影矩阵分解为两个矢量乘积，引入额外的映射向量w_h，w_t, w_r
          
                  *   TranSparse:
          
                      *   简化TransR,强制投影矩阵的稀疏性
          
              *   relaxing translational requirement:放松h+r≈t的限制
          
                  *   TransM: 每个事实（三元组）关联一个权重，通过降低一对多，多对一，多对多关系的权重，TransM允许t在这些关系中远离h+r
          
                  *   ManifoldE: 放松约束关系，t约束在以h+r为质心，权重值为半径的超球体中
          
                  *   TransF: 放松约束关系，t约束在与h+r为同向即可
          
                  *   TransA: 为每个关系r引入对称非负矩阵，使用自适应Mahalanobis距离定义score
          

        • Gaussian Embeddings，实体/关系被看做随机变量

          *   KG2E：将实体和关系表示成从多元高斯分布中提取的随机向量
          
              *   使用 Kull-back-Leibler散度计算得分
          
              *   使用概率内积计算得分
          
          *   TransG: 实体h,t利用高斯分布建模，关系r认为可能有多重语义信息，被表示为混合高斯分布
          

        • 其他距离模型：

          *   UM(unstructured model)
          
              *   TransE的简化版本，令r = 0
          
              *   不能区分不同的关系
          
          *   SE(structured embedding):
          
              *   对每个关系r，使用两个不同的投影矩阵，分别用于head entity, tail entity
          

      • semantic matching models: 使用基于相似度的score func，通过匹配实体、关系见的潜在语义来衡量事实的合理性

        • RESCAL及其扩展

          *   RESCAL:
          
              *   也叫双线性模型，将实体h,t与一个vector关联来捕捉潜在语义，关系r与一个matrix关联来建模latent factors间的两两交互
          
              *   其score func捕捉到了所有h,t所有成分间的两两交互
          
          *   TATEC:
          
              *   不仅建模了h,r,t间3者交互，还定义了h,r/t,r间2者交互
          
          *   DisMult
          
              *   简化了RESCAL，将矩阵Mr限制为对角阵
          
              *   其score func捕捉到了h,t中相同维度上成分间的两两交互，减少了每个关系r所有的参数数量
          
              *   模型过于简单【对角矩阵使得实体可交换】，只能处理对称关系，对于一般的KG功能不够强大
          
          *   HolE(Holographic Embeddings)全息嵌入：
          
              *   将RESCAL的表现力与DisMult的简洁高效结合
          
              *   将实体、关系均表示为vector，进行Circular correlation，对pairwise interactions进行压缩，减少了每个关系r所有的参数数量，比RESCAL高效；且Circular correlation不能交换，可以像RESCAL一样，对非对称关系进行建模
          
          *   ComplEx(Complex Embeddings)复数嵌入：
          
              *   对DisMult的扩展，引入复数嵌入，可以更好建模非对称关系
          
              *   h，r，t不再依赖实数空间，而是依赖复数空间，非对称关系最终得到的事实会得到不同的score，这依赖相关实体对应的orders、
          
              *   共轭对称施加在embeddings时，HolE被视为ComplEx的一种特殊情况
          
          *   ANALOGY:
          
              *   扩展RESCAL，进一步对实体、关系中相似的属性建模
          
              *   已被证明DisMult、HolE、ComplEx均属于ANALOGY的一种特殊情况
          

        • 利用神经网络进行匹配

          *   SME: Semantic Matching Energy，
          
              *   在Input layer: 将fact三要素h,r,t映射为vector embeddings
          
              *   在Hidden layer：将关系r与head entity h结合得到g_u(h,r);将关系r与tail entity h结合得到g_v(r, t)
          
              *   score定义为g_u,g_v的点积
          
              *   根据g_u,g_v的形式不同，SME有两个版本：
          
                  *   SME(linear):
          
                  *   SME(bilinear)
          
          *   NTN: neural tensor network:
          
              *   在Input layer: 将fact三要素h,r,t映射为vector embeddings
          
              *   在Hidden layer：将h，t，和二者与特定关系张量Mr结合三者映射到一个非线性hidden layer
          
          *   SLM:single layer model：
          
              *   NTN的简化形式，将h，t对应的权重矩阵，bias置零，只保留NTN中的最后一个要素
          
          *   MLP: multi-lalyer perceptron：
          
              *   h，r，t均映射为单vector
          
              *   在Input layer上将三者拼接，映射到非线性hidden layers
          
          *   NAM:neural association model:（多隐层，其他都是单隐层）
          
              *   在Input layer: 将fact中h,r映射为vector embeddings后进行拼接，经过多隐层（激活函数：Relu）和t生成的embeddings乘积得到score
          

      • 模型的训练:

        • 一些先验知识：http://www.sohu.com/a/144575100_464088

          *   封闭世界假设(Closed World Assumption, CWA)
          
                *   即如果我们在知识库中推不出来P或P的否定，就把P的否定加入知识库。有两种情况, CWA很有用. 一是可以当假设知识库中的知识是完全的时候. 例如, 在数据库中, 如果学生表中没有Peter, 则认为Peter不是学生. 二是当知道知识库的知识是不完全的, 如不足于回答一些问题, 但我们必须在不完全知识的情况下做出决定, 这时候CWA就有用了
          
          *   开放世界假设(Open World Assumption, OWA)
          
                *   对推不出来的命题就很诚实地当作不知道这个命题的正确与否, 这样的后果就是知识库中能推导出来的结论大大减少
          
          *   在语义Web环境下, 因为Web的开放性, 相关的知识很可能分布在Web上不同的场所, 因此在语义Web上推理, 用CWA是很不恰当的. 例如, 如果在一个知识库中只说了hasFriend(Peter, Tom), 如果采用CWA, 就会得到结论: Peter只有一个朋友. 这当然是不合理的, 因为很可能在别的地方说了Peter还有其他的朋友. 所以, 如果要在语义Web中聚集不同来源的知识, 应该采用OWA. (有一种中庸之道: 局部封闭世界(Local Closed World), 这里不多说). 描述逻辑中的推理刚好是采用OWA的, 所以它的确适合作为语义Web的逻辑基础
          

        • 目标函数：

          *   logistic loss最小化
          
                  *   优势：对一些复杂的关系模式（如transitive relations）得到一些紧凑的表达方式
          
          *   pairwise ranking loss最小化
          
                  *   优势：不假设负样本一定是(命题)错误的，只是和正样本相比可能性小，使得positive facts得分要尽可能高于negative ones
          
          *   以上的目标函数中均包含约束项/正则项【不同的embedding模型不同】，已证明：logistic loss+semantic matching models（DisMult、ComplEx等）性能更好；pairwise ranking loss+translational distance models（TransE）性能更好
          
          *   优化方法：SGD+minibatch
          

  • step3: 学习entities和relations的表示

    • 解决对所有观测facts的合理性最大化(maximize plausibility)的最优化问题

【未完待续...】