参考文献

论文：Translating Embeddings for Modeling Multi-relational Data

作者：Bordes A, Usunier N, Garcíadurán A, et al.

来源：International Conference on Neural Information Processing Systems. 2013.

背景介绍

近年来，知识图谱的构建和应用得到了迅速的发展。常用的知识图谱有FreeBase、DBpedia、OpenCyc和YAGO等，而且各大搜索引擎如百度、谷歌等都拥有自己的知识图谱。目前知识图谱广泛应用于多种实际场景，如：命名实体、语义解析、消歧、信息提取和问答等。知识图谱中的每条边都表示为（头实体，关系，尾实体）的形式，表示两个实体通过特定的关系连接在一起。这种结构虽然在表示结构化数据方面很有效，但是三元组的底层符号特性给知识图谱的操作带来困难。因此知识图谱嵌入（Knowledge Graph Embedding）就应运而生。知识图谱嵌入的关键思想是将知识图谱中的知识表示到连续的低维向量空间中，同时保留原有的结构，从而达到简化计算的目标。

KG Embedding

KG Embedding的应用：

在知识图谱内可以用于链接预测、三元组分类、实体分类和实体解析等方面。而将该方法扩展到其他领域可以解决关系抽取、问答和推荐系统等方面的问题。

KG Embedding的一般步骤：

1.     表示图中的实体和关系

2.     定义一个打分函数

3.     学习实体和关系的向量表示

KG Embedding技术根据打分函数的不同大致可以分为两类：平移距离模型和语义匹配模型。前者使用基于距离的评分函数，后者使用基于相似度的评分函数。

本篇论文所引出的算法就是以距离为评分函数所设计的算法。

图1 KG Embedding常用的方法

TransE算法

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

图2  TransE算法的向量表示

算法将打分函数定义为h+r和t在空间之中的距离：

在训练过程中将损失函数定义为：

其中γ是超参数，表示负样本的分数比正样本的分数高γ，S是以三元组形式存储的知识的集合，即正样本。E是实体的集合。S'是负样本。其包含的样本如下公式。

根据损失函数可以看出，训练模型需要满足原三元组的距离d(h+r,t)尽可能小，而用来做负样本的三元组的距离d(h'+r,t')尽可能大，使得模型的损失函数的值尽可能小，从而达到很好的表示知识的目的。在构建负样本并没有同时打乱头实体和尾实体，而是采取了控制变量的方法，保持一个不变，随机改变另外一个，保持对照性。

损失函数后的下角标+表示该损失函数为合页损失函数，当L值大于0时取原值，小于等于0时则为0。

这种训练方法叫做margin-based ranking criterion。目标是将对的三元组和错误的三元组尽可能分开。

图3  TransE算法流程

实验部分

为了验证算法的可行性，在论文中进行了对比实验。

数据集：

实验采取的数据集是wordnet和freebase。

Wordnet 这个知识库用于产生直觉上可用的字典和辞典，并且支持自动文本分析。它的实体对应着词义，关系定义它们之间的词汇关系。元组的样例为(score NN 1, hypernym, evaluation NN 1)或者(score NN 2, has part, musical notation NN 1)。

Freebase是一个很大并且不断增长的知识库；目前有大约12亿的三元组和超过8千万的实体。在论文中通过Freebase构建出两个训练集。首先通过选择在维基百科中出现并且在freebase中出现至少一百次（包含实体和关系）的实体，同时移除了仅仅互换了头实体和尾实体的关系，最终构建出一个含有14951个实体，1345个关系，以及592213个三元组的相对较小的数据集。其次选择出最频繁出现的一百万个实体构建出一个大的数据集，这个数据集大约有25K的关系和170万个训练元组。

评价方案：

对每个测试元组，移除头实体或者用字典中的每个实体轮流替换。首先通过模型计算这些错误元组的相似性（或者能量），然后按升序排列；最后，存储正确的实体排名。重复这个过程，把移去头部用移去尾部代替。报告这些预测排名的平均值和hits@10，也就是，排在前10的正确实体的比例。

对比实验：

在实验过程中对比了其他算法如RESCAL、SE、SME（线性）、SME（非线性）和LFM。感兴趣的可以搜索相关论文了解这些算法。

实现：

关于TransE的实验，对于随机梯度下降的学习率λ从{0.001,0.01,0.1}中选择，边际值γ从{1,2,10}中选择，k从{20,50}中选择。相似性度量d根据验证的性能选择L1选择L2。优化配置为：在Wordnet上k=20，λ=0.01，γ=1，d=L1；在FB15k上，k=50，λ=0.01，γ=1，d=L1；在FB1M上，k=50，λ=0.01，γ=1，d=L2。对所有的训练集，训练时间最多为1000次。通过验证集（原始数据）上的平均排名来选取最好的模型。

实验结果

链接预测：

表1  链接预测结果

从表中可以看出论文中给出的算法TransE在各个数据集上的表现都要好于其他算法。

关系聚类的详细结果：

表2  关系聚类结果

该表展示了在FB15k上依据关系的几种类别的分类结果，并依此对几种方法进行预测。根据头和尾的基数参数把关系分为4类：1-1，1-多，多-1，多-多。如果一个头部至多对应一个尾部，那么它们的关系是1-1，如果一个头部对应多个尾部，那么它们的关系是1-多，如果很多头部对应同一个尾部，那么它们的关系是多-1，如果多个头部对应多个尾部，那么它们是多-多关系。给定一个序对（l，t），计算头部h出现在FB15k数据集上的平均数。如果这个平均数小于1.5就被标记为1-多等等。例如，每个尾部平均有1.2个实体并且每个头部平均有3.2个尾部的关系被分类为1-多。在FB15k上有26.2%的1-1关系，22.7%的1-多关系，28.3%的多-1关系和22.8%的多-多关系。

TransE在FB15k测试集上的样例预测：

为了说明模型在预测方面的能力，论文中做了下面这个实验：给定一个头实体和一个标签，预测尾实体。这些样例来自FB15k的测试集。即使排在最高位的不总是最好的答案，但这个预测也反映了一般的常识。实验结果在下表展示。

表3  TransE预测尾实体结果

总结

这篇论文提出了一种新的学习知识库嵌入的方法，通过优化模型的参数来表示层次关系。论文通过与其他已有的算法在两个不同且规模很大的知识库上进行的对比实验，证明了该模型的可行性，同时相对于其他算法，该算法拥有更好的表现。

关于 天 方 夜 “谈”

天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。

方班人有自己的浪漫，

我们探讨知识，谈论理想，

采摘科研的繁星，

脚下是星辰大海。

天：代表我们的理想犹如天空般浩荡

方：代表方班

夜：代表代码人的冷静与静谧

谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”