什么，AI 竟然能自己改進(jìn)矩陣乘法，提升計(jì)算速度了？！
還是直接打破人類(lèi) 50 年前創(chuàng)下的最快紀(jì)錄的那種。
要知道，矩陣乘法可是計(jì)算機(jī)科學(xué)中最基礎(chǔ)的數(shù)學(xué)算法之一，也是各種 AI 計(jì)算方法的基石，如今計(jì)算機(jī)處理圖像語(yǔ)音、壓縮數(shù)據(jù)等全都離不開(kāi)它。
但自從德國(guó)數(shù)學(xué)家沃爾克?施特拉森（Volker Strassen）在 1969 年提出“施特拉森算法”后，矩陣乘法的計(jì)算速度一直進(jìn)步甚微。
現(xiàn)在，這只新出爐的 AI 不僅改進(jìn)了目前最優(yōu)的 4×4 矩陣解法（50 年前由施特拉森提出），還進(jìn)一步提升了其他 70 余種不同大小矩陣的計(jì)算速度。
這是 DeepMind 最新研究成果 AlphaTensor，一經(jīng)發(fā)出就登上了 Nature 封面。
有意思的是，AlphaTensor 并非一開(kāi)始就是專(zhuān)攻理論研究的，它的前身 AlphaZero 其實(shí)是個(gè)用來(lái)下下圍棋、國(guó)際象棋的“棋類(lèi) AI”。
這項(xiàng)研究發(fā)布后，一名在 DeepMind 工作 6 年的老員工表示：
我在 DeepMind 干了這么些年，能讓我吃驚的東西確實(shí)不多了，但這項(xiàng)研究確實(shí)讓我倒吸一口涼氣。
前谷歌大腦工程師 Eric Jang 也激動(dòng)轉(zhuǎn)發(fā)：干得好！
那么，這只“游戲”AI 究竟是怎么打破 50 年前人類(lèi)創(chuàng)下的紀(jì)錄的？
從最強(qiáng)棋類(lèi) AI 進(jìn)化而來(lái)
AlphaTensor，從 DeepMind 的最強(qiáng)通用棋類(lèi) AI“AlphaZero”進(jìn)化而來(lái)。
所以，矩陣乘法和棋類(lèi)有什么關(guān)系？
和棋盤(pán)一樣，矩陣看起來(lái)也是方方正正的，每一格可以用對(duì)應(yīng)的數(shù)據(jù)表示。
因此研究人員突發(fā)奇想，能不能直接把 AI 做矩陣乘法，當(dāng)成是 AI 在棋盤(pán)上下棋？
其中棋盤(pán)代表要解決的乘法問(wèn)題，下棋步驟代表解決問(wèn)題的步驟，對(duì)應(yīng)的規(guī)則被命名為 TensorGame，一種新的“3D 棋類(lèi)游戲”。
但與棋類(lèi) AI 略有不同的是，AlphaZero 要找到的是做矩陣乘法的最佳算法 —— 即通過(guò)盡可能少的步驟，來(lái)“贏”得比賽，也就是計(jì)算出最終結(jié)果。
在了解 AlphaTensor 具體如何訓(xùn)練之前，先來(lái)簡(jiǎn)單回顧一下矩陣乘法的計(jì)算。
以計(jì)算最簡(jiǎn)單的 2×2 矩陣乘法為例：
正常來(lái)說(shuō)，我們需要計(jì)算 8 次乘法，再通過(guò) 4 次加法來(lái)獲得最終的結(jié)果：
但在矩陣乘法運(yùn)算中，乘法的復(fù)雜度是 O (n3)，而加法的復(fù)雜度只有 O (n2)，n 越大時(shí)此方法的收益就越大。
因此，如果能想辦法降低做乘法的步驟，就能進(jìn)一步加速矩陣乘法的運(yùn)算速度。
例如根據(jù)經(jīng)典的 Strassen 算法，兩個(gè) 2×2 的矩陣相乘只需做 7 次乘法，時(shí)間復(fù)雜度也會(huì)進(jìn)一步下降。
當(dāng)然，這只是最簡(jiǎn)單的矩陣乘法之一。
對(duì)于更大、更復(fù)雜的矩陣乘法來(lái)說(shuō)，計(jì)算出最終結(jié)果的可能性只會(huì)越來(lái)越多 ——
甚至對(duì)于兩個(gè)矩陣相乘的方法來(lái)說(shuō)，最終可能性比宇宙中的原子還要多（數(shù)量級(jí)達(dá)到 10 的 33 次方）。
與 AlphaZero 之前搞定的圍棋游戲相比，AlphaTensor 的計(jì)算量還要更大，因?yàn)榫仃嚦朔ū葒蹇赡艿牟襟E還要多出 30 倍左右。
它同樣采用強(qiáng)化學(xué)習(xí)訓(xùn)練，并在訓(xùn)練之前先學(xué)習(xí)了一些人類(lèi)計(jì)算矩陣乘法的方法，避免在過(guò)程中“無(wú)腦亂猜”，浪費(fèi)不必要的計(jì)算量。
在訓(xùn)練時(shí)，AlphaTensor 每一步都會(huì)從一個(gè)可選擇的操作集（包含下一步可以做的所有計(jì)算動(dòng)作）選擇要完成的下一個(gè)動(dòng)作，最終訓(xùn)練自己通過(guò)更少的步驟達(dá)成計(jì)算目標(biāo)。
具體在選擇的過(guò)程中，AlphaTensor 采取了樹(shù)搜索（Tree Search）的方法，即基于現(xiàn)有游戲結(jié)果預(yù)測(cè)下一個(gè)最可能降低步驟的動(dòng)作。
出乎研究者們意料的是，AlphaTensor 發(fā)現(xiàn)的計(jì)算矩陣乘法的方法真的挺有效。
例如在英偉達(dá) V100 GPU 和谷歌 TPU v2 這兩種硬件上，使用 AlphaTensor 發(fā)現(xiàn)的算法計(jì)算矩陣乘法，比常用算法要快上 10~20% 左右。
（當(dāng)然研究者們也表示，其他處理器還得看硬件邏輯，計(jì)算方法不一定針對(duì)每個(gè)處理器都有這么好的加速作用）
具體而言，AlphaTensor 一共改進(jìn)了 70 多種不同大小矩陣的計(jì)算方法。
效率超越 70 + 現(xiàn)有計(jì)算方法
矩陣乘法是計(jì)算機(jī)要做的最關(guān)鍵數(shù)學(xué)計(jì)算之一。
同時(shí)，它也是機(jī)器學(xué)習(xí)計(jì)算中不可或缺的基礎(chǔ)，無(wú)論在 AI 處理手機(jī)圖像、理解語(yǔ)音命令，還是渲染電腦游戲畫(huà)面（計(jì)算機(jī)圖形學(xué)）等方面，都能見(jiàn)到它的身影。
如今我們做矩陣乘法，很大程度上仍然離不開(kāi) 50 年前的 Strassen 算法。
1969 年，德國(guó)數(shù)學(xué)家沃爾克?施特拉森（Volker Strassen）證明，將兩個(gè) 2×2 的矩陣相乘，不一定需要進(jìn)行 8 次乘法。
他巧妙的通過(guò)構(gòu)造 7 個(gè)中間變量，用增加 14 次加法為代價(jià)省去了一次乘法，這種方法被稱(chēng)為“施特拉森算法”（Strassen 算法）。
基于 Strassen 算法邏輯，沃爾克?施特拉森改進(jìn)了當(dāng)時(shí)的一大批矩陣乘法。
50 多年來(lái)，盡管針對(duì)一些不容易適應(yīng)計(jì)算機(jī)代碼的地方進(jìn)行了輕微改進(jìn)，但該算法一直是大多數(shù)矩陣大小上最有效的方法。
現(xiàn)在，AlphaTensor 的出現(xiàn)刷新了這一紀(jì)錄：
它發(fā)現(xiàn)了一種僅用 47 次乘法就能將兩個(gè) 4×4 的矩陣相乘的算法，超過(guò)了施特拉森算法所需的 49 次乘法。
不僅如此，AlphaTensor 還發(fā)現(xiàn)了比以前想象的更豐富的矩陣乘法算法空間 —— 每種尺寸上多達(dá)數(shù)千個(gè)算法。
最終，它在 70 種不同大小矩陣的矩陣乘法中擊敗了現(xiàn)有的最佳算法。
舉個(gè)例子，2 個(gè) 9×9 矩陣相乘所需的步驟數(shù)從 511 步減少到 498 步，2 個(gè) 11×11 矩陣相乘所需的步驟數(shù)從 919 步減少到 896 步……
所以在時(shí)間復(fù)雜度上，AlphaTensor 是否做出了對(duì)應(yīng)的突破？
對(duì)此論文介紹稱(chēng)，目前最優(yōu)的矩陣乘法時(shí)間復(fù)雜度，仍然是 2021 年 3 月 MIT & 哈佛大學(xué)研究中達(dá)成的這一數(shù)值（AlphaTensor 改善的時(shí)間復(fù)雜度并不比它更低）——
BUT，這個(gè)操作起來(lái)實(shí)在是太麻煩了，所以在實(shí)際計(jì)算中用處不大，除非計(jì)算的是天文數(shù)字大小的矩陣。
換而言之，即使 Strassen 算法的復(fù)雜度只達(dá)到 O (n^2.81)，但在大多數(shù)情況下，都要比上面那個(gè)時(shí)間復(fù)雜度更低的計(jì)算方法更實(shí)用。
嗯，更別提在不少特定矩陣乘法中還超過(guò)了 Strassen 算法的 AlphaTensor 了。
同時(shí)研究人員也表示，AlphaTensor 設(shè)計(jì)的算法具有一定的靈活性。
它不僅可能推進(jìn)各種應(yīng)用程序重新設(shè)計(jì)算法，還可能優(yōu)化能源使用量和數(shù)值穩(wěn)定性等指標(biāo)，幫助在實(shí)際應(yīng)用時(shí)防止算法運(yùn)行時(shí)出現(xiàn)小的舍入誤差（包括 Strassen 算法等計(jì)算矩陣乘法，都會(huì)出現(xiàn)一定的誤差）。
此外，雖然目前這些突破還只是針對(duì)特定算法改進(jìn)的，但也有科學(xué)家認(rèn)為 AlphaTensor 的潛力不止于此。
例如，MIT 計(jì)算機(jī)科學(xué)家 Virginia Williams 就表示：
研究者們可以再?lài)L試一下，去搞明白這些特定算法中有沒(méi)有什么特殊規(guī)律。此外，也可以研究一下如果將這些特殊算法組合起來(lái)，是否能發(fā)現(xiàn)更多更優(yōu)的計(jì)算方法。
目前 AlphaTensor 的相關(guān)代碼已經(jīng)開(kāi)源。
共同一作也是 AlphaGo 關(guān)鍵“擺棋手”
AlphaTensor 的研究團(tuán)隊(duì)都來(lái)自 DeepMind。
5 位共同一作分別是 Alhussein Fawzi、Matej Balog、黃士杰、Thomas Hubert 和 Bernardino Romera-Paredes。
其中黃士杰來(lái)自中國(guó)臺(tái)灣，本科畢業(yè)于臺(tái)灣交通大學(xué)計(jì)算機(jī)與信息科學(xué)專(zhuān)業(yè)，在臺(tái)灣師范大學(xué)獲得研究生、博士學(xué)位，后前往加拿大阿爾伯塔大學(xué)攻讀博士后，于 2012 年加入 DeepMind。
他曾在 AlphaGo 和李世石大戰(zhàn)中，擔(dān)當(dāng) AlphaGo 的“人肉臂”（順便把棋輸入電腦），也是 AlphaGo 論文的共同一作。
對(duì)于這只 AI 達(dá)成的新成就，有網(wǎng)友調(diào)侃：
有意思的是，這只 AI 竟然是基于舊的矩陣乘法運(yùn)算規(guī)則，算出這個(gè)新矩陣乘法計(jì)算方法的。
論文地址：
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
本文來(lái)自微信公眾號(hào)：量子位 （ID：QbitAI），作者：羿閣、蕭簫
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。