图1 交互式图搜索实例
Fig. 1 Example of interactive graph search
北京大学学报(自然科学版) 第59卷 第5期 2023年9月
Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 59, No. 5 (Sept. 2023)
国家自然科学基金青年基金(61902074)资助
doi: 10.13209/j.0479-8023.2023.049
收稿日期: 2022–08–15;
修回日期: 2022–09–22
摘要 现有的交互式图搜索方法主要局限于优化单一数据的标注成本。为解决这一问题, 针对现实场景中更常出现的批量数据标注任务, 提出一种基于知识驱动建模先验概率信息的方法。利用该方法对批量数据的实体间知识进行提取, 并用于指导机器算法, 可以在整体上降低交互式图搜索的成本。在真实数据集上的实验结果表明, 与现有方法相比, 所提出的算法具有交互效率方面的优势。
关键词 图搜索; 人机交互; 实体知识; 知识驱动
交互式图搜索(interactive graph search, IGS)是众包构建常用的一种算法, 旨在通过人机交互的方式, 将数据分类到一张有向无环图(directed acyclic graph, DAG)上。用 G = (V, E)表示一张 DAG, V 表示G 的节点集合, |V |=n, E 表示 G 的边集合。通常集合V 中的节点 v 表示一种具体分类概念。设 u 是 v 在 G的父节点, (u, v)表示 u 到子节点 v 的有向边。IGS 的目标是通过图搜索, 找到实体 o 在 DAG 中对应的节点 t。机器将从图中挑选出一个节点 x, 并询问人类“o 是否属于 x”, 即“在 DAG 中是否有从 x 到 t 的一条可达路径”。随后人类会作出判断, 给出“Yes”或“No”的回答。得到答案之后, 机器继续选择 DAG中的下一个节点并重复交互过程, 直至找到目标节点 t。
例如, 图 1 所示为商品分类树的一部分。假设当前处理的目标实体名为“iphone 12 pro”, 它的真实类别为 Mobile Phones 这个节点。按照 IGS 的提问搜索逻辑, 机器会首先提问: “iphone 12 pro”属于Clothes & Accessories 吗？即 Clothes & Accessories与 Mobile Phones 之间是否有可达的路径。由于“iphone 12 pro”不属于 Clothes & Accessories, 因此人类给出“No”的回答。于是机器选择下一个节点Mobile Device 并再次询问: “iphone 12 pro”属于Mo-bile Device 吗？人类给出“Yes”的回答。然后机器再次依照算法逻辑, 寻找新的节点并提问: “iphone 12 pro”属于 Headphone 吗？人类回答: “No”。最后机器提问: “iphone 12 pro”属于 Mobile Phones 吗？人类回答“Yes”。至此, 机器找到“iphone 12 pro”所属的类别“Mobile Phones”, 针对该节点的 IGS 搜索结束。
图1 交互式图搜索实例
Fig. 1 Example of interactive graph search
在 IGS 对数据分类的过程中, 机器与人类不断交互, 机器选择节点, 人类回答可达性问题, 巧妙地结合了人类的智慧与机器的计算存储能力。由于与人类回答问题的时间相比, 机器的运算时间可以忽略不计, 所以交互的次数直接决定人力与时间成本。因此, IGS 问题的优化目标是减少交互问题的数量。根据图谱基本性质可知, 当且仅当 x 不存在可达 t 的子节点时, IGS 算法终止。给定 DAG G= (V, E), IGS 问题的优化目标是减少搜索目标 o 在 DAG上执行搜索带来的代价 W。
交互式图搜索算法的出发点是结合人类和机器的智能, 借助人类的知识来回答机器难以判断的图上节点的可达性问题, 从而辅助机器进行图搜索。Top-Down 类型算法是由 Parameswaran 等[1]提出的交互式图搜索基础算法, 基于广度优先搜索(BFS)和深度优先搜索(DFS)等逻辑, 从根节点开始, 由浅到深, 依次向人类询问节点可达性问题, 以便查找目标节点。Top-Down 算法的思路简单, 且容易实现。但是, 当图谱的节点数量较多时, Top-Down 算法的搜索代价会相应地变得较为昂贵[1]。因此, Top-Down 算法不适用于大规模的图谱。
为了减少交互成本, Tao 等[2]提出基于路径分解思想的 IGS 算法——DFS-Interleave 算法。相较于Top-Down 算法, 该算法会优先探索规模较大的子树空间。此外, 它通过重路径树分解结合路径二分的方式来执行搜索[3], 能更快地缩小搜索空间。假设 DAG 中最长的有向边路径长度为 h, 节点度数最大值为 d。DFS-Interleave 算法至多需要[log2h]·(1 +[log2n])+(d–1)[logdn]个问题[2]。在实验表现方面, DFS-Interleave 在多种数据集上也被证明能比 Top-Down 算法大幅降低交互式图搜索成本[2]。
给定 DAG G 中的节点 u 和它的子节点 v, 如果v的子树(后继节点集合)是 u 的子节点中包含节点数量最多的一棵, 那么称 u 与 v 之间的连接边为重边(heavy edge)。由 heavy edge 连接而成的路径称为重路径(heavy path)。若重路径不能再被另一条重边扩展, 则该路径称为最大重路径(maximal heavy path)。以图 2 为例, 1→2, 2→5, 5→8 是 3 条重边, 1→2→ 5→8→11 连起来是以 1 为根节点的重路径, 同时也是该 DAG 的最大重路径。基于重路径的定义, DFS-Interleave 算法包括两个步骤: 深度优先重路径树生成和重路径树搜索。
1)在执行过程中, DFS 算法选取当前层已经压入栈内的节点弹出, 然后再压入该节点的子节点或弹出栈内的后一个节点。深度优先重路径树的生成则是在每次拓展下一层的节点时, 优先拓展子树规模更大的子节点, 并将其压入栈中, 之后的步骤与DFS 相同。根据搜索顺序, 可得到搜索树 T’。将 T’的每一层按照子树规模大小从左向右排序, 最后得到深度优先重路径树 T, 即深度优先重路径树 T中,
图2 DAG G与深度优先重路径树 T
Fig. 2 DAG G and heavy-path DFS tree T
在节点深度相同时, 左侧节点的子树规模总是大于等于右侧节点的子树规模。图 2 中, 树 T即为在图 1 所示的 DAG 上执行上述生成步骤后得到的深度优先重路径树。
2)DFS-Interleave 的第二个步骤是在重路径树上执行搜索。选择当前根节点下最左侧的一条直达叶节点的边, 即从当前根节点出发, 在选择某一深度的节点构成路径时, 优先选择深度优先重路径树T 中靠左侧的节点, 直到拓展至叶节点, 这些节点构成的路径即为重路径。在重路径上通过二分搜索得到最后一个可达 t 的节点, 选取这个节点中左起第一个可达 t的子节点, 再将此子节点作为新的根节点, 循环上述步骤, 直至算法达到终止条件。
DFS-Interleave的算法表示如下。
算法1 DFS-Interleave。
输入: 目标实体 o 和从有向无环图 G 生成的重路径树 T
输出: o 在 G 中对应的位置节点 t
1. 
←T 的根节点
2. While t没被查找到 do
3. π←T中从开始最左侧直到叶节点的路径
4. 二分搜索 π 直至找到最深的可达 t 的节点 u
5. 找到 u 中最左侧可达 t 的子节点 v
6. if v 不存在或
没有子节点then
7. return u
8. else
9. ←v
基于 DFS-Interleave 算法, 提出本文的改进思路: 1)以二分剩余搜索空间为目标, 选取路径节点; 2)以降低整体搜索代价为目标, 结合实体知识, 模拟实体的图上概率分布, 从而降低实体集合的总体搜索代价。
DFS-Interleave 在重路径上的二分点不一定是剩余树搜索空间的二分点, 因此路径上的二分搜索和子节点遴选等步骤或许不是切割搜索空间的最优选择。本文提出基于重路径分解树进行的 Bina-ry-Tree 算法, 旨在通过调整原算法的节点选择策略, 提升每次交互能缩减的搜索空间。
Binary-Tree 的核心思想是, 依靠重路径分解树, 寻找 DAG 的最优二分节点。若重路径分解树可以被完美二分, 那么最多只需要 log(n)的时间, 就能一定能找到目标节点的位置。但是, 完美二分点往往不存在或不连续存在, 因此只能找到树内最接近二分的节点, 本文称其为最优二分点。基于分解树的结构, 可以得到关于最优二分点的如下定理。
定理 1 对有向无环图 G 对应的重路径分解树T 而言, T 上的最优二分节点一定位于重路径节点和各重路径节点同一深度下的第一个右侧兄弟节点组成的集合中。
证明 如图 3 所示, 设树 T 的根节点为 A, 大小为 S, 最左侧的路径 A→B→E→…是一条重路径。因为 S1>S2>S3, 且 S=S1+S2+S3+, …, 所以 
, 设 
。由于
, 因此 C 右侧节点的子树与二分点的差距更大, 故它们不可能是最优二分点, 否则一定能找到与 C 同等或更优的二分点。B 节点则因为其与子树大小一半的差距未知, 并且无法与 C 做差距比较, 所以需要被放入候选集中。同样地, 当算法递归到叶子节点后, 最优二分候选点集就是定理 2 中描述的集合。
图3 最优二分点集定理
Fig. 3 Optimal binary node theorem
Binary-Tree 算法依旧以重路径分解树为对象, 但每次检索时, 优先寻找重路径以及重路径节点右侧节点集内在当前剩余树中的最优二分点, 而非DFS-Interleave 选择的路径二分点。然后, 根据人类反馈的布尔值, 将下一轮搜索空间缩小为最优二分点的子树或在原空间中删掉该二分点子树后的剩余部分, 并递归调用该搜索逻辑。我们用剩余搜索空间(candidate search space, CSS)表示在当前搜索状态下根节点的子树规模, 即每次剪枝后剩余待搜索区域中包含的节点个数。算法的具体步骤如下。
算法2 Binary-Tree算法。
输入: 目标实体 o, 路径树 T, T 的根节点 r, 剩余搜索空间 CSS
输出: 实体 o 的位置节点 t
初始: T 是从有向无环图 G 生成的重路径树, 剩余搜索空间 CSS 为重路径树节点集合
1. if CSS 大小为 1 then
2. return CSS[0]
3. else
4. π←T 中从 r 开始最左侧直到叶节点的重路径
5. β←π中节点每层右侧第一个兄弟节点的集合
6. γ←π∪β
7. 搜索 γ 直至找到 T 的最优二分节点 u
8. if u 到 o 可达 then
9. T←T 中 u 的子树
10. CSS←CSS∩T
11. return Binary-tree (T, u, o, CSS)
12. else
13. T←T 除去 T 中 u 的子树
14. CSS←CSS 除去 T 中 u 的子树
15. return Binary-Tree (T, u, o, CSS)
在 IGS 问题中, 每个点是答案的概率均为
, 那么对于节点 u, IGS 问题产生的期望成本为
, Query(u)为使用算法在 DAG 中搜索到该节点所需要的交互成本。因此, 在有向无环图 G中搜索实体 o 所需要的期望成本为
。尽管 IGS 问题或许存在期望意义上的最优解, 但找到该最优解十分困难。根据 Cicalese 等[4]的研究, 寻找到此类问题的最优解是一个 NP-hard 问题, 不过相比于最优解法, Binary-Tree 算法在交互问题数量方面达到 O(log(n))的近似率[4–5]。其中近似率指当前算法与最优解法需要的交互问题数量比值:
本文将优化目标由降低单个实体交互成本扩展到降低实体集合整体搜索成本, 并结合实体知识模拟实体的图上概率分布, 优化实体集合的总体搜索效率。
2.2.1交互式多任务协同搜索问题定义
面对大容量实体数据集, 算法的优化目标应该扩展到优化搜索完整个实体数据集所需要的代价。本文给出多任务交互图搜索优化的问题定义。给定有向无环图 G=(V,E), V 是 G 的节点集合, E 为G 的边集合。在多任务搜索中, 以整体代价为目标, 在允许部分实体信息搜索损耗增加的前提下, 降低总体交互搜索成本。本文中, 多任务协同图搜索的优化目标定义如下: 给定实体数据集 O={o1, o2, o3, …}, 设数据集中每个实体 oi 的交互问题数量为 ki, 优化的目标是整个数据集需要的交互搜索成本
2.2.2基于概率知识优化图搜索策略
我们发现数据集内部的实体在 DAG 上的数量分布不均匀, 并且实体间的相似程度存在明显的差异。因此设想, 对某个实体 o 而言, 它在 DAG 节点上的分布并非均匀分布, 而是在不同节点上有差异的概率分布。如果提前知道实体 o 在 DAG 上的概率分布, 算法可以调整搜索策略, 根据实际的分布, 优先搜索 o 存在概率更大的区域, 将图从概率意义上二分, 从而在期望意义上减少搜索代价。
如图 4 所示, , 假设当前处理的目标实体名为“iphone 12 pro”, 它位于 Mobile Phones 节点。假设已知其在 DAG 各个节点上分布的先验概率(节点旁的数字), 按照 DFS-Interleave 的搜索逻辑, 本文优先搜索 Clothes&Accessories→Shoes→Highheels 这一条 heavy path 及其经过的子树空间。但是, 从结果论的角度出发, 若事先知道先验概率, 便可以优先搜索 Mobile Device→Mobile Phones 方向上的区域, 就不必在左侧的空间浪费交互成本。
图4 先验概率对IGS策略的影响
Fig. 4 Influence of prior probability on IGS strategy
在实际应用场景中, 无法事先得知, 实体集合在 DAG 上的先验概率分布, 但是我们可以利用实体信息尽可能合理地模拟这种分布。对于概率分布的模拟, 本文从以下 3 个方面进行分析。
1)每个节点初始拥有相同的概率权重, 并且子树的概率权重与子树节点数量成正比。在未计算实体数量分布和相似知识的情况下, 本文认为初始状态下 DAG 中每个节点是目标位置的概率均为。
2)被确定位置的实体数量足够多之后, 基于现有确认位置的实体分布模拟将要被搜索的实体在DAG 上的概率分布。本文设置一个冷启动过程, 当搜索完成的实体数量少于既定阈值 Ld 时, 不参考实体分布; 当搜索完成的实体数量超过 Ld 时, 再让实体数量分布参与概率分布的模拟过程, 从而使得模拟方法更加准确。
3)借助实体相似度知识, 对先验概率进行模 拟[6]。如果已被定位在 DAG 某节点上的实体与当前目标高度相似, 那么目标有更大的概率位于该节点。文本实体之间可以通过语言模型[7]和杰卡德相似系数[8]等方法来计算词汇或句子的相似度, 图片实体可以通过计算机视觉算法来计算彼此之间的相似度[9]。由于 DAG 节点大部分时候以文本形式描述自己的类别, 因此还可以计算 DAG 节点概念描述文本与文本类实体之间的相似度。
以图 5 为例, 对于当前目标实体“iphone 12 pro”, 根据图中展示的已经落位实体的位置和高相似度的实体位置, 可以认为当前实体位于 Mobile Phones 节点附近区域的可能性更大。
基于 2.2 节对先验概率知识的表达方式, 结合路径分解方法和概率分布模拟方法, 本文设计基于知识的交互式图搜索算法——Knowledge-Based Interactive Graph Search (KIGS)算法。KIGS 算法将节点数量、实体分布以及相似知识转化为各个节点u 对应的模拟分布概率。依据概率大小分配节点权重, 从而将 DAG 转化为带有节点权重的图 Gw, 在 Gw 上使用 Binary-Tree 方法进行后续搜索。图 6展示 KIGS 算法的整体框架。
对于实体分布, 节点 u 的概率权重与已经落位在 u 上的实体数量成正比。设落位在节点 u 上的实体集合为 Located (u), 用 size (Located (u))表示实体集合的规模, 用下式表示实体分布对 DAG 上节点权重的参与:
对于相似知识, 用相似模型[7,9–11](用 Mod()表示)和杰卡德相似系数 Jac()计算 o 与 Located(u)中各个落位实体之间的相似度或 o 与 u 之间的相似度:
图5 通过先验概率优化策略
Fig. 5 Optimize search strategy by prior probability
图6 KIGS算法整体框架
Fig. 6 Overall framework of KIGS
综合考虑节点数量、实体分布和相似知识后, DAG 上节点的概率模拟权重 Pw(u)可以表示为
其中, C 表示初始状态下每个 DAG 节点被赋予的相同权重。
在每个节点的权重为 Pw(u)的带权图 Gw上, 节点 u 的权重越大, 表示目前实体 o 落位于此处的概率越大。为确保概率模拟准确, 本文设定阈值 Ld 和阈值指示函数 Id, 当已落位实体的数量超过阈值时, Id 为 1, 否则取为 0。
通过阈值指示函数 Id, 可以确保权重计算在积累足够多的已落位实体后才结束冷启动。在初期, KIGS 算法的搜索逻辑与 Binary-Tree 保持一致。当Located (root)的规模超过阈值后, KIGS 进行赋权操作, 并进行权重图分解以及树上的交互搜索。随着交互实体数量增加, KIGS 会在搜索过程中适当放大Dist (u, o)在赋权函数中的比例, 适当降低 Sim (u, o)的比例。这是因为, 本文认为已落位实体的分布对概率分布的模拟准确度总体上比相似知识模拟的准确度稳定。
假设 Located (root)的规模已超过阈值 Ld, 下面介绍如何在带权图上进行交互搜索。
给定带权有向无环图 Gw中的节点 u以及 u 的子节点 v, 如果 v 是 u 的子节点中子树权重分数(即子树内所有节点的权重加和)最高的点, 那么称 u→ v 为一条重权边(heavy-weight-edge)。由重权边连接组成的路径称为重权路径(heavy-weight-path)。如果重权路径不能再被另一条重权边拓展, 那么称这条路径为最大重权路径。
以图 7 展示的带权有向无环图 Gw 为例, 假设每个节点 u 旁的数据为根据概率知识生成得到的权重, 根据定义, 1→3→7→10→13 是 Gw 中的一条最大重权路径。在给定权值和重权路径的定义之后, KIGS对 Gw 使用深度优先重权路径生成树算法, 在每次拓展节点时, 优先拓展子树总权重更高的节点, 从而得到对应的深度优先权重生成树 Tw。
从图 7 可以看出, 通过对 Gw使用深度优先重权路径搜索, 可以得到权重生成树 Tw。对比图 2 展示的深度优先重路径树 T可以得知, Tw 不再以节点数量作为排序和搜索的优先凭据。这是因为重权生成树算法中, 节点数量累积代表的概率权重在本质上与节点数量是等价的, 所以当权重计算不考虑实体分布和相似知识时, Tw 就是 T。因此, 可以将重权路径生成树算法视为重路径生成树算法在扩展了概率模拟模块后的拓展。与定理 1 类似, 本文在带权图上可以得到类似的定理。
定理 2 在对带权有向无环图 Gw 进行重权路径分解搜索得到的重权路径分解树 Tw 中, 最优权重二分节点一定位于重权路径上或各重权路径节点同一深度下的第一个右侧兄弟节点上。
定理 2 是定理 1 在带权图上的延伸, 其证明过程几乎一致, 不赘述。在生成权重路径树之后, 参考 Binary-Tree 的算法, 在权重树上进行搜索。根据上文以及文献[4–5]可知, 当概率建模准确时, KIGS是比最优算法更接近 O(log(n))近似比率的算法。KIGS 算法的流程如下所示。
算法3 KIGS算法。
输入: 目标实体 o, 路径树 Tw, Tw 的根节点 rw, 剩余搜索空间 CSSw
输出: 实体 o 的位置节点 t
初始: Tw 是从有向无环图 Gw 生成的带权重路径树, 剩余搜索空间 CSSw 为带权重路径树节点集合
1. if 被搜索完的实体数量小于阈值 Ld then
2. 使用 Binary-Tree 算法
3. else
4. if CSSw 大小为 1 then
5. return CSSw[0]
6. else
7. πw←Tw 中从 rw 开始最左侧直到叶节点的重路径
8. βw←πw 中节点每层右侧第一个兄弟节点的集合
9. γw←πw∪βw
10. 搜索 γw 直至找到 Tw 的最优二分节点 uw
11. if uw 到 o 可达 then
12. Tw←Tw 中 uw 的子树
13. CSSw←CSSw󠇆∩Tw
14. return KIGS (Tw, uw, o, CSSw)
15. else
16. Tw←Tw除去 Tw 中 uw 的子树
17. CSSw←CSSw󠇆 除去 Tw 中 uw 的子树
18. return KIGS (Tw, uw, o, CSSw)
1) Amazon 数据集。Amazon 商品数据集[12]记录部分在 Amazon 网站上架的商品实体文本数据, 通过一张表示产品层次体系的有向图来记录商品信息。本文根据 10000 个实体的目录生成一张 DAG, 整张 DAG 包含 2427 个节点。数据集中实体的深度分布和各层深度节点的度数分布如图 8(a)所示。
图7 带权 DAG Gw 与深度优先权重生成树 Tw
Fig. 7 Weighted DAG Gw and heavy-weight-path DFS tree Tw
2) DBpedia 数据集。DBpedia[13]涵盖多领域人类知识的文本实体对信息。在 DBpedia 数据集内的实体都归类到一个有向无环图目录中。整张 DAG包含 765 个节点, 数据集中实体的深度分布和各层深度节点的度数分布如图 8(b)所示。
3) ImageNet 数据集。ImageNet 数据集[14]是基于 WordNet 生成的图片实体数据集, 通过一张有向无环图, 将各张图片分类到子目录下。本文对原DAG 进行规格上的缩小, 减少了 DAG 中的节点数量, 缩小后共包含 4628 个节点, 各层深度节点的度数分布如图 8(c)所示。
假设实验中从人类得到的答案完全正确, 即不考虑人类发生错误的情况。实验中 3 个数据集上测试的实体数量分别为 10000, 10000 和 1000。
本文实验的衡量指标包括剩余搜索空间随交互问题数量的下降趋势、不同深度的节点所需要的问题数、随实体数量增加总共搜索交互次数的提升趋势以及最终需要询问的交互问题次数。
实验中使用 Python 进行编码, 在配置为 2.80 GHz 的 Intel Core 7-7700HQ CPU, 8 GB 内存的机器上完成。
本文针对以下 3 种算法进行比较: DFS-Inter-leave, Binary-Tree 和 KIGS。
图8 Amazon, DBpedia和ImageNet数据集信息
Fig. 8 Information of Amazon, DBpedia and ImageNet dataset
3.3.1 算法剪枝能力评测分析
从图 9 所示的剩余搜索空间 CSS 的下降趋势看, Binary-Tree 和 KIGS 总体上比 DFS-nterleave 更有效地缩减剩余搜索空间。由于 DFS-Interleave使用路径二分的方法, 因此其下降趋势有一定的对数特性。然而, Binary-Tree 因为更接近有效二分搜索,其 CSS 下降曲线呈现的对数曲线下降特性也更强。此外, 由于 KIGS 是针对带权图的二分, 是对总权重之和而非节点数量的二分, 所以不呈现对数下降趋势。虽然 KIGS 前期的每次问答并不保证 CSS 能缩减到比前两者少, 但从总体上看, 在中后期之后, KIGS 就能把 CSS 缩小到 Binary-Tree 和 DFS-Inter-leave 之下。
图9 Amazon, DBpedia和ImageNet数据集剩余搜索空间与交互问题数量的关系
Fig. 9 Relationship between the CSS and the number of interactive questions in Amazon, DBpedia and ImageNet datasets
3.3.2 不同深度节点问答成本
从图 10 所示的不同深度的节点问答所需成本来看, Binary-Tree 和 KIGS 在总体上降低了交互成本, 但在不同节点深度上存在差异。在 Amazon 数据集上, 与 DFS-Interleave 相比, Binary-Search 在各个深度的节点的搜索过程中以适中的程度减少了交互成本, KIGS 则在浅层节点上大量减少交互成本, 但是也带来深层节点交互成本的增加。这是由于Amazon 数据集中大部分实体的实际深度都是 2, 3和 4 (图 8(a)), 因此 KIGS 强化捕捉并模拟了这些深度下实体的概率分布, 以牺牲部分极深层和极浅层实体的交互成本为代价, 换来占比更高的 2～4 层实体交互成本的降低, 从而实现整体上的代价缩减。类似的现象在 DBpedia 和 ImageNet 数据集上也有所体现。
3.3.3 整体实体集交互成本
从图 11 所示搜索整个实体集时交互成本的上升情况看, 在整体实体集的搜索情景中, KIGS 和Binary-Tree 在交互成本的上升程度总体上比 DFS-Interleave 低, 在最终的总交互问题数量上也更少。ImageNet数据集在节点交互成本方面的表现在一定程度上优于前二者, 这是因为在 ImageNet 数据集上, 实体相似度的计算模型更加准确。此外, 由于KIGS 存在冷启动问题, 因此在前期, 为已经落位实体的数量少于阈值 Ld时, KIGS 的表现与 Binary-Tree 保持一致; 当实体信息储备足够时, 算法启动基于权重的交互图搜索, 从而逐渐降低交互成本。
图10 Amazon, DBpedia和ImageNet数据集节点深度与交互问题数量的关系
Fig. 10 Relationship between node depth and number of interaction problems in Amazon, DBpedia and ImageNet datasets
图11 Amazon, DBpedia和ImageNet数据集实体数量与交互问题数量的关系
Fig. 11 Relationship between the number of entities and the number of interaction problems in Amazon, DBpedia and ImageNet datasets
3.3.4 平均交互成本
不同数据集上各算法对于搜索单个实体消耗的平均代价如表 1 所示。与 DFS-Interleave 算法相比, Binary-Tree 和 KIGS 算法平均在每个实体上消耗更少的问题数量。
表1 3种算法在数据集上的平均交互成本
Table 1 Average cost of each entity on different datasets
数据集单个实体平均交互问题数量 DFS-InterleaveBinary-TreeKIGS Amazon17.0314.7012.91 DBpedia14.8413.8612.22 ImageNet54.6852.4839.86
从总体上看, 与 DFS-Interleave 算法相比, 本文提出的 Binary-Tree 和 KIGS 算法在目前设计的 3 个数据集中实验效果都有提升。
针对交互式图搜索问题, 以 DFS-Interleave 算法为基础, 本文首先提出基于图特征的单任务交互搜索策略, 然后通过节点数量、实体分布和相似度计算, 建模先验概率知识, 在此基础上提出基于模拟权重的多任务协同图搜索算法 KIGS, 最后在真实数据集上进行实验, 证明在剪枝能力、不同深度节点问答成本、整体实体集交互成本和平均交互成本方面, 本文算法相对于对比算法具有效率上的优势, 能有效地减少批量实体集上的交互成本。
参考文献
[1] Parameswaran A G, Sarma A D, Hector G M, et al. Human-assisted graph search: it’s okay to ask ques-tions. VLDB, 2011, 4(5): 267–278
[2] Tao Yufei, Li Yuanbing, Li Guoliang. Interactive graph search // Proceedings of the 2019 International Con-ference on Management of Data. Amsterdam, 2019: 1393–1410
[3] Sleator D D, Tarjan R E. A data structure for dynamic trees // Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing. Los Angeles, 1981: 114–122
[4] Cicalese F, Jacobs T, Laber E, et al. On the complexity of searching in trees and partially ordered structures. Theoretical Computer Science, 2011, 412(50): 6879–6896
[5] Chakaravarthy V T, Pandit V, Roy S, et al. Decision trees for entity identification: approximation algo-rithms and hardness results. ACM Transactions on Algorithms (TALG), 2011, 7(2): 1–22
[6] Fan J, Li G, Ooi B C, et al. iCrowd: an adaptive crowdsourcing framework // Proceedings of the 2015 ACM SIGMOD International Conference on Manage-ment of Data. Melbourne, 2015: 1015–1030
[7] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space // Proceedings of Workshop at ICLR. Scottsdale, 2013: 1–12
[8] Jaccard P. The distribution of the flora in the alpine zone. New Phytologist, 1912, 11(2): 37–50
[9] Brown D T. Error detecting and correcting binary codes for arithmetic operations. IRE Transactions on Elec-tronic Computers, 1960(3): 333–337
[10] Devlin J, Chang M W, Lee K, et al. BERT: pre-training of deep bidirectional transformers for language un-derstanding // Proceedings of NAACL-HLT. Minnea-polis, 2019: 4171–4186
[11] LeCun Y, Boser B, Denker J S, et al. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1989, 1(4): 541–551
[12] He R, McAuley J. Ups and downs: modeling the visual evolution of fashion trends with one-class collabora-tive filtering // Proceedings of the 25th International Conference on World Wide Web. Montreal, 2016: 507–517
[13] Auer S, Bizer C, Kobilarov G, et al. Dbpedia: a nuc-leus for a web of open data // The Semantic Web: 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference. Busan, 2007: 722–735
[14] Deng J, Dong W, Socher R, et al. ImageNet: a large-scale hierarchical image database // 2009 IEEE Con-ference on Computer Vision and Pattern Recognition. Salt Lake, 2009: 248–255
Knowledge-Driven Interactive Graph Search
Abstract The existing interactive graph search methods are mainly limited to optimize the annotation cost of single data. To solve this problem, this paper introduces a knowledge-driven method of modeling prior probability information for batch data annotation tasks which are more common in real scenes. This method extracts knowledge between entities of batch data and guides machine algorithms, thus reducing the cost of interactive graph search on the whole. The results of experiments on real datasetsverifies the superiority of proposed algorithm in terms of interaction efficiency compared with existing methods.
Key words graph search; human-machine interaction; entity knowledge; knowledge-driven