今天發(fā)表在《Nature》(《自然》)雜志上的論文中,DeepMind提出了AlphaTensor,這是第一個用于發(fā)現(xiàn)新的、高效的、可證明正確的矩陣乘法等基本任務算法的人工智能(AI)系統(tǒng)。這揭示了數(shù)學中一個長達50年的開放性問題,即尋找兩個矩陣相乘的最快方法。
矩陣相乘的重要性 AlphaTensor如何找到更快的矩陣運算方法 AlphaTensor的開源實現(xiàn)和使用使用方法 矩陣相乘的重要性
矩陣相乘是當今深度學習算法的基礎運算之一。盡管高中時期可能就已經(jīng)有了教學,但是它對于當今數(shù)字世界有著巨大的影響力。
兩個矩陣相乘這一操作被用于處理智能手機上的圖像,識別語音命令,為計算機游戲生成圖形,運行模擬以預測天氣,壓縮數(shù)據(jù)和視頻以在互聯(lián)網(wǎng)上共享,以及其他更多的操作。世界各地的公司花費了大量的時間和金錢來開發(fā)計算硬件,以有效地進行矩陣乘法。因此,即使是對矩陣乘法效率的微小改進也會產(chǎn)生廣泛的影響。
這篇論文是DeepMind推動科學發(fā)展和利用人工智能解開最基本問題的使命中的一塊踏腳石。AlphaTensor建立在AlphaZero的基礎上,AlphaZero是一個在國際象棋、圍棋和象棋等棋類游戲上表現(xiàn)出超人表現(xiàn)的代理,這項工作展示了AlphaZero從玩游戲到首次解決未解決的數(shù)學問題的過程。
幾個世紀以來,數(shù)學家們認為,標準的矩陣乘法算法是人們在效率方面所能達到的最佳狀態(tài)。但在1969年,德國數(shù)學家Volken Strassen(沃爾肯-斯特林)震驚了數(shù)學界,他表明確實存在更好的算法。
下圖是Volken Strassen的算法示例。
通過研究非常小的矩陣(大小為2x2),他發(fā)現(xiàn)了一種巧妙的方法來組合矩陣的條目,從而產(chǎn)生一種更快的算法。盡管經(jīng)過幾十年的研究,這個問題的更大版本仍然沒有得到解決—以至于人們不知道如何有效地將兩個小到3x3的矩陣相乘。
在我們的論文中,我們探討了現(xiàn)代人工智能技術(shù)如何推進新矩陣乘法算法的自動發(fā)現(xiàn)。在人類直覺進步的基礎上,AlphaTensor發(fā)現(xiàn)了在許多矩陣大小上比現(xiàn)有技術(shù)水平更有效的算法。我們的人工智能設計的算法優(yōu)于人類設計的算法,這是在算法發(fā)現(xiàn)領域的一個重大進步。
AlphaTensor如何找到更快的矩陣運算方法
首先,我們將尋找高效的矩陣乘法算法的問題轉(zhuǎn)化為一個單人游戲。在這個游戲中,棋盤是一個三維張量(數(shù)字陣列),記錄了當前算法離正確的程度。通過一組與算法指令相對應的允許移動,玩家試圖修改張量并將其條目清零。當玩家成功做到這一點時,對于任何一對矩陣來說,都會產(chǎn)生一個可證明正確的矩陣乘法算法,而其效率則由將張量清零所需的步驟數(shù)來體現(xiàn)。
這個游戲具有難以置信的挑戰(zhàn)性—要考慮的可能算法的數(shù)量遠遠大于宇宙中的原子數(shù)量,即使是矩陣乘法的小案例。與幾十年來一直是人工智能挑戰(zhàn)的圍棋游戲相比,我們的游戲每一步可能的動作數(shù)量要大30個數(shù)量級(對于我們考慮的一個設置,超過1033個)。
從本質(zhì)上講,要玩好這個游戲,需要在巨大的干草堆中找出最微小的針。為了應對這個明顯不同于傳統(tǒng)游戲的領域的挑戰(zhàn),我們開發(fā)了多個關(guān)鍵組件,包括一個新的神經(jīng)網(wǎng)絡架構(gòu),其中包括特定問題的歸納偏見,一個生成有用的合成數(shù)據(jù)的程序,以及一個利用問題的對稱性的配方。
然后,我們利用強化學習訓練了一個AlphaTensor代理來玩游戲,開始時沒有任何關(guān)于現(xiàn)有矩陣乘法算法的知識。通過學習,AlphaTensor隨著時間的推移逐漸改進,重新發(fā)現(xiàn)了歷史上的快速矩陣乘法算法,如Strassen的算法,最終超越了人類的直覺領域,發(fā)現(xiàn)的算法比以前已知的更快。
例如,如果學校教授的傳統(tǒng)算法是用100次乘法對一個4x5乘以5x5的矩陣進行乘法,而這個數(shù)字在人類的聰明才智下被減少到80次,AlphaTensor已經(jīng)找到了只用76次乘法就能完成相同操作的算法。
除了這個例子,AlphaTensor的算法自50年前發(fā)現(xiàn)以來,首次在有限域中改進了Strassen的兩級算法。這些小矩陣的乘法算法可以作為基元用于任意大小的大得多的矩陣的乘法。
此外,AlphaTensor還發(fā)現(xiàn)了一組具有最先進復雜度的多樣化算法—每種大小的矩陣乘法算法多達數(shù)千種,表明矩陣乘法算法的空間比以前想象的要豐富。
在這個豐富的空間中的算法具有不同的數(shù)學和實踐屬性。利用這種多樣性,我們對AlphaTensor進行了調(diào)整,專門尋找在特定硬件上速度快的算法,如Nvidia V100 GPU,以及谷歌TPU v2。 這些算法在相同硬件上比常用的算法快10-20%,這展示了AlphaTensor在優(yōu)化任意目標方面的靈活性。
AlphaTensor的開源實現(xiàn)和使用
目前,谷歌已經(jīng)在GitHub上貢獻了AlphaTensor,它包含4個方向:
algorithms包含AlphaTensor發(fā)現(xiàn)的算法,表示為矩陣乘法張量的因式分解,以及一個顯示如何加載這些算法的Colab。 benchmarking包含一個腳本,可以用來測量矩陣乘法算法在NVIDIA V100 GPU上的實際速度。 nonequivalence包含了AlphaTensor為同一個矩陣乘法問題(4x4矩陣相乘)所發(fā)現(xiàn)的14236種不對等的算法,以及一個驗證其不對等性的Colab。 recombination包含了我們用來分解較大的矩陣乘法張量的代碼,通過重新組合較小的矩陣乘法張量的因子。
具體的論文詳情和代碼詳情,請參考:DeepMind最新研究研究AlphaTensor發(fā)布——可以快速求解矩陣相乘的AI算法 | 數(shù)據(jù)學習者官方網(wǎng)站(Datalearner)
訪談
更多做行業(yè)賦能者 HID迎接數(shù)字化浪潮新機遇 破解新挑戰(zhàn)
今年3月份,全球可信身份解決方案提供商HID發(fā)布了最新的《安防行業(yè)現(xiàn)狀報告》(以下簡稱“報告”),該報告…
數(shù)字化浪潮下,安防廠商如何滿足行業(yè)客戶的定制化需求?
回顧近兩年,受疫情因素影響,包括安防在內(nèi)的諸多行業(yè)領域都遭受了來自市場 “不確定性”因素的沖擊,市場…
博思高鄧紹昌:乘產(chǎn)品創(chuàng)新及客戶服務之舟,在市場變革中逆風飛揚
11月24日,由慧聰物聯(lián)網(wǎng)、慧聰安防網(wǎng)、慧聰電子網(wǎng)主辦的2022(第十九屆)中國物聯(lián)網(wǎng)產(chǎn)業(yè)大會暨品牌盛會,在深…