數(shù)千年來(lái)，算法一直在幫助數(shù)學(xué)家進(jìn)行基本運(yùn)算。

古埃及人發(fā)明了一種不需要乘法表就能得出兩個(gè)數(shù)字的乘積的算法；歐幾里得描述了一種沿用至今的計(jì)算最大公約數(shù)的算法；在伊斯蘭的黃金時(shí)代，花拉子米設(shè)計(jì)出了求解線性方程和二次方程的新算法。盡管現(xiàn)如今我們對(duì)算法已經(jīng)非常熟悉，但發(fā)現(xiàn)新算法的過(guò)程仍是非常困難的。

在一篇于近期發(fā)表在《自然》雜志上的論文中，DeepMind團(tuán)隊(duì)介紹了第一個(gè)用于發(fā)現(xiàn)新的、高效的、可證明正確的基本算法（如矩陣乘法）的人工智能系統(tǒng)——AlphaTensor。它打破了一個(gè)保持了50多年的記錄，發(fā)現(xiàn)了一種能更快地計(jì)算兩個(gè)矩陣之間的乘法的算法。

核心運(yùn)算：矩陣乘法

矩陣乘法是我們非常熟悉，也是代數(shù)中最基本的運(yùn)算之一。這個(gè)看似簡(jiǎn)單的數(shù)學(xué)運(yùn)算，對(duì)當(dāng)代數(shù)字世界有著巨大的影響。

兩個(gè)3×3矩陣相乘的例子。（圖/DeepMind）

矩陣乘法是許多不同應(yīng)用程序的核心計(jì)算類型，從處理智能手機(jī)中的圖像到識(shí)別語(yǔ)音指令，從為電腦游戲生成圖像到模擬復(fù)雜的物理學(xué)……可以說(shuō)，在我們的日常生活中，矩陣乘法無(wú)處不在。

加快這種運(yùn)算的計(jì)算速度可以對(duì)無(wú)數(shù)日常生活和工作中的計(jì)算任務(wù)產(chǎn)生重大影響。世界各地的公司不惜花費(fèi)大量的時(shí)間和金錢來(lái)開(kāi)發(fā)計(jì)算硬件，為的就是能夠進(jìn)行有效地矩陣相乘。因此，即使只是微小的改進(jìn)矩陣乘法的效率，也能產(chǎn)生廣泛的影響。

我們很多人在高中時(shí)期就學(xué)習(xí)過(guò)應(yīng)該如何計(jì)算矩陣乘法。兩個(gè)矩陣相乘通常涉及用一個(gè)矩陣中的行，乘以另一個(gè)矩陣的列。比如兩個(gè)大小都為2×2的矩陣相乘時(shí)，就需要進(jìn)行8次乘法運(yùn)算才能求得兩個(gè)矩陣的乘積。在長(zhǎng)達(dá)幾個(gè)世紀(jì)的時(shí)間里，數(shù)學(xué)家們都認(rèn)為，矩陣乘法的這種標(biāo)準(zhǔn)算法有著最優(yōu)效率。

但在1969年，德國(guó)數(shù)學(xué)家沃爾克·施特拉森（Volker Strassen）證明，還有更好的算法存在。通過(guò)研究2x2矩陣，他發(fā)現(xiàn)了一種只需要7次就能將2x2矩陣相乘的方法。

施特拉森算法

這種算法被稱為施特拉森算法，這種算法需要進(jìn)行多一些的加法，但這是可以接受的，因?yàn)橛?jì)算機(jī)在計(jì)算加法時(shí)要比計(jì)算乘法快得多。

標(biāo)準(zhǔn)算法與施特拉森算法的對(duì)比：當(dāng)兩個(gè)2×2的矩陣相乘時(shí)，標(biāo)準(zhǔn)算法需要經(jīng)過(guò)8次乘法運(yùn)算，而施特拉森算法只需要進(jìn)行7次乘法運(yùn)算。對(duì)整體效率來(lái)說(shuō)，乘法的影響比加法更大。（圖/DeepMind）

