AI重写排序算法，速度快70％：DeepMind AlphaDev革新计算基础( 二 ) _排序算法

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 有能力发掘出原创性的解决方案，并挑战人类对如何改进计算机科学算法的思考方式。