本文介绍的是ICDE 2020入选论文《AutoSF: Searching Scoring Functions for Knowledge Graph Embedding》，作者来自中国香港科技大学和第四范式。
作者 | 张永祺、姚权铭
| 戴文渊、陈 雷
- 论文地址：https://arxiv.org/pdf/1904.11682.pdf
- 代码地址：https://github.com/yzhangee/AutoSF
- 幻灯片地址：https://github.com/yzhangee/research/blob/master/ICDE2020_slides.pdf
1
简介
评分函数（Scoring Function，SF）是衡量知识图谱（Knowledge Graph，KG）中三元组可编程性的重要指标，已成为知识图谱嵌入的关键。近年来，大量的评分函数被设计出来，用于捕捉知识图谱中的各种关系。然而，由于关系可能表现出复杂的模式，而这些模式在训练前很难推断，因此在现有的基准数据集上，没有一个能比其他模式表现得更好。
本次工作年来自动化机器学习（AutoML）的启发，提出了一种自动设计和发现知识图谱嵌入（KG Embedding，KGE）中更好SF的AutoSF算法。通过使用一个由滤波器和具有特定领域知识的预测器增强的渐进贪婪搜索算法，可以有效地设计出新的、与数据相关、且性能优于人类最新设计模型的SF。边预测和三元组分类结果表明，AutoSF搜索的评分函数具有KG依赖性，且比人最新设计的评分函数性能更优。
2
背景介绍
知识图谱(KG)作为一种特殊的以实体为节点、以关系为边的图结构，可提供更高效的搜索结果、发现节点的潜在特性、并启发了如结构化搜索等许多下游应用，对数据挖掘和机器学习都具有重要的意义。其目标是尽可能的保存原始图谱信息，改善推荐、问答等下游机器学习任务。在知识图谱中，每条边都表示为一个三元组，其形式（头实体、关系、尾实体）表示为（h、r、t）。近年来广受关注的知识图谱嵌入（KGE）是用于解决如何量化三元组合理性的有效方法之一，且极具前景。在一组三元组中，KGE可学习实体和关系的低维向量表示，从而使三元组的合理性可以量化。评分函数基于嵌入返回（h，r，t）的评分，用于度量合理性。一般来说，SF是由人类设计和选择的，它对学习嵌入系统的质量有着重要的影响。
知识图谱示例
自从知识图谱嵌入发明以来，学术界提出了许多评分函数。例如知名的TransE和相关拓展模型TransH、TransR，将嵌入向量投影到不同的空间，并使嵌入能够对一对多、多对一或多对多的关系建模。这些模型被归类为平移距离模型（Translational Distance Models，TDMs）。然而，TDMs表达能力不强，实证性能不如其他模型。RESCAL、DistMult、ComplEx、Analogy和最近提出的SimplE使用双线性函数h⊤Rt来建模三元组的合理性，其中R是与关系嵌入相关的平方矩阵。这些模型属于双线性模型BiLinear Models（BLMs）。不同的BLMs使用不同的约束条件对关系矩阵R进行正则化，以适应不同的数据集。受深度学习的启发，MLP、NTM、Neural LP和convE等神经网络模型（Neural Network Models，NNMs）也被用作SFs。尽管神经网络功能强大，表达能力强，但由于没有很好的正则化，NNMs在KGE中的性能并不理想。
在现有的SF中，基于BLM的SF是最有效的，这一点可以从最新的论文和关于表现力的理论保证中看出。然而，由于不同的KG在关系上有不同的模式，能够很好适应一个KG的SF在其他KG上的表现可能不一致，所以设计新的SF以超过最先进的SF是一个挑战，如何为某个KG选择、设计一个好的SF更是难上加难。
3
本次工作的方法
近年来，自动化机器学习（AutoML）因可大幅降低机器学习的门槛和人力成本受到了学术界和工业界的广泛关注。其在超参数优化、模型选择、神经网络搜索和特征工程等方面显示出其强大的功能。近年来很热门的神经网络搜索算法（Neural architecture search，NAS），设计出的模型，可以比人类设计的网络具有更少的参数和更好的性能。
自动化机器学习（AutoML）示意图 [Yao et.al. arvix 2018]
受AutoML的启发，此次工作提出了自动评分函数（AutoSF），可以自动搜索给定KG的SF,其不仅可以适应不同的KG，还可降低门槛和成本。然而，要实现上述目标并非易事，其中需要考虑两个重要方面：一是搜索空间，它有助于找出目标问题建模的重要性质；二是搜索算法，它决定了在空间搜索的效率。
该工作的解决思路是：针对不同的KG 结构自适应搜索调整BLMs，从而设计出新的数据相关的SF。此外，如何利用KG领域特有的性质，来帮助AutoSF的搜索是非常重要的。我们首先在常用的SF上确定一个统一的表示，用来建立AutoSF的搜索空间。然后，我们提出一个贪婪算法来有效地搜索SF，并通过滤波器和预测器进一步加快了算法的速度，避免了重复训练具有相同表达能力的SF，有助于在模型训练前的搜索过程中移除效果差的候选对象。
具体而言，不同的SF对KG中不同关系的建模能力是有区别的，如下表所示，DistMult只能针对对称关系建模，而其他几种SF对非对称，反对称等关系有着不同建模能力。同时他们的表达形式也是有区别的。
为了建立有效的搜索空间，AutoSF首先针对表中的几种BLM建立了统一的表达形式，即不同SF都可以表达成的形式，其中h和t为头尾实体的嵌入表达，R是一个跟关系嵌入相关的方阵，而这些SF的区别就在于R的形式不同。如下图所示，这些SF的R都可以抽象成4x4的分块矩阵，区别主要在如何将关系嵌入r填入其中每一块，及它们的正负号。基于此观察，AutoSF抽象除了下图(e)所示的搜索空间，可以有效覆盖已知的BLM，同时有能力探索新颖的模型。
考虑到这个搜索空间中有个不同结构，而训练和评估每一个结构都需要花费数十分钟的时间，如何快速有效地搜索更好的结构，是搜索算法所需要关心的问题。
AutoSF首先利用贪婪算法，从简单模型渐进搜索更复杂的模型。
为进一步提高搜索效率，我们提出一个特殊的滤波器，可以把不满秩的矩阵，以及等价的矩阵结构过滤掉，避免在这些不好的、等价的模型上花费时间去评估。同时，为了挖掘KG中对称性等重要性质，采用预测器的技术，从矩阵结构提取对称相关的特征（如下图），再利用评估过的结果，学习特征与效果之间的映射，从而可以只利用矩阵结构，选出更值得训练的模型。
基于贪心算法，滤波器，预测器的搜索算法，使得AutoSF可以在仅搜索上百个模型的基础上，就能找到比现有模型更好的SF。
该工作的贡献在于：
- 首先，该工作对现有的SF进行了重要的观察，使我们能够以统一的形式表示基于BLM的SF。在统一表示的基础上，将SF的设计表示为AutoML问题（AutoSF），并建立相应的搜索空间，涵盖了人类设计的优秀SF，且足够广泛。
- 其次，该工作发现不同的KG在对称、不对称、逆等关系上具有不同的性质，因此对KGE模型进行领域特定分析，并设计约束以有效地指导后续的空间搜索。
- 第三，该工作提出了一个渐进贪婪算法来搜索空间，通过建立一个滤波器以避免训练冗余的SF，并建立具有特定对称相关特性（SRF）的预测器以选择有效的SF。该算法通过捕获候选SF的特定领域属性，显著减小搜索空间的大小。
- 最后，在五个流行的链接预测和三重集分类任务基准上的实验结果表明，由AutoSF搜索的SF优于由人类设计的最新SF。此外，搜索到的SF具有KG依赖性。我们进一步对搜索到的SF进行了案例研究，为分析KG提供了方法，且为以后的研究提供了更好的理解。
4
实验结果
该工作在五个流行的链接预测和三重集分类任务基准上进行了实验。
验证AutoSF的有效性
下图中显示了AutoSF和当前最先进SF的测试性能比较，可以看出，在BLMs中没有绝对的赢家。
此外，论文中绘制了用AutoSF搜索到的最佳SF和基准模型DistMult、Analogy、ComplEx、SimplE的学习曲线。如下图所示，搜索到的SF不仅优于基线，而且收敛速度更快，这可能是因为这些SF能够更好地捕获这些数据集中的关系。
Fig. 4. Comparison on clock time (in hours) of model training v.s testing MRR between search SFs (by AutoSF) and human-designed ones.
验证AutoSF的特殊性
为了验证搜索到的SFs对KG具有依赖性且是新颖的，我们将其绘制在下图中。很明显，这些SF是不同的，而且它们是不等价的。
如下表所示， WN18和FB15k有许多对称、反对称关系和逆关系对，在它们上面搜索的最佳SF非常相似并且具有相同的对称性特征。其他三个数据集更真实，包含的对称、反对称和逆关系较少，因此具有不同的对称特征，这也反应了预测器的重要性。
验证AutoSF的效率
该工作将AutoSF与随机搜索和Bayes算法、以及一个一般近似器进行了比较。如下图所示，一般近似器的性能比BLM差得多，因为它太灵活，无法考虑领域特定的约束，以及容易过拟合。对于BLM的设置，Bayes算法可以提高随机搜索的效率，但却很容易陷入局部最优，而且没有考虑KG的领域特有性质。综合来看，AutoSF是最高效的，且具有最佳任意时间性能。
5
结语
本文提出了一种自动设计和发现KGE中更好SF算法AutoSF。通过使用一个由滤波器和具有特定领域知识的预测器增强的渐进贪婪搜索算法，AutoSF可以在巨大搜索空间中有效地设计出与KG相关的、新的、优于人类的SF。搜索算法中的每一个分量都是有意义的，并且搜索对于超参数不敏感。
在未来的工作中，一个有希望的方向是探索如何在特定领域约束下有效地搜索基于神经网络模型的SF。AutoSF中使用的贪婪算法在某种程度上限制了对搜索空间的探索，这是一个有待解决的潜在问题。早停法等快速评估方法可以与该工作提出的方法相结合，以进一步提高搜索效率。
