qc302 xz05 90e0h
976 87932 x20104
当前位置:FX168财经网 >> 财经 >>

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

时间:2022-10-07 15:53  |  来源: IT之家   |  阅读量:9964  |  

什么,AI可以自己改进矩阵乘法,加快运算速度。!

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

还是直接打破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最强通用国际象棋AIalpha zero进化而来。

那么,矩阵乘法和象棋有什么关系呢。

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

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

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

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

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

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

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

但是在矩阵乘法中,乘法的复杂度是O,而加法的复杂度只有O 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居然在旧的矩阵乘法规则的基础上,研究出了这个新的矩阵乘法计算方法。

论文地址:

参考链接:

声明:以上内容为本网站转自其它媒体,相关信息仅为传递更多企业信息之目的,不代表本网观点,亦不代表本网站赞同其观点或证实其内容的真实性。投资有风险,需谨慎。