【新智元导读】DeepMind碾压人类高手的AI围棋大师AlphaZero，下一个目标是数学算法！现已发现50年以来最快的矩阵乘法算法。
下围棋碾压人类的AlphaZero，开始搞数学算法了，先从矩阵乘法开始！
在昨天DeepMind团队发表在Nature上的论文中，介绍了 AlphaTensor，这是第一个用于为矩阵乘法等基本计算任务发现新颖、高效、正确算法的AI系统。
论文链接：https://www.nature.com/articles/s41586-022-05172-4.pdfAlphaTensor为一个 50 年来的悬而未决的数学问题找到了新答案：找到两个矩阵相乘的最快方法。先看看这研究都说的啥。提高基础计算算法的效率一直都是学界热点，因为它会影响大量计算的整体速度，从而对智能计算领域产生多米诺骨牌式的效应。上一张图，来看看AlphaTensor有多「能干」。
图a,b为AlphaTensor发现的算法在GPU (a) 和 TPU (b)上的加速百分比表现，针对大小为 8,192 × 8,192的矩阵乘法进行了优化矩阵乘法就是这样一项原始任务，从神经网络到科学计算程序，它都是不可或缺的部分。然而，算法发现过程的自动化是复杂的，因为可能的算法空间是巨大的。DeepMind这次发布了一种基于AlphaZero的深度强化学习方法，用于发现任意矩阵乘法的有效且可证明正确的算法。这个算法空间包含标准矩阵乘法算法和递归算法。DeepMind将矩阵乘法算法发现过程（即张量分解问题）制定为一个单人游戏——TensorGame。
AlphaTensor 建立在 AlphaZero 之上，训练了一个神经网络来指导规划过程，以搜索有效的矩阵乘法算法。
我们的框架使用单个智能体来分解各种大小的矩阵乘法张量，从而产生跨各种张量的学习分解技术的转移。为了解决游戏的挑战性，AlphaTensor 使用专门的神经网络架构，利用问题的对称性并利用合成训练游戏。AlphaTensor可扩展到比人工或组合搜索所能达到的算法空间大得多的算法空间。事实上，AlphaTensor 从零开始发现了许多可证明正确的矩阵乘法算法，这些算法在标量乘法的数量方面改进了现有算法。结果表明，AlphaTensor发现的算法在许多矩阵规模上都优于最先进的方法。
从围棋到矩阵乘法：AlphaZero「出圈」
矩阵乘法，学过线性代数的都熟悉，作为矩阵变换的基础运算之一，矩阵乘法是线性代数的基础工具，不仅在数学中有大量应用，在应用数学、物理学、工程学等领域也有广泛使用。作为构成数学算法的基础运算之一，矩阵乘法的应用史长达数千年。早在古埃及时代，人们就创造了一种无需乘法表的两个数字相乘的算法，希腊数学家欧几里德描述了一种计算最大公约数的算法，这种算法至今仍在使用。
在伊斯兰黄金时代，波斯数学家Muhammad ibn Musa al-Khwarizmi设计了新的算法来解决线性和二次方程。事实上，al-Khwarizmi的名字被翻译成拉丁文为Algoritmi，这就是今天英文「算法」一词的前身。但是，尽管今天人们对算法非常熟悉，但是，发现新算法的过程是非常困难的。在我们今天发表在《自然》杂志上的论文中，我们介绍了AlphaTensor，这是第一个用于发现新的、高效的、可证明正确的矩阵乘法等基本任务算法的AI系统。这为数学领域一个长达50年的开放性问题——如何寻找两个矩阵相乘的最快方法——给出了答案。这是DeepMind推动科学发展和利用AI解开最基本问题的又一次实践。AlphaTensor建立在AlphaZero的基础上，后者是一个在国际象棋、围棋和象棋等棋类游戏上表现超出人类的智能体，从下棋，到解决半个世纪以来的数学算法，AlphaZero是如何做到的？
打破矩阵乘法50年最快记录
矩阵乘法是代数中最简单的操作之一，通常在高中数学课上教授。但在课堂之外，这个不起眼的数学运算在当代数字世界有着巨大的影响力，在现代计算机中无处不在。
3*3矩阵相乘的计算矩阵乘法被用于处理智能手机上的图像，识别语音命令，为计算机游戏生成图形，运行模拟以预测天气，压缩数据和视频以在互联网上共享等，应用极为广泛。世界各地的公司花费了大量的时间和金钱来开发计算硬件，以有效地进行矩阵乘法。因此，即使是对矩阵乘法效率的微小改进也会产生广泛的影响。几个世纪以来，数学家们认为，标准的矩阵乘法算法是人们在效率方面所能达到的最佳状态。
但在1969年，德国数学家Volken Strassen震惊了数学界，他表明确实存在更好的算法。 
此前的矩阵乘法的标准算法与Strassen的算法相比，后者在乘2x2矩阵时少用了一个标量乘法（7次而不是8次）。就整体计算效率而言，乘法比加法重要得多。通过研究非常小的矩阵（大小为2x2），他发现了一种巧妙的方法来组合矩阵的条目，从而产生一种更快的算法。尽管经过几十年的研究，这个问题的更大版本仍然没有得到解决--以至于人们不知道如何有效地将两个小到3x3的矩阵相乘。在Nature的新论文中，我们探讨了现代人工智能技术如何推进新矩阵乘法算法的自动发现。AlphaTensor发现了在许多矩阵大小上比现有技术水平更有效的算法。我们的人工智能设计的算法优于人类设计的算法，这是在算法发现领域的一个重大进步。
