AlphaZero 对数学的首次扩展为研究开启了新的可能性
数千年来，算法一直帮助数学家进行基本运算。 古埃及人创造了一种不需要乘法表就能将两个数相乘的算法，希腊数学家欧几里德描述了一种计算最大公约数的算法，该算法至今仍在使用。
在伊斯兰黄金时代，波斯数学家 穆罕默德·本·穆萨·赫瓦里兹米 设计了新的算法来求解线性和二次方程。 事实上，花剌子模的名字，翻译成拉丁语为 阿尔戈里特米，导致了术语算法。 但是，尽管今天人们对算法很熟悉——从课堂代数到尖端科学研究，整个社会都在使用——发现新算法的过程非常困难，这是人类思维惊人推理能力的一个例子。
在我们的 纸，今天发表在《自然》杂志上, 我们介绍 阿尔法张量，第一个人工智能 (AI) 系统，用于为矩阵乘法等基本任务发现新颖、高效且可证明正确的算法。 这揭示了一个 50 年前的数学悬而未决的问题，即找到将两个矩阵相乘的最快方法。
这篇论文是 DeepMind 推进科学和使用 AI 解决最基本问题的使命的垫脚石。 我们的系统 AlphaTensor 建立在 AlphaZero 之上，这是一个具有 在国际象棋、围棋和将棋等棋盘游戏中表现出超人的表现，而这项工作首次展示了 AlphaZero 从玩游戏到解决未解决的数学问题的旅程。
矩阵乘法
矩阵乘法是代数中最简单的运算之一，通常在高中数学课上教授。 但在课堂之外，这种不起眼的数学运算对当代数字世界产生了巨大的影响，在现代计算中无处不在。
此操作用于处理智能手机上的图像、识别语音命令、为电脑游戏生成图形、运行模拟以预测天气、压缩数据和视频以在互联网上共享等等。 世界各地的公司花费大量时间和金钱开发计算硬件以有效地乘法矩阵。 因此，即使是对矩阵乘法效率的微小改进也会产生广泛的影响。
几个世纪以来，数学家认为标准矩阵乘法算法是效率最高的算法。 但在 1969 年，德国数学家 Volken Strassen 震惊了数学界 通过证明确实存在更好的算法。
通过研究非常小的矩阵（大小为 2×2），他发现了一种巧妙的方法来组合矩阵的条目以产生更快的算法。 尽管在 Strassen 的突破之后进行了数十年的研究，但这个问题的更大版本仍未解决 - 以至于不知道将两个小至 3×3 的矩阵相乘的效率有多高。
在我们的论文中，我们探讨了现代 AI 技术如何推动新矩阵乘法算法的自动发现。 基于人类直觉的进步，AlphaTensor 发现了对于许多矩阵大小而言比现有技术更有效的算法。 我们的 AI 设计算法优于人工设计的算法，这是算法发现领域向前迈出的重要一步。
自动化算法发现的过程和进展
首先，我们将寻找有效矩阵乘法算法的问题转化为单人游戏。 在这个游戏中，棋盘是一个 XNUMX 维张量（数字数组），用于捕捉当前算法离正确的程度。 通过一组与算法指令相对应的允许移动，玩家尝试修改张量并将其条目归零。 当玩家设法这样做时，这将为任何一对矩阵生成可证明正确的矩阵乘法算法，并且其效率由将张量归零所采取的步骤数来衡量。
这个游戏非常具有挑战性——要考虑的可能算法的数量远远大于宇宙中的原子数量，即使对于矩阵乘法的小情况也是如此。 与围棋游戏相比， 几十年来人工智能面临的挑战，我们游戏每一步的可能移动数要大 30 个数量级（超过 1033 对于我们考虑的设置之一）。
从本质上讲，要玩好这个游戏，人们需要在巨大的可能性大海捞针中找出最微小的针。 为了解决这个与传统游戏明显不同的领域的挑战，我们开发了多个关键组件，包括一个新的神经网络架构，它结合了特定问题的归纳偏差、一个生成有用的合成数据的程序，以及一个利用对称性的配方。问题。
然后，我们使用强化学习训练了一个 AlphaTensor 代理来玩游戏，开始时对现有的矩阵乘法算法没有任何了解。 通过学习，AlphaTensor 随着时间的推移逐渐改进，重新发现了历史上的快速矩阵乘法算法，例如 Strassen 的，最终超越了人类直觉的领域，发现算法比以前知道的更快。
例如，如果在学校教授的传统算法使用 4 次乘法将 5×5 x 5×100 矩阵相乘，并且这个数字通过人类的聪明才智减少到 80，那么 AlphaTensor 发现了仅使用 76 次乘法即可完成相同运算的算法。
除了这个例子，AlphaTensor 的算法自 50 年前发现以来首次在有限域中改进了 Strassen 的两级算法。 这些用于乘法小矩阵的算法可以用作原语来乘以任意大小的更大矩阵。
此外，AlphaTensor 还发现了具有最先进复杂性的多样化算法集——每种大小的矩阵乘法算法多达数千个，表明矩阵乘法算法的空间比以前想象的要丰富。
在这个丰富的空间中的算法具有不同的数学和实际属性。 利用这种多样性，我们调整了 AlphaTensor 以专门寻找在给定硬件（例如 Nvidia V100 GPU 和 Google TPU v2）上快速的算法。 这些算法在相同硬件上乘以大矩阵的速度比常用算法快 10-20%，这展示了 AlphaTensor 在优化任意目标方面的灵活性。
探索对未来研究和应用的影响
从数学的角度来看，我们的结果可以指导复杂性理论的进一步研究，该理论旨在确定解决计算问题的最快算法。 通过以比以前的方法更有效的方式探索可能的算法空间，AlphaTensor 有助于加深我们对矩阵乘法算法丰富性的理解。 了解这个空间可能会解锁新的结果，以帮助确定矩阵乘法的渐近复杂度， 计算机科学中最基本的开放问题之一.
由于矩阵乘法是许多计算任务的核心组成部分，涵盖计算机图形学、数字通信、神经网络训练和科学计算，AlphaTensor 发现的算法可以显着提高这些领域的计算效率。 AlphaTensor 考虑任何类型目标的灵活性也可以激发新的应用程序来设计算法，以优化能量使用和数值稳定性等指标，帮助防止小的舍入误差在算法工作时滚雪球。
虽然我们在这里专注于矩阵乘法的特定问题，但我们希望我们的论文能够启发其他人使用 AI 来指导其他基本计算任务的算法发现。 我们的研究还表明，AlphaZero 是一种强大的算法，可以远远超出传统游戏的领域，以帮助解决数学中的开放问题。 基于我们的研究，我们希望推动更多的工作——应用人工智能来帮助社会解决数学和科学领域的一些最重要的挑战。
