【Nature】DeepMind提出AlphaDev, 用强化学习将排序算法提升70%

机器之心报道

机器之心编辑部

计算的基础就此改变了。「通过交换和复制移动，AlphaDev 跳过了一个步骤，以一种看似错误，但实际上是捷径的方式连接项目。」这种前所未见、违反直觉的思想不禁让人回忆起 2016 年那个春天。

七年前，AlphaGo 在围棋上击败人类世界冠军，如今 AI 又在编程上给我们上了一课。 今天凌晨，Google DeepMind CEO 哈萨比斯的两句话引爆了计算机领域：「AlphaDev 发现了一种全新且更快的排序算法，我们已将其开源到主要 C++ 库中供开发人员使用。这只是 AI 提升代码效率进步的开始。」

这一次，Google DeepMind 的全新强化学习系统 AlphaDev 发现了一种比以往更快的哈希算法，这是计算机科学领域中的一种基本算法，AI 的成果现已被纳入 LLVM 标准 C++ 库 Abseil 并开源。 这个成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科学家 Daniel J. Mankowitz 表示：「我们估计它发现的排序和哈希算法每天会在全世界被调用数万亿次。」

AI 似乎从算法层面加速了世界的运转。

这些算法改进了 LLVM libc++ 排序库，对于较短的序列，排序库的速度提高了 70%，对于超过 25 万个元素的序列，速度也能提高约 1.7%。Google DeepMind 表示，这是十多年来排序库这部分的第一次变化。看起来，现在 AI 不仅可以帮人写代码，而且可以帮我们写出更好的代码。 在最新的博客中，新系统的作者们对 AlphaDev 进行了详细介绍。

新的算法将改变计算基础

数字社会推动了对计算和能源日益增长的需求。过去五十年里，数字时代依靠硬件的改进来跟上需求。但是随着微芯片接近其物理极限，改进在其上运行的代码变得至关重要。对于每天运行数万亿次的代码所包含的算法来说，这尤其重要。 Google DeepMind 的这项研究就是因此产生的，相关论文已发表在《Nature》上，AlphaDev 是一个 AI 系统，它使用强化学习来发现算法，甚至超越了科学家和工程师们几十年来打磨出来的成果。

论文地址：https://www.nature.com/articles/s41586-023-06004-9

总体来说，AlphaDev 发现了一种更快的排序算法。虽然数十亿人每天都在使用这些算法，但却没有人意识到这一算法还存在优化空间。排序算法应用范围广泛，从在线搜索结果、社交帖子排序，到计算机以及手机上的各种数据处理，都离不开排序算法。利用 AI 生成更好的算法将改变人类编程计算机的方式，对日益数字化的社会将产生重大影响。 通过在主要的 C++ 库中开源新排序算法，全球数百万开发人员和公司现在可以在云计算、在线购物和供应链管理等各行各业的人工智能应用中使用它。这是十多年来对排序库的首次更改，也是通过强化学习设计的算法首次被添加到该库中。这将这视为使用人工智能逐步优化世界代码的重要里程碑。

关于排序

排序算法是一种按照特定顺序对某些任务进行排列的方法。例如，按字母先后顺序排列三个字母，从大到小排列五个数字，或者对数百万条记录的数据库进行排序。 这种算法由来已久，并得到了很好的演进。其中关于排序的最早一个示例可追溯到公元 2 世纪和 3 世纪，当时学者们在亚历山大图书馆的书架上手工按字母顺序排列了数千本书。随着工业革命的到来，出现了可以帮助人们进行排序的机器，其中制表机使用打孔卡片存储信息，这些卡片被用于收集美国 1890 年的人口普查结果。

随着上世纪 50 年代商用计算机的兴起，最早用于排序算法的计算机科学算法开始发展。如今，在全球的代码库中有许多不同的排序技术和算法被用于处理海量的在线数据。

将一系列未排序的数字输入到算法中，输出已排序的数字。

经过计算机科学家和程序员们几十年的研究，目前的排序算法已经非常高效，以至于很难再实现进一步的改进，这有点类似于试图找到一种新的节省电力或更高效的数学方法，而这些算法也是计算机科学的基石。 探索新算法：汇编指令

AlphaDev 从头开始探索更快的算法，而不是基于现有算法之上，除此以外，AlphaDev 还能用于寻找大多数人所不涉足的领域：计算机汇编指令。

汇编指令可用于创建计算机执行的二进制代码。开发人员使用诸如 C++ 之类的高级语言编写代码，但必须将其转换为计算机能够理解的「低级」汇编指令。

Google DeepMind 认为这个层次存在许多改进的空间，而这些改进在更高级的编程语言中可能很难被发现。在这个层次上，计算机的存储和操作更加灵活，这意味着存在更多潜在的改进可能性，这些改进可能对速度和能源使用产生更大的影响。

代码通常是用高级编程语言（如 C++）编写的。然后，编译器将其转换为低级 CPU 指令，称为汇编指令。汇编器将汇编指令转换为可执行的机器码，以便计算机可以运行。

图 A：C++ 算法示例，该算法可对最多两个元素进行排序；图 B：相应的汇编表示形式。 用 AlphaGo 的方法寻找最佳算法

