translating-embeddings-for-modeling-multi-relational-data
转换嵌入以建模多关系数据
今天来看一篇有关知识图谱嵌入的文章，Translating Embeddings for Modeling Multi-relational Data，文章的链接见这里。
这是一篇发表在NIPS2013的文章，标题这么长，其实就是非常著名的用于进行知识图谱嵌入的transE模型，单篇文章的被引量已经超过了两千。大佬的方法总是简洁有效，接下来几句让我们一起学习一下这个知道之后觉得每个人都能想到但是只有人家想到的方法。
要解决什么问题？
在定义问题之前，我们先来了解一些前置的知识，以便我们能对问题有一个更好的理解。
预置知识：知识图谱嵌入
这里先介绍一下知识图谱嵌入是什么。对于嵌入这个词，在自然语言处理方面可能应用比较多，其本身的含义就是将一组词中的每一个词都映射到一个定长的向量，同时保证得到的每个向量都互不相同，并且具有相近语义的词汇对应的向量具有较小的距离。所以从直观上来看就是用向量来表示词汇了。进一步地，对于知识图谱，这个嵌入就是要将知识图谱中出现的实体和关系进行嵌入，众所周知，RDF格式的知识图谱的基本数据单元为\((h,l,t)\)，也就是头实体、关系和尾实体。
预置知识：多关系数据
其实就是一个知识图谱，有向图，按照存储边的形式存储数据，并且每条边的表示形式为\((h,l,t)\)，其中\(l\)指的就是这个边的\(label\)。
预置知识：score 函数
定义一个函数\(s(h,l,t)\)，这个函数将一个三元组映射到一个数值，用来描述该三元组属于这个知识图谱的置信度，关于函数的具体形式会在后面给出，对于这个置信度我们称之为该三元组的分数，这个分数一般是越小越好。
预置知识：衡量指标
其实训练起来很简单，只是这个衡量的过程有点麻烦，为了更加清楚地解释问题，让我们先进行一些定义。有一个知识图谱 \(\mathcal{G} = \{(h,l,t)\ \ w.r.t.\ h,t \in \mathcal{E}, l \in \mathcal{R}\}\) ，其中\(\mathcal{E},\mathcal{R}\)分别是该知识图谱的所有实体和关系的集合。用黑体的\((\boldsymbol{h},\boldsymbol{l},\boldsymbol{t})\)表示嵌入后的三元组，也就是这里的黑体都代表一个向量。
对于一个特定的三元组\((\boldsymbol{h_0},\boldsymbol{l_0},\boldsymbol{t_0})\)，我们用所有的\(e \in \mathcal{E}\)，替换这个三元组中的头实体，得到 \(|\mathcal{E} - 1|\)个新的三元组，将这\(|\mathcal{E} - 1|\)个三元组和\((h_0,l_0,t_0)\)共同组成一个新的知识图谱\(\mathcal{G}_{h\sim (h_0,l_0,t_0)}\)。对于这个新的知识图谱中的所有三元组，我们认为只有一个是真正应该属于知识图谱的，那就是\((h_0,l_0,t_0)\)，而其它的都是错误的三元组。
明确了这一点之后，我们应用score function对\(\mathcal{G}_{h\sim (h_0,l_0,t_0)}\)中的所有三元组求分数，按照这个分数对三元组从小到大排序。然后我们对所有的正确的三元组都进行这样的操作，于是每个三元组都有了一个排名\(rank_{head\sim}(h,l,t)\)，同样的道理如果替换尾实体排名就用\(rank_{tail\sim}(h,l,t)\)表示，\((h_0,l_0,t_0)\)的排名越考前越好
为了衡量这个事情，我们引入衡量指标：平均排名（MR），平均倒数排名（MRR），hit指标。具体见公式 \[ MR = \frac{\sum_{(h,l,t) \in \mathcal{G} }\{rank_{head\sim}(h,l,t) + rank_{tail\sim}(h,l,t)\} }{2 * |\mathcal{G}|}\\ MRR = \frac{\sum_{(h,l,t) \in \mathcal{G} }\{\frac{1}{rank_{head\sim}(h,l,t)} + \frac{1}{rank_{tail\sim}(h,l,t)}\} }{2 * |\mathcal{G}|}\\ HIT@n = \frac{\sum_{(h,l,t) \in \mathcal{G} \wedge rank_{head\sim}(h,l,t) \leq n}\{1\} + \sum_{(h,l,t) \in \mathcal{G} \wedge rank_{tail\sim}(h,l,t) \leq n}\{1\} }{2 * |\mathcal{G}|} \] 有了前面的这些预置知识，我们就可以非常方便地定义问题的目标了，就是使\(MR\)更小，\(MRR\)更大，\(HIT@n\)更大。结束了上面的描述，要完成这个衡量的过程，还需要解决两个问题，一个是如何构建每个实体和关系的嵌入，另一个是定义score function，这也正式解决知识图谱嵌入的问题的关键。下面，我们就会在方法论中对这个问题进行讲解。
方法论
整个论文中的方法论只有不到一页，简洁有效，再赞一个！！
我们将实体和关系嵌入为\(k\)维向量，同时满足\(\boldsymbol{h}+\boldsymbol{l}\approx\boldsymbol{t}\)，\(\boldsymbol{t}\)应该是\(\boldsymbol{h}+\boldsymbol{l}\)最近的向量，否则越远越好。这个远近就用欧式距离或者曼哈顿距离\(d(\boldsymbol{h}+\boldsymbol{l},\boldsymbol{t})\)来衡量。于是乎，模型的优化目标，损失函数，还有之前提到的score function都解决了。其中，损失函数如下所示，其中\([x]_+\)代表一个实数的正数部分，也就是说如果是负数的话，就用0代替，\(\gamma\)是超参数，有了这个损失函数就用梯度下降法解就可以了： \[
\mathcal{L} = \sum_{(h,l,t) \in \mathcal{G} }{\sum_{(h',l,t') \in \mathcal{G}'_{(h,l,t)} }{[\gamma+d(\boldsymbol{h}+\boldsymbol{l},\boldsymbol{t}) - d(\boldsymbol{h'}+\boldsymbol{l},\boldsymbol{t'})]_+} }\\
w.r.t.\ \mathcal{G}'_{(h,l,t)} = \mathcal{G}_{h\sim (h_0,l_0,t_0)} \cup \mathcal{G}_{t\sim (h_0,l_0,t_0)}
\] 具体的算法伪代码如下所示：
实验
数据集
Wordnet：这个知识图谱旨在生成直观可用的词典和同义词库，并支持自动文本分析。 它的实体（称为同义词集）对应于词义，并且关系定义了它们之间的词汇关系。
Freebase：Freebase是一个庞大且不断增长的知识库。目前大约有12亿个三元组和8000万个实体。论文的作者使用Freebase创建了两个数据集。首先，为了建立一个小的数据集进行试验，选择了Wikilinks数据库中也存在的实体子集，并且在Freebase中至少有100个提及（针对实体和关系）。这产生了592,213个三元组，其中有14,951个实体和1,345个关系被随机拆分，如表2所示。此数据集的其余部分表示为FB15k。（引用）“我们还希望拥有大规模数据，以便大规模测试TransE。因此，我们通过选择频率最高的一百万个实体从Freebase创建了另一个数据集。这导致了大约25,000个关系的分裂和超过1,700万个训练三元组，我们称之为FB1M。”
baseline
实验结果
总结
直接引用原文的conclusion，如下所示：
我们提出了一种学习知识库嵌入的新方法，重点是模型的最小参数化，主要表示层次关系。 我们证明，与在两个不同知识库上的竞争方法相比，它工作得很好，并且还是一个高度可扩展的模型，因此，我们将其应用于了很大一部分的Freebase数据。 尽管我们尚不清楚是否可以通过我们的方法对所有关系类型进行适当的建模，但是通过将评估分为几类（1对1、1对多，...），与所有设置中的其他方法。
We proposed a new approach to learn embeddings of KBs, focusing on the minimal parametrization of the model to primarily represent hierarchical relationships. We showed that it works very well compared to competing methods on two different knowledge bases, and is also a highly scalable model, whereby we applied it to a very large-scale chunk of Freebase data. Although it remains unclear to us if all relationship types can be modeled adequately by our approach, by breaking down the evaluation into categories (1-to-1, 1-to-Many, . . . ) it appears to be performing well compared to other approaches across all settings.