使用机器学习对非结构化数据加速查询(具有统计保证的近似选择查询)

本文主要是介绍使用机器学习对非结构化数据加速查询(具有统计保证的近似选择查询),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者:Daniel Kang, Edward Gan, Peter Bailis, Tatsunori Hashimoto, and Matei Zaharia

翻译:殷之涵  校对:方星轩

本文约2800字,建议阅读8分钟

本文以作者第一人称的方式向读者介绍了在2020年8月底对非结构化数据进行具有统计保证的近似选择查询方面所开展的工作,包含查询语义及查询背后的具体算法——如何在实现统计保证的同时提升查询结果的质量。

这篇文章介绍了我们最近在对具有统计保证的近似选择查询方面所开展的工作。虽然此文章将是独立出来的,但还是欢迎参阅我们的其他博客文章,以了解其他相关工作进展和更多背景信息(第1部分)!

正如我们在第1部分中所述,随着强大的深度神经网络(DNN)和人工标记服务(我们统称为“Oracle方法”)的出现,我们可以越来越多地对非结构化数据记录(例如,视频、文本)进行自动化查询。以我们正在与斯坦福生物系研究人员的合作为例,他们已经收集了数百天的实地视频,想要发现蜂鸟的出现与实地微生物记录的匹配规律。

(图注:鸟(左)和空灌木(右)视频的绝大多数是空的(> 99%),因此出于科学目的而变得无趣。)

