源自：软件学报     作者：蒋逸 张伟 王佩 张馨月 梅宏
摘要
知识图谱是一种基于图的结构化知识表示方式.如何构造大规模高质量的知识图谱, 是研究和实践面临的一个重要问题.提出了一种基于互联网群体智能的协同式知识图谱构造方法.该方法的核心是一个持续运行的回路, 其中包含自由探索、自动融合、主动反馈3个活动.在自由探索活动中, 每一参与者独立进行知识图谱的构造活动.在自动融合活动中, 所有参与者的个体知识图谱被实时融合在一起, 形成群体知识图谱.在主动反馈活动中, 支撑环境根据每一参与者的个体知识图谱和当前时刻的群体知识图谱, 向该参与者推荐特定的知识图谱片段信息, 以提高其构造知识图谱的效率.针对这3个活动, 建立了一种层次式的个体知识图谱表示机制, 提出了一种以最小化广义熵为目标的个体知识图谱融合算法, 设计了情境无关和情境相关两种类型的信息反馈方式.为了验证所提方法及关键技术的可行性, 设计并实施了3种类型的实验: 仅包含结构信息的仿真图融合实验、大规模真实知识图谱的融合实验, 以及真实知识图谱的协同式构造实验.实验结果表明, 该知识图谱融合算法能够有效利用知识图谱的结构信息以及节点的语义信息, 形成高质量的知识图谱融合方案; 基于“探索-融合-反馈”回路的协同方法能够提升群体构造知识图谱的规模和个体构造知识图谱的效率, 并展现出较好的群体规模可扩展性.

图 1 基于群体智能的知识图谱构造框
为了验证所提方法及关键技术的可行性, 我们设计并实施了3种类型的实验: 仅包含结构信息的仿真图融合实验、大规模真实知识图谱的融合实验以及真实知识图谱的协同式构造实验. 第1类实验的目的是为了观察本文提出的知识图谱融合算法对图结构信息的利用能力; 第2类实验的目的是为了验证算法对图结构信息和节点语义信息的融合能力; 第3类实验的目的是为了考察本文提出的协同式知识图谱构造方法的可行性.
为了实施第3类实验, 我们开发了一个支持“探索-融合-反馈”回路的多人在线知识图谱构造环境, 并分别在1、2、4、8人规模的参与者群体中进行了真实的知识图谱构造实验. 实验结果表明: (1) 本文提出的知识图谱融合算法能够有效利用知识图谱的结构信息以及节点的语义信息, 形成高质量的知识图谱融合方案(在两个真实知识图谱融合数据集上, 相比较目前最好的知识图谱融合算法, 本文算法在Hit@1指标上分别实现了2.24%和11.4%的提升); (2) 基于“探索-融合-反馈”回路的协同方法能够提升群体构造知识图谱的规模和个体构造知识图谱的效率, 并展现出较好的群体规模可扩展性(在相同时间内, 相比较单人独立构造知识图谱, 8人协同构造形成的群体知识图谱的规模提升了约11倍, 且参与者的单人构造效率提升了约1.5倍).

1 相关工作
1.1知识图谱的构建
知识图谱最早可以追溯到20世纪60年代的语义网络(semantic network)以及20世纪70年代的专家系统(expert system). 在这一时期, 领域专家是知识的主要来源, 知识图谱主要通过单一个体或小规模群体手工构造的方式完成. 2000年左右, Tim Berners-Lee提出了语义网(semantic Web)和关联数据(linked data)的概念[2], 其目是为互联网中存在的海量数据信息提供一种标准的描述框架, 从而促成大规模知识的结构化表示、互联与共享. 2012年, 谷歌正式提出了知识图谱(knowledge graph)的概念, 将其用于语义化搜索, 展现出泛在的应用前景. 在此之后, 知识图谱得到了工业界和学术界的广泛关注.
知识图谱在实践和研究中的一个重要问题是: 如何构造大规模高质量的知识图谱. 目前, 知识图谱的构造方式大致可分为两类: 人工构造和自动化构造.
  1.1.1 人工构建
