图谱论文笔记2 - ComplEx｜YOLO - A Blog You Only Look Once

1.1k words in total, 4 minutes required.

图谱论文笔记：Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, Guillaume Bouchard. “Complex Embeddings for Simple Link Prediction”. ICML 2016.

基于latent factorization来解决link prediction问题。（low-rank factorization或embeddings被用于KG completion问题）

low-rank factorization：将观测到的张量/矩阵分解为多个低秩的embedding matrices的相乘，使得数据库中每个entity或relation都有固定维度的vector表达；

内积（dot product）： scale well；可处理对称性（symmetry）和自反性（reflexivity）；然而对于不对称的关系的处理能力不够；

complex valued embeddings: The composition of complex embeddings can handle a large variety of binary relations, among them symmetric and antisymmetric relations.

在复数空间中，内积操作通常被称之为Hermitian dot product^[1]，亦称为半线性（sesquilinear）内积，因其引入了共轭转置(conjugate-transpose)。
由此，Hermite内积不再对称，根据entity的位序而有所不同。

矩阵分解，内积和Embedding表达

通常而言，我们可以用一个$n \times n$的邻接矩阵来表示KG中$n$个实体在某个关系上的boolean关系。这个矩阵成为关系矩阵

由此，我们可以将这个矩阵$M$分解为两个矩阵的相乘$X=UV^\mathsf{T}$，此处$U$和$V$都是$n \times K$的矩阵，$K$是embedding的长度。我们可以看到，此时的假定是每个实体在作为head和tail时各有一个embedding，分别在$U$和$V$中。

为了使得head和tail拥有统一的embedding表达，内积被提出使用，即$X=EWE^{-1}$。这里，为了使得$E^{-1} = E^\mathsf{T}$，需要保证$E$是正交的。

ComplEx将每个embedding表达为一个复数，即embedding $x \in \mathbb{C}^K$包含实数部分$Re(x) \in \mathbb{C}^K$和虚数部分$Im(x) \in \mathbb{C}^K$。

Hermitian内积

$\langle u, v \rangle = \bar{u}^\mathsf{T} v$

在上式中，$u$和$v$是两个复数； $\bar(u) = Re(u) - iIm(u)$即取$u$的共轭。

复数空间下的矩阵分解

$X = EW\bar{E}^\mathsf{T}$

上式中，$W \in \mathbb{C}^{n \times n}$是降序奇异值的对角矩阵；$E \in \mathbb{C}^{n \times n}$是特征向量的一个酉矩阵 (Unitary matrix - 酉矩阵的逆矩阵，就是其共轭转置)，$\bar{E}$表示它的复数共轭。

在ComplEx中，对于矩阵$X$的分解仅投影到实数部分，即

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

最终，$E$的每一行代表一个entity，它的tail和head的复数表达互为共轭。

关系矩阵分解和link prediction

link prediction问题可以建模为从一个带有噪声的观测关系矩阵中恢复完全的形态。这里假设是矩阵具有low sign-rank。

通过强制指定low-rank $K \ll n$在$EW\bar{E}^\mathsf{T}$上，$\text{diag}{W}$只有前$K$个值非零。这样能够得到$K$维的embedding表达。给定任意两个entity $s$和$o$，他们的关系得分可以预测为

$X_{so} = Re(e_s^\mathsf{T}W\bar{e}_o)$

扩展到多元关系上

上述理论的叙述是在单一的relation matrix上进行的，我们对此进行multi-relational data的扩展。

给定关系的集合$R$和实体的集合$E$，我们通过下列的概率公式来推断一个关系是否成立：

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

上式中，$r \in R$是一个关系，$s, o \in E$是head和tail entities；$\phi$是scoring function，$\Theta$是对应的参数。

假定观测的训练数据包含true和false的facts，如$\{\mathbf{Y}_{rso}\} \in \{ -1, 1 \}$。

ComplEx中的scoring function定义如下

$\begin{aligned} \phi(r,s,o;\Theta) & = Re(\langle w_r, e_s, \bar{e}_o \rangle) \\ & = Re(\sum_{k=1}^K w_{rk} e_{sk} \bar{e}_{ok}) \\ & = \langle Re(w_r), Re(e_s), Re(e_o) \rangle \\ & + \langle Re(w_r), Im(e_s), Im(e_o) \rangle \\ & + \langle Im(w_r), Re(e_s), Im(e_o) \rangle \\ & - \langle Im(w_r), Im(e_s), Re(e_o) \rangle \end{aligned}$

此处$w_r \in \mathbb{C}^K$表示关系$r$的复数embedding。

这个公式提供了两种view，其中一种类似于DistMult，但是引入了复数共轭形式；另一种将其建模为Re和Im两个部分，但是在实现上全部可以用实数来表示，不需要使用虚数。

当一个关系是完全非对称是，Re部分完全为0；相反，则Im部分完全为0。

训练目标函数

link prediction中的loss function定义在log-likelihood上加上L2正规项，如下

$\min_{\Theta} \sum_{r(s,o) \in \Omega} log(1 + \exp(-\mathbf{Y}_{rso}\phi(s, r, o; \Theta))) + \lambda ||\Theta||^2_2$

1.https://zhuanlan.zhihu.com/p/43612010. ↩

Table of Contents

1. 矩阵分解，内积和Embedding表达
1. 1.1. Hermitian内积
2. 1.2. 复数空间下的矩阵分解
2. 关系矩阵分解和link prediction
3. 扩展到多元关系上
4. 训练目标函数