VLDB 2023 | 机器学习模型的高效近似查询

时空实验室 2023-07-10

通过机器学习预测回答查询的问题在数据库社区中得到了关注。有效的机器学习方式能够极大地提高效率与质量。由于目前的方式与模型在应用查询中可能会被禁止，解决这个问题具有挑战性。本次为大家带来国际数据挖掘顶级会议VLDB 2023上的论文：《On Efficient Approximate Queries over Machine Learning Models》

1、背景

数据库和机器学习前沿的一些应用需要支持机器学习模型上的查询处理。回答这些查询的一种直接方式是将模型应用到数据库中的所用对象后返回结果，但由于成本昂贵这种方式往往被禁止。机器学习的查询处理重点是在不影响精度的前提下提高效率，在最近的工作中建议使用近似于oracle标签的廉价代理模型来解决问题，但是很难设置oracle预算，这也会导致答案的不准确，对于偏向于查全(RT)或者查准(PT)的结果往往没有实践意义。在文章提出的模型中，它考虑互补率(CR)并产生最小的oracle调用，这使得查全查准相互平衡并降低了成本。这一问题也面临了三项挑战，第一，确保答案的高质量；第二，最小化oracle调用；第三，最大化互补率。文章提出了两种假设和对应的两种算法，并在五个不同数据集上进行实验证明了模型的高效性和低成本。

2、问题定义

文章推广固定半径邻(FRNN)查询到AOS-FRNN查询。

定义2.1 AOS-FRNN查询

对于给定的数据库D，半径r，查询q和距离规则，定义

O为oracle调用，N_s为数据库任意子集与NN^O的交集取模大小。M_P(S)和M_r(S)定义如下：

对于一种测量偏好M和目标γ，对于M(Ans)≥γ称其为有效答案，定义PoS(S, M,γ)为M(S)的成功概率。AOS-FRNN查询即找到具有最大成功概率的有效答案。

问题1 AOS-FRNN问题

对于给定数据集D和一个AOS-FRNN查询Q，找到一个有效的答案，使得产生的oracle调用次数最少，在此基础上互补率最大。

3、方法概述

文章提出方法的关键是用更便宜的代理模型来近似oracle。对于一个给定的数据库D，定义一个映射I:D→{i|1≤i≤|D|}，按升序枚举数据对象。D_k表示在该映射关系下查询对象最近的k个邻居。如果I(x) = k，则称D_k为x的代理前缀。为解决有保证的AOS-FRNN问题，文章考虑了两个假设。

假设1 代理质量

当代理质量即oracle可以以概率方式量化时，模型的目标是在没有oracle调用的情况下找到最大期望互补率的高概率有效答案。文章提出了PQA算法，它假设了dist^o(x)并计算给出disp^p(x),这使得计算PoS(S, M,γ)与期望的互补率是可能的。对于已知k^*，可证明D_k*为最优解。并且不论PT或RT查询，均随k值单调递增。

假设2 核心集闭合

当代理质量难以量化时，模型目的则变为找到k^*与D_k*。通过从数据库D中均匀抽取m个大小为s的样本来估计k^*作为k_s，S为样本的并集，将D_ks作为答案返回。对于偏好RT的查询，将k_s设为最大的I(x)，PT则相反。对于核心集C，当它满足以下一个条件时，称其为闭合的：(1)Q是RT查询并且对于所有x∈C，任意代理索引比x大的oracle邻居都在C中。(2) Q是PT查询并且对于所有x∈C，任意代理索引比x小的oracle邻居都在C中。对于这些情况，文章提出了CSC算法来有效解决并返回D_ks作为答案，它具有最小的oracle开销和良好的互补率。

如果这些假设不成立，文章还提出了相对的补充算法PQE与CSE，总体上保证了较高的成功率。图一为不同算法的工作流程。

图一不同算法的工作流程

4、算法与理论分析

4.1代理质量

4.1.1代理质量假设

在问题设置中，给定查询对象的代理距离与oracle差异是独立同分布的，并且满足卡方分布，并且在不同来自真实世界的测试集中，代理均具有很好的质量，可以近似oracle的预测。在此条件下，x_i∈D成为oracle邻居的条件概率为

为简化问题，定义 ϕ(x_i):= CDF_χ(r-distP(x_i))，它提供了x_i成为oracle邻居的可能性。如果一个子集S有很高的准确率或者查全率，它的成功率会等于所有可能世界的可能性之和。让p_Ns(k):=p_r[N_s =k]，有一个重要的事实是对于S⊆D,x_i∉S，存在以下等式关系

这显示可以使用迭代的方式来计算p_Ns。并且可通过以下方式来计算出PoS(S, M,γ)

第一个等式说明了PT查询的情况，第二个等式说明了RT查询的情况。

4.1.2 PQA算法

PQA算法可以在代理质量假设下返回高质量的答案。对于PT查询，PQA-PT计算使得PoS(D_k, M_p, γ)≥ 1 - δ的最大k值作为k^*。PoS(S, M_p,γ)可以通过p_Ns在线性时间内得到，PQA-PT依次增量计算

和PoS(S, M_p,γ)，最后返回满足要求的D_k_*。而对于RT查询，PQA-RT使用二分查找来识别最小的k^*使得PoS(D_k, M_p, γ)≥ 1 - δ，接着计算出D_k的互补率并返回D_k_*作为答案。以下是算法伪代码1-8为PQA-PT，9-26为PQA-RT。

算法一PQA算法

4.1.3 最优性分析

对于数据库D的子集S，有两项操作可产生新的结果，第一是将S中的已有元素替换为未有元素，第二则是追加新元素。在先前已提到对于替换操作PoS(S, M,γ)和互补率均是单调的，基于该引理，可以知道一个查询的成功概率和期望互补率均单调增加，并且可用于在查询早期阶段的剪枝。对于所有目标γ，D_k会拥有一个最大的成功可能性和期望的互补率，这说明给定一个查询，存在0 ≤ k^*≤ |D|使得D_k_*是最优答案。而在追加单调性的引理下，k的增大会让D_k具有高召回率，这也意味着它是最优答案。总之，对于任意给定的查询，通过这些单调性引理，PQA算法能够返回最优的答案。

如果代理质量假设不成立，文章也提出了PQE算法。在PQE中，假设代理是oracle的无偏估计器，并通过启发式的方法将参数传递给PQA进行计算。

4.2核心集闭合

4.2.1 核心集闭合假设

对于一个查询，核心集的定义式代理前缀为有效答案的所有oracle邻居合集，c为核心集大小。核心集闭合表示对于PT查询，任意一个属于核心集C的元素都有另外的元素的所有oracle邻居的代理索引大于它本身的所有oracle邻居代理索引，RT查询则是小于。RT查询总是闭合的，但PT查询可以通过适当处理让核心集不闭合。第三部分对该假设已有介绍，以下讨论两种情况。

第一是c已知。在这种情况下，给定s和m，调用oracle的次数为EOC(s,m)，当EOC(s,m)最小化且满足f(|D|, s,m, c) ≥ 1 - δ可以得到s^*和m^*。通过插入与重新表达，可以将约束最简化为m ≥ m(s)。在m增加时，EOC(s,m)也增加。基于以上条件，一个朴素的s^*和m^*计算方式为计算EOC(s,m)。但是对于这种准确的计算会带来昂贵的数据库开销，求取近似解往往是研究中需要考虑的。根据策略将oracle预期数量表示为|D| - EOC(s,m)，定义节省比率

，越大的节省比率表示更优的近似解。

第二是c未知。引入额外的oracle调用，并应用到Hoeffding边界来确保高成功率。对于RT查询和目标γ，核心集有最大代理索引的top(1-γ)×100% oracle邻居组成。当s与m确定时，f(|D|, s,m, c)随c的增大而增大，让c表示c概率的下界，通过在c已知中提出的约束与最小化，可以得到大概准确的s与m。使用Hoeffding边界可以找到c。对于PT查询，c是难以获得的，通过给定δ和k，也可以应用类似Hoeffding边界为M_p(D_k)找到一个概率下界，称为

，可以通过启发式方法来识别具有良好互补率和高

的D_k。

4.2.2 CSC算法

CSC算法以c为输入，通过最小的oracle调用和经验上良好的互补率返回高效率的答案。下图给出了CSC算法的详细步骤，第二行给出了计算s^*和m^*的方法，并在第三行绘制样本，四到八行根据查询类型返回对应结果。CSE算法则引起了更多的oracle调用，它通过CSC算法找到好的候选按答案，并应用Hoeffding边界来返回有效的答案。

算法二CSC算法

4.2.3 渐进式查询处理

景观算法最小化了oracle的使用，但对于一些挑战性大的查询，oracle调用的最低限度可能还是比较高，为此提出了渐进式查询处理。CSC和CSE算法绘制了m个大小为s的样本来计算K_S和D_Ks，可以在看到每个样本后推导得到k_s，并使用k_s’来选择能够自适应成功概率边界，得到更加好的答案。

5、实验

文章通过广泛的实验证明了PQA在代理质量假设下的性能和CSC在核心集闭合假设下的性能，并且考虑了PQE和CSE在oracle预算，查询时间，CPU开销上与基线的差异性。在数据集和代理的选择上，实验选取了多标签图像识别，医疗和视频三种场景，分别选取数据集，考虑类似的图片，病人和车框架，并使用不同代理。在基线的选取上则是SUPG，TOP-K和Sample2Test，评估指标考虑成功概率，平均互补率，CPU开销和oracle调用数量。以下为部分实验结果。

图二VOC和eICU数据集上具有扰动的PQA算法结果

图三oracle使用和CSC-RT和CSC-PT的经验成功概率

图二可以看出在尊重成功概率约束的情况下，PQA均得到了互补率最高的答案。图三则说明了在核心集闭合的假设下CSC算法的有效性。关于oracle效率的实验，通过对CSE的Oracle使用量进行扰动并作用于多个基线，文章验证了在RT查询时CSE是最有效的算法，而PT查询时，除了Sample2Test其他均取得了很高的成功概率。同样的，在时间效率上，文章提出的算法也大大降低了开销。

6、总结

本文形式化的解决了精确目标查询和召回目标查询两种非常适合机器学习预测结果的范式，并提出了两种假设和四种算法。在五个数据集上进行的实验页说明成本较小但互补率良好，即在查全率和查准率之间取得了良好的平衡。文章提出的框架可以扩展到使用三角不等式等度量属性来优化查询效率，也可扩展到不同精度和成本的代理，这很符合真实场景。目前研究人员正在探索有多个代理所造成的搜索空间指数增长的解决方案。

-End-

本文作者

周敏欣

重庆大学计算机科学与技术专业（卓越）本科二年级在读学生，重庆大学START团队成员。主要研究方向：时空数据挖掘。

时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

机器学习近似算法概率计算 pt 算法

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

VLDB 2023 | 机器学习模型的高效近似查询

评论

相关阅读