论文导读 | 高效知识图谱精度评估

图谱学苑 2021-05-29

2950

编者按：

本文是2019年发表在VLDB上的一篇文章，主要介绍了对大规模知识图谱的质量评估方式。

对于大规模知识图谱的准确率评估往往需要人们从图谱中进行抽样并人工检查，因此如何在保证评估的有效性的同时，尽量减少人工评估的成本成为了知识图谱构建及下游应用面临的关键问题之一。文章提出了一种基于“聚类抽样”思想的评估框架，可对静态图谱和演化图谱进行评估。经实验证实，该方式有效地减少了人工评估的成本，且评估的有效性可经统计理论验证。

论文地址：

https://dl.acm.org/doi/abs/10.14778/3342263.3342642

（或点击文末“阅读原文”跳转）

问题定义

在过去几年中，大规模知识图谱越来越多，但知识图谱的构造过程还远不够完美，如知识图谱中可能存在着许多不正确的实例。这个问题虽然重要，但现在却鲜有研究。

知识图谱的正确率是指知识图谱中正确的三元组所占的比例，所谓正确是指三元组表示的关系与真实世界相符。通常，我们只能依靠人工来判断一个三元组是否正确，但这在大规模的知识图谱上的成本代价是极其昂贵的，因此，现在的评估方式往往先对知识图谱进行抽样，然后对抽样样本进行评估，以此近似替代知识图谱的准确率。最简单的抽样方式即简单随机抽样，但以此种方式抽取的样本数量较少，就会导致整体的准确率评估出现较大的偏差，反之，则会带来昂贵的评估成本。

另一方面，现代知识图谱的实时更新性，导致其准确率也在变化，因此如何对知识图谱进行增量评估也是一个较为重要的问题。

问题定义

文章首先明确了问题的一些基本概念：

（1）知识图谱（G）即为三元组的集合：

,其中，(s, p,o)分别代表了三元组中的（主语，谓词，宾语）。

（2）实体簇（G[e]）即为知识图谱具有相同实体（e）作为主语的三元组的集合：

。

（3）实体集合（E）即为知识图谱中的实体构成的集合：

。

（4）三元组插入批次（D）即为知识图谱每次更新时插入的三元组集合：

，其中

为

中实体e对应的实体簇：

（5）知识图谱的正确率

定义为知识图谱中正确三元组所占的比例：

。其中

研究方法

(1)灵感来源及整体框架

文章首先从人工评估的过程出发，利用两个具体的评估过程的实例，发现了不同评估实例间的差异及可进行改进的策略。如下图所示：

任务一中每个三元组都包含不同的实体，当人工评估时，首先需要根据每个实体找到其相应的现实世界的资源（后文称该子任务为实体识别），然后根据资源进行实体关系的评估（后文称该子任务为关系验证）。这里，由实体匹配资源就是一个非常耗时的过程。而任务二中的每个三元组均包含相同的实体，这样只需要进行一次实体资源的匹配过程，因此极大的减少了评估时间。

受到上述例子的鼓舞，文章提出一种基于“聚类抽样”的迭代评估框架。该框架帮助用户迭代地进行抽样和评估，直到满足用户自定义的错误阈值，避免了过度取样和人工评估的浪费。其中的聚类抽样方法，充分利用了上述评估过程的特点，既保证了评估的有效性，又减少了人工评估的成本，并在数学上给出了抽样样本的大小。

评估框架的整体结构如下图：

该框架包含静态评估和动态评估两个子程序，其中静态评估可分为四个步骤，首先使用一种抽样策略获得一批抽样样本，然后将抽样样本放入抽样池中进行人工评估，之后对上述批样本进行准确率评估，最后判断评估结果是否符合用户预期，如果符合则导出结果，否则迭代上述过程。而动态评估则使用有效的增量评估方法进行评估。

（2）抽样策略详述

1）约束条件

抽样策略作为整个评估框架的核心，文章首先给出了抽样策略需要满足的两个条件，即无偏性

和

倍的置信区间（

，假设n个变量是独立同分布的）。其中，

是根据抽样策略 D 得到的关于G的一个子集G’

上的准确率的估计量，又将

记为MOE 。然后，将静态图谱上的抽样样本的评估成本转换为一个最优化问题：

其中，e是给定的MOE 的上界。同理，演化图谱（只考虑三元组批量插入）的评估成本问题即可转化为：

其中，成本函数充分考虑了上述实例所揭示的特征，将其定义为

， E’是G’ 上的实体集合，C1、C2 分别是实体识别过程和关系验证过程的平均消耗。

2）静态图谱评估

对于静态图谱的评估，文章将抽样策略分为基于三元组的和基于实体的两类。其中前者采用简单随机抽样（SRS）策略，后者则设计了三种不同的聚类抽样（CS）策略。

以简单随机抽样为例，下图展示了使用此种方式可以保证无偏性，且可得到理论的采样数量与知识图谱大小无关、而只与图谱的准确率有关的结论。这一结论说明理论采样数量并不会随着知识图谱规模的扩张而无限增大，这表明了采样在实际应用中的可行性。需要注意的是，这个理论采样数量并不是实际中一次性采样的数量，因为公式中的μ是未知的。这个公式的意义在于，在迭代过程中，可以通过判断采样数量是否达到了理论最小采样数量，来确定迭代是否可以停止。

而三种聚类抽样策略如下表所示（策略无偏性和置信区间的证明请参考论文1）：

策略名称	策略描述
随机聚类抽样（RCS）	从G中随机选择n个实体簇
加权聚类抽样（WCS）	从G中依概率选择实体簇，概率为每个实体簇大小在G中所占的比例
两阶段加权聚类抽样（TWCS）	在第一阶段，使用WCS选择实体簇；在第二阶段，从第一阶段得到的每个实体簇中，随机选取个样本，其中是第个实体簇的大小，m是给定的从每个实体簇中可抽取最大样本量。

此外，文章还指出可应用分层抽样（Stratification）策略对上述策略进一步优化。

3）演化图谱评估

对于演化知识图谱的评估，文章提出了两种增量抽样评估方式，希望能够利用尽可能多的已标注样本对新图谱的准确率进行评估。第一种方法借鉴了经典水塘抽样（RS）的思路，将增量batch中每个实体的所有元组视为整体，根据三元组个数进行加权，计算key值确定选取的样本，并通过理论分析确定新抽取的样本数量不会太多。第二种是分层增量评估（SS），将图谱的增量视为一个单独的层，在其上使用两阶段加权抽样后与之前若干层的结果加权，直到置信区间小于阈值。这种方法的优点在于完全利用了前面所有的评估结果，因而效率更高。