【技术】如果我告诉你数据库索引是可以学习的,你会怎么做?

这篇论文是我在NIPS中看到的,在过去的几天里,在ML的圈子里得到了相当多的关注。论文中反复强调:在他们的心里,数据库索引是模型。它们可能不(通常)是有统计学意义的,但它们是提供(希望相当快的)输入(索引创建的关键)和输出(内存中的位置)之间的映射的结构。二叉树,是一种典型的有序数据结构,甚至采用了树的形式,这是机器学习工具箱中的核心工具。

论文地址:https://www.arxiv-vanity.com/papers/1712.01208/

在这一关键的直觉上,该论文提出了这样的问题:如果这些结构只是模型,那么可以通过统计模型来学习,然后利用这些模型,被索引的数据的分布比目前使用的索引更好,更小,更有效吗?剧透:答案(至少对于数值型数据类型)是肯定的。

例如,它可能的情况是,所有的元素都是一样的长度,并且每个数字键的位置都会增加5:在这种情况下,你可以很容易地学习键和位置之间的线性回归映射,其速度远远超过有序分裂的B树。B树在最坏的情况下也是有效的,在这种情况下,数字键位置的CDF密度(如果你将其排序为一行的话)是真正随机的,并且假设其是未知的。

关于B树的一个有趣的事实是,每当添加新数据时,它们都需要重新平衡,作者认为这与重新训练模型类似。因此,出于比较的目的,他们只是比较了训练集的性能,因为B树和候选统计模型只有在经过重新训练才会起作用。

作者通过训练一个基线模型开始:包含2层,32个隐藏单元,并且紧密相连的网络。这个模型有两个主要问题。

  1. 首先,它生成预测min / max的搜索位置作为关键函数的速度非常缓慢:它需要在Tensorflow中训练,这需要很高的前期成本,对于这个小模型来说不值得。
  2. 其次,它在单个键的级别上并不是很精确。虽然它在学习累积键分布的整体形状方面做得很好,但它避免了CDF函数中局部变量的过度拟合,因此当你在关键空间的小区域“放大”时,它就变得不那么准确了。正因为如此,它并没有显著地加快查找过程,而是在做一个完整的基线键扫描。按照他们设计这个问题的思路,一个简单的模型可以很容易地将预期搜索误差从1亿减少到10000,但是由于模型中固有的平滑性假设,很难将其降低到100s量级。

解决这些问题有两个关键的解决方案:一个是实现细节,一个是理论创新。第一个是相对简单的(至少在概念上是这样):构建一个框架,通过该框架,你可以在Tensorflow中训练模型,但是模型的推理阶段是在c++中进行评估的。这使得以前测试的基准模型的性能显着提高:从80,000ns降至30ns。

第二,框架作为解决“最后一英里”精度问题的解决方案,是递归模型。在这个框架中,我们从训练一个“顶层”模型开始,该模型输出对键的位置的预测。然后,我们把空间分成三个部分,然后分别学习每个子区域的模型。例如,顶层模型可以预测出,在一个10000长内存区域内,键4560将映射到位置2000。因此,他们根据顶层模型的预测,将观测结果分组,并对新模型进行特定训练,比如,预测位置在0到3500之间的键。

当这种方法——使用优化代码的层次结构模型——在带有数字键值的数据上进行尝试时,结果令人印象深刻。与B树相比,学习索引实现了有意义的提速,提高了超过60%。值得注意的是,下面的结果并不使用GPU。这表明,如果GPU在数据库硬件中变得更标准,这种改进甚至可能会增加。

它们目前只显示了对数字键建模的成果,但建议将目前用于文本(RNNs,character -level CNNs)的更复杂的方法添加到这个通用框架中。

为什么所有这些都是有趣的,除了可能导致新一代数据库索引设计的实际事实?

首先,我要承认,这篇论文在我在心里有特殊的意义。它除了介绍一些引人注目的ML概念之外,还使我更深入、更清晰地思考了索引工作背后的机制,而以前,这一直是我简单理解但没有深入研究的内容。

其次,利用机器学习模型来优化他们所运行的各种低级系统,这似乎有现实意义。这是我记得的第一批使用机器学习来优化计算过程的论文之一,但似乎不太可能是最后一个。

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2017-12-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【深度学习会被可微分编程取代?】展望30年后的神经网络和函数编程

作者:colah 译者:文强,刘小芹 【新智元导读】在Yann LeCun“深度学习已死”的惊人发言下,可微分编程的概念引发了广泛关注。机器学习著名博主cola...

3554
来自专栏机器之心

学界 | 减少模型半数内存用量:百度&英伟达提出混合精度训练法

机器之心编译 选自:arXiv 参与:李泽南、蒋思源 ? 深度学习的模型正在变得越来越复杂,所需要的计算资源也越来越多,在开发更加强大的硬件的同时,很多人也在致...

3039
来自专栏IT派

读懂概率图模型:你需要从基本概念和参数估计开始

概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团队邀请数据科学家 Prasoon Goyal 在其博客上分两部分发表了一篇有关概率图模型的...

3944
来自专栏AI科技评论

微软IJCAI演讲PPT Part II:深度学习在统计机器翻译和对话上的应用

前天我们翻译了微软关于NLP(自然语言处理)的PPT的概览部分,今天我们为大家带来了这份PPT的第二部分:同上次一样,我们将翻译内容放在图里的同时也写在了下面,...

3106
来自专栏机器之心

读懂概率图模型:你需要从基本概念和参数估计开始

选自statsbot 作者:Prasoon Goyal 机器之心编译 参与:Panda 概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团...

34511
来自专栏开心的学习之路

知识篇——聚类算法应用

时隔两月开始继续储备机器学习的知识,监督学习已经告一段落,非监督学习从聚类开始。 非监督学习与监督学习最大的区别在于目标变量事先不存在,也就是说 监督学习...

3165
来自专栏AI科技大本营的专栏

AI技术讲座精选:NLP 模型到底选 RNN 还是 CNN?

【AI100 导读】本文系统地对比了 CNN 和 RNN 在 NLP 各大任务上的表现,包括:情感分类、关系分类、文本蕴含、答案选择、问题关系匹配、PQA、词...

3104
来自专栏AI研习社

谷歌 AI:语义文本相似度研究进展

最近基于神经网络的自然语言理解的研究的迅速发展,尤其是关于学习文本语义表示的研究,使一些十分新奇的产品得到了实现,比如智能写作与可对话书籍。这些研究还可以提高许...

1182
来自专栏人工智能

ML工作流程(第5部分) - 特征预处理

我们已经讨论了ML工作流程的前四个步骤。到目前为止,我们通过DICTR(离散化,积分,清理,转换,还原)对原始数据进行预处理,然后采用特征提取的方式将数据转化为...

2200
来自专栏数据派THU

一文读懂机器学习概率图模型(附示例和学习资源)

来源:机器之心 本文长度为10085字,建议阅读15分钟 本文结合基础应用示例系统性的为你讲解概率图模型。 概率图模型是人工智能领域内一大主要研究方向。近日,数...

6969

扫码关注云+社区