利用 Pytorch-BigGraph 从知识图中提取知识详解

雷锋网 AI 科技评论按，机器学习使我们能够训练一个模型，该模型可以将数据行转换为标签，从而使相似的数据行映射到相似或相同的标签。

以我们为电子邮件构建垃圾邮件过滤器为例。我们有很多电子邮件，其中一些被标记为垃圾邮件，一些被归类到收件箱。我们可以建立一个模型去学习识别垃圾邮件。要标记为垃圾邮件的邮件在某种程度上与已标记为垃圾邮件的邮件相似。

相似性的概念对于机器学习至关重要。在现实世界中，相似性的概念是非常具体的主题，它取决于我们的知识。

另一方面，大多数数学模型都假定相似性的概念是被定义的。通常，我们将数据表示为多维向量，并测量向量之间的距离。

图片来源：https://www.quora.com/Why-do-we-use-cosine-similarity-on-Word2Vec-instead-of-Euclidean-distance

特征工程是将我们对现实物体的认知转化为这些数值表示的过程。我们将认为相似的物体表示为邻近的向量。

例如，我们要对房价进行评估。我们的经验告诉我们，房子是由卧室的数量，浴室的数量，房龄，面积，位置等来定义的。购买位于同一个街区，面积和年限相似的房子应该花费差不多的金额。我们根据对房地产市场的了解，将房子的描述转化为数字，并用这些数字来估计房子的价格。

不幸的是，如上所述，手动特性工程在将我们的知识转换为可以描述的特性的能力方面存在局限性。

有时知识只能局限于相似性原则，而不局限于使事物相似的确切特征。通常，我们对现实世界的了解远比简单的表格内容更为复杂。它通常是一个相互关联的概念和关系图。

嵌入模型允许我们获取原始数据，并根据我们对原理的了解将其自动转换为特性。

word2vec

word2vec 可能是最著名的 embedding 模型，它为单词构建相似向量。在这种情况下，我们对世界的了解是以故事的形式呈现的，以文本的形式表示，而文本是一系列的单词。

几十年来，人们一直在努力用人工定义的特征来描述单词，但成功率有限。这些解决方案通常无法扩展到完整的知识体系或在条件有限的情况下工作。

当 Tomas Mikolov 和他在谷歌的团队决定建立一个模型时，一切都发生了变化，这个模型基于众所周知的相似性原则。在类似的上下文中，使用的单词通常是相似的。在本例中，上下文由附近的单词定义。

单词序列的图表示法

我们看到的是，考虑到这些原则，我们可以通过在一个预先定义的窗口（通常是 5 个词）内简单地将每个词与其相邻词连接起来，从文本中构建一个图。

现在，我们有了一个图，它是基于我们的知识连接起来的真实单词对象（单词）的图。

最简单/复杂的单词表示法

我们仍然无法建立任何模型，因为单词没有以固定的形式或向量表示。

如果我们需要做的只是把单词转换成数字，那么有一个简单的解决方案。让我们拿着我们的字典，把每个单词在字典中的位置分配给它们。

例如，如果我有三个词：cat, caterpillar, kitten。

我的矢量表示方法如下：cat-[1], caterpillar-[2] 和 kitten-[3]。

不幸的是，这行不通。通过指定这样的数字，我们隐式地引入了单词之间的距离。cat 和 caterpillar 之间的距离是 1，cat 和 kitten 之间的距离是 2。我们说猫更像是 caterpillar，而不是 kitten，这与我们的认知相矛盾。

另一种表示被称为「独热编码（one-hot encoding）」的方法也可以做到这一点：

cat — [1,0,0]

caterpillar — [0,1,0]

kitten — [0,0,1]

这个模式表示所有单词都是正交的。我们承认，没有预想到单词相似性的概念。我们将依靠我们的知识图谱（如上所述），它结合了我们的单词相似性原则，来构建 embedding。

在现实世界中，字典的大小远远大于 3。典型的维度是从数万到数百万。这些向量不但不能真正代表我们相似性的概念，而且它们也非常庞大，不能真正用于实践。

构建单词 embedding

我们的知识图谱为我们提供了大量的图边，对每个边来说，输入数据为其起点，标签为其终点。我们正在建立一个模型，试图用某个单词周围的单词作为标签来预测它。这通常有两种方式。我们可以根据邻接词重建词向量，也可以做相反的事情，即尝试通过这个词预测邻接词。

