50年后，矩阵乘法迎来全新突破！

数千年来，算法一直在帮助数学家进行基本运算。

古埃及人发明了一种不需要乘法表就能得出两个数字的乘积的算法；欧几里得描述了一种沿用至今的计算最大公约数的算法；在伊斯兰的黄金时代，花拉子米设计出了求解线性方程和二次方程的新算法。尽管现如今我们对算法已经非常熟悉，但发现新算法的过程仍是非常困难的。

在一篇于近期发表在《自然》杂志上的论文中，DeepMind团队介绍了第一个用于发现新的、高效的、可证明正确的基本算法（如矩阵乘法）的人工智能系统——AlphaTensor。它打破了一个保持了50多年的记录，发现了一种能更快地计算两个矩阵之间的乘法的算法。

核心运算：矩阵乘法

矩阵乘法是我们非常熟悉，也是代数中最基本的运算之一。这个看似简单的数学运算，对当代数字世界有着巨大的影响。

两个3×3矩阵相乘的例子。（图/DeepMind）

矩阵乘法是许多不同应用程序的核心计算类型，从处理智能手机中的图像到识别语音指令，从为电脑游戏生成图像到模拟复杂的物理学……可以说，在我们的日常生活中，矩阵乘法无处不在。

加快这种运算的计算速度可以对无数日常生活和工作中的计算任务产生重大影响。世界各地的公司不惜花费大量的时间和金钱来开发计算硬件，为的就是能够进行有效地矩阵相乘。因此，即使只是微小的改进矩阵乘法的效率，也能产生广泛的影响。

我们很多人在高中时期就学习过应该如何计算矩阵乘法。两个矩阵相乘通常涉及用一个矩阵中的行，乘以另一个矩阵的列。比如两个大小都为2×2的矩阵相乘时，就需要进行8次乘法运算才能求得两个矩阵的乘积。在长达几个世纪的时间里，数学家们都认为，矩阵乘法的这种标准算法有着最优效率。

但在1969年，德国数学家沃尔克·施特拉森（Volker Strassen）证明，还有更好的算法存在。通过研究2x2矩阵，他发现了一种只需要7次就能将2x2矩阵相乘的方法。

施特拉森算法

这种算法被称为施特拉森算法，这种算法需要进行多一些的加法，但这是可以接受的，因为计算机在计算加法时要比计算乘法快得多。

标准算法与施特拉森算法的对比：当两个2×2的矩阵相乘时，标准算法需要经过8次乘法运算，而施特拉森算法只需要进行7次乘法运算。对整体效率来说，乘法的影响比加法更大。（图/DeepMind）

在施特拉森做出突破后，数学家又进行了几十年的研究，尽管发现了一些不适用于计算机代码的微小改进，但对更大的矩阵来说问题仍然没有得到解决——在某种程度上，他们甚至不知道用这种方法计算两个大小仅为3x3的矩阵相乘的效率如何。

在新研究中，DeepMind团队探索了现代人工智能技术如何推动新的矩阵相乘算法的自动发现，并发现了一种可以在当前硬件上完美运作的更快的算法。

一个困难的棋盘游戏

首先，研究人员将寻找矩阵乘法的有效算法的问题，转化为一个名为TensorGame的三维棋盘游戏。在这个游戏中，棋盘是一个三维张量，代表要解决的乘法问题；每一步棋都代表解决问题的下一步，因此游戏中所采取的一系列的移动就代表一种算法。

玩家的目标是，通过允许的移动来修改张量，从而用最少的步骤让张量中的所有数字都归零。这是一项极具挑战性的游戏，因为每一步都可能需要从万亿步棋中进行选择。两个矩阵相乘的方法比宇宙中原子数量还要多。在一些例子中，这个游戏每一步可能的走法数量，是10的33次方（10³³）。

