DeepMind 將矩陣乘法化為單人遊戲，打破維持 50 年的紀錄

Ars Technica 於 2022 年 10 月報導，DeepMind 找到了更有效率的矩陣乘法方式，打破了一項維持 50 年的紀錄。1969 年，Volker Strassen 找到一種演算法，能以 49 次乘法、而非課堂教法所需的 64 次乘法，計算兩個 4x4 矩陣的乘積。DeepMind 使用名為 AlphaTensor 的神經網路，找到以 47 步完成的方法，並發表於《Nature》。

DeepMind 把這個問題設計成一場單人遊戲。「棋盤」是一個三維張量，用來表示目前演算法距離正確答案還有多遠；允許的動作對應演算法指令，玩家試圖把張量的各項歸零。做到這一點，就能得到一個可證明對任意一對矩陣都正確的演算法，而效率則由步數多寡來體現。AlphaTensor 像 AlphaGo 一樣透過強化學習訓練，據 DeepMind 所述，它先重新發現了 Strassen 的成果與其他數學家的工作，然後超越他們。

對於 5x5 矩陣，AlphaTensor 找到 96 步的方法，而較舊的方法需要 98 步。一週後，林茨約翰尼斯克卜勒大學的 Manuel Kauers 與 Jakob Moosbauer 報告了 95 步的方法，並寫道他們的解法是從 DeepMind 的方案經過一連串轉換、消去一次乘法而得到。Ars 指出，矩陣乘法是語音與影像辨識及圖形處理的基礎，每天有數兆次這類計算在 GPU 上執行，因此微小的節省也能積少成多。

把尋找更快矩陣演算法的過程，重新表述為在張量上進行的單人遊戲，讓會玩遊戲的 AI 能發現可證明正確的演算法。

正確的演算法就是一個被歸零的張量，因此正確性已內建於遊戲規則之中。

所用的步數是乾淨俐落的評分，因此 AI 能學習哪些動作會導向更短的演算法。

矩陣乘法用途極為廣泛，因此即使在 GPU 規模下，從 49 步降到 47 步也有影響。

公布所發現的方案，讓人類研究者在短短一週內就能在此基礎上繼續推進。

如果一個研究問題能被框構成有明確評分的遊戲，會玩遊戲的 AI 就能對其進行搜尋，而其結果也能成為人類進一步改良的起點。

在 DeepMind 公布後一週，兩位奧地利研究者以 DeepMind 的成果為基礎，宣稱找到了 5x5 矩陣的 95 次乘法方案。Ars 推測，既然 AI 現在已能搜尋新演算法，其他長久未破的數學紀錄可能很快就會被打破。