凯发k8网页登录
领先车焦点 > 行情 > 重现当年alphago神来之笔,deepmind新ai发现提速70%排序

重现当年alphago神来之笔,deepmind新ai发现提速70%排序-凯发k8网页登录

编辑:兰心雪   时间:2023-06-10 08:15  来源:it之家  阅读量:19983     

deepmind 又双叒叕带着重磅成果登 nature 了!

这一次,他们又一强化学习 ai,在计算机领域最最最基础的两个算法上做了新突破:

一个是排序算法,发现了速度最高可提升 70% 的新实现;

另一个是哈希算法,也找到了速度提高 30% 的新方法。

不仅如此,该 ai 所用方法被称为“重现当年 alphago 的神来之笔”,也就是看似违法直觉,实则一举击败人类高手李世石的那次。

消息一出,立刻引爆学术圈,有网友就直呼:

没想到这么古老又基础的算法还能被进一步改进。

而正是因为这一最新成果,十年都没有更新的 llvm 标准 c 库都更新了,并且数十亿人将会受益。

因为,无论是排序还是哈希,它们的应用场景从在线购物、云计算到供应链管理等各个场景都能用到,每天会被调用上亿次!

不过,如 deepmind 所说:

大家千万不要太兴奋了,ai 的力量用于代码效率提升才刚刚开始。

alpha 家族“新贵”发现更快排序算法

这个 ai 名叫 alphadev,属于 alpha 家族“新贵”,并且基于 alphazero 打造。

它的发现并非基于现有算法,而是从最底层的汇编指令开始摸索的。

deepmind 的研究员给它设计了一种单人“组装”游戏:

只要能够搜索并选择出合适的指令,正确且快速地排好数据(下图 b 流程),就能获得奖励。

但这个游戏的挑战不仅在于搜索空间的大小,也在于奖励函数的性质,因为一条错误指令就可能会使整个算法失效。

alphadev 拥有两个核心组件:学习算法和表示函数。

其中,学习算法主要是在强大的 alphazero 上扩展的,它可以结合 drl 和随机搜索优化算法来进行巨量的指令搜索;主要的表示函数则基于 transformer,它能够抓住汇编程序的底层结构,并表示成特殊的序列。

随着 alphadev 不断地打怪升级,研究员还会限制它能执行的步数,以及待排序列的长度。

最终,alphadev 发现了一种全新排序算法:

如果序列较短,相比人类基准排序算法,它能将速度提高 70%;如果序列长度超过 25000 个元素,则提高 1.7%。

具体而言,该算法的创新主要在于两种指令序列:

alphadev swap move(交换移动)

alphadev copy move(复制移动)

如下图所示,左边是利用了 min 的原始 sort3 实现,右边是通过“alphadev swap move”,只需要 min (a,b) 的实现。能够发现可以省掉一步指令,还只需要算出 a 和 b 的最小值即可。

作者表示,这种新颖的方法让人想起当年 alphago 的“第 37 步”—— 一种违反直觉的下法却直接击败传奇围棋选手李世石,让观众全都震惊不已。

同样,alphadev 则是通过交换和复制移动,跳过了一个步骤,以一种看似错误但实际上是捷径的方式达成目标。

如下图所示,在对 8 个元素进行排序的算法中,alphadev 也同样利用“alphadev copy move”,用 max ) 替换了原始实现中更为复杂的 max (b, min (a, c, d)) 指令,并且使整个算法的指令总数也减少了一步。

而在发现更快的排序算法后,作者也用 alphadev 试了试哈希算法,以此证明其通用性。

结果也没有让人失望,alphadev 在 9-16 字节的长度范围内也实现了 30% 的速度提升。

和排序算法一样,他们已将新方法集成到了 abseil 库中,全球数百万开发人员现在都可以使用。

最后,作者表示,两种新算法的实现显示 alphadev 具有强大的发现原始凯发真人首先娱乐的解决方案的能力,并且将使我们进一步思考计算机领域基础算法的改进方式。

不过,由于本次研究中使用的汇编语言具有局限性,他们接下来还是打算尝试 alphadev 在高级语言中优化算法的能力。

网友:不算发现新的排序算法

对于这一成果,不少人表示非常兴奋。

如这位网友所说:

alphago 惊艳全世界后,强化学习还能做什么?还能做任何有实际意义的事情吗?这就是答案。

不过这次,有不少人指出,deepmind 似乎有夸大标题的嫌疑。

它计算的是算法延迟,而非传统意义上的时间复杂度。如果真算时间复杂度,数据可能不好看。

它改进的并不是排序本身,而是在现代 cpu 上做新的排序。这种操作其实不算罕见,比如 fftw、atlas 这些库就是这么做的。

同意,他们只是为特定 cpu 找到了更快的机器优化,并不算发现新的排序算法,方法本身很酷,但还不算开创性研究。

大家怎么看?

论文地址:

官方博客:

参考链接:

郑重声明:此文内容为本网站转载企业宣传资讯,目的在于传播更多信息,与本站立场无关。仅供读者参考,并请自行核实相关内容。

网站地图