论文阅读|NeurIPS 2013：（TransE）Embedding Embedding for Modeling Multi-relational Data
- 摘要
我们研究了低维向量空间中多关系数据的嵌入实体和关系问题。我们的目标是提出一个易于训练的规范模型，它将包含一组较少的参数，并且可以扩展到非常大的数据库，因此，我们提出了TransE，该方法可以将对关系的建模在低维度的实体表征空间上视为一种翻译操作。尽管它很简单，但这个假设被证明是很强大的，因为广泛的实验表明TransE在两个知识库上的的链接预测显著优于STOA方法。此外，它还在一个拥有1M个实体，25K个关系和超过17M个训练样本的大数据集上成功训练。
- 介绍
多关系数据是指节点对应于实体和边的形式（head，label，tail）（记做(h，l，t)），其中每一个都表示在实体head和tail之间存在一个关系label。多关系数据模型在许多领域中都扮演了关键角色。例如社会网络分析，其中实体是成员，边（关系）是友谊/社会关系链接；推荐系统中的实体是用户和产品，关系是购买、评级、评论或搜索产品；或知识库（KBs）例如Freebase，Google Knowledge Graph或GeneOntology。其中每个知识库中的实体都表示一个现实世界的抽象概念或具体实体，而关系是谓词，表示涉及其中两个概念的事实。我们的工作是建模来自知识库（本文中的Wordnet和Freebase）多关系数据，目标是提供一个有效的工具，通过自动添加新的事实来完成它们，而不需要额外的知识。
建模多关系数据 一般来说，建模过程归结为提取实体之间的局部或全局连接模式，并通过使用这些模式来泛化特定实体与所有其他实体之间的观察到的关系来进行预测。单一关系的位置概念可能是纯粹的结构性的，例如在社会网络中我朋友的朋友就是我的朋友，但也可能会依赖其他实体，例如喜欢星球大战IV的人也喜欢星球大战V，但他们可能喜欢或不喜欢泰坦尼克号。与单关系数据相反，在单关系数据中，可以在对数据进行一些描述性分析之后作出特定但简单的建模假设，关系数据的困难在于，局部性的概念可能同时涉及不同类型的关系和实体，因此对多关系数据建模需要更通用的方法，这些方法可以选择同时考虑所有异构关系的适当模式。
随着用户/项目聚类或矩阵分解技术在协同过滤中表示单个数据中实体的连通性模式之间的非平凡相似性的成功，正如所指出的，大多数现有的多关系数据方法都是在从潜在属性进行关系学习的框架内设计的；也就是说，通过学习和操作组成部分（实体和关系）的潜在表示（或嵌入）。从这些方法的自然扩展到多关系领域，例如随机模块模型的无参数贝叶斯扩展，以及基于张量分解或集体矩阵分解的模型，在贝叶斯聚类框架或基于能量的框架中，许多最新的方法都集中于提高模型的表达性和通用性，用于在低维空间中学习实体的潜入。这些模型更强的表达能力是以模型复杂性的大幅增加为代价的，这将导致难以解释的建模假设和更高的计算成本。此外，这些方法可能会受到过度拟合的影响，因为这种大容量模型的适当正则化很难设计，或者不拟合，因为有许多局部极小值的非凸优化问题需要解决来训练它们。事实上，[2]中显示了一个更简单的模型(线性的而不是双线性的)在具有相对大量不同关系的多个多关系数据集上取得了几乎和最有表现力的模型一样好的性能。这表明，即使在复杂和异构的多关系领域中，简单而适当的建模假设也可以在准确性和可伸缩性之间实现更好的权衡。
关系作为嵌入空间中的翻译 在本文中，我们引入transE，一个可以学习实体的低维向量嵌入的基于能量的模型。在TransE中，关系被表示成“向量空间中的翻译”：如果成立，那么尾实体
的嵌入加上某个依赖于关系
的向量应该接近头实体h的嵌入。我们的方法依赖于一组简化的参数，因为对于每个实体和每个关系它只学习一个低维向量。
我们基于翻译的参数化背后的主要动机是层次关系在KB中非常常见，而翻译是表示它们的自然转换。的确，考虑到树的自然表现（即，维度2中节点的嵌入），兄弟节点彼此靠近，给定高度的节点被组织在x轴上，父-子关系对应于y轴上的翻译。由于空翻译向量对应于实体间的等价关系，因此模型也可以表示兄弟关系。因此我们选择使用每个关系的参数预算（一个低维向量）来表示我们认为的KB中的关键关系。另一个次要的动机来自于最近的工作[8]，作者从自由文本中学习单词嵌入，和一些一对一的不同类型的实体之间的关系，这样的国家与城市之间的“...的首都”，是（巧合的是而不是希望是）在嵌入空间中被模型表示成翻译。这表明可能存在嵌入空间，在这些空间中，不同类型的实体之间的一对一关系也可以通过翻译来表示。我们的模型的目的是强制这种嵌入空间的结构。
我们在第4节中的实验证明，这个新模型虽然简单并且其架构主要是为层次结构建模而设计的，但最终在大多数类型的关系上都很强大，并且在真实世界KBs上的链接预测方面显著优于STOA方法。此外，它的轻量级参数使得它能够在包含1M个实体、25k个关系和超过17M个训练样本的大规模分割Freebase上成功训练。
- 基于翻译的模型
给定一个训练集S，其中三元组由两个实体
（实体集合）和一个关系
（关系集合）组成，我们的模型学习实体和关系的向量嵌入。嵌入从
中取值（
是一个模型超参数）并且用黑体字符记做相同的字母。我们模型背后的基本思想是由
标签的边引入的函数关系对应着嵌入的翻译，即当
成立时我们想让
（
应该是
最近的邻居），否则
应该远离
。在基于能量的框架下，对于不同的度量
，一个三元组的能量等于
，我们认为这是
或
范数。
为了学习这样的嵌入，我们在训练集上最小化一个基于边缘的排序准则：
其中表示
的正的部分，
是一个边缘超参数，并且
根据公式2构造的被破坏的三元组由训练三元组组成，其中头或尾被一个随机实体替换(但不是同时替换)。损失函数(1)倾向于训练三元组的能量值比损坏三元组的能量值更低，因此这也是预期准则的自然实现。注意，对于一个给定实体，不管当它是作为三元组的头还是尾出现时，它的嵌入向量都是相同的。
优化是通过随机梯度下降（小批量模式），在可能的和
上进行的，附加约束是嵌入的
范数是1（标签嵌入
没有正则化或范数约束）。这一约束对我们的模型是重要的，就像它对于以前的基于嵌入的方法[3，6，2]那样，因为它防止了训练过程中通过人为地增加实体嵌入规范来最小化
。
算法1描述了具体的优化流程。所有实体和关系的嵌入首先按照[4]中提出的随机过程进行初始化。在算法的每次主要迭代中，首先对实体的嵌入向量进行归一化。然后，从训练集中采样出一个三元组的小集合，并将作为小批量的训练三元组。对于每一个这样的三元组，随后我们会采样一个单独的破坏三元组。然后以恒定的学习速率梯度更新参数。该算法将根据其在验证集上的性能停止。
- 相关工作
第1节描述了关于嵌入KB的大量工作。我们在这里详细说明了我们的模型与[3](结构化嵌入或SE)和[14]之间的联系。
SE将实体嵌入，将关系嵌入两个矩阵
和
，使得
对于破坏三元组
较大（否则较小）。基本思想是，当两个实体属于同一个三元组时，它们的嵌入在某个子空间内应该靠的很近，这取决于它们之间的关系。对头部和尾部使用两种不同的投影矩阵是为了解释关系
可能的不对称。当不同的函数采用形式：
，其中
（即
是一个规范），那么嵌入大小为k+1的SE比我们的嵌入大小为k的模型更具有表示能力，因为k+1维中的线性算子可以在k维的子空间中复制仿射变换（通过约束所有嵌入的k+1维等于1）。SE，以
为单位矩阵，取
来再现翻译，则等价于TransE。尽管我们的模型表达能力更低，但在我们的实验中，我们仍然取得了比SE更好的表现。我们认为这是因为（1）我们的模型是以一种更直接的方式来表示关系的真实属性，并且（2）在嵌入模型中优化是困难的。对于SE来说，更强的表现力似乎更等同于不匹配，而不是更好的性能。训练错误(第4.3节)倾向于确认这一点。
另一个相关的方法是神经张量模型（Neural Tensor Model）[14]。该模型的一个特例对应于学习以下形式的学习分数（被破坏的三元组的分较低）：
其中，
，
，它们都依赖于
。
如果我们以欧式距离的平方来考虑TransE的不同函数，有：
考虑我们的规范约束和排序标准(1)，其中
在比较损坏三元组时没有起到任何作用，因此我们的模型涉及到用
对三元组进行评分，因此对应于模型[14]（公式(3)），其中
为单位矩阵，并且
。我们不能用这个模型进行实验(因为它与我们的模型同时发布)，但TransE的参数要少得多：这可以简化训练，防止拟合不足，并可以弥补较低的表达能力。
然而，TransE的简单表述，可以看作是对一系列双向交互进行编码（例如开发版本），包含缺陷。对于建模数据，
，
和
之间的三向关系是非常重要的，我们的模型可能会失败。例如，在小规模亲属数据集[7]上，TransE在交叉验证（精确召回曲线下的区域测量）方面的表现无法与最先进的交叉验证[11,6]相媲美，因为这种三元交互在本例中至关重要(参见[2]中的讨论)。尽管如此，我们在第4节的实验表明，为了处理像Freebase这样的通用大型KB，应该首先像TransE那样正确地建模最频繁的连接模式。
- 实验
我们的方法，TransE，是根据从Wordnet和Freebase（表2给出了它们的统计数据）中提取的数据进行评估的，与文献中最近的几种方法进行对比，这些方法在各种基准测试中获得了最佳的当前性能，并且可以扩展到相对较大的数据集。
1 数据集
Wordnet 这个知识库旨在生成直观可用的词典和辞典，并支持自动文本分析。它的实体(称为synsets)对应于单词的意义，而关系定义了它们之间的词汇关系。我们考虑了[2]中使用的数据版本，后面我们将它记做WN。三元组的例子是(_socre_NN_1,_hypernym,_evaluation_NN_1)或者(_score_NN_2,_has_part,_musical_notation_NN_1)。
Freebase Freebase是一个庞大且不断增长的数据库；它包含大约12亿个三元组和超过8000万个实体。我们用Freebase创建了两个数据集。首先，为了做一个小数据集来进行实验，我们选择了同样存在于Wikilinks数据库中并且在Freebase中至少有100次提及的实体子集(包括实体和关系)。我们还删除了类似'!/people/person/nationality'这种相比于'/people/person/nationality'只是把头和尾翻转了的关系。结果剩余592213个三元组，其中有14951个实体和1345个关系，这些三元组被随机分割，如表2所示。这一数据集在本节剩余部分被记做FB15k。我们还想有一个大规模数据集，以便在大规模上测试TransE。因此，我们通过选择最常出现的100万个实体，从Freebase中创建了另一个数据集。这导致了大约25k个关系和超过1700万的训练三元组，我们称之为FB1M。
2 实验设置
评估协议 对于评估，我们采用与[3]相同的排序过程。对于每一个测试三元组，头依次被字典的每个实体移除并替换。模型首先计算出这些被破坏的三元组的差异性(或能量)，然后按升序进行排序；最终存储正确实体的秩序。当去掉尾实体而不是头实体时，整个过程重复进行。我们记录了这些预测排名的mean rank和[email protected]，即排名前10的正确实体的比例。
References
[1] K. Bollacker, C. Evans, P . Paritosh, T. Sturge, and J. Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008.
[2] A. Bordes, X. Glorot, J. Weston, and Y . Bengio. A semantic matching energy function for learning with multi-relational data. Machine Learning, 2013.
[3] A. Bordes, J. Weston, R. Collobert, and Y . Bengio. Learning structured embeddings of knowledge bases. In Proceedings of the 25th Annual Conference on Artificial Intelligence (AAAI),2011.
[4] X. Glorot and Y . Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the International Conference on Artificial Intelligence and Statistics(AISTATS)., 2010.
[5] R. A. Harshman and M. E. Lundy. Parafac: parallel factor analysis. Computational Statistics & Data Analysis, 18(1):39-72, Aug. 1994.
[6] R. Jenatton, N. Le Roux, A. Bordes, G. Obozinski, et al. A latent factor model for highly multi-relational data. In Advances in Neural Information Processing Systems (NIPS 25), 2012.
[7] C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda. Learning systems of concepts with an infinite relational model. In Proceedings of the 21st Annual Conference on Artificial Intelligence (AAAI), 2006.
[8] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems (NIPS 26), 2013.
[9] G. Miller. WordNet: a Lexical Database for English. Communications of the ACM, 38(11):39–41, 1995.
[10] K. Miller, T. Griffiths, and M. Jordan. Nonparametric latent feature models for link prediction. In Advances in Neural Information Processing Systems(NIPS 22), 2009.
[11] M. Nickel, V . Tresp, and H.-P . Kriegel. A three-way model for collective learning on multi-relational data. In Proceedings of the 28th International Conference on Machine Learning(ICML), 2011.
[12] M. Nickel, V . Tresp, and H.-P . Kriegel. Factorizing Y AGO: scalable machine learning for linked data. In Proceedings of the 21st international conference on World Wide Web (WWW),2012.
[13] A. P . Singh and G. J. Gordon. Relational learning via collective matrix factorization. In Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD), 2008.
[14] R. Socher, D. Chen, C. D. Manning, and A. Y . Ng. Learning new facts from knowledge bases with neural tensor networks and semantic word vectors. In Advances in Neural Information Processing Systems (NIPS 26), 2013.
[15] I. Sutskever, R. Salakhutdinov, and J. Tenenbaum. Modelling relational data using bayesian clustered tensor factorization. In Advances in Neural Information Processing Systems (NIPS 22), 2009.
[16] J. Weston, A. Bordes, O. Y akhnenko, and N. Usunier. Connecting language and knowledge bases with embedding models for relation extraction. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013.
[17] J. Zhu. Max-margin nonparametric latent feature models for link prediction. In Proceedings of the 29th International Conference on Machine Learning(ICML), 2012.