TransE

桃扇骨 2022-10-14 05:28 8阅读 0赞

网络上已经存在了大量知识库（KBs），比如OpenCyc，WordNet，Freebase，Dbpedia等等。这些知识库是为了各种各样的目的建立的，因此很难用到其他系统上面。为了发挥知识库的图（graph）性，也为了得到统计学习（包括机器学习和深度学习）的优势，我们需要将知识库嵌入（embedding）到一个低维空间里（比如10、20、50维）。我们都知道，获得了向量后，就可以运用各种数学工具进行分析。深度学习的输入也是向量。（考虑一下，word2vec，我们训练出一个向量后，可以做好多事情，深度学习的输入也往往是一个矩阵。

TransE的直观含义，就是TransE基于实体和关系的分布式向量表示，将每个三元组实例（head，relation，tail）中的关系relation看做从实体head到实体tail的翻译。通过不断调整h、r和t（head、relation和tail的向量），使（h + r） 尽可能与 t 相等，即 h + r = t。

以前有很多种训练三元组的方法，但是参数过多，以至于模型过于复杂难以理解（作者表达的意思就是，我们的工作效果和你们一样，但我们的简单易扩展）。（ps：作者以前也做过类似的工作，叫做Structured Embeddings，简称SE，只是将实体转为向量，关系是一个矩阵，利用矩阵的不可逆性反映关系的不可逆性。距离表达公式是1-norm）。也就是：  
 d ( h , r , t ) = ∥ h + r − t ∥ 2 2 d(h,r,t) = \\left \\| h+r-t \\right \\|\_2^2 d(h,r,t)=∥h\+r−t∥22

# TransE的训练 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]  
这里注意，entity需要在每次更新前进行归一化，这是通过人为增加embedding的norm来防止Loss在训练过程中极小化。

TransE的Loss function (Hinge Loss Function) 为:  
 L = ∑ ( h , l , t ) ∈ S ∑ ( h ′ , l , t ′ ) ∈ S ′ ( h , l , t ) \[ γ + d ( h + l , t ) − d ( h ′ + l , t ′ ) \] + \\mathcal\{L\} = \\sum\_\{(h,l,t) \\in S \}\\sum\_\{(h^\\prime,l,t^\\prime) \\in S^\\prime(h,l,t)\} \[\\gamma + d(h+l, t)-d(h^\\prime+l, t^\\prime)\]\_+ L=(h,l,t)∈S∑(h′,l,t′)∈S′(h,l,t)∑\[γ\+d(h\+l,t)−d(h′\+l,t′)\]\+  
其中 \[ x \] + \[x\]\_+ \[x\]\+表示x最小值为0, 即 \[ x \] + = m a x ( 0 , x ) \[x\]\_+=max(0,x) \[x\]\+=max(0,x)， S ′ S^\\prime S′表示负例的集合。

直观上，我们要前面的项（原三元组）变小（positive），后面的项（打碎的三元组corrupt triple）变大（negative）。就跟喂小狗一样，它做对了，就给骨头吃；做错了，就打两下。前面的项是对的（来自于训练集），后面的项是错的（我们随机生成的）。不同时打碎主体和客体，随机挑选一个打碎，另一个保持不变，这样才能够有对照性。

> 合页损失函数(hinge loss function)，这种训练方法叫做margin-based ranking criterion。是不是听起来很熟悉？对的，就是来自SVM。支持向量机也是如此，要将正和负尽可能分开，找出最大距离的支持向量。同理，TransE也是如此，我们尽可能将对的和错的分开。margin值一般设为1了

L 2 L\_2 L2范数形式如下：  
 ∣ ∣ x ∣ ∣ 2 = ( ∣ x 1 ∣ 2 + ∣ x 2 ∣ 2 + . . . + ∣ x n ∣ 2 ) ||x||\_2=\\sqrt\{(|x\_1|^2+|x\_2|^2+...+|x\_n|^2)\} ∣∣x∣∣2=(∣x1∣2\+∣x2∣2\+...\+∣xn∣2)

