AlphaTensor横空出世！打破矩阵乘法计算速度50年纪录，Deep

什么，AI可以自己改进矩阵乘法，加快运算速度？！

还是直接打破50年前人类创下的最快纪录的那种。

要知道，矩阵乘法是计算机科学中最基本的数学算法之一，也是各种AI计算方法的基石。现在，没有它，计算机就不能处理图像、声音和压缩数据。

然而，自1969年德国数学家Volker Strasen提出“Strasen算法”以来，矩阵乘法的计算速度却进展甚微。

现在，这个新发布的AI不仅提高了当前最优的4×4矩阵解，还进一步加快了其他70多个不同大小矩阵的计算速度。

这是DeepMind的最新研究成果，AlphaTensor，发表在《自然》的封面上。

有趣的是，AlphaTensor并不是一开始就专门从事理论研究的。它的前身AlphaZero其实是一个用来下围棋和象棋的“象棋AI”。

这项研究发布后，一位在DeepMind工作了6年的老员工说:

我在DeepMind工作了这么多年，能让我惊喜的东西真的不多，但是这个研究真的让我倒吸一口凉气。

前谷歌大脑工程师Eric Jang也兴奋地转发:干得好！

那么，这个“游戏”AI是如何打破人类50年前创下的纪录的呢？

从最强象棋AI进化而来

AlphaTensor，由DeepMind最强通用国际象棋AI“alpha zero”进化而来。

那么，矩阵乘法和象棋有什么关系呢？

和棋盘一样，矩阵看起来是正方形的，每个格子都可以用相应的数据来表示。

因此，研究人员突发奇想。他们能直接把AI乘成矩阵，当成AI在棋盘上下棋吗？

其中棋盘代表要解决的乘法问题，下棋步骤代表解决问题的步骤。相应的规则被命名为TensorGame，一种新的“3D棋盘游戏”。

但与国际象棋AI略有不同的是，AlphaZero寻找的是做矩阵乘法的最佳算法——即通过尽可能少的步骤“赢得”比赛，也就是计算出最终结果。

在知道如何训练AlphaTensor之前，我们先简单回顾一下矩阵乘法的计算。

以最简单的2×2矩阵乘法为例:

通常情况下，我们需要计算8次乘法，然后加上4次才能得到最终结果:

但是在矩阵乘法中，乘法的复杂度是O，而加法的复杂度只有O (n)。n越大，这种方法的收益越大。

因此，如果能找到减少乘法步骤的方法，就可以进一步加快矩阵乘法的运算速度。

比如按照经典的Strassen算法，两个2×2矩阵相乘只需要7次乘法，时间复杂度会进一步降低。

当然，这只是最简单的矩阵乘法之一。

对于更大更复杂的矩阵乘法，计算出最终结果的可能性只会增加——

即使是两个矩阵相乘的方法，最后的可能性也比宇宙中的原子多。

相比之前AlphaZero做的围棋游戏，AlphaTensor需要的运算量更大，因为矩阵乘法比围棋多了30倍左右的步骤。

还采用强化学习训练，训练前学习一些人类计算矩阵乘法的方法，避免过程中“无脑猜测”，浪费不必要的计算。

训练时，AlphaTensor会从每一步的可选操作集合中选择下一个要完成的动作，最终训练自己通过更少的步骤达到计算目标。

在具体的选择过程中，AlphaTensor采用了树搜索的方法，即基于已有的游戏结果，预测下一个最有可能的动作来减少步骤。

令研究人员惊讶的是，AlphaTensor发现的计算矩阵乘法的方法真的很有效。

比如在英伟达V100 GPU和谷歌TPU v2上，使用AlphaTensor发现的算法计算矩阵乘法，比常用算法快10~20%左右。

具体来说，AlphaTensor改进了70多个不同大小矩阵的计算方法。

效率超过70+现有计算方法。

矩阵乘法是计算机最重要的数学计算之一。

同时也是机器学习和计算中不可或缺的基础，在处理手机图像、理解语音命令、渲染电脑游戏画面等AI中都可以看到。

如今，没有50年前的Strassen算法，我们就做不了矩阵乘法。

1969年，德国数学家Volker Strasen证明了两个2×2矩阵相乘不一定需要八次乘法。

他巧妙地构造了7个中间变量，以加14次为代价省略了1次乘法，被称为“Strasen算法”。

沃尔克·斯特拉森在斯特拉森算法逻辑的基础上，改进了当时大量的矩阵乘法。

50多年来，这种算法一直是大多数矩阵规模中最有效的方法，尽管对一些不易适应计算机代码的地方做了一些细微的改进。

现在，AlphaTensor的出现创造了一个新纪录:

找到了一种仅用47次乘法就可以将两个4×4矩阵相乘的算法，超过了Strasen算法所需的49次乘法。

不仅如此，AlphaTensor还为矩阵乘法算法找到了比以前想象的更丰富的空间——每种尺寸有数千种算法。

最终在70个不同大小矩阵的矩阵乘法中击败了现有的最佳算法。

例如，将两个9×9矩阵相乘所需的步骤数从511减少到498，将两个11×11矩阵相乘所需的步骤数从919减少到896...

那么在时间复杂度上，AlphaTensor有没有相应的突破？

根据这篇论文，2021年3月矩阵乘法的最优时间复杂度仍然是MIT amp哈佛大学的研究得出了这个数值—

但是，操作起来太麻烦了，所以在实际计算中用处不大，除非是天文矩阵。

换句话说，即使Strassen算法的复杂度仅达到O，但在大多数情况下，它比上述时间复杂度更低的计算方法更实用。

好吧，且不说在很多特定的矩阵乘法上已经超过了Strassen算法的AlphaTensor。

同时，研究人员还表示，AlphaTensor设计的算法具有一定的灵活性。

它不仅可以促进各种应用中算法的重新设计，还可以优化能耗和数值稳定性，并有助于防止实际应用中算法运行中的小舍入误差。

此外，虽然这些突破目前只是针对特定算法的改进，但一些科学家认为AlphaTensor的潜力并不止于此。

例如，麻省理工学院的计算机科学家维吉尼亚·威廉姆斯说:

研究人员可以再次尝试，找出这些特定算法中是否有什么特殊的规则。此外，我们还可以研究如果将这些特殊算法结合起来，是否能找到更多更好的计算方法。

目前AlphaTensor的相关代码已经开源。

合作也是AlphaGo的关键“棋手”。

AlphaTensor的研究团队都来自DeepMind。

五名合著者是:Alhussein Fawzi、Matej Balog、黄士杰、Thomas Hubert和Bernardino Romera-Paredes。

其中，黄士杰来自中国台湾省。毕业于台湾交通大学，获计算机与信息科学学士学位，获得台湾省师范大学研究生和博士学位，后赴加拿大阿尔伯塔大学从事博士后研究。他于2012年加入DeepMind。

他在AlphaGo与李世石的战争中担任AlphaGo的“人臂”，也是AlphaGo论文的合著者。

对于这个AI的新成果，有网友调侃道:

有趣的是，这个AI居然在旧的矩阵乘法规则的基础上，研究出了这个新的矩阵乘法计算方法。

论文地址:

参考链接: