矩阵相乘怎么计算
羿阁 萧箫 发自 凹非寺
量子位 | 公众号 QbitAI
什么，AI竟然能自己改进矩阵乘法，提升计算速度了？！
还是直接打破人类50年前创下的最快纪录的那种。
要知道，矩阵乘法可是计算机科学中最基础的数学算法之一，也是各种AI计算方法的基石，如今计算机处理图像语音、压缩数据等全都离不开它。
但自从德国数学家沃尔克·施特拉森（Volker Strassen）在1969年提出“施特拉森算法”后，矩阵乘法的计算速度一直进步甚微。
现在，这只新出炉的AI不仅改进了目前最优的4×4矩阵解法（50年前由施特拉森提出），还进一步提升了其他70余种不同大小矩阵的计算速度。
这是DeepMind最新研究成果AlphaTensor，一经发出就登上了Nature封面。
有意思的是，AlphaTensor并非一开始就是专攻理论研究的，它的前身AlphaZero其实是个用来下下围棋、国际象棋的“棋类AI”。
这项研究发布后，一名在DeepMind工作6年的老员工表示：
我在DeepMind干了这么些年，能让我吃惊的东西确实不多了，但这项研究确实让我倒吸一口凉气。
前谷歌大脑工程师Eric Jang也激动转发：干得好！
那么，这只“游戏”AI究竟是怎么打破50年前人类创下的纪录的？
从最强棋类AI进化而来
AlphaTensor，从DeepMind的最强通用棋类AI“AlphaZero”进化而来。
所以，矩阵乘法和棋类有什么关系？
和棋盘一样，矩阵看起来也是方方正正的，每一格可以用对应的数据表示。
因此研究人员突发奇想，能不能直接把AI做矩阵乘法，当成是AI在棋盘上下棋？
其中棋盘代表要解决的乘法问题，下棋步骤代表解决问题的步骤，对应的规则被命名为TensorGame，一种新的“3D棋类游戏”。
但与棋类AI略有不同的是，AlphaZero要找到的是做矩阵乘法的最佳算法——即通过尽可能少的步骤，来“赢”得比赛，也就是计算出最终结果。
在了解AlphaTensor具体如何训练之前，先来简单回顾一下矩阵乘法的计算。
以计算最简单的2×2矩阵乘法为例：
正常来说，我们需要计算8次乘法，再通过4次加法来获得最终的结果：
但在矩阵乘法运算中，乘法的复杂度是O(n³)，而加法的复杂度只有O(n²)，n越大时此方法的收益就越大。
因此，如果能想办法降低做乘法的步骤，就能进一步加速矩阵乘法的运算速度。
例如根据经典的Strassen算法，两个2×2的矩阵相乘只需做7次乘法，时间复杂度也会进一步下降。
当然，这只是最简单的矩阵乘法之一。
对于更大、更复杂的矩阵乘法来说，计算出最终结果的可能性只会越来越多——
甚至对于两个矩阵相乘的方法来说，最终可能性比宇宙中的原子还要多（数量级达到10的33次方）。
与AlphaZero之前搞定的围棋游戏相比，AlphaTensor的计算量还要更大，因为矩阵乘法比围棋可能的步骤还要多出30倍左右。
它同样采用强化学习训练，并在训练之前先学习了一些人类计算矩阵乘法的方法，避免在过程中“无脑乱猜”，浪费不必要的计算量。
在训练时，AlphaTensor每一步都会从一个可选择的操作集（包含下一步可以做的所有计算动作）选择要完成的下一个动作，最终训练自己通过更少的步骤达成计算目标。
具体在选择的过程中，AlphaTensor采取了树搜索（Tree Search）的方法，即基于现有游戏结果预测下一个最可能降低步骤的动作。
出乎研究者们意料的是，AlphaTensor发现的计算矩阵乘法的方法真的挺有效。
例如在英伟达V100 GPU和谷歌TPU v2这两种硬件上，使用AlphaTensor发现的算法计算矩阵乘法，比常用算法要快上10~20%左右。
（当然研究者们也表示，其他处理器还得看硬件逻辑，计算方法不一定针对每个处理器都有这么好的加速作用）
具体而言，AlphaTensor一共改进了70多种不同大小矩阵的计算方法。
效率超越70+现有计算方法
矩阵乘法是计算机要做的最关键数学计算之一。
同时，它也是机器学习计算中不可或缺的基础，无论在AI处理手机图像、理解语音命令，还是渲染电脑游戏画面（计算机图形学）等方面，都能见到它的身影。
如今我们做矩阵乘法，很大程度上仍然离不开50年前的Strassen算法。
1969年，德国数学家沃尔克·施特拉森（Volker Strassen）证明，将两个2×2的矩阵相乘，不一定需要进行8次乘法。
他巧妙的通过构造7个中间变量，用增加14次加法为代价省去了一次乘法，这种方法被称为“施特拉森算法”（Strassen算法）。
基于Strassen算法逻辑，沃尔克·施特拉森改进了当时的一大批矩阵乘法。
50多年来，尽管针对一些不容易适应计算机代码的地方进行了轻微改进，但该算法一直是大多数矩阵大小上最有效的方法。
现在，AlphaTensor的出现刷新了这一纪录：
它发现了一种仅用47次乘法就能将两个4×4的矩阵相乘的算法，超过了施特拉森算法所需的49次乘法。
不仅如此，AlphaTensor还发现了比以前想象的更丰富的矩阵乘法算法空间——每种尺寸上多达数千个算法。
最终，它在70种不同大小矩阵的矩阵乘法中击败了现有的最佳算法。
举个例子，2个9×9矩阵相乘所需的步骤数从511步减少到498步，2个11×11矩阵相乘所需的步骤数从919步减少到896步……
所以在时间复杂度上，AlphaTensor是否做出了对应的突破？
对此论文介绍称，目前最优的矩阵乘法时间复杂度，仍然是2021年3月MIT&哈佛大学研究中达成的这一数值（AlphaTensor改善的时间复杂度并不比它更低）——
BUT，这个操作起来实在是太麻烦了，所以在实际计算中用处不大，除非计算的是天文数字大小的矩阵。
换而言之，即使Strassen算法的复杂度只达到O(n^2.81)，但在大多数情况下，都要比上面那个时间复杂度更低的计算方法更实用。
嗯，更别提在不少特定矩阵乘法中还超过了Strassen算法的AlphaTensor了。
同时研究人员也表示，AlphaTensor设计的算法具有一定的灵活性。
它不仅可能推进各种应用程序重新设计算法，还可能优化能源使用量和数值稳定性等指标，帮助在实际应用时防止算法运行时出现小的舍入误差（包括Strassen算法等计算矩阵乘法，都会出现一定的误差）。
此外，虽然目前这些突破还只是针对特定算法改进的，但也有科学家认为AlphaTensor的潜力不止于此。
例如，MIT计算机科学家Virginia Williams就表示：
研究者们可以再尝试一下，去搞明白这些特定算法中有没有什么特殊规律。此外，也可以研究一下如果将这些特殊算法组合起来，是否能发现更多更优的计算方法。
目前AlphaTensor的相关代码已经开源。
共同一作也是AlphaGo关键“摆棋手”
AlphaTensor的研究团队都来自DeepMind。
5位共同一作分别是Alhussein Fawzi、Matej Balog、黄士杰、Thomas Hubert和Bernardino Romera-Paredes。
其中黄士杰来自中国台湾，本科毕业于台湾交通大学计算机与信息科学专业，在台湾师范大学获得研究生、博士学位，后前往加拿大阿尔伯塔大学攻读博士后，于2012年加入DeepMind。
他曾在AlphaGo和李世石大战中，担当AlphaGo的“人肉臂”（顺便把棋输入电脑），也是AlphaGo论文的共同一作。
对于这只AI达成的新成就，有网友调侃：
有意思的是，这只AI竟然是基于旧的矩阵乘法运算规则，算出这个新矩阵乘法计算方法的。
论文地址：
https://www.nature.com/articles/s41586-022-05172-4参考链接：
[1]https://www.technologyreview.com/2022/10/05/1060717/deepmind-uses-its-game-playing-ai-to-best-a-50-year-old-record-in-computer-science/[2]https://www.nature.com/articles/d41586-022-03166-w[3]https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor[4]https://twitter.com/DeepMind/status/1577677899108421633— 完 —
量子位 QbitAI · 头条号签约
","force_purephv":"0","gnid":"9ad2b7e9704078d21","img_data":[{"flag":2,"img":[{"desc":"","height":"1326","title":"","url":"https://p0.ssl.img.360kuai.com/t01de7ecb0d122813b9.jpg","width":"1000"},{"desc":"","height":"396","title":"","url":"https://p0.ssl.img.360kuai.com/t012bb7d9ba2cf2c785.jpg","width":"1064"},{"desc":"","height":"178","title":"","url":"https://p0.ssl.img.360kuai.com/t011e866cc10c15421c.jpg","width":"1080"},{"desc":"","height":"592","title":"","url":"https://p0.ssl.img.360kuai.com/t01164dfecae12f29c5.jpg","width":"856"},{"desc":"","height":"270","title":"","url":"https://p0.ssl.img.360kuai.com/t01e0cbc189c1c5f52f.jpg","width":"1080"},{"desc":"","height":"1246","title":"","url":"https://p0.ssl.img.360kuai.com/t0115b8df3f937dfd2d.jpg","width":"976"},{"desc":"","height":"696","title":"","url":"https://p0.ssl.img.360kuai.com/t01aed02975f60b2ef4.jpg","width":"1008"},{"desc":"","height":"1084","title":"","url":"https://p0.ssl.img.360kuai.com/t014eb69edef04beaaf.jpg","width":"1080"},{"desc":"","height":"1118","title":"","url":"https://p0.ssl.img.360kuai.com/t01ab32c1034e1297ed.jpg","width":"848"},{"desc":"","height":"772","title":"","url":"https://p0.ssl.img.360kuai.com/t01b6d7f4e46fb7cfe1.jpg","width":"1080"},{"desc":"","height":"256","title":"","url":"https://p0.ssl.img.360kuai.com/t0131539edae3dfa518.jpg","width":"1276"},{"desc":"","height":"764","title":"","url":"https://p0.ssl.img.360kuai.com/t01a01aa205228d84e1.jpg","width":"692"},{"desc":"","height":"522","title":"","url":"https://p0.ssl.img.360kuai.com/t01025a1dc209ff2845.jpg","width":"1080"},{"desc":"","height":"602","title":"","url":"https://p0.ssl.img.360kuai.com/t01d8bcc71564d5cbb9.jpg","width":"1012"},{"desc":"","height":"366","title":"","url":"https://p0.ssl.img.360kuai.com/t01e8ae501f338306e9.jpg","width":"1080"}]}],"original":0,"pat":"art_src_3,fts0,sts0","powerby":"hbase","pub_time":1665034260000,"pure":"","rawurl":"http://zm.news.so.com/8a24fd6d3cf94e2d53bfdcbd6ad40390","redirect":0,"rptid":"d89564eb1f4bb644","s":"t","src":"量子位","tag":[],"title":"AlphaTensor横空出世！打破矩阵乘法计算速度50年纪录，已开源
伍婷缸4042矩阵乘法是怎么乘的啊. -
诸贝善18251747851 ______ 左乘矩阵的第1行的数0,0,1 分别乘 右乘矩阵第1列对应的 1,0,0 再加起来 就是乘积矩阵第1行第1列的数 一般情况 是 左乘矩阵的第 i 行的数 分别乘 右乘矩阵第 j 列对应的数 再加起来 就是乘积矩阵第 i 行第 j 列的数
伍婷缸4042老师,矩阵相乘怎么算
诸贝善18251747851 ______ 矩阵乘法 百科名片 矩阵乘法是一种高效的算法可以把一些一维递推优化到log( n ),还可以求路径方案等,所以更是是一种应用性极强的算法.矩阵,是线性代数中的基本概念之一.一个m*n的矩阵就是m*n个数排成m行n列的一个数阵.由于它...
伍婷缸4042矩阵平方怎么运算
诸贝善18251747851 ______ 矩阵平方运算是|aA|=a^n|A|,矩阵相乘最重要的方法是一般矩阵乘积.它只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有意义.一般单指矩阵乘积时,指的便是一般矩阵乘积.一个m*n的矩阵就是m*n个数排成m行n列的一个数阵.由于它把许多数据紧凑地集中到了一起,所以有时候可以简便地表示一些复杂的模型,如电力系统网络模型.
伍婷缸4042矩阵乘法怎么做啊.. -
诸贝善18251747851 ______ 若矩阵A是m*n阶的,B是p*q阶的矩阵,AB能相乘,首先得满足 n=p即A的列数要等于B的行数 AB=C,则,C中的元素C(ij)是A中对应第i行乘以B中的第j列元素相加得到
伍婷缸4042谁能告诉我矩阵的乘法怎么算哦
诸贝善18251747851 ______ 两个矩阵相乘,满足第一个矩阵的列数等于第二个矩阵的行数.第一个矩阵第一行的每个数与第二个矩阵第一列的每个数相乘之和为新矩阵的第一个数,第一个矩阵第一行的每个数与第二个矩阵第二列的每个数相乘之和为新矩阵的第一行第二个数,依次
伍婷缸4042两个行列式如何相乘
诸贝善18251747851 ______ 行列式相乘计算有两种方法,一是将两个矩阵相乘,得到一个新矩阵,求其行列式,即可.另一种方法是,将各个行列式分别求出结果,然后两数相乘,即可.行列式在数学中,是一个函数,其定义域为det的矩阵A,取值为一个标量,写作det(A)或|A|.无论是在线性代数、多项式理论,还是在微积分学中(比如说换元积分法中),行列式作为基本的数学工具,都有着重要的应用.行列式可以看做是有向面积或体积的概念在一般的欧几里得空间中的推广.或者说,在n维欧几里得空间中,行列式描述的是一个线性变换对“体积”所造成的影响.
伍婷缸40422x3矩阵的乘法怎么算? -
诸贝善18251747851 ______ 2x3矩阵,左边矩阵第一行的元素分别与右边矩阵第一列的元素相乘,求和得到相乘矩阵的第一行的第一个元素.左边矩阵第一行的元素分别与右边矩阵第二列的元素相乘,求和得到相乘矩阵的第一行的锋伍第二个元素.以此类推. 具体方法如下图: 设m*n的矩阵A与n*s矩阵B相乘,得到m*s的矩阵C.矩阵C的第i行第j列的元素Cij就是取A的第i行、B的第j列,然后对应散扒元素相乘. 这是2*3矩阵与3*3矩阵相乘银掘或的具体结果,可以比对一下.关键还是要掌握一般矩阵乘法的判定方法、基本规则.
伍婷缸4042求矩阵乘法公式 -
诸贝善18251747851 ______ ........1*2+2*1+1*3..1*3+2*5+1*6..1*4+2*2+1*7..7.19.15 A*B=2*2+5*1+3*3..2*3+5*5+3*6..2*4+5*2+3*7=18.49.39 ........1*2+3*1+4*3..1*3+3*5+4*6..1*4+3*2+4*7..17.42.38 ...表示空格 规则就是,把前面矩阵的第i行与后面矩阵的第j列对应元素相乘再相加,放到结果矩阵的第(i,j)这个位置上. 明白了吗?
伍婷缸4042三乘三矩阵的乘法运算怎么进行的? -
诸贝善18251747851 ______ 三乘三矩阵的乘法运算(也称为矩阵乘法)涉及到两个三乘三矩阵的相乘.具体计算过程如下:1.初始化:首先,我们需要有两个三乘三矩阵,例如矩阵A和矩阵B:A=|a11a12a13||a21a22a23||a31a32a33|B=|b11b12b13||b21b22b23||b31b32b33|2...