谷歌DeepMind打破算法封印！AlphaDev登场颠覆人类算法格局

今天，「Alpha」家族再添一名新成员：AlphaDev。

整个计算生态系统的基础，或将被AI创造的新算法颠覆！

(资料图)

谷歌大脑和DeepMind合体没多久，就带来这样一个惊世之作。

AlphaDev不仅可以将排序算法提速70％，甚至在有的算法上，能比人类快3倍之多。

十多年来，C++排序库首次更改。AI优化世界代码，又达新里程碑。

目前，最新研究已登上Nature。

通过强化学习，AlphaDev发现了更加有效的算法，直接超越了科学家和工程师们几十年来的精心打磨。

现在，新的算法已经成为两个标准C++编码库的一部分，每天都会被全球的程序员使用数万亿次。

有网友表示，终于来了，我们现在正在踏入未知领域：人工智能正在构建人工智能！

01 强化学习打破十年算法瓶颈

如同AlphaZero、AlphaFold等前辈一样，AlphaDev也直接掀起了一个领域的变革。

DeepMind计算机科学家、论文一作Daniel Mankowitz表示，「我们起初根本不相信。」

「说实话，我们没有想到会取得更好的成绩：这是一个非常短的程序，而这些类型的程序，此前已经被研究几十年了。」

当前，GPT-4、Bard等大模型的参数指数级增长，对算力等资源的需求不断增长。而过去50年里，人类不断依靠芯片的改进以跟上步伐。

但随着微芯片接近物理极限，改进代码让计算更强大、更持续变得至关重要。尤其是，对每天运行数万亿次代码的算法愈重要。

今天，Google DeepMind在Nature发表的论文中，首次介绍了阿尔法家族的「新贵」AlphaDev。

AlphaDev发现了一种更快的排序算法，数十亿人每天都在不知不觉中使用这些算法。

它们是一切的基础，从在线搜索结果，社交帖子，到计算机和手机数据处理方式。这些算法每天都要执行数万亿次。

利用AI生成更好的算法，将改变我们对计算机编程的方式，并影响我们数字化社会的方方面面。

根据Nature论文中的数据，AlphaZero所创造的算法能比人类的数据排序速度快三倍。

开源地址：https://reviews.llvm.org/D118029

今天，Google DeepMind还开源了在主C++库中的最新排序算法，所有人皆可用。

02 什么是排序？

排序是一种以特定顺序组织多个项目的方法。

比如按字母顺序排列三个字母，从大到小排列五个数字，或者将包含数百万条记录的数据库排序。

在人类历史中，排序方法一直在演变。最早的例子可以追溯到二、三世纪，那时的学者们在亚历山大图书馆的书架上，靠纯手工的方式，以字母顺序排列摆放了数千本书。

工业革命后，我们发明了可以帮助分类的机器——制表机将信息存储在穿孔卡上，用于收集1890年美国的人口普查结果。

而随着20世纪50年代商业计算机的兴起，出现了最早的计算机科学排序算法。

在今天，世界各地的代码库中都使用了许多不同的排序技术和算法，在线组织大量数据。

排序算法，也就是输入一系列未排序的数字，然后输出排序后的数字

这些算法，都已成为计算机科学的基石。

如今我们的算法，都需要计算机科学家和程序员投入几十年的研究去开发。

这是因为，现有的算法效率如此之高，再往前的每一步改进，都是重大的挑战。

这个艰难程度就好比找到一种节省电力能源的新方法，或者找到更高效的数学方法。

03 寻找新算法

AlphaDev的创新意义在于，它并不是通过改进现有算法，而是完全从头开始发现了更快的算法。

而且，它竟然着手于大多数人类并没有想到的地方——计算机汇编指令。

汇编指令用于创建二进制代码。虽然开发者写代码时用的是C++等高级语言，但为了让计算机理解，这些高级语言必须翻译成「低级」的汇编指令。

我们一般用C++之类的高级编程语言写代码，然后使用编译器将其转换为低级CPU指令，即汇编指令。汇编器再将汇编指令转换为可执行的机器代码