然而详尽地人工注释这些数据实在太昂贵了——这将花费数十万美元, 因此我们的合伙人不得不做出权衡:通过近似选择(approximate selection)来找到80%的包含蜂鸟的视频帧(即80%的召回率)即可。在执行此类查询时,对科学分析的一项关键要求是实现召回的统计保证,即“在执行查询时,所得记录集将在100次中的95次里具有80%的召回率。” 这些统计保证是进行科学分析所必需的,就像我们在以往的相关工作(详见http://blinkdb.org/)中所做的那样。

先前的工作(包括我们的工作,请参阅我们关于NoScope的博客文章:https://dawn.cs.stanford.edu/2017/06/22/noscope/)旨在通过使用代理模型来加速这些查询,这些模型是“Oracle方法”的廉价近似值,但并不能达到统计保证,下面我们将对此进行说明。为了说明基于代理模型的朴素算法(Naive)无法获得统计上的查询准确性保证,我们在下方展示了在ImageNet数据集上运行100次蜂鸟查询的精度,此时目标精度为90%。正如我们在箱线图中所看到的那样,基于代理模型的朴素算法在过半情况下都无法达到目标精度,甚至出现了实际上返回的精度低至20%的情况,远低于目标值(90%)。

(图注:在ImageNet数据集中查找蜂鸟的朴素算法和SUPG算法。如图,朴素算法在过半情况下都无法达到目标精度。)

先前的工作使用代理模型来生成代理分数,分数代表的是给定数据记录满足oracle谓词(oracle predicate,即通过sql中的where语句得到的满足某些条件的记录,例如“包含蜂鸟”就可以作为对帧查询时的条件)的未经校准的可能性。虽然朴素算法无法获得统计保证,但是我们可以对其做一些修正来达到保证。

在本文的其余部分,我们将介绍带有保证的近似选择查询的查询语义、如何实现这些保证以及如何提高查询结果的质量。

查询语法和语义

为了让用户指定带有统计保证的近似选择(SUPG查询),我们提供了继承自SQL的语法。下面显示的是蜂鸟查询的示例:

1. SELECT frame FROM bush_video  
2. WHERE HUMMINGBIRD_PRESET(frame)  
3. ORACLE LIMIT 10,000  
4. USING MASK_RCNN(frame)  
5. RECALL TARGET 90%  
6. WITH PROBABILITY 95%

我们的工作与先前的工作的关键不同之处在于我们提高了成功的可能性。直观地讲,95%的成功概率意味着:如果某一查询被执行100次,我们希望至少在95次中能够达到召回率/精度的目标值。这样的保证与其他系统为近似聚合查询(approximate aggregation queries)所提供的保证相似,但是对于近似选择查询(approximate selection queries)来说却是新的保证。

最后,为了避免琐碎的解决方案(例如,返回整个数据集确实能够实现100%的召回率,但这样做显然有悖我们的初衷),我们指定查询应尽可能精确地返回(即刚好保证90%的召回率,以上方的蜂鸟查询代码为例)。

实现统计保证

如前文所示,使用代理分数的朴素算法无法获得查询准确性的统计保证。为了解其原因,我们将概述朴素算法背后的算法过程,并说明问题出在哪里。

所有算法(包括先前的工作和我们的工作)都遵循相同的基本过程:

1. 对所有数据记录都分别生成代理分数

2. 在记录中对oracle谓词(oracle predicate,即通过sql中的where语句得到的满足某些制定条件的记录,下同)进行采样

3. 使用这些样本为代理分数设置阈值

4. 返回代理得分高于所选阈值的所有记录

要了解朴素算法为什么无法实现统计保证,让我们通过一个以60%为目标召回率的典型示例来说明。在下图中,蓝色记录代表与oracle谓词匹配的记录(即该帧包含蜂鸟),红色记录代表与oracle谓词不匹配的记录(即该帧不包含蜂鸟),这些记录是按代理分数进行排序的。在这个示例中,我们显示了一组记录,这些记录是被均匀随机抽样的,样本中的经验阈值为60%(即样本内召回率为60%时的代理分数阈值所在之处,在下图中由虚线表示)。显而易见的是,样本中的60%并不能反映整个数据集中的60%!这个例子具有更普遍的含义:朴素算法并不考虑采样中的随机性,并且很有可能失败。

(图注:使用样本内经验阈值朴素算法示例。这些朴素算法并未对抽样偏差进行校正,因此有较大概率无法实现目标。)

为了校正采样中的随机性,我们使用置信区间来限制失败的可能性。回到之前的相同示例,我们将用如下图所示的方式在样本中绘制经验阈值。但是,这一次我们不只是简单地返回超过该经验阈值的记录,而是在整个数据集中构建一个60%召回率的置信区间。

(图注:使用同样朴素算法的示例,但通过置信区间对经验阈值进行了校正。该算法实现了统计保证,但仍然可能返回质量较低的查询结果。)

为了把我们的算法(SUPG查询,即带有统计保证的近似选择)与朴素算法进行对比,我们在下图中展示了当尝试在四个真实数据集上实现90%的召回率时,运行100次的实际召回率。如我们所见,朴素算法始终失败,而SUPG算法成功的可能性很高。

(图注:当尝试实现90%召回率时SUPG算法和朴素算法100次运行的召回率表现。SUPG算法有较高概率成功,而朴素算法却正相反。)

实现高质量查询结果

我们在上文中已得知,使用具有置信区间的均匀采样会产生有效但质量较差的查询结果。为了提高查询质量,我们利用代理模型在为我们提供有关查询信息方面的关键属性:理想状态下,较高的代理分数表示该记录与oracle谓词相匹配可能性更高。

为了利用这一属性,我们使用“重要性采样”,即对代理得分较高的记录进行更多的采样。但是,我们的设置与标准重要性采样方法不同,因为真实数量(oracle谓词结果)是二项的(例如有或无蜂鸟出现)。为了说明不同的假设,我们提出了一种新的重要性加权方法——我们基于代理分数的平方根进行成比例的采样。至于为何这种加权方法是最佳设置,我们在这里不过多展开讨论,但是可以参阅这篇论文(https://ddkang.github.io/papers/2020/supg-paper.pdf)以获取详细信息!

(图注:使用同样重要性采样算法并通过置信区间对经验阈值进行了校正的示例。重要性采样在实现统计保证的同时提升了查询结果质量。)

为了说明重要性采样算法的实用性,我们展示了四个真实数据集上的召回目标查询的查询精度。我们改变召回率目标并显示相应的精度——高精度意味着表现更好。如我们所见,重要性采样算法在数据集中的表现优于均匀采样算法。

 

(图注:基于特定召回目标的SUPG算法和均匀采样算法在4个真实数据集上的精度表现(精度更高意味着表现更好)。重要性采样的表现在各数据集上都要更好。)

 

结论

在本篇博客中,我们描述了具有统计保证的近似选择查询的查询语义,以及能够高效执行此类查询的算法。我们还将在本周的VLDB 2020上介绍我们的工作——欢迎来听听我们的演讲!我们的代码都是开源的,并且非常有兴趣了解相关的新应用;如果您想进一步讨论,请通过supg@cs.stanford.edu与联系我们。

原文标题:

Accelerating Queries over Unstructured Data with ML, Part 2 (Approximate Selection Queries with Statistical Guarantees)

原文链接:

https://dawn.cs.stanford.edu/2020/08/31/supg/

译者简介:殷之涵(Jane),研究生毕业于康奈尔大学生物统计与数据科学专业,本科毕业于普渡大学精算与应用统计专业。

END

版权声明:本号内容部分来自互联网,转载请注明原文链接和作者,如有侵权或出处有误请和我们联系。


合作请加QQ:365242293  

数据分析(ID : ecshujufenxi )互联网科技与数据圈自己的微信,也是WeMedia自媒体联盟成员之一,WeMedia联盟覆盖5000万人群。

这篇关于使用机器学习对非结构化数据加速查询(具有统计保证的近似选择查询)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/943222

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

Pandas透视表(Pivot Table)的具体使用

《Pandas透视表(PivotTable)的具体使用》透视表用于在数据分析和处理过程中进行数据重塑和汇总,本文就来介绍一下Pandas透视表(PivotTable)的具体使用,感兴趣的可以了解一下... 目录前言什么是透视表?使用步骤1. 引入必要的库2. 读取数据3. 创建透视表4. 查看透视表总结前言

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读