Google DeepMind破十年算法瓶颈

·排序算法是世界各地的计算机不断使用的基本功能，虽然数十亿人每天都在使用该算法，但没有人意识到算法还存在优化空间。Google DeepMind表示：“看起来，现在AI不仅可以帮人写代码，而且可以帮我们写出更好的代码。”

·“通过优化和推出全球开发人员使用的改进排序和哈希算法，AlphaDev展示了其具有真实世界影响的泛化和发现新算法的能力。我们将AlphaDev视为发展通用人工智能工具的一步，这些工具可以帮助优化整个计算生态系统，并解决其他有益于社会的问题。”

当地时间6月7日，最近刚刚合并而成的Google DeepMind宣布推出Alpha家族的新成员——AlphaDev，这是一种利用强化学习来改进计算机科学算法的人工智能系统，其发现了一种速度更快的排序算法，被誉为打破了十年来的算法“封印”，并成为使用人工智能优化代码的重要里程碑。

(资料图)

Google DeepMind首席执行官戴密斯·哈萨比斯（Demis Hassabis）在社交平台上宣布：“AlphaDev发现了一种全新且更快的排序算法，我们已将其开源到主要C++库中供开发人员使用。这只是AI提升代码效率进步的开始。”

对于较短的序列，这一新算法可将排序库速度提高70%，对于超过25万个数据的序列，速度也能提高约1.7%，超越了人类科学家和工程师几十年来的精心打磨。从在线搜索结果、社交帖子，到计算机和手机数据处理方式，算法存在于互联网的每一处，且每天都要执行数万亿次。利用AI生成更好的算法，将改变我们对计算机编程的方式，并影响我们数字化社会的方方面面。

该成果现已被纳入LLVM标准C++库Abseil并开源，这是十多年来C++排序库首次更改，也是通过强化学习设计的算法首次被添加到该库中。相关研究论文以“Faster sorting algorithms discovered using deep reinforcement learning”为题，已发表在权威科学期刊《自然》（Nature）上。

Alpha家族新AI打破代码瓶颈，数十亿人使用的算法效率提高70%。

通过游戏找到提速算法最优解

排序算法是世界各地计算机不断使用的基本功能，虽然数十亿人每天都在使用该算法，但没有人意识到算法还存在优化空间。Google DeepMind表示：“看起来，现在AI不仅可以帮人写代码，而且可以帮我们写出更好的代码。”

据介绍，AlphaDev基于AlphaZero强化学习模型构建，其工作方式与AlphaZero相似，后者结合计算机推理和直觉，曾在围棋、国际象棋等游戏中屡次击败世界冠军。在棋盘游戏中，AlphaZero有能力选择每一步的走法，不过AlphaDev只能选择添加指令，并不会选择下一步怎么走棋。

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

为了训练AlphaDev来发现新的算法，Google DeepMind将排序问题转化成了一个“汇编游戏”（Assembly Game）。在每一轮中，AlphaDev都需要观察它生成的算法以及中央处理器（CPU）中包含的信息，并通过在算法中添加一条指令来进行移动。而这个汇编游戏非常困难，因为AlphaDev必须有效地搜索大量可能的指令组合，从而找到一个可以排序且比当前最佳算法更快的算法。

其中AlphaDev需要操作的“可能的指令组合”的数量，堪比宇宙中的粒子数量，或者国际象棋（10的120次方局）和围棋（10的700次方局）中可能的走法组合数。更为严苛的是，任何一个错误的移动，都可能会使整个算法无效。DeepMind的突破在于将寻找更快算法的问题视为一场游戏，然后让它的人工智能赢得这场游戏，最后根据AlphaDev正确排序数字的能力以及完成排序的速度和效率给予奖励，而AlphaDev则需要通过发现一个正确且更快的程序来赢得游戏。如果AlphaDev的算法既正确又比现有算法快，那么它就赢了。

或可解决摩尔定律放缓问题

排序算法使得LLVM libc++排序库得到改进：对于较短的序列，排序库的速度提高了70%，对于超过25万个数据的序列，速度提高了约1.7%。

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

而事实上，AlphaDev不仅发现了更快的算法，还发现了新的方法。它的排序算法包含新的指令序列，每次应用时都会节省一条指令——这显然会产生巨大的影响，因为这些算法每天都要使用数万亿次。研究人员把这些称为“AlphaDev的交换和复制动作”。

这种新颖的方法让人联想到AlphaGo的“第37步”——当时这这种反直觉的下法让围观者目瞪口呆，并导致李世石这位传奇围棋选手被打败。通过交换和复制动作，AlphaDev跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式连接项目。这表明AlphaDev有能力发掘出原创性的解决方案，并挑战人类对如何改进计算机科学算法的思考方式。

“说实话，我们没有想到会取得更好的成绩：这是一个非常短的程序，这些类型的程序已经被研究了几十年。”论文的第一作者、Google DeepMind的研究科学家丹尼尔·曼科维茨（Daniel Mankowitz）说，“我们最初以为它犯了一个错误，或者有一个bug或其他东西，但是，当我们分析这个程序时，我们意识到AlphaDev实际上已经发现了更快的东西。”

曼科维茨表示：“优化每天被调用数万亿次的基本函数的代码，有望带来足够大的好处，鼓励人们尝试执行更多这些函数，并将其作为解决摩尔定律放缓瓶颈的途径之一。”

英国伯明翰大学教授马克·李（Mark Lee）则认为，AlphaDev很有意思，即使是1.7%的速度提升也很有用，但尚不能确定这种方法是否可以弥补摩尔定律的瓶颈，因为它不能在更复杂的情况下取得同样的收益。

哈希算法速度提高30%

在发现更快的排序算法后，团队测试了AlphaDev是否可以概括和改进不同的计算机科学算法：哈希。

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

目前，Google DeepMind正在探索AlphaDev在C++等高级语言中直接优化算法的能力，这对于开发人员来说将更加有用。

Google DeepMind在官方博客中写道：“通过优化和推出全球开发人员使用的改进排序和哈希算法，AlphaDev展示了其具有真实世界影响的泛化和发现新算法的能力。我们将AlphaDev视为发展通用人工智能工具的一步，这些工具可以帮助优化整个计算生态系统，并解决其他有益于社会的问题。”