早期的知识图谱主要依靠单一个体或小规模群体进行人工构造. 这一时期的典型工作包括Cyc和WordNet这两个知识图谱构造项目. Cyc通过手工构造的方式将专家知识表示为一阶逻辑形式[3]. WordNet则主要依靠语言学专家手工输入词语之间的语义关系[4]. 随着互联网的普及与发展, 众包成为一种新的知识图谱构造方式. 例如, Freebase项目采用类似维基百科的方式将知识图谱的创建、修改、查看权限对外开放, 使得互联网上的任一用户都可以自由创建和编辑知识图谱[5]. DBpedia项目将知识图谱构造任务进行微任务化, 由大规模志愿者群体手工完成对维基百科中自然语言知识的结构化表示[6].
通过人工方式构造形成的知识图谱具有较高的准确性、可用性和可信性. 但是, 受到构造者个体能力的限制, 这种方式存在知识覆盖面窄, 更新缓慢等问题. 虽然互联网众包大大提高了知识图谱的构造规模, 但这种方式仍然存在对一个小规模核心专家群体的强依赖. 例如, 不同用户提交的数据之间存在的不一致性, 仍然需要由社区核心成员进行裁决[7, 8].
1.1.2 自动化构造
知识图谱的自动化构造算法大致可以分为基于规则和基于统计两种类别. 在基于规则的构造算法中, 需要由领域专家事先给定适用于特定数据集的知识抽取、融合以及补全规则[9−12], 然后算法将这些规则应用到特定的数据集上, 形成知识图谱. 基于统计的构造算法则自动识别特定领域数据源的统计特征, 并自动完成知识图谱的构造[13−16]. 目前, 主流的基于统计的自动化构造算法普遍采用监督学习的方式, 依赖于事先人工标注的大规模训练数据集, 且针对不同的问题领域需要建立不同的训练数据集. 针对开放领域存在的样本数据稀疏问题, 也有学者探索采用弱监督学习的方式进行知识图谱的自动化构造[17, 18].
自动化算法在一定程度上提高了知识图谱的构造效率, 降低了构造成本, 但仍然存在两个基本问题. (1) 自动化算法, 特别是采用监督学习的知识图谱构造算法, 严重依赖于训练数据集的规模和质量. (2) 在可以预见的将来, 自动化算法所具有的对一般性非结构化知识的理解能力还远远达不到人类个体的能力, 这在很大程度上限制了自动化算法的应用范围. 在谷歌搜索引擎使用的知识图谱中, 就大量包含了Freebase项目中由人工方式构造的知识谱图信息[19, 20]. 一些研究工作也表明, 在自动化构造知识图谱的过程中, 加入人类的反馈信息, 能够明显提升知识图谱的构造质量[21−23].

