使用Facebook的Pytorch的BigGraph从知识图谱
机器学习使我们能够训练一个可以将数据转换为标签的模型，从而把相似的数据映射到相似或相同的标签。
例如，我们正在为电子邮件构建一个垃圾邮件过滤器。我们有很多电子邮件，其中一些标记为垃圾邮件，另一些标记为正常邮件(INBOX)。我们可以构建一个模型，该模型学习识别垃圾邮件。被标记为垃圾邮件的邮件在某种程度上类似于已经标记为垃圾邮件的邮件。
相似性的概念对于机器学习至关重要。在现实世界中，相似性的概念与某个主题相关，它取决于我们的知识。
另一方面，数学模型定义了相似性的概念。通常，我们将数据表示为多维向量，并测量向量之间的距离。
0_LXrVzPbG3uA0gd--
https://www.quora.com/Why-do-we-use-cosine-similarity-on-Word2Vec-instead-of-Euclidean-distance
特征工程是将我们对现实世界中的某个对象的知识转换为数字表示的过程。我们认为相似的对象转化为数字后的向量也会很靠近。
例如，我们正在估算房价。我们的经验告诉我们，房屋是由卧室的数量，浴室的数量，房龄，房屋面积，位置等来定义的。位于同一社区，具有相同大小和房龄的房屋的价格应该大致相同。我们将对房屋市场的了解转化为表征房屋的数字，并用它来估算房屋的价格。
不幸的是，如上所述，手动特征工程在将我们的知识转换为描述性特征的能力方面存在局限性。
有时，知识的使用仅限于相似性原理，而不是对象的确切相似特征。通常，我们对现实世界的了解要比简单的表格所代表的要复杂得多。它通常是相互联系的概念和图形。
嵌入模型使我们能够获取原始数据，并根据我们的知识自动将其转换为特征。
Word2Vec
Word2Vec可能是最著名的嵌入模型，它为单词建立相似度向量。在这种情况下，我们对世界的了解用文字来进行表示，即文字序列。
虽然数十年来，人们尝试使用手动定义的特征来刻画单词，但收效甚微。这些解决方案通常无法扩展到全部知识，也无法在有限的情况下起作用。
托马斯·米科洛夫（Tomas Mikolov）和他在Google的团队决定建立模型时，一切都改变了，该模型基于众所周知的相似性原理进行工作。在相似上下文中使用的词通常相似。在这种情况下，上下文由附近的单词来定义。
0_T7wsEHGyun-cqnyi
单词序列的图形表示。
我们看到的是，只要牢记这些原则，我们就可以通过在预定义窗口（通常为5个单词）内将每个单词与其相邻单词简单地连接起来，从而在文本中构建图形。
现在我们有了一个基于我们的知识连接起来的真实单词对象的图形。
最简单/最复杂的单词表示
我们仍然无法建立任何模型，因为单词没有以表格或向量表示。
如果我们需要将单词转换为数字，那么有一个简单的解决方案。让我们来看看字典，并为每个单词指定其在字典中的位置。
例如，如果我有三个单词：猫(cat)，毛毛虫(caterpillar)，小猫(kitten)。
我的向量表示法如下：cat—[1]，caterpillar—[2]，和kitten—[3]。
不幸的是，这不起作用。通过这样分配数字，我们隐式地引入了单词之间的距离。猫和毛毛虫之间的距离是1，猫和小猫之间的距离是2。这样进行表示就等于，我们说猫比起小猫更像毛毛虫，这与我们的知识是相互矛盾的。
另外一个解决方案也称为独热编码(one-hot encoding)：
cat — [1,0,0]
caterpillar — [0,1,0]
kitten — [0,0,1]
该方法表示所有单词都彼此正交。我们没有单词相似性的先入观念。我们将依靠我们的知识图谱（如上所述）和的单词相似性原理来构建嵌入模型。
在现实世界中，字典的大小远远大于3。字典的维数可能是数万到数百万。这些向量不仅不能真正代表我们的相似性概念，而且它们的体积也很大，无法在实际中使用。
建立词嵌入(word embeddings)
我们的知识图谱为我们提供了非常多的边，每条边都可以解释成输入数据作为边的起点，标签为边的终点。我们正在构建一个模型，该模型试图使用被标签包围的单词来预测单词。通常以两种方式完成。我们要么从某个单词的所有邻居来构造单词向量，要么从某个单词来构造其所有邻居。
0_1vIH7iHHene0u7d6
https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
该模型的详细信息超出我要讲的范围，并且在许多其他文章中都有详细描述。从根本上讲，该团队使用基本的编码器/解码器模型来学习从高维空间（数百万个维）到有限维空间（通常为300个）到高维空间的投影。训练的目的是在压缩过程中保留尽可能多的信息（用最小化交叉熵的方法）。
0_ikyY6V-JYhpfk7Or
http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/
把稀疏，正交，高维的数据空间投影到更密集的低维空间，这一概念是许多其他嵌入训练模型的基础。
该模型通常使用Google，Twitter或Wikipedia数据集等来进行训练。我们消耗世界的知识，以此建立我们的单词嵌入模型。
Word2Vec嵌入的属性
Word2Vec的重要属性是保留单词之间的关系和表示结构关系。
下图显示了国家与首都之间的联系。
0_K4K24XlR-RWIUKAc
或其他不同的概念。
0_2N0COC6bTB2SIWw1
https://www.tensorflow.org/tutorials/representation/word2vec
本质上，它允许像这样对单词进行代数运算：
国王-男人+女人=女王。
使用单词嵌入
单词嵌入可以极大地改善诸如文本分类，命名实体识别，机器翻译等等任务的执行效果。
更多信息：http://www.wildml.com/2015/11/understanding-convolutional-neural-networks-for-nlp/
Node2Vec
Node2Vec（作者：A. Grover and J. Leskovec）是在Word2Vec思想的基础上，对齐次加权图进行分析。本文的思想是通过探索图节点的周围环境来刻画图节点的特征。我们对世界的理解是建立在两个原则的基础上的——同质和结构对等。
同质
相似的节点位于附近。
示例：
-
社交网络-我们与像我们这样的人有更多的联系
-
商业地点-金融公司、医生办公室或营销公司似乎通常位于同一条街上
-
组织结构-同一团队的人有相似的特征
结构对等
不同的社区共享相同的结构：
- 组织结构-虽然团队之间可能存在弱连接，但团队的结构（经理、高级成员、新成员、初级成员）在团队之间重复。
1_LV1J~1
https://arxiv.org/pdf/1607.00653.pdf
为了将这两个原则结合到我们的嵌入中，Node2Vec的作者提出了一种结合广度优先采样和深度优先采样的随机游走方法来捕获同质性和结构等价性。
如我们所见，节点（u）在组（s1、s2、s3、s4）中充当中心，这类似于s6是（s7、s5、s8、s9）的中心。我们通过BFS发现（s1，s2，s3，s4）社区，通过DFS发现（u）<->（s6）相似性。
我们通过探索每个节点的周围环境来了解它们。这种探索将图转换为随机游动产生的大量序列（句子），将BFS和DFS探索结合起来。BFS和DFS的混合由图边的权值和模型的超参数控制。
一旦我们有了完整的序列（句子），我们就可以像应用于文本一样应用Word2Vec方法。它产生了基于我们定义的原则和从图中获得的知识的图节点嵌入。
Node2Vec 性质
Node2Vec表示改进了节点的聚类和分类模型。嵌入中学习到的相似性将有助于欺诈检测等任务。
node2vec生成的Les Misérables共现网络的互补可视化，标签颜色反映了同质（顶部）和结构等价性（底部）。— https://arxiv.org/pdf/1607.00653.pdf
1_LBFW~1
https://arxiv.org/pdf/1607.00653.pdf
Node2Vec在链路预测（link prediction）方面有显著的改进。它能够提高重建图的能力，其中删除了一定比率的边。本文将进一步讨论链路预测评估过程。
知识图谱
下面我们将讨论PYTORCH-BIGGRAPH:一个大规模的图嵌入系统论文（进一步命名为PBG）以及相关论文。
知识图谱是一种特殊的图形类型，它包含已知的实体和不同类型的边。它代表结构知识。
在知识图谱中，节点通过不同类型的关系连接起来。
1_SIM2~1
https://arxiv.org/pdf/1503.00759.pdf
训练的目标是产生代表知识的嵌入。一旦我们有了节点的嵌入，就应该很容易通过特定类型的关系来确定相应的节点在我们的知识图谱中是否是连接的（或应该连接的）。
不同的模型提出了不同的比较嵌入的方法。最简单的模型使用余弦或向量积距离来比较嵌入向量。比较复杂的模型在比较之前对向量的元素应用不同的加权方案。加权方案表示为矩阵，并且特定于关系类型。作为训练的一部分，我们可以学习加权矩阵。
1_Y8SY~1
https://www.sysml.cc/doc/2019/71.pdf
我们需要找到一种方法来度量边之间的相似性得分，并使用该得分来估计这些节点连接的可能性。
知识图谱的表示
知识图谱可以表示为邻接张量。要建立它，我们需要一个平方矩阵来表示每种类型的关系。每个矩阵的列或行数与图形中的节点数相同。通过这种类型的关系，如果这些节点中相互连接，则矩阵的值将是1，否则为0。很明显，这个矩阵非常大，非常稀疏。
为了学习我们的嵌入，我们需要将每个节点转换成固定大小的向量。让我们讨论“好”嵌入的性质。
好的嵌入以图边的形式表示我们的知识。位于“附近”的嵌入向量应该表示更有可能连接的节点。基于此观察，我们将训练我们的模型，使相邻张量中标记为1的连接节点的相似度得分更高，相邻张量中标记为0的连接节点的相似度得分更低。
1_4M22~1
https://arxiv.org/pdf/1503.00759.pdf
我们正在训练我们的嵌入以最小的信息损失从节点嵌入重建 知识图谱的边。
负采样
我们的训练方法有点问题。我们正在尝试使用图数据来区分1（节点已连接）和0（节点未连接）。然而，我们实际拥有的唯一数据是连接在一起的节点。就像只看猫就学会了分辨猫和狗。
负采样是一种通过使用非常简单的观测来扩展数据集并提供更好的训练数据的技术。任何随机选择的节点，如果没有作为我们的图的一部分进行连接，将用标签0表示一个样本数据。出于训练的目的，PBG提出读取图的每条边，然后提出一个负样本，其中一个节点被随机选择的节点替换。
对于每一条边，我们可以指定一个正相似度得分和一个负相似度得分。基于节点嵌入和边关系类型权重计算正相似度得分。用同样的方法计算负相似度得分，但是边的一个节点被损坏并被随机节点替换。
排名损失函数，将在训练期间进行优化。它的构造是为了在图中所有节点和所有关系类型的正负相似度得分之间建立一个可配置的边距（margin）。排名损失是节点嵌入和特定关系权重的函数，通过寻找最小的排名损失进行学习。
训练
现在我们有了训练嵌入模型所需的一切：
-
数据-负边和正边
-
标签-（1或0）
-
优化函数（可以是排名损失、更传统的logistic回归损失或在word2vec中使用的交叉熵softmax损失）
-
我们的参数是用于相似性评分函数的嵌入和权重矩阵。
现在是用微积分来寻找参数-嵌入的问题，优化我们的损失函数。
随机梯度下降
随机梯度下降的实质是逐步调整损失函数的参数，使损失函数逐渐减小。为此，我们以小批量方式读取数据，使用每个批次计算对损失函数参数的更新，以将其最小化。
随机梯度下降有多种方法。PBG论文利用随机梯度下降的一种形式ADAGrad来寻找使损失函数最小化的参数。我强烈推荐这个博客来了解梯度下降的所有类型：http://ruder.io/optimization-gradient-descent/index.html#adagrad
tensorflow和Pythorch等软件包为不同的类型提供了开箱即用的实现。
梯度下降的关键是模型参数的多次更新，直到损失函数最小化。在训练结束时，我们期望能有嵌入和评分函数，以满足我们整合知识的目标。
HogWild-分布式随机梯度下降
随机梯度下降的分布式是一个挑战。如果我们同时通过调整参数来训练以最小化损失函数，就需要某种锁定机制。在传统的多线程开发中，我们在更新过程中通过悲观或乐观锁定来锁定数据。锁定会减慢进度，但会确保结果的正确性。
幸运的是， hogwild paper 证明了我们不需要锁定机制。我们可以简单地批量读取数据，计算参数调整，并将这些数据保存在共享参数空间中，而不考虑其正确性。HogWild算法正是这样做的。训练可以是分布式的，每个HogWild线程可以更新我们的参数，而不考虑其他线程。
我推荐这个博客来获取更多关于HogWild的信息： https://medium.com/@krishna_srd/parallel-machine-learning-with-hogwild-f945ad7e48a4
分布式训练
当图跨越数十亿个节点和数万亿条边时，很难在一台机器的内存中拟合所有参数。如果我们在开始另一批之前等待每一批的结束来完成计算，也需要很多时间。我们的图是如此之大，这将有利于能够同时进行并行化的训练和参数学习。这个问题是由Facebook团队解决的，他们发布了PBG的论文。
节点按实体类型拆分，然后组织为分区：
1_UO0R~1
https://torchbiggraph.readthedocs.io/en/latest/data_model.html
1_H6RW~1
https://torchbiggraph.readthedocs.io/en/latest/data_model.html
1_-C8N~1
https://www.sysml.cc/doc/2019/71.pdf
-
节点被划分为P个bucket，边被划分为PxP个bucket。不必对基数较小的实体类型进行分区。
-
训练与下列限制同时进行：
对于除第一个外的每个边 bucket（p1；p2），在前一个迭代中训练边 bucket（p1；*）或（*；p2）是很重要的。
只要多个边 buckets 在不相交的分区集上操作，它们可以并行训练。
1_VST6~1
https://www.sysml.cc/doc/2019/71.pdf
训练在多台机器上并行进行，并且每台机器有多个线程。每个线程根据分配的bucket和批数据计算参数更新。锁服务器根据建立的约束分发训练 buckets。注意，锁服务器只控制hogwild线程中批数据的分布，而不控制参数更新。
PBG嵌入特性
知识嵌入可以通过两种方式使用：
- 链接预测。
链接预测有助于通过查找可能连接或即将连接的节点来填补我们知识中的空白。
示例：该图表示客户和客户购买的产品。边是采购订单。嵌入可用于形成下一个购买建议。
- 学习节点的属性
嵌入可以用作特征向量作为各种分类模型的输入。所学的类可以填补我们对对象属性的知识空白。
使用MRR/Hits10评估链路预测
这篇论文Learning Structured Embeddings of Knowledge Bases描述了这个过程，后来被用作衡量嵌入模型质量的方法，在包括Facebook PBG在内的许多其他论文上都有报道。
算法获取测试边的子集并执行以下操作：
-
通过将边的开始或结束替换为负采样边来损坏边。
-
在部分损坏的数据集上训练模型
-
计算测试数据集边的聚合MRR和Hits10度量。
平均倒数排序(Mean reciprocal rank)
MRR或Mean reciprocal rank是衡量搜索质量的指标。我们选取一个未损坏的节点，以距离作为相似度得分来寻找“最近邻”。我们根据相似度得分对最近的邻居进行排序，并期望连接的节点出现在排序的顶部。MRR会在节点没有倾斜到顶部的情况下降低精度得分。
另一种方法是Hits10，我们期望损坏的节点出现在前10个最近的邻居中。
1_BM_X~1
https://www.sysml.cc/doc/2019/71.pdf
PBG的研究表明，在许多数据集上，MRR指标随着我们将资源分配到训练中而逐渐增加。并行性不会影响排名质量，但可以节省大量时间。
可以通过简单地探索和可视化图来执行进一步的评估。
0_RN-J~1
上面的图像是根据Freebase知识图谱构建的嵌入的二维投影。如我们所见，相似的节点被组合在一起。即使在精心准备的二维投影图上，国家、数字、科学期刊行业似乎也有集群。
知识图谱模型的局限性
如上所述的知识图谱表示的是我们知识的静态快照。它并不能反映知识是如何建立起来的。在现实世界中，我们通过观察时间模式来学习。虽然可以学习节点A和节点B之间的相似性，但就像3年前一样，很难看到节点A和节点C之间的相似性。
例如，如果我们看一天森林，我们会看到两棵大红杉之间的相似性。然而，如果没有对这片森林的长期观察，很难理解哪棵小树会长成一棵大红杉树。
理想情况下，我们需要探索在不同时间点构建的一系列知识图谱，然后构建嵌入，这将包含代与代之间的相似性。
原文链接：https://towardsdatascience.com/extracting-knowledge-from-knowledge-graphs-e5521e4861a0
欢迎关注磐创AI博客站：
http://panchuang.net/
sklearn机器学习中文官方文档：
http://sklearn123.com/
欢迎关注磐创博客资源汇总站：
http://docs.panchuang.net/
