Complex Embeddings for Simple Link Prediction

• 第一篇将复数空间引入知识图谱嵌入的文献。
• 复数空间中的共轭向量使得传统的点积可以在不对称关系中用起来。
• ComplEx 模型主要受 DistMult 模型的启发，做了一些改进，但这个改进非常精妙。

1. 模型讲解

这篇文章主要是解决 link prediction 问题。ComplEx 是基于语义匹配的模型，它将 link prediction 任务看成是一个 3D 的二元 tensor 的补全问题。这种方式就是将观测到的 tensor 分解成秩较小的 embedding matrices 的乘积，从而为每个 entity 和 relation 生成固定尺寸的 vector representation。

1.1 引入复数空间

一个好的 relational model 应该具有如下两个特点：

• 能够学习出关系的 reflexivity/irreflexivity、symmetry/antisymmetry 和 transitivity 的特点；
• 其算法在时间和内存的扩充都是随着 KB 增长而线性增长的。

Embedding 做 dot product 是 scale well 的，并且由于其数学上的可交换性，它可以很自然地处理 symmetry 和 reflexivity/irreflexivity 的 relations，但是它在处理 antisymmetry 的 relation 时却是困难的。像 RESCAL 的关系矩阵 $R_k$ 是非对称的情况下，才能建模非对称关系，但这样参数量巨大，为了降低参数量，DistMult 将关系限制为对角阵，虽然参数量降下来了，但是只能建模对称关系了。

而如果换成复数，用 complex vector 就可以描述非对称关系了，同时也还能保留 dot product 的效率优势（即空间和时间的复杂度均为线性）。

1.2 只有一个 relation 的情况

1.2.1 符号说明

• 只有一个 relation
• $\varepsilon$ 代表 entities 的 set，一共有 n 个 entity
• $Y\in \mathbb{R}^{n \times n}$ 表示 the partially observed sign matrix，如果两个 entities 之间具有 relation，则 $Y_{so}=1$，否则 $Y_{so}=-1$
• $X \in \mathbb{R}^{n \times n}$ 是 latent matrix of scores

$X$ 与 $Y$ 之间的关系：$P(Y_{so}=1)=\sigma(X_{so})$

1.2.2 奇异值分解（SVD）

我们的目的是找到一个更加灵活地表示 KB 中事实的 X 的 generic structure。

SVD 矩阵分解可以施加于任何矩阵，其公式如下：

$$X \approx UV^T$$

其中 $U$ 和 $V$ 都是两个在功能上独立的 $n \times K$ 的 matrix，K 是 matrix 的 rank。

如果采用这种形式，那么就假定了 entity 出现在 subject 和出现在 object 的位置上会有不同的 representation。但是在许多 link prediction 问题中，相同的 entity 在 subject 和 object 具有相同的 embedding 是更自然的，因此引出下面的研究。

1.2.3 特征值分解（EVD）

特征值分解可以做到我们想要的：

$$X = EWE^{-1}$$

但这里通常用于 X 是实对称阵的情况，这是所有的 eigenvalues 和 eigenvectors 都存在于 real space 中，并且分解得到的 E 是一个正交阵：$E^T=E^{-1}$。但我们在这里比较关注 X 是非对称的情况，这时 EVD 不可能在 real space 中进行了，而是只存在于 complex space 中的 decomposition 了。

这时，embedding $x \in \mathbb{C}^K$ 由 real vector component $Re(x)$ 和 imaginary vector component $Im(x)$ 组成，即 $x = Re(x) + iIm(x)$，这时的 dot product 定义为：

$$<u, v> := \overline{u}^T v$$

• $\overline{u}$ 是 vector $u$ 的共轭，$\overline{u}=Re(u)-iIm(u)$

复数空间下的 EVD 可以写成：

$$X = EW\overline{E}^{-1} = EW\overline{E}^{T}$$

• 这里 $W \in \mathbb{C}^{n \times n}$ 是由特征值组成的对角阵；
• $E \in \mathbb{C}^{n \times n}$ 是由特征向量组成的矩阵；

由于 scores 是一个实数，因此我们让 X 取计算公式的实数部分，即：

$$X = Re(EW\overline{E}^T)$$

SVD v.s. EVD

与 SVD 相比，EVD 具有两个关键的区别：

• The eigenvalues are not necessarily positive or real;
• for a given entity, its subject embedding vector is the complex conjugate of its object embedding vector.

1.2.3 低秩分解（Low-Rank Decomposition）

为了让我们的 model 是 learnable 的，我们必须做出一些假设：我们所要处理的 binary relations 是具有较低的 sign-rank。

sign-rank

The sign-rank of a sign matrix is the smallest rank of a real matrix that has the same sign-pattern as $Y$ :

$$rank_{\pm}(Y)=\min_{A \in R^{m \times n}} \{rank(A)|sign(A)=Y\}$$

用 sign-rank 可以很好地衡量 sign matrix 的 complexity，并且关系到 model 的 learnability，并被一系列的 factorization model 所验证。

当我们对低 sign-rank 的 matrix $Y$ 进行分解后，得到的矩阵的 rank 会比 $Y$ 低很多。通过将矩阵 $EW\overline{E}^{T}$ 压至 rank $K \lt n$，这时 $diag(W)$ 只有前 k 个值是非零的，这样也就可以直接将 W 表示为一个 $K \times K$ 的复数矩阵了，于是对于 embedding $e_s, e_o \in \mathbb{C}^K$ 有：

$$\color{red}{X_{so}=Re(e_s^T W \overline{e}_o)}$$

于是，我们将之前的讨论总结为如下三点：

1. 我们的因式分解包含所有可能的二元关系；
2. 通过构造，它可以准确地描述对称和反对称关系；
3. learnable 的关系可以通过简单的低秩分解来进行近似，并且将向量映射到复数空间中。

1.3 应用到 Multi-Relational Data

现在我们把刚刚讨论的只有一种 relation 的情况拓展到多关系的情况。

1.3.1 符号说明

• $w_r \in \mathbb{C}^K$：an embedding of relation $r$
• $\mathcal{R}$、$\mathcal{\varepsilon}$ 分别是 relations 和 entities 的 set
• $\Omega$ 是所有 positive triples 的集合

我们想做的是复原每一个 relation $r \in R$ 的 scores matrix $X_r$，并且对于 fact r(s, o)，其成立的概率等于：

$$P(Y_{rso}=1)=\sigma(\phi(r,s,o;\Theta))$$

• $\phi$ 是 scoring function
• $\Theta$ 是对应模型的参数

1.3.2 目标

对于 link prediction 的任务，我们的目标是对于 $r'(s', o') \notin \Omega$，计算出 $Y_{r's'o'}=1$ 的概率，从而预测该 triple 是否成立。

1.3.3 ComplEx 的 scoring function

由于我们需要将 $\phi(r,s,o;\Theta)$ 用于预测 tensor $X$，因此可以得到下面的 scoring function：

我们可以从两个不同的视角来看待这个模型所做的事情：

• Changing the representation：相较于 DistMult，由于使用了共轭向量，因此可以表示非对称关系的 embedding；
• Changing the scoring function：得分仅涉及对应于嵌入和关系的实部和虚部的实向量。

当 $w_r = i Im(w_r)$，也就是只有虚部时，表示 antisymmetric 的关系；当 $w_r=Re(w_r)$，也就是只有实部时，表示 symmetric 的关系。所以：

• 从代数上理解，relation embedding vector $w_r$ 就是将关系 relation 投影到 symmetric 和 antisymmetric 这两个方向上，然后再利用点积计算 scoring function；
• 从图形上理解，relation embedding vector $w_r$ 可以视为实体嵌入向量 E 进行各向异性的缩放，然后再投影到 real subspace 上。

2. SGD for the ComplEx model

// TODO