1.3.2
基于互联网的人类群体智能
互联网上已经出现了很多人类群体智能现象或系统, 为很多领域带来了创新性的问题求解方法. 其中, 一些群体智能现象/系统是长期的社会-技术协同演化的产物, 另一些则是针对特定的问题精心设计的群智化求解系统. 例如, 在软件工程领域, 经过数十年的演化, 开源软件开发[33]已经成为一种重要的社会-技术现象; 在其中, 地理分布的大规模开发者群体通过互联网进行有效的协同, 成功开发出数量众多的高质量复杂软件应用. 在单项选择题求解领域, UNU系统[34]提供了一个有趣的多人在线环境, 可以支持一个大规模群体通过持续协同的方式确定一个单项选择题的答案, 在很多实际场景中的预测和决策问题上表现出很高的准确率. 在生物学研究领域中, EteRNA系统[35]提供了一个多人在线游戏, 通过大规模非专业个体的持续协同求解复杂的蛋白质结构问题.
群体智能的研究还远远落后于实践; 现有的研究成果几乎没有对人工群体智能系统的构造产生实质性的影响. 目前存在的较为成功的人工群体智能系统都不是在任何成熟的群体智能理论的指导下构造形成的. 主要原因在于, 目前的研究工作主要关注群体智能的解释型理论(即如何解释某一群体智能现象的形成机理), 而较少触及群体智能的构造型理论(即如何可控地构造求解特定问题的群体智能系统). 一个典型案例是环境激发效应. 这一概念在提出时是用于解释社会性昆虫群体中群体智能现象[31], 而且近年来也被广泛用于分析和解释人类群体智能现象[36, 37]. 我们认为, 环境激发效应提供了一种针对群体智能的解释性模型, 能够对已经存在的群体智能现象进行有效的事后分析. 但是, 这一概念能够在何种程度上有效指导一个人工群体智能系统的构造, 仍然需要进一步的观察和确认.
2.方法
本节介绍一种基于互联网群体智能的知识图谱构造方法. 该方法的核心是一个持续运行的回路, 包含3个并行的活动: 自由探索、自动融合、主动反馈. 本节分别对这3个活动及其中的基本概念和关键技术进行说明.
2.1 自由探索
在自由探索活动中, 每一参与知识图谱构造的人类个体独立进行知识图谱的构造活动, 不与其他参与者发生直接的交互. 在任一时刻, 对于每一参与者而言, 其探索活动的输出是一个个体知识图谱.
2.1.1 个体知识图谱
个体知识图谱的表示需要考虑两个方面的因素. 一方面, 所采用的表示机制应该具备有效的抽象性和良好的可扩展性, 从而支持对不同领域中存在的多样性知识片段进行有效的建模. 另一方面, 这种表示机制应该能够支持算法有效识别不同知识图谱之间的共性和差异性, 从而实现对群体知识的有效融合与反馈. 基于上述考虑, 我们设计了一种层次式的个体知识图谱, 支持对二元关系、多元关系以及高阶关系的统一标识, 且可以被方便地转换为一种边上带标签的有向图, 从而基于图结构进行多源信息的分析、融合与反馈.
定义 1(个体知识图谱). 个体知识图谱是一个五元组K≐(K0, K1, K2, K3, K4). 其每个元素的定义如下.
1. K0≐(L, V, ℓ, ≻, ⊒,  , ⊔, ⊓, η, α): 个体知识图谱框架, 满足如下条件.
(a) L≐{0, 1, 2, 3, 4}: 个体知识图谱中节点具有的5个层次. 其中, 0、1、2、3、4分别表示道层(tao level)、元元模型层(meta-meta-model level)、元模型层(meta-model level)、模型层(model level)、实例层(instance level).
(b) V: 个体知识图谱的节点集合.
(c) ℓ: V→L: 层次映射函数, 将个体知识图谱节点映射到其所在的层次. 为方便下文叙述, 令 前者表示由V中处于i层的元素构成的集合; 后者表示由V中所有不处于i层的元素构成的集合.
(d)  : 个体知识图谱节点之间的实例化关系. 对于任何(u, v)∈≻(也记为u≻v), 表示v是u的一个实例, 或u是v的一个类型. 为方便下文描述, 令V(≻v)≐{u∈V|u≻v}, 且V(u≻)≐{v∈V|u≻v}. 前者表示由V中所有v的类型构成的集合; 后者表示由V中所有u的实例构成的集合(下文会根据需要将这种表示符号应用到其他集合与二元关系上)). 实例化关系不具有自反性、对称性、传递性. 对任何u≻v, 有ℓ(v)=ℓ(u)+1成立.
(e) : 个体知识图谱节点之间的一般特殊关系. 对任何(g, s)∈⊒(也记为g⊒s), 称g是s的一般概念, 或s是g的特殊概念, 满足: 对任何s≻w, 有g≻w成立. 也即一个概念的任何一个实例一定是这个概念的一般概念的实例. 对任何u, v∈∈V, 如果u⊒v且v⊒u, 则称u, v等价, 记为u=v. 一般特殊关系具有自反性、传递性, 但不具有对称性.
(f) : 个体知识图谱节点之间的幂集关系, 一个部分函数(partial function). 对任何(u, v)∈ (也记为 , 称v是u的幂概念, 满足: 对任何v≻w, 有u⊒w成立. 也即一个概念的幂概念的任何一个实例一定是这个概念的一个特殊概念.
(g) : 个体知识图谱节点之间的并集关系, 一个部分函数. 对任何u↦v∈⊔(也记为⊔(u)=v), 称v是u的所有实例的并集, 满足: (1) 对任何x, y∈V, 如果u≻x且x≻y, 则v≻y成立; (2) 对任何y∈V, 如果v≻y, 则存在x∈V, 有u≻x且x≻y成立. 也即一个概念的所有实例的并集是由这些实例的所有实例构成的集合.
(h): 个体知识图谱节点之间的交集关系, 一个部分函数. 对任何u↦v∈⊓(也记为⊓(u)=v), 称v是u的所有实例的交, 满足: (1) 对任何x∈V, 如果对所有y∈V(u≻), y≻x成立, 则有v≻x成立; (2) 对任何x∈V, 如果v≻x, 则对任何y∈V(u≻), 有y≻x成立. 也即一个概念的所有实例的交集是由这些实例的共有实例构成的集合.
(i) η: V→V(Str≻): 标识符函数. 将个体知识图谱节点映射到字符串上. Str是模型层知识图谱的一个节点, 表示由所有字符串构成的集合. 该函数的主要目的是为个体知识图谱中的每一个节点关联一个人类可理解的描述信息.
(j) : 符号字面量函数. 将V中符号概念⊛实例的实例映射到字符串上. 符号概念⊛是元模型层知识图谱的一个节点. 该函数的主要目的是为每一个符号概念实例的实例关联一个对应的字面量. 不失一般性, 令α⊆η. 也即一个符号的字面量即提供对该符号的一种描述信息.
2. K1≐(○1, ∅1): 元元模型层知识图谱, 满足: {○1, ∅1}⊆V. ○1表示元元模型层的满节点, 满足: (1) ℓ(○1)=ℓ; (2) 对于任何v∈V(1), 有○1⊒v成立. 可知, 对任何1≻v成立. 元素∅1表示元元模型层的空节点, 满足: (1) ℓ(∅1)=1; (2) 对于任何v∈V(1), 有v⊒∅1成立. 可知, 不存在v∈V(2), 使得∅1≻v成立.
3. K2≐(○2, ∅2, ⊙, ⊝, ⊚, ⊛): 元模型层知识图谱, 满足: {○2, ∅2, ⊙, ⊝, ⊚, ⊛}⊆V. ○2表示元模型层的满节点, 满足: (1) ℓ(○2)=2; (2) 对任何v∈V(2), 有○2⊒v成立. 可知, 对任何v∈V(3), 有○2≻v成立. ∅2表示元模型层的空节点, 满足: (1) ℓ(∅2)=2; (2) 对任何v∈V(2), 有v⊒∅2成立. 可知, 不存在v∈V(3), 使得∅2≻v成立. ⊙、⊝、⊚、⊛分别表示实体概念、关系概念、角色概念、符号概念, 满足○1≻⊙, ○1≻⊝, ○1≻⊚, ○1≻⊛.
4. K3≐(○3, ∅3, Str, Int, ↠, π, κ,
(a) (○3, ∅3, Str, Int)⊆V. ○3表示模型层的满节点, 满足: (1) ℓ(○3)=3; (2) 对任何v∈V(3), 有○3⊒v成立. 可知, 对任何v∈V(4), 有○3≻v成立. ∅3表示模型层的空节点, 满足: (1) ℓ(∅3)=3; (2) 对任何v∈V(3), 有3成立. 可知, 不存在v∈V(4), 使得∅3≻v成立. 元素Str、Int分别表示字符串、整数, 满足⊛≻Str, ⊛≻Int. 令Ints= (int), 也即Ints是Int的幂概念.
(b) ↠: V(⊝≻)←V(⊚≻): 关系概念实例与角色概念实例之间的关联关系. 其逆关系↠−1是一个函数, 即任何一个角色概念实例只与一↠: V(⊝≻)←V(⊚≻): 关系概念实例与角色概念实例之间的关联关系. 其逆关系↠−1是一个函数, 即任何一个角色概念实例只与一个关系概念实例相关.
(c) π: V(⊚≻)→V(3): 角色概念实例的承担者函数, 将一个角色概念实例映射到模型层知识图谱的节点上. 其具体含义见实例层知识图谱.
(d) κ: V(⊚≻)→V(Ints≻): 角色概念实例的承担者数量限制函数, 将一个角色概念实例映射到一个整数集合上. 其具体含义见实例层知识图谱.
(e) τ, ⇝, ↱, ↰): 关于时间点、时间点先后关系、以及时间区间的模型层知识图谱. 其中, τ表示时间点, 满足⊛≻τ. ≤τ⊆V(τ≻)×V(τ≻)表示时间点之间的先后关系; ≤τ是一个偏序关系(具有自反性、传递性, 但不具有对称性). 对任何(t0, t1)∈≤τ (也记为t0≤τt1), 若满足t1≤τt0, 则称t0和t1相等(记为t0=t1). ⇝表示时间区间, 满足⊛≻⇝. ↱: V(⇝≻)→V(τ≻)表示一个函数, 将时间区间实例映射到对应的开始时间点实例上. ↰: V(⇝≻)→V(τ≻)表示一个函数, 将时间区间实例映射到对应的结束时间点实例上. 对任何p∈V(⇝≻), 有↱(p)≤τ↰(p)成立.
5. K4≐(ρ, ↺): 实例层知识图谱, 满足如下条件.
(a): 关系概念实例的实例到角色承担者的映射函数. 对于其中的一个元素(v, r)↦w, v表示一个关系概念的实例u的实例, r表示u的一个角色, w表示角色r在v上的承担者集合, 且满足: (1) w是π(r)的一个特殊概念; (2) w的实例的数量是κ(r)中的一个元素. 可以看到, 模型层知识图谱中定义的角色概念实例的承担者函数π和承担者数量限制函数κ对ρ包含的元素进行了限制.
(b) ↺: V(4)→⇝: 实例层节点到其生命周期的映射函数.
该定义给出了一种层次式的知识图谱, 其中包含5个层次: 道层、元元模型层、元模型层、模型层、实例层.
个体知识图谱包含的每一个节点都处于且仅处于一个层次中. 相邻层次的节点之间通过实例化关系相互关联. 实例化关系的定义建立在概念外延的基础上, 即将一个概念理解为由其所有实例形成的集合; 若一个元素属于概念的外延集合, 则表明该元素是该概念的一个实例. 除实例层外(不包括实例层), 处于其他层的节点均是概念, 且指代了概念的外延. 个体知识图谱还定义了概念之间的一般特殊关系、幂集关系、并集关系、交集关系. 对于个体知识图谱中的每一个节点, 通过标识符函数, 将该节点与对应的字符串描述信息进行关联. 对于个体知识图谱中的每一个节点, 如果是符号概念⊛实例的实例, 则通过标识符函数将其与对应的字面量进行关联. 对于元元模型层、元模型层、以及模型层, 分别定义了若干基本节点以及节点之间的关系; 需要指出的是, 这些元素不是一个全集, 可以根据实际需要向其中添加新的元素. 实例层包含两个函数: ρ函数将关系概念⊝实例的实例映射到涉及角色的承担者; ↺函数将实例层节点映射到其生命周期. 另外, 对于道层, 由于其中包含的元素(处于元元元模型层或之上)过于抽象, 且不会对知识图谱的构造产生直接的影响, 所以我们没有对其中的元素进行定义.
2.1.2 个体知识图谱的图表示
给定个体知识图谱K≐(K0, K1, K2, K3, K4), 其图表示(graph representation)是一个边上带标签的有向图
基于个体知识图谱生成对应的图表示的基本思想如下: 把个体知识图谱内置的每一种二元关系包含的每一个元素转化为图表示中两个节点之间一条带标签的有向边; 有向边上的标签即是对应的关系名. 除此之外, 算法1还包含对两种例外情况的处理. (1) 对于函数ℓ, 把其值域中的5个整数分别转化为符号概念实例l的5个实例li, i∈L; 然后, 把ℓ中的每个元素(v, i)转化节点v和li之间一条标签为“l”的有向边. (2) 对于函数ρ中的每一个元素(v, r, w), 创建r的一个实例γ; 然后, 在节点v和γ之间建立一条标签为“↠”的有向边, 在节点γ和w之间建立一条标签为“ρ”的有向边.

图 2给出了个体知识图谱图表示的一个示例.