【QUERY2BOX: REASONING OVER KNOWLEDGE G RAPHS IN VECTOR SPACE USING BOX EMBEDDINGS】

本文是Jure的一篇刚发的文章，讲的是如何使用一种全新的Embedding的方式对于知识图谱之中的元素进行建模，大家都知道知识图谱可以捕获不同的实体之间的关系，比如说Hinton是Canada的公民。但是有时候在知识图谱之中也会有另外的一种Query的情况

“where did Canadian citizens with Turing Award graduate?”

对于上面的这种情况，我们需要同时从Canadian和Turing Award出发经过Born和Win这两个关系，找到所可能的对象，然后再去处理Graduate的关系。大家如果知道的话，对于知识图谱的处理我们一般会先对于关系和实体在向量空间之中进行Embedding，然后通过简单的相加以处理Query的关系，具体的细节参照Knowledge Graph Introduction这篇笔记之中的内容。使用图片表示大概就是

上图的左边的这种形式。但是向量他是一个固定的数值，在向量空间之中就是一个固定的Point，在处理这种可能会有多个对应的实体的时候具有天然的弱式，所以作者提出了一种方法，并不将其映射在空间之中的一个点，而是映射成为一个Box，一个Hyper Box，使得可以处理多个实体都被涵盖的问题。那么接下来看看整个过程是如何实现的

Model

首先还是定义我们的知识图谱$G = (V,R)$,其中的$v\in V$代表了实体，而$r\in R$代表了一个二元函数$r: V\times V \to \{True, False\}$.代表了关系$r$是不是在一对实体之间存在，或者说，就是这两个节点之间是不是存在着边。

上述的那种即是Turing又是Canada的问题有一个专门的名词叫做是Conjunctive Queries，其数以一阶逻辑查询的一个子集

其中的$v_a$代表了一个称为Anchor的Entity，而$V_1 , \cdots ,V_k$则是那些可能的边界变量，$V_{?}$代表了目标变量。我们回答Logical Query $q$的目标可以看成是寻找一些实体的集合$Q \in V$,$v\in Q , if q[v] = True$，并且称$Q$为Denotation 集合.

如上面的图一A所示，Dependency 图是$q$的一个图形化表示。而具体的计算可以看成是两类操作的结果

1. Projection:给定一个实体集合$S \in V$,并且关系$r\in R$,通过Projection运算可以得到$\cup_{v\in S}A_{r}(v) $，其中$A_{r}(v) = \{v’\in V: r(v,v’) = True\}$
2. Intersection:给定一系列的实体集$\{S_1,S_2,\cdots,S_n\}$ ,通过InterSection可以得到这一系列的实体集的交集$\cap_{i=1}^{n} S_{i}$

那么我们将其看成是了一个计算图之中，我们就可以在知识图谱之中对于他们进行操作了。不同于使用某一个具体的点，我们使用Box对于实体们进行Embedding，假设我们的操作是在空间$R^{d}$之中的，而记$p = (Cen(p) , Off(p)) \in R^{2d}$，那么定义一个Hyper Box 通过：

$$ Box_{p } = \{ v\in R^{d} :  Cen(p )  – Off (p ) \leq v \leq Cen(p ) + Off(p)\}$$

在知识图谱之中的每一个实体都还是给分配进了一个Vector之中$v\in R^d$，其实也可以看成是一个盒子，不过这个是一个大小为0的盒子罢了。而使用Box Embedding的过程可以看成是从Source Nodes(Anchor Entities)不断的使用Logical Operator更新Embedding的过程。

Embedding Process

每一个Source 节点都代表了一个Anchor Entity$v\in V$，虽然其仅仅是一向量，但是我们依旧可以将其看成是一个Box Embedding,也就是将其记作$(v,0)$.那么对于每一个关系$r$他都有一个Relation Embedding $r = (Cen(r) , Off(r)) \in R^{2d}$,给定任何的一个Input Box Embedding $p$，将投影操作记成是$p+r$,也就是将Center和Offset都相加起来，那么我们就可以获得一个新的Box Embedding有着更新了的Center和更大的Offset.

Projection完了之后就该进行Intersection了，现在已经获得了一堆box embedding$\{ p_1, \cdots,p_n\}$，还有一个称为是$p_{inter} = (Cen(p_{inter}) , Off(p_{inter}))$的东西，那么这个玩意是怎么计算的呢？使用的还是Attention这个阴魂不散的小妖精。

$$\begin{split}Cen(p_{inter}) &= \sum_{i} a_{i} \odot Cen(p_i), \quad a_{i} = \frac{\exp(MLP(p_i))}{\sum_{j}\exp(MLP(p_j))}\\Off(p_{inter}) & = Min(\{Off(p_1,\cdots,Off(p_n))\}) \odot \\ & \sigma(DeepSets(p_1,\cdots,Off(p_n))\}))\end{split}$$

其中的DeepSets是一个Permutation函数，为了增加模型的Robust而设置的。

好了知道了$p_{inter}$是什么之后我们又要干嘛呢？在给定了$q\in R^{2d}$和$v \in R^{d}$的情况下,我们定义他们之间的距离是

$$dist_{box} (v,q) = dist_{outside}(v;q) +\alpha\cdot dist_{inside}(v;d)$$

那么out和in是什么呢？如果将$q_{max} = Cen(q)+Off(q)$而$q_{min} = Cen(q)-Off(q)$,而$\alpha$记作是一个固定的参数，

$$\begin{split}dist_{outside}(v;q) &= ||\max(v-q_{max},0) +\max(q_{min} – v, 0)||\\ dist_{inside}(v;q)  &= ||Cen(q) – \min (q_{max} , Max(q_{min},v))|| \end{split}$$

形象化的说的话，$dist_{outside}$代表了Entity和Box之中的最近的那条边之间的距离，而$dist_{inside}$则表示了盒子的中间与其边之间的距离，或者是说盒子的大小。

有了这些之后我们就可以看看如何学习Entity Embedding了，文章使用的还是用负采样来加速运算

$$L = -\log \sigma(\gamma – dist_{box} (v;q))  – \sum_{i=1}^{k}\frac{1}{k}\log \sigma (dist_{box} (v_i’ ; q) – \gamma)$$

文章之中还有一个非常有意思的点就是，还是以

“where did Canadian citizens with Turing Award graduate?”

为例子的话，原本的计算的方法是

左边这种分步的方法，左边的这种方法称为是EPFO，但是如果是按照左边的这种方式计算的话，计算的复杂度将会相当的大，所以作者通过一些理论的推导，将左边的EPFO的形式改写成为了右边的这种DNF(Disjunctive Normal Form)的形式以降低计算的复杂度。

Comments

以上就是Box Embedding的过程，在现在的各种向量的Embedding的大行其道的年代，能够想到使用Box作为一种Embedding的方式对于自己的所需要的需求进行特殊化的Embedding，从源头上对于模型改进，可以说一股清流吧。自己看着这个模型其实有点纠结为什么是一个Box而不是一个Ball呢？这个模型依旧是在欧几里得空间计算，那么干脆要不然搏一搏直接放在Poincare half Space之中进行那么结果会不会更好呢？自己倒感觉这又可以水一篇文章了。

Reference

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings