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

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

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

核心運算：矩陣乘法

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

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

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

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

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

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

施特拉森算法

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

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

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

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

一個困難的棋盤游戲

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

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

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

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

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

有效的計算

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

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

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

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

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

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

未來研究與應用

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

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

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