Deep Mind AlphaTensor 将发现新算法

Deep Mind 已将 AlphaZero 扩展到数学，为研究算法开启新的可能性。

AlphaTensor 以 AlphaZero 为基础，AlphaZero 是一种在国际象棋、围棋和将棋等棋盘游戏中表现出超人表现的代理，这项工作展示了 AlphaZero 从玩游戏到首次解决未解决的数学问题的旅程。

古埃及人创造了一种无需乘法表即可将两个数相乘的算法，希腊数学家欧几里德描述了一种计算最大公约数的算法，该算法至今仍在使用。

在伊斯兰黄金时代，波斯数学家 Muhammad ibn Musa al-Khwarizmi 设计了新的算法来求解线性和二次方程。 事实上，al-Khwarizmi 的名字，翻译成拉丁语为 Algoritmi，导致了算法一词。 但是，尽管今天人们对算法很熟悉——从课堂代数到尖端科学研究，整个社会都在使用——发现新算法的过程非常困难，这是人类思维惊人推理能力的一个例子。

他们发表在《自然》杂志上。 AlphaTensor 是第一个用于为矩阵乘法等基本任务发现新颖、高效且​​可证明正确的算法的人工智能 (AI) 系统。 这揭示了一个 50 年前的数学悬而未决的问题，即找到将两个矩阵相乘的最快方法。

从头开始训练，AlphaTensor 发现了比现有的人类和计算机设计的算法更有效的矩阵乘法算法。 尽管对已知算法进行了改进，但他们注意到 AlphaTensor 的一个限制是需要预先定义一组潜在的因子条目 F，这会使搜索空间离散化，但可能会导致错过有效算法。 未来研究的一个有趣方向是使 AlphaTensor 用于搜索 F。AlphaTensor 的一个重要优势是它除了查找算法外，还支持复杂的随机和不可微分奖励（从张量等级到特定硬件上的实际效率）的灵活性用于各种空间（例如有限域）中的自定义操作。 他们相信这将刺激 AlphaTensor 应用于设计优化我们在此未考虑的指标的算法，例如数值稳定性或能量使用。

矩阵乘法算法的发现具有深远的意义，因为矩阵乘法是许多计算任务的核心，例如矩阵求逆、计算行列式和求解线性系统。

自动化算法发现的过程和进展
首先，他们将寻找有效矩阵乘法算法的问题转化为单人游戏。 在这个游戏中，棋盘是一个 XNUMX 维张量（数字数组），用于捕捉当前算法离正确的程度。 通过一组与算法指令相对应的允许移动，玩家尝试修改张量并将其条目归零。 当玩家设法这样做时，这将为任何一对矩阵生成可证明正确的矩阵乘法算法，并且其效率由将张量归零所采取的步骤数来衡量。

这个游戏非常具有挑战性——要考虑的可能算法的数量远远大于宇宙中的原子数量，即使对于矩阵乘法的小情况也是如此。 与几十年来一直是人工智能挑战的围棋游戏相比，他们游戏每一步的可能移动数量要大 30 个数量级（他们考虑的一种设置超过 10^33）。

从本质上讲，要玩好这个游戏，人们需要在巨大的可能性大海捞针中找出最微小的针。 为了解决这个与传统游戏明显不同的领域的挑战，我们开发了多个关键组件，包括一个新的神经网络架构，它结合了特定问题的归纳偏差、一个生成有用的合成数据的程序，以及一个利用对称性的配方。问题。

然后，他们使用强化学习训练了一个 AlphaTensor 代理来玩这个游戏，从没有任何关于现有矩阵乘法算法的知识开始。 通过学习，AlphaTensor 随着时间的推移逐渐改进，重新发现了历史上的快速矩阵乘法算法，例如 Strassen 的，最终超越了人类直觉的领域，发现算法比以前知道的更快。

探索对未来研究和应用的影响
从数学的角度来看，他们的结果可以指导复杂性理论的进一步研究，该理论旨在确定解决计算问题的最快算法。 通过以比以前的方法更有效的方式探索可能的算法空间，AlphaTensor 有助于加深我们对矩阵乘法算法丰富性的理解。 了解这个空间可能会为帮助确定矩阵乘法的渐近复杂性解锁新的结果，矩阵乘法是计算机科学中最基本的开放问题之一。

由于矩阵乘法是许多计算任务的核心组成部分，涵盖计算机图形学、数字通信、神经网络训练和科学计算，AlphaTensor 发现的算法可以显着提高这些领域的计算效率。 AlphaTensor 考虑任何类型目标的灵活性也可以激发新的应用程序来设计算法，以优化能量使用和数值稳定性等指标，帮助防止小的舍入误差在算法工作时滚雪球。

虽然他们在这里专注于矩阵乘法的特定问题，但我们希望我们的论文能够启发其他人使用 AI 来指导其他基本计算任务的算法发现。 他们的研究还表明，AlphaZero 是一种强大的算法，可以远远超出传统游戏的领域，以帮助解决数学中的开放问题。 在我们的研究的基础上，他们希望推动更多的工作——应用人工智能来帮助社会解决数学和科学领域的一些最重要的挑战。

Nature——通过强化学习发现更快的矩阵乘法算法

抽象
提高基础计算算法的效率会产生广泛的影响，因为它会影响大量计算的整体速度。 矩阵乘法就是这样一项原始任务，发生在许多系统中——从神经网络到科学计算程序。 使用机器学习自动发现算法提供了超越人类直觉并超越当前最佳人工设计算法的前景。 然而，算法发现过程的自动化是复杂的，因为可能的算法空间是巨大的。 在这里，我们报告了一种基于 AlphaZero1 的深度强化学习方法，用于发现任意矩阵乘法的有效且可证明正确的算法。 我们的代理 AlphaTensor 接受过单人游戏训练，其目标是在有限因子空间内找到张量分解。 AlphaTensor 发现的算法在许多矩阵大小上都优于最先进的复杂性。 特别相关的是有限域中 4 × 4 矩阵的情况，据我们所知，AlphaTensor 的算法自 50 年前发现以来首次改进了 Strassen 的两级算法。 我们通过不同的用例进一步展示了 AlphaTensor 的灵活性：结构化矩阵乘法具有最先进复杂性的算法，并通过优化特定硬件上的运行时矩阵乘法来提高实际效率。 我们的结果突出了 AlphaTensor 在一系列问题上加速算法发现过程并针对不同标准进行优化的能力。