Trans系列模型详解

当前主流知识库中，知识被存储为$(h,r,t)$的三元组形式，其中 $h$ 表示头实体，$r$ 表示联系，$t$表示尾实体。知识表示学习的任务就是学习 $h,r,t$ 的分布式表示（也被叫做知识图谱的嵌入表示(embedding)）。

目前，知识表示学习方法从实现形式上可以分为两类：基于结构的方法和基于语义的方法。基于结构的嵌入表示方法包括TransE, TransH, TransR&CTransR, TransD等，这类方法从三元组的结构出发学习KG的实体和联系的表示；基于语义的嵌入表示方法包括NTN, SSP, DKRL等，这类方法从文本语义的角度出发学习KG的实体和联系的表示。

知识表示学习从发展来看可以分成两个阶段，以2013年Borders等人受Mikolov发现的语义空间中词向量的平移不变现象启发，从而提出了翻译模型(TransE)为分割。在TransE之前，有Structed Embedding, Semantic Matching Energy等模型，在TransE之后，人们在此基础上进行改进，依次提出了TransH, TransR, TransD等模型。接线来介绍基于Trans系列的模型。

Trans系列模型汇总

• TransE, NIPS2013, Translating embeddings for modeling multi-relational data

• TransH, AAAI2014, Knowledge graph embedding by translating on hyperplanes

• TransR, AAAI2015, Learning Entity and Relation Embeddings for Knowledge Graph Completion
• TransD, ACL2015, Knowledge graph embedding via dynamic mapping matrix
• TransA, arXiv2015, An adaptive approach for knowledge graph embedding
• TranSparse, AAAI2016, Knowledge graph completion with adaptive sparse transfer matrix
• TransG, arXiv2015, A Generative Mixture Model for Knowledge Graph Embedding
• KG2E, CIKM2015, Learning to represent knowledge graphs with gaussian embedding

TransE：多元数据嵌入

这篇文章提出了一种将实体与关系嵌入到低维向量空间中的简单模型，弥补了传统方法训练复杂、不易拓展的缺点，对实体和关系的建模十分简单明了，可解释性也很强。尽管现在还不清楚是否所有的关系种类都可以被这种方法建模，但目前这种方法相对于其他方法表现不错。在后续的研究中，TransE更是作为知识库vector化的基础，衍生出来了很多变体。

TransE的直观含义，就是TransE基于实体和关系的分布式向量表示，将每个三元组实例（head，relation，tail）中的关系relation看做从实体head到实体tail的翻译（其实我一直很纳闷为什么叫做translating，其实就是向量相加），通过不断调整h、r和t（head、relation和tail的向量），使（h + r） 尽可能与 t 相等，即 h + r = t。其损失函数为：

$$f_{r}(h, t)=\|h+r-t\|_{L_{1} / L_{2}}$$

显然，对于正确的三元组，应该有较低的得分。在训练过程中，使用等级损失函数，这是因为在当前情况下我们没有就标签而言的监督，只有一对正确项$(h, r, t) \in \Delta$ 和不正确项 $(h^{\prime}, r^{\prime}, t^{\prime}) \in \Delta^{\prime}$ ，我们的目的是让正确项的得分比不正确项高。这种情况出现在我们只有正例时，知识图谱就是这种情况，我们只知道正确的三元组（golden triplet），再通过破坏一个正例来生成负例。等级损失就适用于这种情况，因此我们定义损失函数：评分函数为：

$$L=\sum_{(h, r, t) \in \Delta}\sum_{(h^{\prime}, r^{\prime}, t^{\prime}) \in \Delta^{\prime}} \max \left(f_{r}(h, t)+\gamma-f_{r^{\prime}}\left(h^{\prime}, t^{\prime}\right), 0\right)$$

其中$\gamma$表示margin，通常取1

其中避免出现负值的原因：如果某一项是负的，那么可以通过使得这个负值的模非常大，来使得整个公式的值是一个模非常大的负值。而这样显然不是我们想要的。这样仅仅使得某一项符合要求，并不是全局最优。

