谷歌DeepMind打破十年算法封印 AlphaDev登场

“Alpha”家族又添新成员，AlphaDev！整合Google Brain DeepMind后的首款力作，新AI系统排序算法提速70%，C++排序库十年来首次改版。 AI造AI时代来临？

今天，“Alpha”家族又添了一位新成员：AlphaDev。

整个计算生态系统的基础可能会被人工智能创造的新算法所颠覆！

没过多久，Google Brain 和DeepMind 就强强联手，带来了如此惊艳的作品。

AlphaDev 不仅可以将排序算法的速度提高70%，甚至在某些算法中，它甚至可以比人类快3 倍之多。

十多年来，C++ 排序库第一次发生了变化。 AI优化世界代码，迈向新里程碑。

目前，最新研究成果已发表在《自然》杂志上。

论文地址：https://www.nature.com/articles/s41586-023-06004-9 通过强化学习，AlphaDev发现了一种更有效的算法，直接超越了科学家和工程师几十年的精心打磨。

现在，新算法是两个标准C++ 编码库的一部分，每天被世界各地的程序员使用数万亿次。

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

强化学习打破十年算法瓶颈与AlphaZero、AlphaFold等前辈一样，AlphaDev也直接掀起了一个领域的革命。

“起初我们不相信，”DeepMind 的计算机科学家、该论文的第一作者Daniel Mankowitz 说。

“说实话，我们没想到会取得更好的成绩：这是一个非常短的项目，而这类项目已经研究了几十年。”

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

但随着微芯片接近其物理极限，改进代码以使计算更强大和可持续变得至关重要。特别是对于每天运行数万亿代码的算法来说，这一点尤为重要。

今天，谷歌DeepMind在Nature发表的一篇论文中首次介绍了Alpha家族的“新贵”AlphaDev。

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

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

使用人工智能生成更好的算法将改变我们对计算机进行编程的方式，并影响我们数字社会的方方面面。

根据Nature 论文中的数据，AlphaZero 创建的算法可以比人类快三倍的速度对数据进行排序。

今天，谷歌DeepMind也在主C++库中开源了最新的排序算法，让所有人都可以使用。

开源地址：https://reviews.llvm.org/D118029 什么是排序？排序是一种按特定顺序组织多个项目的方法。

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

分类方法在整个人类历史中不断发展。最早的例子可以追溯到二世纪和三世纪，当时学者们在亚历山大图书馆的书架上按字母顺序手工排列了数千本书。

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

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

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

排序算法，将未排序的数字序列作为输入并输出排序数字的算法，已成为计算机科学的基石。

我们今天的算法需要计算机科学家和程序员数十年的研究才能开发出来。

这是因为现有的算法非常高效，每一步改进都是一个重大挑战。

这种难度就像找到一种新的节省电能的方法，或者找到一种更有效的数学方法。

AlphaDev 在寻找新算法上的创新之处在于它不是改进现有算法，而是从头开始发现更快的算法。

而且，它适用于大多数人不会想到的地方—— 计算机汇编指令。

汇编指令用于创建二进制代码。虽然开发人员在编写代码时会使用C++等高级语言，但为了让计算机能够理解，这些高级语言必须被翻译成“低级”的汇编指令。

我们通常使用C++ 等高级编程语言编写代码，然后使用编译器将其转换为低级CPU 指令，称为汇编指令。然后，汇编程序将汇编指令转换为可执行的机器代码Google DeepMind 研究人员认为，在这个较低级别上存在许多改进空间，而这在高级编程语言中可能很难找到。

在这个较低的层次上，计算机在存储和操作方面更加灵活，因此再进行一些潜在的改进可能会对速度和能源产生巨大影响。

图A：最多对两个元素进行排序的C++ 算法

图B：代码对应的汇编

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

p>

而我们这次的主角 ——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」，不仅表明它可以改进算法，还可以找到新的解决方案。

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

网友热评

英伟达科学家 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

本文来自微信公众号：新智元 （ID：AI_era）