几千年来，算法一直在帮助数学家进行基本运算。很久以前，古埃及人发明了一种无需乘法表即可将两个数相乘的算法。希腊数学家欧几里德描述了一种计算最大公约数的算法，至今仍在使用。在伊斯兰黄金时代，波斯数学家穆罕默德·伊本·穆萨·花拉子米设计了一种求解线性方程和二次方程的新算法，这两者都对后来的研究产生了深远的影响。其实算法这个词的出现有这样一种说法：波斯数学家穆罕默德·伊本·穆萨·花拉子米名字中的al-Khwarizmi这个词翻译成拉丁语Algoritmi的意思，从而引出了算法这个词。然而，虽然今天我们对算法非常熟悉，可以从课堂上学习，在科研领域也经常遇到，似乎整个社会都在使用算法，但发现新算法的过程却很艰难。如今，DeepMind使用AI来发现新算法。在最新一期的Nature封面论文《Discovering faster matrix multiplication algorithms with reinforcement learning》中，DeepMind提出了AlphaTensor，并称它是第一个可用于发现新颖、高效且??可证明正确算法的人工智能系统，用于矩阵乘法等基本任务。简单来说，使用AlphaTensor来发现新算法。该研究揭示了一个存在了50年的数学问题，即找到将两个矩阵相乘的最快方法。论文地址：https://www.nature.com/articles/s41586-022-05172-4GitHub地址：https://github.com/deepmind/alphatensorAlphaTensor建立在AlphaZero的基础上，AlphaZero是一个Agents可以在国际象棋、围棋和将棋等棋盘游戏中击败人类。这项工作展示了AlphaZero从用于游戏到首次用于解决未解决的数学问题的转变。矩阵乘法矩阵乘法是代数中最简单的运算之一，经常在高中数学课上讲授。但在课堂之外，这种不起眼的数学运算对当代数字世界产生了巨大影响，在现代计算中无处不在。两个3x3矩阵相乘的示例。你可能没有注意到，矩阵乘法在我们的生活中无处不在，比如智能手机中的图像处理、语音命令的识别、电脑游戏的图形生成等。世界各地的公司都愿意花费大量的时间和金钱来开发计算硬件来高效地解决矩阵乘法问题。因此，即使矩阵乘法效率的微小改进也会产生广泛的影响。几个世纪以来，数学家们一直认为标准矩阵乘法算法是最高效的算法。但在1969年，德国数学家VolkenStrassen证明确实存在更好的算法，震惊了数学界。与标准算法和Strassen算法相比，后者需要的乘法运算次数少了一次，为7次，而前者需要8次，整体效率大大提高。通过研究非常小的矩阵（大小为2x2），Strassen发现了一种巧妙的方法来组合矩阵的条目以产生更快的算法。在随后的几十年里，研究人员一直在研究更大的矩阵，甚至找到了一种高效的3x3矩阵相乘的方法，但至今仍未解决。DeepMind最近的研究探索了现代人工智能技术如何促进自动发现新的矩阵乘法算法。基于人类直觉的进步，AlphaTensor发现的算法对于更大的矩阵比许多SOTA方法更有效。这项研究表明，人工智能设计的算法优于人类设计的算法，是算法发现领域向前迈出的重要一步。算法发现自动化的过程和进展首先将发现矩阵乘法的高效算法的问题转化为单人游戏。其中board是一个三维张量（数字数组），用于捕获当前算法的正确性。通过一组与算法指令相对应的允许移动，玩家尝试修改张量并将其条目归零。当玩家设法做到这一点时，将为任何一对矩阵生成可证明正确的矩阵乘法算法，其效率通过将张量归零所采取的步骤数来衡量。这个游戏非常具有挑战性，要考虑的可能算法的数量远远大于宇宙中的原子数量，即使对于像矩阵乘法这样小的东西也是如此。与几十年来一直是AI挑战的围棋游戏相比，该游戏每走一步的可能走法多了30个数量级（DeepMind考虑的一个设置超过10^33。）解决这个问题与传统的显着不同游戏为了应对该领域面临的挑战，DeepMind开发了几个关键组件，包括结合特定问题归纳偏差的新型神经网络架构、生成有用合成数据的程序，以及利用问题对称性的方法。接下来，DeepMind使用强化学习AlphaTensor训练了一个代理来玩这个游戏，一开始对任何现有的矩阵乘法算法一无所知。通过学习，AlphaTensor随着时间的推移逐渐改进，重新发现历史上快速的矩阵算法，如Strassen算法，并发现比以前已知的算法更快的算法。AlphaTensor玩的单人游戏，目标是找到正确的矩阵乘法算法。游戏状态是一个立方体数字数组（灰色代表0，蓝色代表1，绿色代表-1）代表剩余的待完成工作。例如，如果学校教授的常规算法可以使用100次乘法将4x5乘以5x5的矩阵相乘，人类的聪明才智可以将这个数字减少到80。相比之下，AlphaTensor发现的算法仅使用76次乘法即可执行相同的运算，如如下图所示。除了以上例子，AlphaTensor发现的算法还首次在有限域中改进了Strassen的二阶算法。这些用于乘以小矩阵的算法可以用作乘以任何大小的较大矩阵的原语。AlphaTensor还发现了一组具有SOTA复杂度的多样化算法，每个大小的矩阵乘法算法多达数千种，这表明矩阵乘法算法的空间比之前想象的要丰富。这个丰富空间中的算法具有不同的数学和实用属性。利用这种多样性，DeepMind调整了AlphaTensor以专门发现在给定硬件（例如NvidiaV100GPU、GoogleTPUv2）上运行速度很快的算法。这些算法在相同硬件上执行大型矩阵乘法比常用算法快10-20%，展示了AlphaTensor在优化任意目标方面的灵活性。AlphaTensor有一个目标对应于算法的运行时间。当找到正确的矩阵乘法算法时，它会在指定的硬件上进行基准测试，然后反馈给AlphaTensor以在指定的硬件上学习更高效的算法。对未来研究和应用的启示从数学的角度来看，DeepMind的结果可以指导对复杂性理论的进一步研究，该理论旨在确定解决计算问题的最快算法。AlphaTensor通过比以前的方法更有效地探索可能算法的空间，帮助加深我们对矩阵乘法算法丰富性的理解。此外，由于矩阵乘法是计算机图形学、数字通信、神经网络训练和科学计算等许多计算任务的核心组成部分，AlphaTensor发现的算法可以显着提高这些领域的计算效率。尽管本文着重于矩阵乘法的具体问题，但DeepMind希望能启发更多人使用AI来指导其他基础计算任务的算法发现。此外，DeepMind的研究还表明，AlphaZero强大的算法远远超出了传统游戏的领域，可以帮助解决数学领域的开放性问题。未来，DeepMind希望基于他们的研究，更多地使用人工智能来帮助社会解决数学和科学领域的一些最重要的挑战。
