【Duality of Link Prediction and Entailment Graph Induction】

NLP领域有两个问题一个叫做是Link Prediction ,另一个叫做Entailment Graph Induction,这两个问题过去是被认为是两个不同的问题，但是在这篇文章内，作者试图证明这两个问题实际上是互补的问题。

Introduction

Link Prediction是为了从已有的知识图谱之中获取到实体(Entity)之间的关系,而Entailment Graph Induction则是分辨实体之间是否是由Entailment(蕴含)的关系

文章作者通过用Link Prediction帮助分辨Entailments或者反之的方式来验证这两个是互补的任务。

一般来说学习Entailment Graph的手段是在关系之中学一个Local的 Entailment Score通过这个Score来判断是否Entailment，而对于Link Prediction的任务来说，现有的方法是通过对于所有的Entity以及可能的Relationship进行Embedding，然后也是计算Score。但是现在的EG的方法受到了数据点稀疏性和噪声的影响，而Link Prediction恰好可以缓解稀疏性，也可以一定程度上的降噪。同样的，已有的Entailment也可以在知识图谱的Link Prediction的任务之中所应用。

Approach

令$T$表示所有的Types(比Entity更高一级的概念)，而令$E(t)$表示在$t$之中所蕴含的所有的实体(Entity),以$R(t_{1},t_{2})$表示两种Types之间的信息，以$E$表示所有的Entity，而以$R$表示所有的Relationships。而一个知识图谱$H(t_{1},t_{2})$则包含了一系列的三元组$(r,e_{1},e_{2})$,其中的$(e_{1},e_{2}) \in E^{2}(t_{1},t_{2})$,而$E^{2}(t_{1},t_{2}) = (E(t_1)\times E(t_2))\cup E(t_2)\times E(t_1)$,也就是$t_1$与$t_2$之间的可能的所有的实体对(Entity Pairs)。那么定义$X_{r,e_{1},e_{2}}$作为一个二元的随机变量，如果$(r,e_{1},e_{2}) \in H$的话，那么就是1，否则就是0。还是比较好理解的哈。

下面再对于两个任务使用数学化的表达进行更深的描述

Link Prediction

对于每一个Triple:$(r,e_{1},e_{2})$来说，一个Link Prediction Model就是定义一个Score Function，$f(r,e_{1},e_{2})$其输出是这个成立的概率，所以我们可以简单的把这个模型记作是$P(X_{r,e_{1},e_{2}})$。而以$S$记录所有的可能的Relation，其中$S$的行是所有的可能的关系，而列是实体对，其Entry就是0或者是1，1代表存在于知识图谱之中，而0则代表其不存在与已有的知识图谱之中。

Entailment Prediction

而这个的目标就是在所有的Relation之中寻找到一个Entailment Score，以$W_{r,q}$表示在$R$之中的两个关系$r,q$的相似程度，而用$W(t_{1},t_{2})$来存储这两个Types之间的信息。而现在的常用的比较相似程度的方法是通过比较这两个实体的特征向量，以Pointwise Mutual Inforamtion作为度量的标准，但是这种方法很容易就导致了稀疏性的问题。

那么这两个任务有什么不同呢？这两个任务的输出，一个是Link Prediction Score$S(t_{1},t_{2})$还有一个叫做是Entailment Score$W(t_{1},t_{2}) $,所以作者在这里动起了脑筋，其使用前者的输出预测后者，再用后者的输出预测前者。具体怎么做呢？
首先看看使用前者预测后者的。为了计算Entailment Score，将知识图谱丢进一条马尔科夫链之中，也就是个二分图(Bipartite Graph) $M = (V_{M},E_{M})$之中，其中的$V_{M} = R\cup E^{2}$是图的节点，而$E_{M}$ 包含了边$(<r>,<e_{1},e_{2}>)$，如果$P(X_{r,e_{1},e_{2}}= 1)>0$ 的话，说的有点抽象，可以看看图

