每日归档： 2022年4月12日

Trans E

Translating Embeddings

基本概念

将集合里的关系和实体各嵌入（embedding）成 $R^k$ 中的一个向量。 Trans E 的合法性是基于下述假设：

设关系 $l$ 嵌入为 $\vec{l}$ ，实体 $h,t$ 嵌入为向量 $\vec{h},\vec{t}$ 。

对于实体 $h,t$ 和关系 $l$，关系 $hlt$ 成立当且仅当 $\vec{h} + \vec{l} = \vec{t}$ 在向量空间成立

流程

input: 训练集 $S = \{(h,l,t)\}$, 实体 $E$, 关系 $L$,差额 $\gamma$ , 图谱维度 $k$
$l,e\gets uniform(-\frac{6}{\sqrt{k}},\frac{6}{\sqrt{k}})\ \forall l \in L,e\in E$ //为何是 6?
$l /= |l|$
loop:

• $e/= |e|$
• $S_{batch} \gets \text{sample} (S,b)$ //b 是集合大小
• for each$(h,l,t)\in S_{batch}: T\cup=\{(h',l,t')\}$ //在这里 h’ 和 t’ 表示二者之一随机替换成其他实体
• $\sum_{(h,l,t),(h',l,t')\in T_{batch}}\nabla[\gamma + d(h+l,t)-d(h'+l,t')]_+$

这样训练的参量规模是 $O(n_ek+n_rk)$ 的。

SGD

上一节我们提到了 $\sum_{(h,l,t),(h',l,t')\in T_{batch}}\nabla[\gamma + d(h+l,t)-d(h'+l,t')]$ 是损失函数。

其中 $d$ 是：

其中$||x||$表示 $x$ 在 $R^k$ 意义下的范数，$||x||_{2}$ 表示 $L2$ 范数，意义是对自己应用乘法以后开根号。上式可以理解为 $(h + l - t)^2$ 的简单展开。

当然这里的加法和乘法（包括乘方）都是构成 $R^k$ 的群操作和域操作。

Trans H

Translating Hyperplanes

基本概念

事实上， Trans E 的假设是建立在关系集合 $L$ 中每一个单独的关系 $l$ 对应的图的边的出入度都至少为 $1$ 的基础上。

倘若任意关系 $l'$ 存在度数不为 $1$ 的点，那么在把元素映射到线性空间时 $l'$ 就会迫使这个度数不为 $1$ 的点相邻的点映射到相近的位置。尽管它们可能完全不同。

Trans H 为了解决这个问题做出如下假设：

设关系 $l$ 嵌入为法向量为 $w_l$ 的 $k-1$ 维超平面及其上的向量 $\vec{l}$ ，实体 $h,t$ 嵌入为向量 $\vec{h},\vec{t}$ 。

则对于实体 $h,t$ 和关系 $l$，关系 $hlt$ 成立当且仅当 $\vec{h_l} + \vec{l} = \vec{t_l}$ 恒成立。

其中：

如果说 Trans E 是把关系集合里的每一张图都嵌入成 $R^k$ 中的一个向量，那 Trans H 就是改为把这张图嵌入成 $R^k$ 中的 $k-1$ 维超平面及其上的一个向量。显然，听起来把一张图嵌入成一个平面比嵌入成一个向量科学很多。

损失函数

其中

其中 $L1$ 和 $L2$ 表示先后的情况。

这样训练的参量规模是 $O(n_ek+2n_rk)$ 的。

 

Trans R

Translating Relations

基本概念

Trans H 把每个关系的那张图嵌入到一个平面中，而 Trans R 则认为每个关系是将原空间进行一次线性变换，然后线性变换之后，关系两端的向量会各自聚成一堆。因此，它做出如下假设：

设关系 $l$ 可被看做 $R^k$ 上的某种线性变换 $M_l$ 和变换后的向量空间中的向量 $\vec{l}$，实体 $h,t$ 嵌入为向量 $\vec{h},\vec{t}$ 。

则关系 $hlt$ 成立当且仅当 $\vec{hM_l} + \vec{l} = \vec{tM_l}$ 在向量空间成立。

 

损失函数

损失函数基本同上。

同样地有评分函数

损失函数也同理。

CTrans R

所谓 Cluster-based TransR ，基于聚类的 Trans R。

基本思路是对映射后的实体对的差值做聚类。

对于每个聚类 $c$ 得到评分函数：

显著缺点

Trans R 在性能上存在一个明显的缺点：线性变换需要一个 $k^2$ 级别的矩阵，因此需要训练的参量规模是 $O(n_ek+n_rk^2)$ 级别的。这意味着，随着对拟合度要求的提高（即向量空间维数 $k$ 的增加），参量规模会显著提升并迅速变得不可接受。

Trans D

Translating Dynamic Mapping Matrix

基本概念

