今日Nature：深度强化学习让AI自行成长！

排序或散列等基本算法，在任何一天都会被使用数万亿次。随着计算需求的增长，这些算法的性能变得越来越重要。

尽管过去已经取得了显著的进步，但进一步提高这些程序的效率对人类科学家和计算方法来说都是一个挑战。

在此，来自英国Deepmind公司的Daniel J. Mankowitz等研究者展示人工智能(AI)如何通过发现迄今未知的例程来超越当前的艺术状态。相关论文以题为“Faster sorting algorithms discovered using deep reinforcement learning”于2023年06月07日发表在Nature上。

与此同时，同期Nature专门发表了一篇Views，以说明该篇文章的重要性。

人类的直觉和专业知识，对改进算法至关重要。然而，许多算法已经达到了人类专家无法进一步优化它们的阶段，导致了不断增长的计算瓶颈。经典程序综合文献中的工作跨越了几十年，旨在使用延迟代理生成正确的程序和/或优化程序。

这些包括枚举搜索技术和随机搜索，以及最近在程序合成中使用深度学习以生成正确程序的趋势。使用深度强化学习(DRL)，人们可以更进一步，通过优化CPU指令级的实际测量延迟，与以往的工作相比，通过更有效地搜索和考虑正确和快速程序的空间，生成正确和高性能的算法。

计算机科学中的一个基本问题是如何对序列进行排序。这是在世界各地的初级计算机科学课程中教授的，并且在广泛的应用中无处不在。

几十年来，计算机科学研究一直专注于发现和优化排序算法。实际解决方案的一个关键组成部分是对短序列的元素进行小排序；在对使用分治法的大型数组进行排序时，会反复调用该算法。

在这项工作中，研究者重点研究了两类小型排序算法：(1)固定排序和(2)变量排序。固定排序算法对固定长度的序列进行排序(例如，sort 3只能对长度为3的序列进行排序)，而变量排序算法可以对大小不等的序列进行排序(例如，变量sort 5可以对1到5个元素的序列进行排序)。

在这里，研究者展示了人工智能如何通过发现迄今未知的例程来超越当前的艺术状态。为了实现这一点，研究者将寻找更好的排序程序作为单人游戏的任务。然后，研究者训练了一个新的深度强化学习代理AlphaDev来玩这个游戏。

AlphaDev从零开始发现了小型排序算法，这些算法的表现超过了之前已知的人类基准。这些算法已集成到LLVM标准C++排序库中。对排序库的这一部分的更改表示用使用强化学习自动发现的算法替换组件。研究者还提供了额外领域的结果，展示了该方法的通用性。

图1. C++和汇编程序之间的关系

图2. AssemblyGame和算法的正确性计算

图3. AlphaDev发现的排序网络和算法改进

图4. AlphaDev发现的完全不同的算法

综上所述，值得注意的是，AlphaDev理论上可以泛化到不需要对测试用例进行彻底验证的函数。例如，哈希函数和加密哈希函数通过哈希冲突的次数来定义函数的正确性。因此，在这种情况下，AlphaDev可以优化最小化冲突和延迟。

从理论上讲，AlphaDev还可以在令人印象深刻的大型功能中优化复杂的逻辑组件。研究者希望AlphaDev能够在人工智能和程序合成社区提供有趣的见解并激发新的方法。

文献信息

Mankowitz, D.J., Michi, A., Zhernov, A. et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 257–263 (2023). https://doi.org/10.1038/s41586-023-06004-9

原文链接：

https://www.nature.com/articles/s41586-023-06004-9

原创文章，作者：菜菜欧尼酱，如若转载，请注明来源华算科技，注明出处：https://www.v-suan.com/index.php/2024/01/04/a871fc594f/

今日Nature：深度强化学习让AI自行成长！

相关推荐

发表回复