人類反超 AI：DeepMind 用 AI 打破矩陣乘法計(jì)算速度 50 年記錄一周后，數(shù)學(xué)家再次刷新

本文作者：我在思考中

2022-10-20 11:48

導(dǎo)語(yǔ)：站在 AI 的肩膀上，人類走得更遠(yuǎn)。

作者 | 李梅、施方圓

編輯 | 陳彩嫻

10 月 5 日，AlphaTensor 橫空出世，DeepMind 宣布其解決了數(shù)學(xué)領(lǐng)域 50 年來(lái)一個(gè)懸而未決的數(shù)學(xué)算法問題，即矩陣乘法。AlphaTensor 成為首個(gè)用于為矩陣乘法等數(shù)學(xué)問題發(fā)現(xiàn)新穎、高效且可證明正確的算法的 AI 系統(tǒng)。論文《Discovering faster matrix multiplication algorithms with reinforcement learning》也登上了 Nature 封面。

然而，AlphaTensor 的記錄僅保持了一周，便被人類數(shù)學(xué)家打破了。

來(lái)自?shī)W地利林茨約翰·開普勒大學(xué)的研究人員 Manuel Kauers 和 Jakob Moosbauer 在其最新工作中表示，他們已經(jīng)打破 AlphaTensor 的矩陣乘法記錄。他們開發(fā)了一種以 95 步執(zhí)行 5×5 矩陣乘法的方法，比 AlphaTensor 的 96 步記錄少了一步，此前的記錄為 98 步。論文預(yù)印版于 10 月 13 日發(fā)布在 arxiv 上。

人類反超 AI：DeepMind 用 AI 打破矩陣乘法計(jì)算速度 50 年記錄一周后，數(shù)學(xué)家再次刷新

論文地址：https://arxiv.org/abs/2210.04045

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

人類反超 AI：DeepMind 用 AI 打破矩陣乘法計(jì)算速度 50 年記錄一周后，數(shù)學(xué)家再次刷新

數(shù)學(xué)問題的探索永無(wú)止境，如作者所說，DeepMind 算法方案 “still not the end of the story”。不過，他們這次的突破是站在巨人也就是 AI 的肩膀上，作者表示，其解決方案是在 DeepMind 方案的基礎(chǔ)上應(yīng)用一系列的轉(zhuǎn)換，從而消除了一步乘法計(jì)算。

前進(jìn) 2 步的 AlphaTensor

我們先來(lái)簡(jiǎn)要回顧一下 AlphaTensor 的成績(jī)。

計(jì)算機(jī)科學(xué)中許多數(shù)學(xué)任務(wù)都是通過矩陣乘法來(lái)處理的，例如機(jī)器學(xué)習(xí)、計(jì)算機(jī)圖形的創(chuàng)建，各種模擬或數(shù)據(jù)壓縮。而計(jì)算機(jī)計(jì)算乘法的速度要遠(yuǎn)遠(yuǎn)慢于加法，因此，即使矩陣乘法的效率提升得很小，也會(huì)產(chǎn)生巨大影響，幾十年來(lái)，數(shù)學(xué)家們一直在尋找更有效的矩陣乘法算法。

1969 年，德國(guó)數(shù)學(xué)家 Volker Strassen 開發(fā)了一種算法，首次將 4×4 矩陣乘法的求解從 64 步減少到 49 步，震動(dòng)了數(shù)學(xué)界。

而 Deepmind 這次發(fā)布的 AI 系統(tǒng) AlphaTensor，發(fā)現(xiàn)了一種比 Strassen 算法更快的新算法。Demis Hassabis 稱，新算法具備在每天數(shù)萬(wàn)億次計(jì)算中將效率提高 10% ~ 20% 的潛力。

AlphaTensor 是一次從游戲到數(shù)學(xué)的飛躍，它基于 2018 年 Deepmind 發(fā)布的通用棋盤游戲 AI 系統(tǒng) AlphaZero。為了訓(xùn)練 AlphaTensor，Deepmind 研究團(tuán)隊(duì)將矩陣乘法問題轉(zhuǎn)化成一種 3D 棋盤游戲，每一步都會(huì)產(chǎn)生新算法的構(gòu)建塊。AlphaTensor 每次會(huì)在數(shù)萬(wàn)次移動(dòng)中進(jìn)行選擇，以盡可能少的步驟生成新算法而獲得獎(jiǎng)勵(lì)。Deepmind 將其稱為“張量游戲”。

在 5×5 的輸入矩陣中，AlphaTensor 獨(dú)立發(fā)現(xiàn)了 Strassen 算法和其他已知的算法。并且，它還開發(fā)了比舊算法更有效的新算法。

例如，5×5 矩陣乘法（n=4）以前要計(jì)算 80 步，而 AlphaTensor 新算法只需 76 步；當(dāng)n=5 時(shí)，AlphaTensor 將求解從原來(lái)的 98 步減少到 96 步。4×4 矩陣乘法由 Strassen 減少到 49 步，AlphaTensor 則將其優(yōu)化到 47 步。這樣的效率是由 AlphaTensor 生成的 70 多個(gè)矩陣乘法的算法實(shí)現(xiàn)的。

人類反超 AI：DeepMind 用 AI 打破矩陣乘法計(jì)算速度 50 年記錄一周后，數(shù)學(xué)家再次刷新

圖注：AlphaTensor 發(fā)現(xiàn)的算法復(fù)雜性與已知矩陣乘法算法比較

此外，AlphaTensor 還可開發(fā)特定硬件的算法，用于機(jī)器學(xué)習(xí)。據(jù)說目前運(yùn)行速度比谷歌 TPU 和英偉達(dá) V100 上的算法快 20%。

自主調(diào)整乘法算法以適應(yīng)硬件的方法對(duì)人類來(lái)說很困難，所以 AlphaTensor 對(duì) Strassen 算法的改進(jìn)創(chuàng)造了 4×4 矩陣乘法的新上限，是 AI 進(jìn)步為其他學(xué)科提供助力的一大證明。它也表明，原本為傳統(tǒng)游戲開發(fā)的 AlphaZero 系統(tǒng)可以解決領(lǐng)域之外的數(shù)學(xué)問題。

人類再向前 1 步

在 Manuel Kauers 和 Jakob Moosbauer 的最新研究中，他們主要有兩個(gè)新發(fā)現(xiàn)，一是對(duì)于 4×4 矩陣，他們提出了另一種 47 步乘法的求解算法，但不同于先前的解決方案；二是對(duì)于 5×5 矩陣，他們首次提出了一種需要 95 步乘法的方案。

在這篇文章中，作者簡(jiǎn)單展示了這兩個(gè)矩陣乘法的方案，不久后將發(fā)表正式論文，更詳細(xì)地介紹求解算法的搜索技術(shù)。

4 × 4 矩陣的新方案共包含 47 次乘法，如下：