Trans D 认为，前面的几种模型是建立在反对称的关系上的。但事实上，关系未必总是反对称（甚至可能是对称的）。所以，在一些特定的样本中，前述模型就会出现问题。

一个自然的想法就是区分头实体和尾实体。

Trans D 于是尝试将每个实体各自嵌入到两个向量：它的位置，和它作为头/尾实体时的调整。

它作出如下假设：

设关系 $l$ 嵌入为 $R^k$ 上的位置向量 $\vec{l}$ 和投影向量 $l_p$ ，实体 $h,t$ 嵌入为位置向量 $\vec{h},\vec{t}$ 和投影向量 $\vec{h_p},\vec{t_p}$ 。

则关系 $hlt$ 成立当且仅当 $\vec{hM_{rh}} + \vec{l} = \vec{tM_{rt}}$ 在向量空间成立。

其中：

这样处理，除了可以拟合非对称的关系以外还有一个优点就是它显著降低了参量规模。因为这里的线性变换矩阵 $M$ 是通过投影向量实时（所谓的 Dynamic ！）生成的，所以参量规模降低到了 $O(2n_ek+2n_rk)$ 。当然，这一定层度上会降低拟合效率。

损失函数

估价函数是：

RotatE

Rotate Embedding（大概）

基本概念

上述的模型都是将关系对映射到 $R^k$ 的。自然地联想到，可以尝试将它映射到其他向量空间中。一个可以考虑的对象是 $C^k$ 。

RotatE 在 $C^k$ 上作出如下假设：

设关系 $l$ 嵌入为 $\vec{l}$ ，实体 $h,t$ 嵌入为向量 $\vec{h},\vec{t}$ 。

关系 $hlt$ 成立当且仅当 $\vec{h}\circ\vec{l} = \vec{t}$在向量空间成立。

其中 $\circ$ 表示 Hadamard 积，而非作用在 $C^k$ 上的那个域的乘法（内积）。

那么有距离函数：

这里的范数是内积意义上的。（显然， Hadamard 积不能导出范数）

RotatE 相比与 Trans E 的一大优势是它良好地解决了对称关系的问题：如果 $\vec{l}$ 的每一个分量都是 $\pm 1$ 的话，它就代表一个对称关系。

最优化方案

最优化的核心仍然是设计损失函数。 RotatE 采用了一种被称为「负采样」的损失函数设计方式：

其中 $\sigma$ 是 Sigmoid 函数，即 $\sigma(x) = \frac{1}{1+e^{-x}}$ ；$h_i',t_i'$ 是各自将其第 $i$ 个分量替换以后得到的向量。 $n$ 是负样本集合规模。

自对抗采样

设计权值函数

其中 $\alpha$ 是一个「温度」参量。这个权重将替换上文的 $\frac{1}{k}$ 而作为每个样本的权重。

这是因为作者认为不同的负样本在学习的时候能够提供不同的启发性。如果一个负样本的估值函数很正，说明它还没有被良好地和正样本区分开，那它就需要加上更多的权重；反之，它就已经被良好地区分开了，于是就不必特别考虑它的影响。这种方法可以有效提升训练效率。

PairRE

Paired Relation Embedding

基本概念

上述的模型常常遇到一个问题，就是无法同时优质拟合多对多、 $1$ 对多、多对 $1$ 和 $1$ 对 $1$ 的关系。就是说，它对度数分布比较复杂的关系拟合可能会出现问题。因为误差参量（margin）$\gamma$ 是个固定值。

PairRE 在 RotatE 的基础上做了一些改良。它结合了 Trans D 的思想，作出如下假设：

设关系 $l$ 嵌入为 $\vec{l_h},\vec{l_t}$ ，实体 $h,t$ 嵌入为向量 $\vec{h},\vec{t}$ 。

关系 $hlt$ 成立当且仅当 $\vec{h}\circ\vec{l_h} = \vec{t}\circ\vec{l_t}$在向量空间成立。

其中 $\circ$ 表示Hadamard 积。

另外， PairRE 还做到了较好的拟合子关系：

若存在子关系对 $r_1,r_2$ ，使得 $\forall h,t: (h,r_1,t) \to (h,r_2,t)$ ，则施加如下约束：

这样就能推导出前者。证明是显然的。

PairRE 的另一个特点是区分了多对多、 $1$ 对多、多对 $1$ 和 $1$ 对 $1$ 的关系。类似于 Trans D ，它通过区分每个关系向量和头实体的相关与其和尾实体的相关，得到了j较好的拟合性。

中间有一些精妙的数学推导，详见论文。

最优化

估价函数：

同样是进行了负采样和自对抗采样。

论文打包下载地址：http://SmokeyDays.top/wordpress/wp-content/uploads/2022/04/KGE-References-TransEHRD-RotatE-PairRE.zip