TransE采取的生成负例三元组的方法是，将正确的三元组的头实体、尾实体、关系三者之一随机替换为其他实体或关系，从而构成负例集合 $\Delta^{\prime}$ ，这种方法称为均匀采样（与后面的伯努利采样相对比）。

整体算法为：

显然，TransE模型在处理复杂关系建模（一对多、多对一、多对多关系）时会遇到困难，例如，对于一对多关系（美国，总统，奥巴马）和（美国，总统，特朗普），TransE模型会使得尾实体向量奥巴马和特朗普的表示非常相似。事实上，这是由于对于不同的关系$r$，实体向量的表示总是相同的.

TransH:将知识嵌入到超平面

TransH客服了TransE模型的上述缺陷，将实体和关系嵌入到同一的向量空间，但实体在不同关系中有不同的表示。

TransH模型对于每一个关系$r$，假设一个对应的超平面，关系$r$ 落在该超平面上，其法向量为$w_{r}$ ，且有$\left\|w_{r}\right\|_{2}=1$ ，

类似于TransE模型的翻译在该超平面上进行，具体地，首先将头实体$h$和尾实体$t$投影到该超平面上得到$h{\perp}$和$$t{\perp}$$$，即

$$h_{\perp}=h-w_{r}^{T} h w_{r}$$ $$t_{\perp}=t-w_{r}^{T} h w_{r}$$

定义得分函数为

$$f_{r}(\mathbf{h}, \mathbf{t})=\left\|\left(\mathbf{h}-\mathbf{w}_{r}^{\top} \mathbf{h} \mathbf{w}_{r}\right)+\mathbf{d}_{r}-\left(\mathbf{t}-\mathbf{w}_{r}^{\top} \mathbf{t} \mathbf{w}_{r}\right)\right\|_{2}^{2}$$

TransE与TransH的对比：

考虑之前总统的例子，也就是一个一对多的问题。将关系表示成超平面后，这种问题得到了解决。如下图所示，如果分别用t和t‘表示两个总统，那么将三元组映射到超平面之后，t和t‘都能满足’（美国，总统，*）这个三元组。并且两个向量在向量空间还是不同的。多对一，多对多的情况也可以这样解决。

loss函数变为：

其中[]+表示的就是TransE公式中的max（*，0），即对于中括号中的值，返回0和它之间的最大值。

上式还得满足三个限制。其中，限制（1）保证每个向量的模都小于1。限制（2）是$d_r$到$w_r$的投影长度除以$d_r$的长度，这个值非常小，保证了dr确实在投影平面上。限制（3）规定投影平面的法向量的模为1，这样做是为了简化公式。否则这个公式的形式就会更为复杂。

虽然TransH模型使得同一实体在不同关系下通过投影有了不同的表示，但投影之后仍然处于原来的空间 $\mathbb{R}^n$ 中，这里 表示实体向量和关系向量均为$n$ 维。换言之，TransH模型假设实体和关系处于相同的语义空间中，这在一定程度上限制了它的表示能力。下面的TransR模型改进了这一缺陷，提高了模型的表示能力。

值得一提的是，在本篇论文中除了提出了TranH模型，另一贡献是提出了基于伯努利分布的采样方法。在原来的均匀采样中，容易将错误的负例引入到训练过程中来，例如，对于正例（美国，总统，奥巴马），随机替换奥巴马为罗斯福构成（美国，总统，罗斯福）作为负例，实际上由于罗斯福也是总统，这并不是一个负例。新的采样方法的动机是，对于一对多关系，我们以更大的概率来替换其头实体，对于多对一关系，我们以更大的概率来替换其尾实体。具体地，对于包含关系$r$ 的所有三元组，我们定义两个统计量：

1. $tph$: 平均每个头实体对应多少个尾实体
2. $hpt$: 平均每个尾实体对应多少个头实体

进而，取伯努利分布的参数为$
p=\frac{t p h}{t p h+h p t}
$ ，即以概率$p$替换三元组的头实体，以概率$1-p$替换三元组的尾实体。实际上， 反映了一对多关系的失衡程度。