在施特拉森做出突破后，數(shù)學(xué)家又進(jìn)行了幾十年的研究，盡管發(fā)現(xiàn)了一些不適用于計(jì)算機(jī)代碼的微小改進(jìn)，但對(duì)更大的矩陣來(lái)說(shuō)問(wèn)題仍然沒(méi)有得到解決——在某種程度上，他們甚至不知道用這種方法計(jì)算兩個(gè)大小僅為3x3的矩陣相乘的效率如何。

在新研究中，DeepMind團(tuán)隊(duì)探索了現(xiàn)代人工智能技術(shù)如何推動(dòng)新的矩陣相乘算法的自動(dòng)發(fā)現(xiàn)，并發(fā)現(xiàn)了一種可以在當(dāng)前硬件上完美運(yùn)作的更快的算法。

一個(gè)困難的棋盤(pán)游戲

首先，研究人員將尋找矩陣乘法的有效算法的問(wèn)題，轉(zhuǎn)化為一個(gè)名為TensorGame的三維棋盤(pán)游戲。在這個(gè)游戲中，棋盤(pán)是一個(gè)三維張量，代表要解決的乘法問(wèn)題；每一步棋都代表解決問(wèn)題的下一步，因此游戲中所采取的一系列的移動(dòng)就代表一種算法。

玩家的目標(biāo)是，通過(guò)允許的移動(dòng)來(lái)修改張量，從而用最少的步驟讓張量中的所有數(shù)字都?xì)w零。這是一項(xiàng)極具挑戰(zhàn)性的游戲，因?yàn)槊恳徊蕉伎赡苄枰獜娜f(wàn)億步棋中進(jìn)行選擇。兩個(gè)矩陣相乘的方法比宇宙中原子數(shù)量還要多。在一些例子中，這個(gè)游戲每一步可能的走法數(shù)量，是10的33次方（1033）。

為了解決這一與傳統(tǒng)游戲截然不同的挑戰(zhàn)，研究人員開(kāi)發(fā)了多個(gè)關(guān)鍵組件，包括一個(gè)包含特定問(wèn)題歸納偏倚的新的神經(jīng)網(wǎng)絡(luò)架構(gòu)，一個(gè)生成有用合成數(shù)據(jù)的程序，以及一個(gè)能充分利用問(wèn)題對(duì)稱性的配方。

然后，研究人員用一種被稱為強(qiáng)化學(xué)習(xí)的機(jī)器學(xué)習(xí)方式，來(lái)訓(xùn)練一個(gè)AlphaTensor智能體來(lái)玩這個(gè)游戲。在開(kāi)始時(shí)，AlphaTensor處于不了解任何現(xiàn)有的矩陣相乘算法的狀態(tài)，通過(guò)學(xué)習(xí)，AlphaTensor會(huì)隨著時(shí)間的推移逐漸改進(jìn)：它開(kāi)始發(fā)現(xiàn)那些人類已知的矩陣相乘算法，比如施特拉森算法，并最終超越人類直覺(jué)的領(lǐng)域，發(fā)現(xiàn)比已知的更快的算法。

由AlphaTensor進(jìn)行的三維棋盤(pán)游戲，其目標(biāo)是找到一個(gè)正確的矩陣乘法算法。游戲狀態(tài)是一個(gè)由數(shù)字組成的立方數(shù)組（灰色表示0、藍(lán)色表示1、綠色表示-1），代表著剩余要做的工作。（圖/DeepMind）

有效的計(jì)算

計(jì)算一個(gè)4x5的矩陣乘以一個(gè)5x5的矩陣，傳統(tǒng)算法需要進(jìn)行100次乘法運(yùn)算；而用在此之前的最佳算法來(lái)計(jì)算，這個(gè)數(shù)字可以減少到80次；現(xiàn)在，AlphaTensor發(fā)現(xiàn)的算法只需76次乘法就能完成運(yùn)算。

