人類反超 AI：DeepMind 用 AI 打破矩陣乘法計算速度 50 年記錄一週後，數學家再次重新整理

作者 | 李梅、施方圓

編輯 | 陳彩嫻

10 月 5 日，AlphaTensor 橫空出世，DeepMind 宣佈其解決了數學領域 50 年來一個懸而未決的數學演算法問題，即矩陣乘法。AlphaTensor 成為首個用於為矩陣乘法等數學問題發現新穎、高效且可證明正確的演算法的 AI 系統。論文《Discovering faster matrix multiplication algorithms with reinforcement learning》也登上了 Nature 封面。

然而，AlphaTensor 的記錄僅保持了一週，便被人類數學家打破了。

來自奧地利林茨約翰·開普勒大學的研究人員 Manuel Kauers 和 Jakob Moosbauer 在其最新工作中表示，他們已經打破 AlphaTensor 的矩陣乘法記錄。他們開發了一種

以 95 步執行 5×5 矩陣乘法

的方法，比 AlphaTensor 的 96 步記錄少了一步，此前的記錄為 98 步。論文預印版於 10 月 13 日釋出在 arxiv 上。

論文地址：https：//arxiv。org/abs/2210。04045

論文標題中的 “FBHHRBNRSSSHK”其實就是 DeepMind 論文所有作者姓氏的首字母組合，這種命名方式也是很有趣了：

數學問題的探索永無止境，如作者所說，DeepMind 演算法方案 “still not the end of the story”。不過，他們這次的突破是站在巨人也就是 AI 的肩膀上，作者表示，其解決方案是

在 DeepMind 方案的基礎上

應用一系列的轉換，從而消除了一步乘法計算。

前進 2 步的 AlphaTensor

我們先來簡要回顧一下 AlphaTensor 的成績。

計算機科學中許多數學任務都是透過矩陣乘法來處理的，例如機器學習、計算機圖形的建立，各種模擬或資料壓縮。而計算機計算乘法的速度要遠遠慢於加法，因此，即使矩陣乘法的效率提升得很小，也會產生巨大影響，幾十年來，數學家們一直在尋找更有效的矩陣乘法演算法。

1969 年，德國數學家 Volker Strassen 開發了一種演算法，首次將 4×4 矩陣乘法的求解從 64 步減少到 49 步，震動了數學界。

而 Deepmind 這次釋出的 AI 系統 AlphaTensor，發現了一種比 Strassen 演算法更快的新演算法。Demis Hassabis 稱，新演算法具備在每天數萬億次計算中將效率提高 10% ~ 20% 的潛力。

AlphaTensor 是一次從遊戲到數學的飛躍，它基於 2018 年 Deepmind 釋出的通用棋盤遊戲 AI 系統 AlphaZero。為了訓練 AlphaTensor，Deepmind 研究團隊將矩陣乘法問題轉化成一種 3D 棋盤遊戲，每一步都會產生新演算法的構建塊。AlphaTensor 每次會在數萬次移動中進行選擇，以儘可能少的步驟生成新演算法而獲得獎勵。Deepmind 將其稱為“張量遊戲”。

在 5×5 的輸入矩陣中，AlphaTensor 獨立發現了 Strassen 演算法和其他已知的演算法。並且，它還開發了比舊演算法更有效的新演算法。

例如，5×5 矩陣乘法（n=4）以前要計算 80 步，而 AlphaTensor 新演算法只需 76 步；當n=5 時，AlphaTensor 將求解從原來的 98 步減少到 96 步。4×4 矩陣乘法由 Strassen 減少到 49 步，AlphaTensor 則將其最佳化到 47 步。這樣的效率是由 AlphaTensor 生成的 70 多個矩陣乘法的演算法實現的。