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

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

在一篇于近期發(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è)看似簡單的數(shù)學(xué)運(yùn)算，對(duì)當(dāng)代數(shù)字世界有著巨大的影響。

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

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

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

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

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

施特拉森算法

這種算法被稱為施特拉森算法，這種算法需要進(jìn)行多一些的加法，但這是可以接受的，因?yàn)?a class="external" href="http://m.hddsmy.com/tag/jisuanji" title="查看與 計(jì)算機(jī) 相關(guān)的文章" target="_blank">計(jì)算機(jī)在計(jì)算加法時(shí)要比計(jì)算乘法快得多。

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

在施特拉森做出突破后，數(shù)學(xué)家又進(jìn)行了幾十年的研究，盡管發(fā)現(xiàn)了一些不適用于計(jì)算機(jī)代碼的微小改進(jìn)，但對(duì)更大的矩陣來說問題仍然沒有得到解決——在某種程度上，他們甚至不知道用這種方法計(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è)困難的棋盤游戲

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

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

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

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

由 AlphaTensor 進(jì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)算；而用在此之前的最佳算法來計(jì)算，這個(gè)數(shù)字可以減少到 80 次；現(xiàn)在，AlphaTensor 發(fā)現(xiàn)的算法只需 76 次乘法就能完成運(yùn)算。

總的來說，AlphaTensor 在超過 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)以來迎來的首個(gè)改進(jìn)。這些用于小矩陣相乘的算法，可作為用來乘任意大小的更大矩陣的原語。

另外，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)測試，然后反饋給 AlphaTensor，以便在目標(biāo)硬件上學(xué)習(xí)更高效的算法。（圖 /DeepMind）

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

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

從數(shù)學(xué)的角度來看，新的結(jié)果可以指導(dǎo)復(fù)雜性理論（旨在確定解決計(jì)算問題的最快算法）的進(jìn)一步研究。可以說，AlphaTensor 提升了我們對(duì)矩陣乘法算法的豐富性的理解，而這種理解或許會(huì)為我們帶來新的驚喜，比如幫助我們確定計(jì)算機(jī)科學(xué)中最基本的開放問題之一——矩陣乘法的漸近復(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ǔ)上，未來能夠有更多的人開始應(yīng)用人工智能來幫助解決數(shù)學(xué)和科學(xué)領(lǐng)域的一些最重要的挑戰(zhàn)。