图片来源：https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

从根本上讲，团队使用基本的编解码器模型，学习从高维空间（数百万维）到有限维空间（通常为 300 维）的映射以及返回高维空间的映射。训练的目标是在压缩过程中尽可能多地保存信息（最小化交叉熵）。

图片来源：http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/

从稀疏正交数据集的低维投影学习到更密集的低维空间的概念是许多其他 embedding 训练模型的基础。

该模型通常是针对谷歌爬虫、Twitter 数据集或维基百科等资源进行训练的。我们正在学习世界的知识，并以此为基础构建我们的词 embedding。

word2vec embedding 的属性

word2vec 的重要特性是保持关系和公开结构的能力。

下面的图表显示了国家和首都之间的联系。

或者其它不同的概念

图片来源：https://www.tensorflow.org/tutorials/representation/word2vec

本质上，它允许在单词上做这样的代数运算：

king — man+woman=queen

使用单词 embedding

单词 embedding 大大改进了诸如文本分类、命名实体识别、机器翻译等任务。

这里可以看到更多信息：http://www.wildml.com/2015/11/understanding-convolutional-neural-networks-for-nlp/

Node2Vec

A.Grover 和 J.Leskovec 提出的 Node2Vec 是一个模型，它通过扩展 Word2Vec 的思想来分析同一类别的加权图。本文背后的思想是，我们可以通过探索图节点周围的元素来描述它。我们对世界的理解基于两个原则——同质性和结构等效。

同质性

相似的节点所在的位置相近。

示例：

