Alpha“家族”再添一员：DeepMind研发AlphaDev，将列表排序速度提高70%

DeepMind 在基础计算机科学领域的一系列发现仍在继续。2022 年，该公司利用其可玩游戏的人工智能 AlphaZero（的一个版本），找到了新的方法来加快许多不同类型代码核心的一个关键数学部分的计算速度，打破了 50 年来的纪录。

现在，它又实现了类似的事。这家总部位于英国的公司（最近更名为谷歌DeepMind）使用 AlphaZero 的新版本 AlphaDev，发现了一种比现有最佳方法快 70% 的方法来对列表进行排序。

它还找到了一种方法，可以将密码学中使用的密钥算法的速度提高 30%。这些算法是软件中最常见的构建模块之一。小的加速就可以带来巨大的不同，降低成本和节约能源。

（来源：STEPHANIE ARNETT/MITTR | MINNEAPOLIS INSTITUTE OF ART）

谷歌 DeepMind 的研究科学家丹尼尔•曼科维茨（Daniel Mankowitz）表示：“摩尔定律即将终结，芯片正在接近其基本物理极限。我们需要找到新的、创新的方法来优化计算。”

“这是一个有趣的新方法，”彼得·桑德斯（Peter Sanders）说，他在德国卡尔斯鲁厄理工学院研究高效算法的设计和实现，他没有参与这项工作。“排序仍然是计算机中最广泛使用的用例之一，”他说。

DeepMind 今天在 Nature 杂志上发表了研究结果。但 AlphaDev 发现的技术已经被数百万软件开发人员所使用。早在 2022 年 1 月，DeepMind 就已向管理 C++ 的组织提交了新的排序算法，经过两个月的严格独立审查，AlphaDev 的算法被添加到该语言中。这是十多年来对 C++ 排序算法的首次修改，也是第一次涉及使用人工智能发现的算法的更新。

DeepMind 将其他新算法添加到了 Abseil 中，Abseil 是一个预先编写的 C++ 算法开源集合，任何使用 C++ 的人都可以使用。这些加密算法可以计算哈希值，可以用作任何类型数据的唯一 ID。DeepMind 估计，它的新算法现在每天被使用数万亿次。

AlphaDev 是建立在 AlphaZero 之上的，AlphaZero 是 DeepMind 训练的、用来学习围棋和国际象棋等游戏的强化学习模型。DeepMind 的突破在于将寻找更快算法的问题视为一场游戏，然后让它的人工智能赢得这场游戏——与去年研究中用来加快计算速度的方法相同。

在 AlphaDev 的案例中，它所做的游戏涉及选择计算机指令并将它们按顺序排列，从而让生成的代码组成算法。如果 AlphaDev 的算法既正确又比现有算法快，那么它就赢了。这听起来很简单，但要玩得好，AlphaDev 必须在无数的可能步骤中搜索。

DeepMind 选择了汇编语言，现在很少有人直接用到它——它是 C++ 等语言编写的代码在运行之前被翻译成的语言，由计算机芯片处理。汇编的优点是它允许将算法分解为更小的步骤——如果它要寻找更快的方法，这是一个很好的起点。

汇编包括一些基本指令，比如 mov（A,B），它告诉计算机将位置 A 的数字移到位置 B。许多这样的指令组合在一起，就可以执行计算机所做的一切。

所玩的游戏就是在它正在构建的算法中添加一个新的汇编指令。一开始，AlphaDev 会随机添加指令，生成无法运行的算法。随着时间的推移，就像 AlphaZero 在棋类游戏中所做的那样，它学会了如何做出有意义的行动。它添加的指令使算法不仅能运行，而且正确、快速。

专注于五位以内的短列表排序算法。在排序较长列表的用例中，这样的算法会被反复调用。因此，这些短算法的加速将产生连锁效应。

但人类对短算法的研究和优化也持续了几十年。作为概念证明，曼科维茨和同事们用到了一种对长度为三的列表进行排序的算法。这种算法的最佳人为设计版本包含 18 条指令。他们不认为它还能被改进。

他说：“老实说，我们没有期望取得更好的成绩。但令我们惊讶的是，它确实做到了。我们最初认为这是一个错误或漏洞之类的，但当我们分析程序时，我们意识到 AlphaDev 实际上发现了一些东西。”

AlphaDev 找到了一种方法，可以用 17 条指令，而不是 18 条指令对长度为三的列表进行排序。它所发现的是某些步骤是可以跳过的。曼科维茨说：“当我们后来看到它的时候，我们觉得，‘这确实说得通。但要（在没有 AlphaDev 的情况下）发现这样的东西，就需要汇编语言专家出马。”

在长度为四的排序算法上，AlphaDev 无法击败人类的最好成绩：28 条指令。但它在长度五上面击败了人类，将指令数量从 46 条减少到了 42 条。

这相当于一个显著的提速。在一个典型的英特尔 Skylake 芯片上，现有的 C++ 算法对一个长度五的列表进行排序，耗时约 6.91 纳秒。AlphaDev 只花了 2.01 纳秒，大约快了 70%。

DeepMind 将 AlphaDev 的发现与 AlphaGo 在 2016 年与围棋大师李世石的比赛中奇怪但制胜的一招进行了比较。“所有的专家看到这一举动后都说，‘这样做不对。这是一个糟糕的行动，’”曼科维茨说，“但实际上这是正确的一步棋，AlphaGo 最终不仅赢得了比赛，还影响了职业围棋选手开始使用的策略。”

桑德斯对此印象深刻，但他不认为结果应该被夸大。他说：“我同意机器学习技术正在逐渐改变编程领域的游戏规则，每个人都期待人工智能很快就能发明出新的、更好的算法。但我们还没有走到那一步。”

首先，桑德斯指出 AlphaDev 只使用了汇编中可用指令的一个子集。他说，许多现有的排序算法使用了 AlphaDev 没有尝试过的指令。这使得将 AlphaDev 的方法与最佳竞争对手的方法进行比较变得更加困难。

AlphaDev 确实有它的局限性。它产生的最长的算法有 130 条指令，用于排序长度五的列表。在每一步中，AlphaDev 都会从 297 条可能的汇编指令中进行选择。“在超过 297 条指令和 130 条指令的组合长度之后，它的学习速度就会变得很慢，”曼科维茨说。

这是因为面对 297 条指令，AlphaDev 可以构建的算法的数量超过了棋类游戏的可能走法（10120）和宇宙中的原子数量（大约 1080）。

对于更长的算法，该团队计划调整 AlphaDev 以使用 C++ 指令而不是汇编。 AlphaDev 可能会错过某些捷径，但这种方法将适用于更广泛的算法。

桑德斯还希望看到与人类设计的最佳方法进行更详尽的比较，特别是对于较长的算法。DeepMind 表示，这是其计划的一部分。曼科维茨希望将 AlphaDev 与人类设计的最佳方法结合起来，让人工智能以人类直觉为基础，而不是从零开始。

这可能会发现更多的算法加速方法。“对于人类来说，要做到这一点，需要大量的专业知识和大量的时间——也许是几天，也许是几周——来仔细查看这些程序并找出改进之处，”曼科维茨说，“因此，以前很少有人尝试过。”

支持：Ren