Daniel Daniel,Peter Bailis和Matei Zaharia作者王雨桐、林亦霖校对王菁编辑Kay翻译

使用机器学习加速对非结构化数据的查询-第1部分(使用BlazeIt加速聚合和限制查询)

本文为大家介绍了针对非结构化数据如何加快聚合和限制查询。

随着强大的深度神经网络(DNN)和人工标记服务(我们统称为“Oracle方法”)的广泛使用,我们可以越来越多地对非结构化数据记录(例如,视频、文本)进行自动化查询。例如,城市规划人员通过查询路边摄像头的视频对车辆进行计数,以了解交通状况。律师可以提取包含雇员/雇主信息的电子邮件(关系提取)来发现有效信息。

执行此类查询的一种简单方法是使用Oracle方法将非结构化数据记录完全转化为结构化信息。例如,对象检测DNN可以从视频的帧中提取对象类型和对象位置,或者基于BERT的DNN可以提取员工/雇主信息。

然而这种传统查询方法的运行成本可能非常高:对象检测DNN的执行速度比实时慢十倍,而人工标注可能要花费数十万美元。为了减少此类查询的成本,NoScope、概率预测等使用了代理模型(proxy model)的方法,它通过训练类似oracle方法的廉价模型得到代理分数,主要是针对二元预测的即席(ad-hoc)方式。但是要对非结构化数据执行查询还有很多工作要做。下面开始介绍我们小组中针对这一问题的几个新项目。

我们将发布一系列博客文章,描述我们最近在对非结构化数据查询进行加速优化方面的工作:

  • 本文将描述即将在VLDB 2020上发表的最新工作BlazeIt。我们将描述如何加快聚合和限制查询
  • 在第2部分中,我们将介绍一类新的查询:具有统计保证的近似选择查询(SUPG查询)。我们将描述为什么我们需要统计保证,其语义以及这些查询的有效算法。SUPG也将在VLDB 2020上展出!
  • 第3部分将描述基于DNN的可视数据查询中的系统瓶颈。我们将展示视觉数据的预处理是当前一个主要瓶颈,以及如何解决这一瓶颈。关于这项工作的论文将在VLDB 2021中发布。
  • 第4部分将介绍如何为相同数据上的各种查询建立索引。我们将展示如何使用索引来有效地回答以前的博客文章及更多文章中的所有查询

代理分数(Proxy Score)

此前在近似二元预测(approximating binary predicates)的语境查询中已经使用了代理模型。这些算法遵循相同的通用策略:使用oracle方法中的标签训练更小更便宜的代理模型。然后代理模型会为每个数据记录生成一个分数,该分数会估计oracle预测的可能性。例如,我们可以训练一个小的DNN来估计汽车是否在视频帧中。

但是许多需求不止是简单地执行二元分类。如查询每帧视频是否有汽车存在,并不能统计每帧视频的汽车数量。

为了纠正这个问题,我们引入了二元分类之外的代理模型。本文将重点介绍代理模型,这些代理模型用于将oracle方法产生的任意值近似于非结构化数据记录。在摄取时,我们的系统使用oracle方法处理一小部分记录:然后在查询时使用这些记录来训练代理模型以估计oracle的结果。

查询中使用代理分数

现在我们可以生成代理分数来近似计算统计信息的oracle方法结果,我们如何使用这些分数来回答查询?我们将简要描述如何完成近似聚合和基数限制的选择查询

系统总览

BlazeIt具有两个关键组件:摄取(离线)组件和查询处理组件。在离线组件中,BlazeIt将使用oracle方法注释一个非结构化数据记录的示例:这些注释用于训练代理模型。BlazeIt的查询处理组件将执行查询,并为每个查询训练新的代理模型。下图展示了Blazelt的系统。

系统总览,BlazeIt尝试在受限的情况下尽可能有效地回答查询

近似汇总

我们描述的第一种查询类型是加速聚合查询,该查询对数据集中的每条记录统计数据进行近似处理(如对每帧视频的汽车数量进行计数)。我们侧重于近似聚合,因为要提供准确的查询答案需要穷举执行oracle方法,而这是非常昂贵的。为了避免详尽实现,我们提供了两种查询处理算法。

我们证明了可以直接使用代理分数来回答近似聚合查询。由于代理分数和基本事实接近,因此我们可以直接汇总分数。例如要计算每条记录的平均值,我们可以对代理分数求和,然后除以记录总数。由于代理模型是通过oracle方法训练的,所以代理和oracle之间的误差将理想地平均化。经证实,直接使用代理分数比回答聚合查询的替代方法要有效得多。

虽然直接使用代理分数可能是有效的,但某些应用程序需要查询准确性的统计保证。为了满足这种需求,我们可以在近似查询处理(AQP)技术的启发下,使用采样技术来加速近似聚合查询。通过适当地使用置信区间,我们可以实现查询的统计保证。但是标准的AQP技术在采样中不使用代理分数,这是有价值的信息来源。为了利用代理评分,我们将它们用作控制变量,这是一种统计方法,可以减少抽样方差。最后我们将控制变量与始终有效的停止算法结合在一起,该算法使用较少样本且方差较小的样本,称为EBS停止。综合讲,这可以使我们的系统在给定的误差水平下使用更少的样本。下图展示了控制变量和算法概述-算法的关键部分是算法始终有效,并根据样本方差终止。