總的來(lái)說(shuō)，AlphaTensor在超過(guò)70種大小各異的矩陣上擊敗了現(xiàn)有的最佳算法。比如它將兩個(gè)9×9的矩陣相乘所需的步數(shù)從511減少到498，將兩個(gè)11×11的矩陣相乘所需的步數(shù)從919減少到896。在其他許多情況下，AlphaTensor重新發(fā)現(xiàn)了那些現(xiàn)有的最佳算法。

不僅如此，AlphaTensor還在有限域內(nèi)改進(jìn)了施特拉森的二階算法，這是施特拉森算法自50年前發(fā)現(xiàn)以來(lái)迎來(lái)的首個(gè)改進(jìn)。這些用于小矩陣相乘的算法，可作為用來(lái)乘任意大小的更大矩陣的原語(yǔ)。

另外，AlphaTensor還發(fā)現(xiàn)了一組具有最先進(jìn)復(fù)雜性的多樣化算法，每種大小都有多達(dá)數(shù)千個(gè)矩陣乘法算法，這表明矩陣乘法算法的空間比以前想象的更為豐富。

AlphaTensor具有一個(gè)對(duì)應(yīng)于算法的運(yùn)行時(shí)間的目標(biāo)。當(dāng)AlphaTensor發(fā)現(xiàn)正確的矩陣乘法算法時(shí)，就會(huì)在目標(biāo)硬件上對(duì)其進(jìn)行基準(zhǔn)測(cè)試，然后反饋給AlphaTensor，以便在目標(biāo)硬件上學(xué)習(xí)更高效的算法。（圖/DeepMind）

在這個(gè)豐富的空間中，算法具有不同的數(shù)學(xué)特性和實(shí)用特性。利用這種多樣性，研究人員將AlphaTensor調(diào)整為專門尋找能在一些特定硬件上快速運(yùn)行的算法。用這些算法來(lái)計(jì)算大矩陣相乘的速度比在相同硬件上的常用算法快10-20%，這展示了AlphaTensor在優(yōu)化任意目標(biāo)方面的靈活性。

未來(lái)研究與應(yīng)用

從數(shù)學(xué)的角度來(lái)看，新的結(jié)果可以指導(dǎo)復(fù)雜性理論（旨在確定解決計(jì)算問(wèn)題的最快算法）的進(jìn)一步研究?？梢哉f(shuō)，AlphaTensor提升了我們對(duì)矩陣乘法算法的豐富性的理解，而這種理解或許會(huì)為我們帶來(lái)新的驚喜，比如幫助我們確定計(jì)算機(jī)科學(xué)中最基本的開(kāi)放問(wèn)題之一——矩陣乘法的漸近復(fù)雜性。

正如前文所提到的，矩陣乘法是計(jì)算機(jī)圖形學(xué)、數(shù)字通信、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和科學(xué)計(jì)算等許多計(jì)算任務(wù)的核心組成部分，因此AlphaTenor的發(fā)現(xiàn)可以大大提高這些領(lǐng)域的計(jì)算效率。AlphaTensor在考慮任何類型的目標(biāo)上所擁有的靈活性，也可以激發(fā)設(shè)計(jì)不同算法的新應(yīng)用。

DeepMind團(tuán)隊(duì)也希望，在這次工作的基礎(chǔ)上，未來(lái)能夠有更多的人開(kāi)始應(yīng)用人工智能來(lái)幫助解決數(shù)學(xué)和科學(xué)領(lǐng)域的一些最重要的挑戰(zhàn)。

參考來(lái)源：

https://www./blog/discovering-novel-algorithms-with-alphatensor

https://www./articles/d41586-022-03166-w

https://www./article/2340343-deepmind-ai-finds-new-way-to-multiply-numbers-and-speed-up-computers/

封面圖/首圖：DeepMind