IJCAI 2017
文章简介:知识库补全(Knowledge base completion)预测知识库中缺少的信息。本文提出了KBC中的OOKB问题(Out-of-Knowledge-Base) ，即如何处理知识库中(训练样本中)没有的实体查询任务，并给出了相应的模型(是早期KBC中用到图神经网络的方法)。
原文
代码
目录:
1 Introduction
2 OOKB Entity Problem in Knowledge Base Completion
2.1 Knowledge Graph
2.2 KBC:Triplet Classifcation
2.3 OOKB Entity Problem
3 Proposed Model
3.1 Graph-NNs
3.2 Propagation Model on a Knowledge Graph
3.3 Output Model: Score and Objective Functions
4 Experiments
4.1 Implementation and Hyperparameters
4.2 Standard Triplet Classification
4.3 OOKB Entity Experiment
4.4 Stacking and Unrolling Graph-NNs
5 Conclusion
1 Introduction
知识库补全(Knowledge base completion,KBC)目的是预测知识库中缺失的信息，比如说我们的数据中有如下关系:A是B的父亲，B是C的父亲，那模型训练后就可以自动补全A是C的祖父。本文提出了OOKB(out-of-knowledge-base )实体问题即三元组中出现了新的实体(训练集中未出现，即没有这个实体的嵌入)时该如何处理。后来我查了些资料，出现未知的新实体应该是属于拓展知识库了(KBP,Knowledge base population)而不再是知识库补全(KBC)，这里的话还是注重在作者解决问题的思路。
作者采用了图神经网络(GNN)的方法来建模，这样的好处是模型可以获得OOKB的嵌入。作者认为的contribution有以下三点:
1.对KBC问题中的OOKB情况提出了新的阐述。
2.对包含OOKB实体的KBC任务提出了适合的GNN模型。
3.在标准数据集以及OOKB情况下，作者实验验证了模型的有效性。
2 OOKB Entity Problem in Knowledge Base Completion
2.1 Knowledge Graph
这里定义的正例是从上帝视角看所有成立的三元组,包括知识库中尚未存在的三元组，反例即是不成立的三元组。KBC任务即要找到所有正例的三元组来补全知识库。
2.2 KBC:Triplet Classification
三元组分类是目前用来评测模型KBC性能的方法。
作为一个机器学习的分类问题，我们把知识库G作为训练集(只包含正例，训练时候会使用负采样无监督的训练方法)，H是测试集，理想情况下正例包含了所有的缺失的正例三元组，负例为各种不成立的三元组。在标准的三元组分类问题中，所有的实体和关系都在训练集(知识库)中出现过。
2.3 OOKB Entity Problem
在OOKB的情况下，训练和之前一样，但是测试集中会先提供包含新实体的三元组(auxiliary knowledge)，即三元组中的实体未在训练集中出现没有嵌入，但是所有关系都是包含在训练集中的。OOKB下的KBC任务即要补全新实体(找到包含新实体的所有正例三元组)。因为新实体没有嵌入，所以我们要通过测试集中提供的包含新实体的三元组(auxiliary knowledge)来对新实体进行嵌入，再完成之后的补全任务。
3 Proposed Model
3.1 Graph-NNs
目前存在的GNN可以将整个图进行嵌入(传统的方法比如邻接矩阵)，本文中的方法是把节点(实体)和边(关系)完成嵌入适应KBC。
一个GNN包含两个模型，propagation model和output model。前者通过节点的邻近节点的嵌入完成嵌入(OOKB实体通过auxiliary knowledge获得邻近节点)，后者根据任务目标定下一个目标函数进行训练，本文使用的是略微改动的TransE。个人的理解在这里训练时propagation model是对每个实体嵌入做初始化
3.2 Propagation Model on a Knowledge Graph
节点v通过邻接的节点(下图公式中分为进入的节点集合head和出去的节点集合tail)获得。
本文使用的方法是(2),(3),(4)，函数T将三元组的两个向量映射为剩下的那个向量，池化函数P将一个集合的向量映射为一个向量。
可以看出如果采用sum pooling，那公式(4)会退化成公式(1)。
接下来是GNN传播信息的方式，分为 stacking和unrolling。大致意思后者的图是静态的参数共享，前者是动态的传播的每一步参数都不同，见下图。这里作者说的很简略我也没太看明白，也没去查更多的资料以后有机会再补吧。我猜测意思就是计算节点嵌入时如果用到不同深度的邻近节点，则T函数会有不同的参数。
3.3 Output Model: Score and Objective Functions
本文略微修改了TransE的损失函数，原本的公式(7)优化正例得分比负例得分低γ以上，而本文提出的公式(8)优化则是让正例得分靠近0，负例得分至少γ。
作者也没有从数学的层面上解释，只是这样的修改效果更好。
4 Experiments
4.1 Implementation and Hyperparameters
本文使用了框架chainer，Adam，α1=0.01，α2= 0.0001，batchsize=5000，标准任务嵌入200维，使用了max pooling，OOKB情况嵌入100维，三种pooling都做了实验。γ取300通过验证集来定的。同时对于一个节点有超过64个邻近节点的情况，考虑到显存限制我们随机取64个。
4.2 Standard Triplet Classification
数据集WN11和FB13通过http://cs.stanford.edu/people/danqi 下载，训练集中不存在负样本，采用负采样来训练(这里用到了TransH中的Bernoulli trick来负采样)。验证集和测试集包含负样本。这里实验没有做广泛使用的Link Prediction，而是Triplet Classification，参数是准确率。数据集及实验结果见下图。
4.3 OOKB Entity Experiment
由上文可以知道，在标准情况下测试集中的实体和关系在训练集中都需要出现过(获得嵌入)。在OOKB的情况下实体可以是从未出现过的未知实体，并且引入了auxiliary knowledge所以训练集，验证集，测试集都需要重新划分。划分大致有两个步骤:
1.选定OOKB实体
这里首先从WN11的测试集中抽出N=1000，3000，5000个三元组，用(Head,Tail,Both)三种方法:Head方法表示N个三元组中头实体都是OOKB实体，Tail表示尾实体是，Both表示都是，所以下图中可以看到Both的OOKB实体数量约等于Head和Tail的OOKB实体之和(略小于，因为实体重复的关系)。这样就出现了九种可能的OOKB实体列表。
2.划分数据集
对于WN11中的训练集三元组，若没有出现OOKB实体则保留在训练集中，若出现了1个OOKB实体则加入auxiliary knowledge，若出现了2个OOKB则直接丢弃。测试集则是在第一步的N个三元组中移除掉不包含OOKB实体的(不太懂，不是就是由这N个决定OOKB实体列表的?难道是因为训练集中2个都是OOKB所有被丢弃了)，验证集则是在WN11验证集中去除掉包含OOKB实体的。
Baseline为图神经网络中没有使用T函数直接将邻近节点池化，并且没有修改TransE的结果。
4.4 Stacking and Unrolling Graph-NNs
得出的结果是不要用图神经网络来传播节点信息，使用一次获得节点嵌入就够了。个人理解为初始化的时候只通过一阶近邻计算嵌入足矣。
5 Conclusion
我自己的感觉是，文章的思路很有趣，而且是在2017年的时候那时使用图神经网络的尝试还较少。但是结果有些差强人意感觉自圆其说，没有用大的数据集也没有使用更广泛接收的Link prediction作为实验。