左边是Relation，而右边是在$T$之中所包含的Entity对。

可以计算出两个概率，第一个概率是通过关系预测出是这两个实体对的概率，还有一个概率是通过实体对计算出关系的概率，使用贝叶斯公式不难得到

$$\begin{split} P(<e_{1},e_{2}>|<r> ) &= \frac{P(X_{r,e_{1},e_{2}}= 1)}{\sum_{e_{1},e_{2} \in E^2}P(X_{r,e_{1},e_{2}}= 1)} \\ P(<r>| <e_{1},e_{2}>) &= \frac{P(X_{r,e_{1},e_{2}}= 1)}{\sum_{r\in R}P(X_{r,e_{1},e_{2}}= 1)}\end{split}$$

而对于关系$r,q$定义Entailment Score$W_{r,q} = P(<q>|<r>)$，而其等于

$$P(<q>|<r>) = \sum_{e_{1},e_{2} \in E^2} P(<e_{1},e_{2}>|<r> ) P(<q>| <e_{1},e_{2}>)$$

那么就成功的在两种Score之中建立起了桥梁。

那么怎么利用后者来辅助前者呢？

作者提到了一个假设叫做是Distributional Inclusion Hypothesis(DIH)假设，其认为一个Word(Relation) r 与另外的一个Word(Relation) q Entail的条件 是在任意的r可以使用的场景下，都可以使用q作为代替，也就是说q蕴含r。那么在一个Complete的知识图谱之中，我们用数学语言进行描述$r\to q$

$$\begin{split}\forall (e_{1},e_{2}) \in E^{2} : \\ X_{r,e_{1},e_{2}} = 1 \to X_{q,e_{1},e_{2}} \end{split}$$

也就是说

$$X_{r,e_{1},e_{2}} \leq X_{q,e_{1},e_{2}}$$

所以说如果$r\to q$的话，那么我们就可以合理的假设$P(X_{r,e_{1},e_{2}} )\leq P( X_{q,e_{1},e_{2}})$，因此我们就可以得到一个新的Link Prediction Score

$$S_{q,e_{1},e_{2}}^{Ent} = \max_{r\in R:r\to q} S_{r,e_{1},e_{2}}$$

也就是说在$e_{1},e_{2}$之中的关系，是$e_{1},e_{2}$的所有的可能的关系之中的最大的那个,似乎与原来的没什么不同，但是这时候由于我们加入了Entailment的信息，打个比方，我们的数据之中有很多的“我爱你”，但是没有什么“我喜欢你”，经过Entailment之后我们知道了“爱”是蕴含在“喜欢”之中的，那么在原来的情况下，我们可能会为可能的实体对更多的赋予爱这个关系，因为在原数据集之中，“爱”比“喜欢”更多，但是由于加了Entailment的话，就增加了说“喜欢”的可能性，达到了另外的一种数据增强的效果。 而为了降低噪声，使用所有的可能的Entailment Relation的加权平均。

$$S_{q,e_{1},e_{2}}^{Ent} = \max(S_{q,e_{1},e_{2}, \sum_{r\in R} W_{r,q}’ S_{r,e_{1},e_{2}})$$

其中的$W_{r,q}’ $是矩阵$W$的第$q$列的平均。

Comments

又是一篇理论性很强的文章啊，通过对于两个任务的目标进行比较，成功用一个模型的结果的对于另一个模型进行提升，这里的将知识图谱丢进马尔科夫链的方法也很奇妙。但是不知道两个任务有这样的关系的话，不仅仅是通过文章之中的这种方法进行进一步的开发，可能也可以通过类似于GAN，Reinforcement Learning的方法进行更进一步的深层次的处理，说不定也可以搞出一个新的什么算法吧。而这里的也可以使用之前的网络外部性的概念进行新的改进吧。

Reference

Duality of Link Prediction and Entailment Graph Induction