控制变量示意图。m(t)是真实值,a(t)是代理分数。虽然并不总是精确的,但a(t)可以近似为m(t)。

EBS停止的伪代码,如果满足差异条件,它将提前停止

为了展示我们算法的效用,我们展示了它们在近似计算每帧视频的汽车数量上的性能。关于每帧视频是否有汽车的问题,我们将原始方法与使用代理模型的方法进行比较。如下图所示,我们的方法大大优于基准方法。尤其是已知某汽车在视频帧中出现,并不能了解该汽车是否在视频中普遍存在。


BlazeIt's 与详尽注释,二进制检测工作和随机抽样相比,聚合查询的性能更高。如图所示,BlazeIt优于所有基准


基数限制选择

我们描述如何加速的第二种查询类型是基数有限的选择查询,用于找到满足某些条件的少量记录。这些查询通常用于手动研究异常事件。

为了加快这些查询的速度,我们使用代理分数对感兴趣的记录进行排名。尤其是,我们训练一个代理模型来估算感兴趣的数量(例如,一帧中的汽车数量)并根据这些分数进行排名。我们发现,即使此类事件很少发生,代理模型在排名最高的数据记录中也可以具有很高的精度。

下图中显示了算法的性能(有和没有代理模型的效果)和基线。与近似聚合一样,对于异常事件的基数限制选择,我们的算法大大胜过传统方法和随机抽样。

与详尽的注释,先前的二元分类工作和随机采样相比,BlazeIt在极限查询上的性能更高。如图所示,BlazeIt优于所有基线。

结论

由于机器学习的发展,非结构化数据查询变得越来越可行。但是部署oracle方法的成本很高,因此执行此类查询的费用可能会过高。我们本文中介绍了使用代理得分来加速汇总和限制查询的方法,我们希望这些方法可以开始对非结构化数据进行查询。在下一篇博文中,我们将介绍如何通过统计保证执行近似选择查询

相关阅读

  • Accelerating Queries over Unstructured Data with ML, Part 2 (Approximate Selection Queries with Statistical Guarantees) 31 Aug 2020(https://dawn.cs.stanford.edu/2020/08/31/supg/)
  • How do MLPerf v0.7 entries compare on cost? 17 Aug 2020(https://dawn.cs.stanford.edu/2020/08/17/mlperf-v0.7-cost/)
  • Selection via Proxy: Efficient Data Selection for Deep Learning 23 Apr 2020(https://dawn.cs.stanford.edu/2020/04/23/selection-via-proxy/)
THU数据派
THU数据派

THU数据派"基于清华,放眼世界",以扎实的理工功底闯荡“数据江湖”。发布全球大数据资讯,定期组织线下活动,分享前沿产业动态。了解清华大数据,敬请关注姐妹号“数据派THU”。

工程机器学习
相关数据
近似计算技术

近似计算是一种计算技术,它返回可能不准确的结果而不是保证的准确结果,并且可以用于近似结果足以满足其目的的应用。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

关系提取技术

关系抽取任务需要检测和分类一组工件中的语义关系提及,通常来自文本或XML文档。该任务与信息提取(IE)的任务非常相似,但是IE另外需要去除重复关系(消歧),并且通常指的是提取许多不同的关系。

基准技术

一种简单的模型或启发法,用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

提前停止技术

在机器学习中,提前停止是一种正则化形式,用于在用迭代方法(例如梯度下降)训练学习器时避免过度拟合。 这种方法更新了学习器,使其更好地适合每次迭代的训练数据。 这提高了学习器在训练集之外的数据上的表现。 但是,提高学习器对训练数据的适应性是以增加的泛化误差为代价的。 提前停止规则提供了在学习器开始过度训练之前可以运行多少次迭代的指导。提前停止规则已经在许多不同的机器学习方法中使用,理论基础不尽相同。

伪代码技术

伪代码,又称为虚拟代码,是高层次描述算法的一种方法。它不是一种现实存在的编程语言;它可能综合使用多种编程语言的语法、保留字,甚至会用到自然语言。 它以编程语言的书写形式指明算法的职能。相比于程序语言它更类似自然语言。它是半形式化、不标准的语言。

置信区间技术

在统计学中,一个概率样本的置信区间(Confidence interval),是对这个样本的某个总体参数的区间估计(Interval Estimation)。置信区间展现的是,这个总体参数的真实值有一定概率落在与该测量结果有关的某对应区间。置信区间给出的是,声称总体参数的真实值在测量值的区间所具有的可信程度,即前面所要求的“一定概率”。这个概率被称为置信水平。举例来说,如果在一次大选中某人的支持率为55%,而置信水平0.95上的置信区间是(50%, 60%),那么他的真实支持率落在50%和60%之区间的机率为95%,因此他的真实支持率不足50%的可能性小于2.5%(假设分布是对称的)。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

法大大机构

深圳法大大网络科技有限公司(www.fadada.com)是国内领先的第三方电子合同平台,主要为金融、房地产、汽车、人力资源服务、教育、保险、第三方支付、旅游、医疗、物流、供应链、B2B、B2C线上交易平台等行业以及政府机构提供电子合同、电子文件签署及存证服务,同时整合提供司法鉴定和律师服务等增值服务。

https://www.fadada.com
暂无评论
暂无评论~