因此以 n o r m = L 2 norm = L2 norm=L2范数为例，求解正确三元组的 h h h的相对于hinge loss function的梯度：  
 ∂ l o s s ∂ h = ∂ \[ γ + ( h + r − t ) 2 − ( h ′ + r − t ′ ) 2 \] ∂ h = \{ 2 ( h + r − t ) , i f γ + ( h + r − t ) 2 − ( h ′ + r − t ′ ) 2 ≥ 0 0 , i f γ + ( h + r − t ) 2 − ( h ′ + r − t ′ ) 2 < 0 \\frac\{\\partial loss\}\{\\partial h\}= \\frac \{\\partial \[\\gamma + (h+r-t)^2- (h^\\prime + r -t^\\prime)^2\]\}\{\\partial h\}= \\begin\{cases\} 2(h+r-t) , if \\gamma + (h+r-t)^2- (h^\\prime + r -t^\\prime)^2 \\ge 0 \\\\ 0, if \\gamma + (h+r-t)^2- (h^\\prime + r -t^\\prime)^2 < 0 \\end\{cases\} ∂h∂loss=∂h∂\[γ\+(h\+r−t)2−(h′\+r−t′)2\]=\{ 2(h\+r−t),ifγ\+(h\+r−t)2−(h′\+r−t′)2≥00,ifγ\+(h\+r−t)2−(h′\+r−t′)2<0

L 1 L\_1 L1范数形式如下：

∣ ∣ x ∣ ∣ 1 = ∣ x 1 ∣ + ∣ x 2 ∣ + . . . + ∣ x n ∣ ||x||\_1=|x\_1|+|x\_2|+...+|x\_n| ∣∣x∣∣1=∣x1∣\+∣x2∣\+...\+∣xn∣

而L1范数的梯度则以\[1,1,-1,1…\]形式出现。

对于模型中Margin的个人理解如下：margin 的作用相当于是一个正确triple与错误triple之前的间隔修正，margin越大，则两个triple之前被修正的间隔就越大，则对于词向量的修正就越严格。

开始阅读论文的时候在纠结一个问题，”这个模型的参数是什么？如何更新？“。后来通过读原文发现其实文章后续中有说明，第3章提到了参数的总量为 O ( n e k + n r k ) O(n\_ek+n\_rk) O(nek\+nrk)，也就是说Loss更新的参数，是所有entities和relations的Embedding数据，每一次SGD更新的参数就是一个Batch中所有embedding的值。TransE里面SGD和一般机器学习方法或者深度学习中SGD中的参数还是有些区别的。

> 关于参数的更新：我们使用的是随机梯度下降（Stochastic Gradient Descent，SGD）训练方法。SGD不用对所有的和求梯度，而是对一个batch求梯度之后就立即更新theta值。  
>   
> 对于数据集大的情况下，有速度。但是每一次更新都是针对这一个batch里的三元组的向量更新的，也就是意味着，一次更新最多更新(3+2)\*batch\_size\*d 个参数（设一个batch的长度为batch\_size）。并不是把所有的theta值都更新了， 或者说不用更新整个（ |E| + |R| ） \* d 矩阵，只需要更新sample里抽出来的batch里的向量即可。为什么可以这样呢（也就是为什么可以不用把参数全更新了，而是只更新一部分）？因为参数之间并没有依赖（或者说冲突conflict），对于此，可以参考论文 Hogwild!: A Lock-Free Approach to Parallelizing Stochastic。

另外，距离公式 d ( h + r − t ) d(h+r-t) d(h\+r−t)可以取 L 1 L\_1 L1或者 L 2 L\_2 L2范数，对于 L 1 L\_1 L1范数， d d d是求绝对值结果 d ( h + r , t ) = ∣ h + r − t ∣ d(h+r,t)=|h+r-t| d(h\+r,t)=∣h\+r−t∣；而对于 L 2 L\_2 L2范数， d ( h + r , t ) = ( h + r − t ) 2 d(h+r,t)=(h+r-t)^2 d(h\+r,t)=(h\+r−t)2。其中要注意的是， L 1 L\_1 L1范数在 x = 0 x=0 x=0处不可导，所以需要使用次微分概念。另一方面，Loss function 希望达到的理想情况是，正确的triple的 d ( h + r , t ) d(h+r,t) d(h\+r,t)尽可能小， 而错误triple的 d ( h ′ + r , t ′ ) d(h^\\prime+r, t^\\prime) d(h′\+r,t′)尽可能大，这样才能让总体的 l o s s loss loss趋向于0。因此，在SDG的update过程中，正例中 h h h和 r r r逐渐减小，但 t t t要逐渐增大；反例中 h ′ h^\\prime h′和 r r r要增大，但 t ′ t^\\prime t′要减小。

测试环节中，可将测试集分为Raw及Filter两种情况，Filter是指过滤corrupted triplets中在training， validation，test三个数据集中出现的正确的三元组。这是因为只是图谱中存在1对N的情况，当在测试一个三元组的时，用其他实体去替换头实体或者尾实体，这个新生成的反例corrupted triple确可能是一个正确triple，因此当遇见这种情况时，将这个triple从测试中过滤掉，从而得到Filter测试结果。

归一化公式的分母是向量的平方和再开方；而对于距离公式，是向量的平方和（没有开方）。公式的错误书写，会引起收敛的失败。

对于每一次迭代，每一次的归一化约束（constraint）实体长度为1（减少任意度量（scaling freedoms（SE）），使得收敛有效（避免 trivially minimize（transE）），但对关系不做此要求。（然而我自己试验的结果是，归一化关系，会使精度加大和收敛加强）

# 代码设计 #

有一点需要注意，在进行Corrupted\_triple的entity替换中时，最开始的设想是保证替换后的triple不能是原有triple\_List中任意一个。这个设计思路并没有错，但在在代码实现过程中会导致代码的运行速度变得奇慢无比。这是因为，FB15k数据集中有超过48万个Triple，每次都要遍历整个List，在对大数据集进行训练时，这个环节会消耗大量的资源，因此在效率和性能中间进行平衡，最终放弃了这个步骤。

另一方面，通过SGD更新词向量时，会同时更新Correct triple和Corrupted triple。这两个triple中其实只有一个实体不同，因此另一个实体就需要更新两次，需要使用同一个，不然后一次更新的结果会将前一次的更新结果覆盖掉。下面是关于SGD 参数更新的代码：

correct_copy_head -= self.learning_rate * correct_gradient
    relation_copy -= self.learning_rate * correct_gradient
    correct_copy_tail -= -1 * self.learning_rate * correct_gradient
    
    relation_copy -= -1 * self.learning_rate * corrupted_gradient
    if correct_sample[0] == corrupted_sample[0]:
          # if corrupted_triples replaces the tail entity, the head entity's embedding need to be updated twice
          correct_copy_head -= -1 * self.learning_rate * corrupted_gradient
          corrupted_copy_tail -= self.learning_rate * corrupted_gradient
    elif correct_sample[1] == corrupted_sample[1]:
          # if corrupted_triples replaces the head entity, the tail entity's embedding need to be updated twice
          corrupted_copy_head -= -1 * self.learning_rate * corrupted_gradient
          correct_copy_tail -= self.learning_rate * corrupted_gradient
    
    # normalising these new embedding vector, instead of normalising all the embedding together
    copy_entity[correct_sample[0]] = self.normalization(correct_copy_head)
    copy_entity[correct_sample[1]] = self.normalization(correct_copy_tail)
    if correct_sample[0] == corrupted_sample[0]:
         # if corrupted_triples replace the tail entity, update the tail entity's embedding
         copy_entity[corrupted_sample[1]] = self.normalization(corrupted_copy_tail)
    elif correct_sample[1] == corrupted_sample[1]:
         # if corrupted_triples replace the head entity, update the head entity's embedding
         copy_entity[corrupted_sample[0]] = self.normalization(corrupted_copy_head)
    # the paper mentions that the relation's embedding doesn't need to be normalised
    copy_relation[correct_sample[2]] = relation_copy

对FB15k数据集进行100个epoch的训练，超参数设置为dimension = 50， margin = 1.0， norm = L1，总耗时约为2小时， 模型后期训练一次epoch的total loss稳定在14000左右。

# 指标 #

## Mean rank ##

对于测试集的每个三元组，以预测`tail`实体为例，我们将 ( h , r , t ) (h,r,t) (h,r,t)中的t用知识图谱中的每个实体来代替，然后通过 d i s t a n c e ( h , r , t ) distance(h, r, t) distance(h,r,t)函数来计算距离，这样我们可以得到一系列的距离，之后按照升序将这些分数排列。

d i s t a n c e ( h , r , t ) distance(h, r, t) distance(h,r,t)函数值是越小越好，那么在上个排列中，排的越前越好。

现在重点来了，我们去看每个三元组中正确答案也就是真实的t到底能在上述序列中排多少位，比如说t1排100，t2排200，t3排60…，之后对这些排名求平均，mean rank就得到了。

## Hit@10 ##

还是按照上述进行函数值排列，然后去看每个三元组正确答案是否排在序列的前十，如果在的话就计数+1

最终 排在前十的个数/总个数 就是Hit@10

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]

# 结论 #

经过transE建模后，在测试集的13584个实体，961个关系的 59071个三元组中，测试结果如下：

mean rank: 353.06935721419984
    hit@3: 0.12181950534103028
    hit@10: 0.2754989758087725

一方面可以看出训练后的结果是有效的，但不是十分优秀，可能与transE模型的局限性有关，transE只能处理一对一的关系，不适合一对多/多对一关系。

虽然TransE模型的参数较少，计算的复杂度显著降低，并且在大规模稀疏知识库上也同样具有较好的性能与可扩展性。但是TransE 模型不能用在处理复杂关系上 ，原因如下：以一对多为例，对于给定的事实，以姜文拍的民国三部曲电影为例，即《让子弹飞》、《一步之遥》和《邪不压正》。可以得到三个事实三元组即（姜文，导演，让子弹飞）、（姜文，导演，一步之遥）和（姜文，导演，邪不压正）。按照上面对于TransE模型的介绍，可以得到，让子弹飞≈一步之遥≈邪不压正，但实际上这三部电影是不同的实体，应该用不同的向量来表示。多对一和多对多也类似。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]: /images/20221014/e1c7bc7bc526438f97619e0f1c7a7e09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]: /images/20221014/b9cc72da9c804028b0ac649fff6638dc.png