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

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

作者: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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd