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

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

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

核心運算：矩陣乘法

矩陣乘法是我們非常熟悉，也是代數(shù)中最基本的運算之一。這個看似簡單的數(shù)學運算，對當代數(shù)字世界有著巨大的影響。

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

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

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

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

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

施特拉森算法

這種算法被稱為施特拉森算法，這種算法需要進行多一些的加法，但這是可以接受的，因為計算機在計算加法時要比計算乘法快得多。

標準算法與施特拉森算法的對比：當兩個 2×2 的矩陣相乘時，標準算法需要經(jīng)過 8 次乘法運算，而施特拉森算法只需要進行 7 次乘法運算。對整體效率來說，乘法的影響比加法更大。（圖 /DeepMind）

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

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

一個困難的棋盤游戲

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

玩家的目標是，通過允許的移動來修改張量，從而用最少的步驟讓張量中的所有數(shù)字都歸零。這是一項極具挑戰(zhàn)性的游戲，因為每一步都可能需要從萬億步棋中進行選擇。兩個矩陣相乘的方法比宇宙中原子數(shù)量還要多。在一些例子中，這個游戲每一步可能的走法數(shù)量，是 10 的 33 次方（10³³）。

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

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

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

有效的計算

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

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

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

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

AlphaTensor 具有一個對應于算法的運行時間的目標。當 AlphaTensor 發(fā)現(xiàn)正確的矩陣乘法算法時，就會在目標硬件上對其進行基準測試，然后反饋給 AlphaTensor，以便在目標硬件上學習更高效的算法。（圖 /DeepMind）

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

未來研究與應用

從數(shù)學的角度來看，新的結果可以指導復雜性理論（旨在確定解決計算問題的最快算法）的進一步研究。可以說，AlphaTensor 提升了我們對矩陣乘法算法的豐富性的理解，而這種理解或許會為我們帶來新的驚喜，比如幫助我們確定計算機科學中最基本的開放問題之一——矩陣乘法的漸近復雜性。

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

DeepMind 團隊也希望，在這次工作的基礎上，未來能夠有更多的人開始應用人工智能來幫助解決數(shù)學和科學領域的一些最重要的挑戰(zhàn)。