谷歌DeepMind的研究者相信，在这个较低的层级中存在许多可改进的空间，而这些改进在更高级的编程语言中可能很难发现。

在这个更低的级别上，计算机的存储和操作都更灵活，因此如果再多做一些潜在的改进，就会对速度和能源产生巨大的影响。

图A：一个最多排序两个元素的C++算法 图B：代码相应的程序集

04 AlphaDev：汇编版AlphaZero

众所周知，DeepMind的强化学习模型，在围棋、国际象棋和将棋等游戏中，屡次击败世界冠军。

而我们这次的主角——AlphaDev，基于的正是AlphaZero。

AlphaDev的工作方式与之前的AlphaZero相似，后者结合了计算机推理和直觉，在棋盘游戏中选择每一步的走法。

只不过，AlphaDev并不会选择下一步怎么走棋，而是选择添加哪些指令。

为了训练AlphaDev来发现新的算法， DeepMind将排序问题转化成了一个「汇编游戏」（Assembly Game）。

在每一轮中，AlphaDev都需要观察它生成的算法以及中央处理器（CPU）中包含的信息，并通过在算法中添加一条指令来进行移动。

而这个汇编游戏非常困难，因为AlphaDev必须有效地搜索大量可能的指令组合，从而找到一个可以排序且比当前最佳算法更快的算法。

其中「可能的指令组合」，甚至可以直接类比于宇宙中的粒子数量，或者国际象棋（10^120局）和围棋（10^700局）中可能的走法组合。

更进一步的是，任何一个错误的移动，都可能会使整个算法无效。

最后，DeepMind会根据AlphaDev正确排序数字的能力以及完成排序的速度和效率给予奖励，而AlphaDev则需要通过发现一个正确且更快的程序来赢得游戏。

图A：汇编游戏。玩家AlphaDev以系统状态st为输入，并通过选择一条汇编指令将其添加到已经生成的算法中来进行一次移动。 图B：奖励计算。在每次移动后，生成的算法会接受测试，智能体将根据算法的正确性和响应时间获得奖励。

具体来说，在进行深入思考（deliberation）时，AlphaZero会在每一个决策点琢磨下一步可能的行动，以及下一步的下一步的可能性。就像树状图一样，一步步往后推，算出哪些行动最有可能成功。

但问题在于，如果把每一个可能的情况分支都考虑到，所需的时间可能要比宇宙的年龄还长。因此，研究人员使用类似直觉（intuition）的东西来缩小范围。

在每一步中，程序将当前状态输入神经网络（一个复杂的、可调的数学函数），以找到最合适的行为。同时，在训练过程中，神经网络还会根据结果不断进行更新。有时还会故意不选评分最高的行为来进行主动探索。

AlphaDev可以采取的行动一共有四种，包括比较不同值、移动数值到另一个位置、或者跳转到程序的不同部分。

在执行完每一步之后，再试图对一组列表进行排序，并根据正确排序的列表中的数值数量获得奖励。

如此这般，这般如此，一直到排完整个列表，或者达到程序长度限制，从头开始一个新的程序。

C++运行速度提升70%

AlphaDev发现新的排序算法，为LLVM libc++排序库带来了明显的改进。

对于较短的序列，速度提高了70%，而对于超过250,000个元素的序列，速度只提高了约1.7%。

研究人员专注于改进3-5个元素较短的序列排序算法。

这些算法是使用最广泛的算法之一，因为它们经常作为更大排序函数的一部分被多次调用。

改进这些算法可以为任何数量的项目的排序提升整体的速度。

为了使新的排序算法为所有人可用，研究人员还将其进行了逆向工程，并将其翻译成「程序猿」最常用的一种编码语言C++。

目前，这些算法现在可以在LLVM libc++标准排序库中找到。

散列函数效率提升30%

在发现更快的排序算法之后，DeepMind测试了AlphaDev是否能够推广并改进不同的计算机科学算法——散列（Hash）。