AlphaDev 基于 Google DeepMind 此前的一项成果：在围棋、国际象棋和象棋等游戏中打败世界冠军的强化学习模型 AlphaZero。而 AlphaDev 展示了这个模型如何从游戏转移到科学挑战，以及从模拟到现实世界的应用。 为了训练 AlphaDev 发现新的算法，团队将排序变成了一个单人的「组装游戏」。在每个回合中，AlphaDev 观察它所产生的算法和 CPU 中包含的信息，然后通过选择一条指令添加到算法中来下一步棋。 汇编游戏是非常困难的，因为 AlphaDev 必须在大量可能的指令组合中进行高效搜索，以找到一个可以排序的算法，并且比当前的最佳算法更快。指令的可能组合数量类似于宇宙中的粒子数量，或者国际象棋（10^120 局）和围棋（10^700 局）中可能的动作组合的数量，而一个错误的动作就可以使整个算法失效。 图 A：组装游戏。玩家 AlphaDev 接收系统 st 的状态作为输入，并通过选择一条汇编指令添加到目前已生成的算法中来下棋。图 B：奖励计算。每次移动后，生成的算法都会输入测试输入序列 —— 对于 sort3，这对应于三个元素序列的所有组合。该算法然后生成一个输出，将其与排序情况下排序序列的预期输出进行比较。智能体根据算法的正确性和延迟获得奖励。

在构建算法时，对于每次的一条指令，AlphaDev 通过将算法的输出与预期结果进行比较来检查它是否正确。对于排序算法，这意味着无序数字进入，正确排序的数字出来。团队会奖励 AlphaDev 对数字的正确排序以及排序的速度和效率，然后 AlphaDev 通过发现正确、更快的程序来赢得比赛。

它发现了更快的排序算法

AlphaDev 发现了新的排序算法，这些算法导致 LLVM libc++ 排序库得到改进：**对于较短的序列，排序库的速度提高了 70%，对于超过 25 万个元素的序列，速度提高了约 1.7%。 **

其中，Google DeepMind 团队更专注于改进三到五个元素的短序列排序算法。这些算法是使用最广泛的算法之一，因为它们通常作为更大排序函数的一部分被多次调用，改进这些算法可以提高对任意数量项目进行排序的整体速度。

为了让新的排序算法对人们更有用，团队对算法进行了逆向工程并将它们翻译成 C++，这是开发人员使用的最流行的编程语言之一。

目前，这些算法已在 LLVM libc++ 标准排序库（https://reviews.llvm.org/D118029）中提供，被全球数百万开发人员和公司使用。 「交换和复制动作」，神之一手重现？

事实上，AlphaDev 不仅发现了更快的算法，而且还发现了新的方法。它的排序算法包含新的指令序列，每次应用时都会节省一条指令 —— 这显然会产生巨大的影响，因为这些算法每天都要使用数万亿次。他们把这些称为「AlphaDev 交换和复制动作」。 这种新颖的方法让人联想到 AlphaGo 的「第 37 步」—— 当时这这种反直觉的下法让围观者目瞪口呆，并导致李世石这位传奇围棋选手被打败。通过交换和复制动作，AlphaDev 跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式连接项目。这表明 AlphaDev 有能力发掘出原创性的解决方案，并挑战人类对如何改进计算机科学算法的思考方式。 左图：min (A,B,C) 原始的 sort3 实现；右图：AlphaDev 交换移动 ——AlphaDev 发现你只需要 min (A,B)。 左图：在一个更大的排序算法中使用 max（B，min（A，C，D））的原始实现，用于排序八个元素；右图：AlphaDev 发现，使用其复制动作时，只需要 max（B，min（A，C））。 扩展能力测验：从「排序」到「哈希」

在发现更快的排序算法后，团队测试了 AlphaDev 是否可以概括和改进不同的计算机科学算法：哈希。 哈希是计算中用于检索、存储和压缩数据的基本算法。就像使用分类系统来定位某本书的图书管理员一样，哈希算法可以帮助用户知道他们正在寻找什么以及在哪里可以找到它。这些算法获取特定密钥的数据（例如用户名 “Jane Doe”）并对其进行哈希处理 —— 这是一个将原始数据转换为唯一字符串（例如 1234ghfty）的过程。计算机使用此哈希来快速检索与密钥相关的数据，而不是搜索所有数据。 **团队将 AlphaDev 应用于数据结构中最常用的哈希算法之一，尝试发现更快的算法。当将其应用于 9-16 字节范围的哈希函数时，**AlphaDev 发现的算法速度提高了 30%。

今年，AlphaDev 的新哈希算法已被发布到开源 Abseil 库中，可供全球数百万开发人员使用，它现在大概每天被使用数万亿次。 开源地址：https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e 结语

Google DeepMind 通过优化和推出改进的排序和哈希算法，供世界各地的开发人员使用，AlphaDev 展示了其概括和发现具有现实影响的新算法的能力。AlphaDev 可被视为开发通用 AI 工具的一步，它可以帮助优化整个计算生态系统并解决其他造福社会的问题。 虽然在低级汇编指令空间中进行优化非常强大，但随着算法的增长， AlphaDev 仍存在局限性，团队目前正在探索其直接在高级语言（如 C++）中优化算法的能力，这对开发人员来说更加有用。 AlphaDev 的发现，例如交换和复制动作，不仅表明它可以改进算法，还可以找到新的解决方案。这些发现或许能够激励研究人员和开发人员创建可以进一步优化基础算法的技术和方法，以创建更强大和可持续的计算生态系统。 参考内容：https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms?utm_source=twitter&utm_medium=social&utm_campaign=OCShttps://news.ycombinator.com/item?id=36228125https://twitter.com/DJ_Mankowitz/status/1666468646863130631