• 社交网络：我们与和我们相似的人有更多的联系。

  商业地点：金融公司、医生办公室或营销公司通常位于同一条街上。

  组织结构：同一团队中的人具有相似的特征。

  结构等效

  不同的社区共享相同的结构：

  • 从组织结构来看，虽然团队之间的连通性很弱，但团队的结构（经理、高级成员、新成员、初级成员）在团队之间是相似的。

    

    图片来源：https://arxiv.org/pdf/1607.00653.pdf

    为了将这两个原理结合到我们的 embedding 中，Node2Vec 论文的作者提出了一种将广度优先抽样与深度优先抽样相结合的 random walk 方法来捕获结构等效性。

    如我们所见，节点（U）在一个组（s1、s2、s3、s4）中充当中心，类似于作为（s7、s5、s8、s9）中心的 s6。我们发现（s1，s2，s3，s4）和（u）<->（s6）用深度优先算法和广度优先算法都是类似的。

    我们通过探索每个节点的周围的元素来了解它。这种探索将图转换成大量 random walk 产生的序列（句子），它将深度优先（DFS）和广度优先（BFS）的探索结合起来。BFS 和 DFS 的结合由图边缘的权重以及模型的超参数控制。

    一旦我们有了完整的序列（句子），我们就可以像应用于文本一样应用 word2vec 方法。它基于我们定义的原则以及从图中获得的知识，它产生了图节点 embedding。

    Node2Vec 属性

    Node2Vec 表示改进了节点的聚类和分类模型。所学的 embedding 相似性将有助于执行欺诈检测等任务。

    Node2Vec 生成的 Les-Mis_rables 共现网络的互补可视化，其标签颜色反映同质性（顶部）和结构等效（底部）。

    

    图片来源:https://arxiv.org/pdf/1607.00653.pdf

    Node2Vec 在链路预测方面有显著改进。它能够提高重建图的能力，去除部分边缘。本篇文章将进一步讨论链路预测评估过程。

    知识图

    下面我们将讨论「PYTORCH-BIGGRAPH: A LARGE-SCALE GRAPH EMBEDDING SYSTEM」这篇论文（下面将论文简写为 PBG），以及和它有关联的系列论文。

    知识图是包含已知实体和不同类型边的特殊类型的图。它代表结构化的知识。

    在知识图中，节点通过不同类型的关系进行连接。

    

    图片来源：https://arxiv.org/pdf/1503.00759.pdf

    训练的目标是产生代表我们知识的 embedding。一旦我们有了节点的 embedding，就可以很容易地通过特定类型的关系确定相应的节点是否在我们的知识图中连接（或应该连接）。

    不同的模型提出了不同的 embedding 比较方法。最简单的模型使用余弦或向量积距离比较 embedding 向量。更复杂的模型在比较之前对向量的元素应用不同的权重方案。加权方案表示为矩阵，并且对于不同的关系类型来说，这个矩阵是特定的。作为训练的一部分，我们可以学习加权矩阵。

    

    图片来源：https://www.sysml.cc/doc/2019/71.pdf

    我们需要找到一种方法来测量边缘之间的相似性分数，并使用该分数来评估这些节点连接的可能性。

    知识图的表示

    知识图可以表示为邻接 tensor。要建立它，我们需要为每一种关系建立一个平方矩阵。每个矩阵的列或行与图中的节点一样多。如果这些节点通过这种关系连接，那么矩阵的值将为 1，如果不是，则为 0。很明显，这个矩阵非常大，非常稀疏。

    为了学习 embedding，我们需要将每个节点转换为固定大小的向量。让我们讨论一下「好」的 embedding 的特性。

    好的 embedding 是以图的边缘的形式来表示我们的知识的。位于「附近」的 embedding 向量应该表示更可能连接的节点。基于这一观察，我们将训练我们的模型，使相邻 tensor 中标记为 1 的连接节点的相似性得分更高，相邻 tensor 中标记为 0 的连接节点的相似性得分更低。

    

    图片来源：https://arxiv.org/pdf/1503.00759.pdf

    我们正在训练我们的 embedding 以最小的信息损失从节点 embedding 重构知识图的边缘。

    负采样

    我们的训练方法有点问题。我们试图学习使用图数据区分 1（节点已连接）和 0（节点未连接）。然而，实际上我们拥有的唯一数据是连接节点的数据。这就像只看猫就要学会区分猫和狗一样。

    负采样是一种扩展数据集并通过简单的观察提供更好的训练数据的技术。任何随机选择的节点，如果没有作为我们图的一部分连接，将会被表示一个标签为 0 的示例数据。为了训练的目的，PBG 提出读取图的每一个边缘，然后提出一个负样本，其中一个节点被随机选择的节点替换。

    对于每个边，我们可以指定一个正相似性得分和一个负相似性得分。基于节点 embedding 和边缘关系类型权重可以计算正相似性得分。负相似度得分的计算方法相同，但边缘的一个节点损坏，被随机节点替换。

    排名损失函数将会在训练时被优化。它的产生是为了在图中所有节点和所有关系类型的正相似度得分和负相似度得分之间建立一个可配置的边界。排名损失是节点 embedding 和关系特定权重的函数，是通过寻找最小排名损失来学习的。

    训练

    现在我们有了训练 embedding 模型所需的一切：

    • 数据:正负边

      标签:1 或 0

      优化函数:可以是排名损失、更传统的逻辑回归损失或 word2vec 中使用的交叉熵 Softmax 损失

      我们的参数是 embedding 以及相似度得分函数的权重矩阵

      现在使用微积分来寻找 embedding 参数，优化我们的损失函数。

      随机梯度下降算法

      随机梯度下降的本质是逐步调整损失函数的参数，使损失函数逐渐减小。为了做到这一点，我们以小批量读取数据，使用每批数据计算其对损失函数参数的更新，以将其最小化。

      随机梯度下降有多种方法。在 PBG 这篇论文里面，采用了随机梯度下降的一种方式——ADAGRAD 来寻找参数，使损失函数最小化。我强烈推荐你阅读这个博客来理解梯度下降的所有风格：http://ruder.io/optimizing gradient depression/index.html adagrad

      像 TensorFlow 和 PyTorch 这样的软件包为不同的风格提供现成的实现。

      梯度下降的关键是多次更新模型参数，直到损失函数最小化。在训练结束时，我们希望有 embedding 和评分功能，以满足合并我们的知识的目标。

      HogWild-分布式随机梯度下降

      随机梯度下降的分布是一个挑战。如果我们同时通过调整参数来进行训练，以最小化损失函数，就需要某种锁定机制。在传统的多线程开发中，我们通过悲观锁或乐观锁在更新期间锁定数据。锁定会减慢进度，但可以确保结果的正确性。

      幸运的是，「HogWild」这篇论文证明我们不需要锁定机制。我们可以简单地批量读取数据，计算参数调整，并将其保存在共享的参数空间中，而不考虑正确性。HogWild 算法就是这么做的。培训可以分发，每个 HogWild 线程可以更新我们的参数，而不需要考虑其他线程。

      我推荐你阅读这个博客来获取更多关于 HogWild 的信息：https://medium.com/@krishna_d/parallel-machine-learning-with-hogwild-f945ad7e48a4

      分布式训练

      当图形跨越数十亿个节点和数万亿个边时，很难将所有参数都放入一台机器的内存中。如果我们在开始另一个 batch 之前等待每个 batch 结束来完成计算，那也需要很多时间。我们的图太大了，所以，能够同时并行训练和学习参数是很有好处的。这个问题由发布 PBG 论文的 Facebook 团队解决。

      节点按实体类型拆分，然后组织到分区：

      

      图片来源：https://torchbiggraph.readthedocs.io/en/latest/data_model.html

      

      图片来源：https://torchbiggraph.readthedocs.io/en/latest/data_model.html

      

      图片来源：https://www.sysml.cc/doc/2019/71.pdf

      1.节点被划分为 P 个 bucket，边缘被划分为 PxP 个 bucket。基数较小的实体类型不必进行分区。

      2.训练与以下限制条件同时进行：

      对于除第一个外的每个边 bucket（p1；p2），在前一个迭代中对边 bucket（p1；*）或（*；p2）进行训练是很重要的。

      多个边 bucket 可以平行训练，只要它们在不相交的分区集上操作。

      

      图片来源：https://www.sysml.cc/doc/2019/71.pdf

      训练在多台机器上并行进行，每台机器有多个线程。每个线程根据分配的存储 bucket 和数据 batch 计算参数更新。锁服务器根据已建立的约束分配训练 bucket。注意，锁服务器只控制数据 batch 在 HogWild 线程之间的分布，而不控制参数更新。

      PBG embedding 的特点

      知识 embedding 有两种方式：

      1.链接预测

      链接预测通过找到可能连接或即将连接的节点，帮助填补我们知识上的空白

      示例：该图表示客户和客户购买的产品，边缘是采购订单。embedding 可用于生成下一个采购建议。

      2.学习节点的属性

      embedding 可以用作提供给各种分类模型的输入的特征向量。所学的类可以填补我们对对象属性的知识空白。

      使用 MRR/Hits10 评估链路预测

      论文「Learning Structured Embeddings of Knowledge Bases」中描述了这一过程，随后将其作为衡量 embedding 模型在许多其他论文（包括 Facebook PBG）中质量的方法。

      该算法获取测试边缘的子集，并执行以下操作：

      通过用负采样边替换边的首尾来破坏边

      在部分损坏的数据集上训练模型

      从测试数据集中计算边缘的聚合 MRR（Mean reciprocal rank）和 HITS10 度量

      平均倒数秩（Mean reciprocal rank）

      MRR（平均倒数秩）是一种度量搜索质量的方法。我们取一个未损坏的节点，找到距离定义为相似性分数的「最近邻」。我们根据相似性得分对最近的节点进行排名，并期望连接的节点会出现在排名的顶部。如果节点没有倾斜在顶部，MRR 会降低精度分数。

      另一种方法是 Hits10，我们期望损坏的节点出现在前 10 个最近的节点中。

      

      图片来源：https://www.sysml.cc/doc/2019/71.pdf

      PBG 论文表明，在许多数据集上，随着我们将资源分配到训练中，MRR 度量逐渐增加。并行性不会影响排名的质量，但可以节省大量的时间。

      进一步的评估可以通过简单地探索和可视化图形来执行。

      

      图片来源：https://ai.facebook.com/blog/open-sourcing-pytorch-biggraph-for-faster-embeddings-of-extremely-large-graphs/

      上图是由 Freebase 知识图谱构建的 embedding 的二维投影。如我们所见，相似的节点被分在一组。国家、数字、专业科学期刊甚至在精心准备的二维投影图上似乎也有集群。

      知识图模型的局限性

      如上所述的知识图表示的是我们知识的静态快照。它并没有反映知识是如何建立起来的。在现实世界中，我们通过观察时间模式来学习。虽然可以了解节点 A 和节点 B 之间的相似性，但是很难看到节点 A 和三年前的节点 C 之间的相似性。

      例如，如果我们观察森林一整天，我们会发现两棵大红杉之间的相似性。然而，如果没有对森林的长期观察，我们很难理解哪个树苗会长成一棵巨大的红杉树。

      理想情况下，我们需要探索在不同时间点构建的一系列知识图，然后构建 embedding，这些 embedding 将包含这一系列知识图的相似点。

      via：https://www.kdnuggets.com/2019/05/extracting-knowledge-graphs-facebook-pytorch-biggraph.html