散列是计算中的一种基本算法，用于检索、存储和压缩数据。就像图书管理员使用分类系统来找到特定的书籍一样，散列算法帮助用户知道他们正在寻找的内容以及确切的位置。

这些算法将特定的key（例如用户姓名「Jane Doe」）进行散列处理，也就是，将原始数据转换为唯一的字符串（例如1234ghfty）。然后，计算机会使用这个散列值来快速检索与键相关的数据，而不是搜索所有数据。

结果显示，当应用于散列函数的9到16字节范围时，AlphaDev发现的算法比传统算法快30%。

现在，DeepMind也将新的散列算法发布到了开源的Abseil库中。据了解，这个算法预计每天都会被使用数万亿次。

两种新策略：「swap move」和「copy move」

AlphaDev不仅发现了更快的算法，还发现了新的方法。

它的排序算法包含新的指令序列，每次应用时都会保存一条指令。这可能会产生巨大的影响，因为这些算法每天被使用数万亿次。

研究人员将其称之为「AlphaDev swap move」和「AlphaDev copy move」。

最新方法让人想起AlphaGo让人震惊的「第37步」。

2016年那场人机大战中，AlphaGo下了一颗违反人类直觉的棋，一个简单的肩冲，击败了传奇围棋选手李世石。

通过这两种策略，AlphaDev跳过了一个步骤，以一种看起来错误，但实际上是快捷方式连接项目。

这表明，AlphaDev有能力发现原创性解决方案，并挑战了我们对如何改进计算机科学算法的思考方式。

如下图示例原始sort3实现，有min(A, B, C)，使用AlphaDev Swap Move，AlphaDev发现，你只需要min(A, B)。

再比如，原始实现用max(B, min(A ,C, D))中较大的排序算法对8个元素进行排序。

AlphaDev发现使用其「swap and copy moves」时只需要max(B, min(A, C))。

优化全世界的代码，一次一个算法

通过优化和推出全球开发者使用的改进排序和散列算法，AlphaDev证明了，它有能力概括和发现世界级的新算法。

Google DeepMind认为，AlphaDev是朝着开发AGI工具迈出的一步，这些工具有助于优化整个计算生态系统，还能解决其他有益于社会的问题。

不过，研究人员也承认，目前AlphaDev在低级汇编指令优化能力非常强，但是随着算法的发展也存在局限性。

为了让开发者更可用，AlphaDev用高级语言（如C++）优化算法的能力正在探索中。

AlphaDev的新发现，如「AlphaDev swap move」和「AlphaDev copy move」，不仅表明它可以改进算法，还可以找到新的解决方案。

研究人员希望，这些发现能激励研究人员和开发人员创造技术和方法，进一步优化基础算法，以创建一个更强大、更可持续的计算生态系统。

05 网友热评

英伟达科学家Jim Fan对AlphaDev做了一个深度总结：

排序算法是所有关键软件的基础。DeepMind的AlphaDev将小序列（3-5项）的排序速度提高了70%。要点：

-  主要的RL算法是基于最初下围棋Go、Chess & Shogi的AlphaZero。同样的想法也适用于搜索程序！

- 研究人员没有对C代码进行优化，而是对汇编代码进行优化。这是一个刻意的选择，去低级别的挤压每一条指令的保存。

- 汇编代码然后被逆向工程为C++，并在LLVM中开源。

- 即使表征网络使用了Transformer，它也不是一个基础模型。整个流程只适用于排序，对于其他任务如散列，必须重新训练。

在使用ML的算法发现方面取得了另一个重要的里程碑!

AlphaDev是DeepMind的一个改变游戏规则的人工智能，它创新了核心计算机科学算法。它正在重新构想排序方法，短序列的速度可提高70%。甚至散列算法的发现速度提高了30%。强化学习正在重塑算法的格局！

还有网友称，在我们对语言模型感到兴奋之余，也不要忘记其他深度学习算法的成功故事：AlphaZero、AlphaFold，以及现在的AlphaDev。

参考资料：

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

关键词：