为了解决这一与传统游戏截然不同的挑战，研究人员开发了多个关键组件，包括一个包含特定问题归纳偏倚的新的神经网络架构，一个生成有用合成数据的程序，以及一个能充分利用问题对称性的配方。

然后，研究人员用一种被称为强化学习的机器学习方式，来训练一个AlphaTensor智能体来玩这个游戏。在开始时，AlphaTensor处于不了解任何现有的矩阵相乘算法的状态，通过学习，AlphaTensor会随着时间的推移逐渐改进：它开始发现那些人类已知的矩阵相乘算法，比如施特拉森算法，并最终超越人类直觉的领域，发现比已知的更快的算法。

由AlphaTensor进行的三维棋盘游戏，其目标是找到一个正确的矩阵乘法算法。游戏状态是一个由数字组成的立方数组（灰色表示0、蓝色表示1、绿色表示-1），代表着剩余要做的工作。（图/DeepMind）

有效的计算

计算一个4x5的矩阵乘以一个5x5的矩阵，传统算法需要进行100次乘法运算；而用在此之前的最佳算法来计算，这个数字可以减少到80次；现在，AlphaTensor发现的算法只需76次乘法就能完成运算。

总的来说，AlphaTensor在超过70种大小各异的矩阵上击败了现有的最佳算法。比如它将两个9×9的矩阵相乘所需的步数从511减少到498，将两个11×11的矩阵相乘所需的步数从919减少到896。在其他许多情况下，AlphaTensor重新发现了那些现有的最佳算法。

不仅如此，AlphaTensor还在有限域内改进了施特拉森的二阶算法，这是施特拉森算法自50年前发现以来迎来的首个改进。这些用于小矩阵相乘的算法，可作为用来乘任意大小的更大矩阵的原语。

另外，AlphaTensor还发现了一组具有最先进复杂性的多样化算法，每种大小都有多达数千个矩阵乘法算法，这表明矩阵乘法算法的空间比以前想象的更为丰富。

AlphaTensor具有一个对应于算法的运行时间的目标。当AlphaTensor发现正确的矩阵乘法算法时，就会在目标硬件上对其进行基准测试，然后反馈给AlphaTensor，以便在目标硬件上学习更高效的算法。（图/DeepMind）

在这个丰富的空间中，算法具有不同的数学特性和实用特性。利用这种多样性，研究人员将AlphaTensor调整为专门寻找能在一些特定硬件上快速运行的算法。用这些算法来计算大矩阵相乘的速度比在相同硬件上的常用算法快10-20%，这展示了AlphaTensor在优化任意目标方面的灵活性。

未来研究与应用

从数学的角度来看，新的结果可以指导复杂性理论（旨在确定解决计算问题的最快算法）的进一步研究。可以说，AlphaTensor提升了我们对矩阵乘法算法的丰富性的理解，而这种理解或许会为我们带来新的惊喜，比如帮助我们确定计算机科学中最基本的开放问题之一——矩阵乘法的渐近复杂性。

正如前文所提到的，矩阵乘法是计算机图形学、数字通信、神经网络训练和科学计算等许多计算任务的核心组成部分，因此AlphaTenor的发现可以大大提高这些领域的计算效率。AlphaTensor在考虑任何类型的目标上所拥有的灵活性，也可以激发设计不同算法的新应用。

DeepMind团队也希望，在这次工作的基础上，未来能够有更多的人开始应用人工智能来帮助解决数学和科学领域的一些最重要的挑战。

#创作团队：

编译：佐佑

#参考来源：

https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor

https://www.technologyreview.com/2022/10/05/1060717/deepmind-uses-its-game-playing-ai-to-best-a-50-year-old-record-in-computer-science/

https://www.nature.com/articles/d41586-022-03166-w

https://www.newscientist.com/article/2340343-deepmind-ai-finds-new-way-to-multiply-numbers-and-speed-up-computers/

#图片来源：

封面图：DeepMind

首图：DeepMind