通过基于伯努利分布的采样，我们就降低了引入错误的负例的概率。在清华大学NLP组的开源代码KB2E中，同时提供了两种采样方式，bern表示伯努利采样，unif表示均匀采样。

TransR&&CTransR:实体和关系分开嵌入

TransR

一个实体是多种属性的综合体，不同关系关注实体的不同属性。直觉上一些相似的实体在实体空间中应该彼此靠近，但是同样地，在一些特定的不同的方面在对应的关系空间中应该彼此远离。
在TransR中，模型将实体和关系嵌入到不同的空间中，在对应的关系空间中实现翻译。因此不同的关系应有不同的语义空间。

TransH模型是为每个关系假定一超平面，将实体投影到这个超平面上进行翻译；而TransR模型是为每个关系假定一语义空间 $\mathbb{R}^m$，将实体映射到这个语义空间上进行翻译。这里$m$表示关系向量的维度为 $m$。

TransR模型可描述为：

$$\mathbf{h}_{r}=\mathbf{h} \mathbf{M}_{r}, \quad \mathbf{t}_{r}=\mathbf{t} \mathbf{M}_{r}$$ $$f_{r}(h, t)=\left\|\mathbf{h}_{r}+\mathbf{r}-\mathbf{t}_{r}\right\|_{2}^{2}$$

其中$h, t \in \mathbb{R}^{n}, r \in \mathbb{R}^{m}, M_{r} \in \mathbb{R}^{n \times m}$ , $h,r,t,hM_r,tM_r$的L2范数均小于等于1

CTransR

CTransR的意思是Cluster-based TransR. CTransR对于每一个特定的关系$r$，首先根据实体对 $(h,t)$进行AP聚类（一种不需要指定类别数的聚类方法），实际上是对实体对的差值向量 $h-t$ 进行聚类，从而将关系 $r$ 分解为更细粒度的子关系 $r_c$ ，CTransR对每个 $r_c$ 分别学习相应的向量表示。

CTransR的得分函数可以描述为：

$$f_{r}(h, t)=\left\|\mathbf{h}_{r, c}+\mathbf{r}_{c}-\mathbf{t}_{r, c}\right\|_{2}^{2}+\alpha\left\|\mathbf{r}_{c}-\mathbf{r}\right\|_{2}^{2}$$

上式中第二项使得 $r_c$ 尽可能地接近 $r$ 。

TransR & CTransR模型将原来的单个语义空间分离为实体空间和关系空间，提高了模型的表示能力，然而，TransR模型仍然存在一些缺点：

1. 在同一个关系 $r$ 下，头、尾实体使用相同的投影矩阵 $M_r$ ，而头、尾实体可能类型或属性相差很大；

2. 投影矩阵仅与关系有关；

3. 参数多，计算复杂度高。

TransD: 通过动态映射矩阵嵌入

TransD在TransR的基础上，将关系的映射矩阵简化为两个向量的积，一定程度上克服了TransR & CTransR的上述缺点。

CTransR模型相比于TransR模型，实际上就是考虑了同一个关系也有不同的类型，然而，实体也有不同的类型。举个例子，在FB15k中，有关系location.location.partially containedby，它可以表示山川大河被某个国家包含，也可以表示山川大河被某个城市/州包含，也可以表示国家被大洲包含，还可以表示地区被国家包含。由于实体有不同的类型，因而使用相同的映射矩阵是不合理的，而且，映射矩阵不应只与关系有关，还应与头尾实体有关。以上就是TransD模型的动机，这实际上是一个更细粒度的扩展模型，本质上还是由实体语义空间和关系语义空间两个空间构成。

具体来说，对于三元组$(h,r,t)$，分别分别定义对应的投影向量$h_p, r_p, t_p$ ，其中 $p$ 表示投影（projection），再定义两个投影矩阵 $\mathbf{M}_{r h}, \mathbf{M}_{r t}$来将实体从实体空间映射到关系空间

$$\begin{aligned} \mathbf{M}_{r h} &=\mathbf{r}_{p} \mathbf{h}_{p}^{\top}+\mathbf{I}^{m \times n} \\ \mathbf{M}_{r t} &=\mathbf{r}_{p} \mathbf{t}_{p}^{\top}+\mathbf{I}^{m \times n} \end{aligned}$$

这里， $r_{p}, r \in \mathbb{R}^{m}, h, h_{p}, t, t_{p} \in \mathbb{R}^{n}, M_{r h}, M_{r t} \in \mathbb{R}^{m \times n}$ ， $I^{m \times n}$ 表示单位阵，它的意思是说用单位阵来初始化投影矩阵。

可见，在上式中，对头实体应用投影矩阵 $\mathbf{M}_{r h}$ ，它不仅与关系有关，还与头实体有关；对尾实体应用投影矩阵 $\mathbf{M}_{r t}$ ，它也不仅与关系有关，还与尾实体有关。利用这两个投影矩阵，可以得到头实体和尾实体在关系空间的投影

$$\mathbf{h}_{\perp}=\mathbf{M}_{r h} \mathbf{h}, \quad \mathbf{t}_{\perp}=\mathbf{M}_{r t} \mathbf{t}$$

所以得分函数为：

$$f_{r}(\mathbf{h}, \mathbf{t})=-\left\|\mathbf{h}_{\perp}+\mathbf{r}-\mathbf{t}_{\perp}\right\|_{2}^{2}$$

显然，TransE是TransD的一个特例，当 $m=n$ 且所有投影向量均为零时，TransD就退化为了TransE. 与TransH对比，显然需先令TransD的 $m=n$ ，再分别写出TransH和TransD的实体投影后的向量：

$$\begin{array}{l}{\text { TransH: } h_{\perp}=h-w_{r}^{T} h w_{r}} \\ {\text { TransD } : h_{\perp}=M_{r h} h=h+h_{p}^{T} h r_{p}}\end{array}$$

因为$r_{p} h_{p}^{T} h=h_{p}^{T} h r_{p}$ ，因此为便于格式上的对比，我们将TransD中的​ $\mathbf{h}_{\perp}$ 写成上述形式。可见，当 $m=n$ 时，TransD与TransH唯一的区别在于TransD中的投影向量不仅与关系有关，还与实体有关。

对比TransR模型，TransD为头实体和尾实体分别设置了投影矩阵，另外，注意到在TransD中公式经过展开之后没有矩阵-向量乘法操作，这相比于TransR模型降低了计算复杂度，更适用于大规模知识图谱的计算。

TransA：自适应度量函数

TransE本质上是欧式距离计算：公式为：

$$\begin{aligned} f_{r}(h, t) &=\|\mathbf{h}+\mathbf{r}-\mathbf{t}\|_{2}^{2} \\ &=(\mathbf{h}+\mathbf{r}-\mathbf{t})^{\top}(\mathbf{h}+\mathbf{r}-\mathbf{t}) \end{aligned}$$

对应图形是一个圆。本文提出了一种基于马氏距离的 TransA 模型，其 PCA 降维图形对应的是一个椭圆：

公式为：

$$f_{r}(h, t)=(|\mathbf{h}+\mathbf{r}-\mathbf{t}|)^{\top} \mathbf{W}_{\mathbf{r}}(|\mathbf{h}+\mathbf{r}-\mathbf{t}|)$$

对$W_r$使用LDL进行分解：

$$\begin{array}{c}{\mathbf{W}_{\mathbf{r}}=\mathbf{L}_{\mathbf{r}}^{\top} \mathbf{D}_{\mathbf{r}} \mathbf{L}_{\mathbf{r}}} \\ {f_{r}=\left(\mathbf{L}_{\mathbf{r}}|\mathbf{h}+\mathbf{r}-\mathbf{t}|\right)^{\top} \mathbf{D}_{\mathbf{r}}\left(\mathbf{L}_{\mathbf{r}}|\mathbf{h}+\mathbf{r}-\mathbf{t}|\right)}\end{array}$$

公式中$Lr$可以看作transformation matrix，将loss vector映射到另一个空间，$D_r$是对角矩阵$$
\mathbf{D}{\mathbf{r}}=\operatorname{diag}\left(w{1}, w{2}, w_{3} \dots\right)$$，对角线上的元素表示不同维度上的权重。