铁拳浪子的不归路

<随心_句子c><随心_句子c><随心_句子c><随心_句子c><随心_句子c>DeepMind攻(gong)克(ke)50年(nian)數(shu)學(xue)難(nan)題(ti)！AlphaZero史(shi)上(shang)最(zui)快(kuai)矩(ju)陣(zhen)乘(cheng)法(fa)算(suan)法登(deng)Nature封(feng)面(mian)

新(xin)智(zhi)元(yuan)報(bao)道(dao)

編(bian)輯(ji)：David Joey

【新智元導(dao)讀(du)】DeepMind 碾(nian)壓(ya)人(ren)類(lei)高(gao)手(shou)的(de)AI圍(wei)棋(qi)大(da)師(shi)AlphaZero，下(xia)壹(yi)個(ge)目(mu)標(biao)是(shi)数学算法！現(xian)已(yi)發(fa)现50年以(yi)來(lai)最快的矩阵乘法算法。

下围棋碾压人类的AlphaZero，開(kai)始(shi)搞(gao)数学算法了(le)，先(xian)從(cong)矩阵乘法开始！

在(zai)昨(zuo)天(tian)DeepMind團(tuan)隊(dui)发表(biao)在Nature上的論(lun)文(wen)中(zhong)，介(jie)紹(shao)了 AlphaTensor，這(zhe)是第(di)一个用(yong)於(yu)為(wei)矩阵乘法等(deng)基(ji)本(ben)計(ji)算任(ren)務(wu)发现新穎(ying)、高效(xiao)、正(zheng)確(que)算法的AI系(xi)統(tong)。

论文鏈(lian)接(jie)：

https://www.nature.com/articles/s41586-022-05172-4.pdf

AlphaTensor为一个 50 年来的懸(xuan)而(er)未(wei)決(jue)的数学問(wen)题找(zhao)到(dao)了新答(da)案(an)：找到兩(liang)个矩阵相(xiang)乘的最快方(fang)法。

先看(kan)看这研(yan)究(jiu)都(dou)說(shuo)的啥(sha)。

提(ti)高基礎(chu)计算算法的效率(lv)一直(zhi)都是学界(jie)熱(re)點(dian)，因(yin)为它(ta)會(hui)影(ying)響(xiang)大量(liang)计算的整(zheng)體(ti)速(su)度(du)，从而對(dui)智能(neng)计算領(ling)域(yu)產(chan)生(sheng)多(duo)米(mi)諾(nuo)骨(gu)牌(pai)式(shi)的效應(ying)。

上一張(zhang)圖(tu)，来看看AlphaTensor有(you)多「能幹(gan)」。

图a,b为AlphaTensor发现的算法在GPU (a) 和(he) TPU (b)上的加(jia)速百(bai)分(fen)比(bi)表现，針(zhen)对大小(xiao)为 8,192?×?8,192的矩阵乘法進(jin)行(xing)了優(you)化(hua)

矩阵乘法就(jiu)是这樣(yang)一項(xiang)原(yuan)始任务，从神(shen)經(jing)網(wang)絡(luo)到科(ke)学计算程(cheng)序(xu)，它都是不(bu)可(ke)或(huo)缺(que)的部(bu)分。

然(ran)而，算法发现過(guo)程的自(zi)動(dong)化是復(fu)雜(za)的，因为可能的算法空(kong)間(jian)是巨(ju)大的。

DeepMind这次(ci)发布(bu)了一種(zhong)基于AlphaZero的深(shen)度強(qiang)化学習(xi)方法，用于发现任意(yi)矩阵乘法的有效且(qie)可證(zheng)明(ming)正确的算法。

这个算法空间包(bao)含(han)标準(zhun)矩阵乘法算法和遞(di)歸(gui)算法。

DeepMind將(jiang)矩阵乘法算法发现过程（即(ji)张量分解(jie)问题）制(zhi)定(ding)为一个單(dan)人遊(you)戲(xi)——TensorGame。

AlphaTensor 建(jian)立(li)在 AlphaZero 之(zhi)上，訓(xun)練(lian)了一个神经网络来指(zhi)导規(gui)劃(hua)过程，以搜(sou)索(suo)有效的矩阵乘法算法。

我(wo)們(men)的框(kuang)架(jia)使(shi)用单个智能体来分解各(ge)种大小的矩阵乘法张量，从而产生跨(kua)各种张量的学习分解技(ji)術(shu)的轉(zhuan)移(yi)。为了解决游戏的挑(tiao)戰(zhan)性(xing)，AlphaTensor 使用專(zhuan)門(men)的神经网络架構(gou)，利(li)用问题的对稱(cheng)性並(bing)利用合(he)成(cheng)训练游戏。

AlphaTensor可擴(kuo)展(zhan)到比人工(gong)或組(zu)合搜索所(suo)能達(da)到的算法空间大得(de)多的算法空间。

事(shi)實(shi)上，AlphaTensor 从零(ling)开始发现了許(xu)多可证明正确的矩阵乘法算法，这些(xie)算法在标量乘法的数量方面改(gai)进了现有算法。

結(jie)果(guo)表明，AlphaTensor发现的算法在许多矩阵规模(mo)上都优于最先进的方法。

从围棋到矩阵乘法：AlphaZero「出(chu)圈(quan)」

矩阵乘法，学过線(xian)性代(dai)数的都熟(shu)悉(xi)，作(zuo)为矩阵變(bian)換(huan)的基础運(yun)算之一，矩阵乘法是线性代数的基础工具(ju)，不僅(jin)在数学中有大量应用，在应用数学、物(wu)理(li)学、工程学等领域也(ye)有廣(guang)泛(fan)使用。

作为构成数学算法的基础运算之一，矩阵乘法的应用史長(chang)达数千(qian)年。

早(zao)在古(gu)埃(ai)及(ji)時(shi)代，人们就創(chuang)造(zao)了一种無(wu)需(xu)乘法表的两个数字(zi)相乘的算法，希(xi)臘(la)数学家(jia)歐(ou)幾(ji)裏(li)德(de)描(miao)述(shu)了一种计算最大公(gong)約(yue)数的算法，这种算法至(zhi)今(jin)仍(reng)在使用。

在伊(yi)斯(si)蘭(lan)黃(huang)金(jin)时代，波(bo)斯数学家Muhammad ibn Musa al-Khwarizmi設(she)计了新的算法来解决线性和二(er)次方程。事实上，al-Khwarizmi的名(ming)字被(bei)翻(fan)譯(yi)成拉(la)丁(ding)文为Algoritmi，这就是今天英(ying)文「算法」一詞(ci)的前(qian)身(shen)。

但(dan)是，盡(jin)管(guan)今天人们对算法非(fei)常(chang)熟悉，但是，发现新算法的过程是非常困(kun)难的。

在我们今天发表在《自然》杂誌(zhi)上的论文中，我们介绍了AlphaTensor，这是第一个用于发现新的、高效的、可证明正确的矩阵乘法等基本任务算法的AI系统。这为数学领域一个长达50年的开放(fang)性问题——如(ru)何(he)尋(xun)找两个矩阵相乘的最快方法——給(gei)出了答案。

这是DeepMind推(tui)动科学发展和利用AI解开最基本问题的又(you)一次实踐(jian)。AlphaTensor建立在AlphaZero的基础上，後(hou)者(zhe)是一个在國(guo)際(ji)象(xiang)棋、围棋和象棋等棋类游戏上表现超(chao)出人类的智能体，从下棋，到解决半(ban)个世(shi)紀(ji)以来的数学算法，AlphaZero是如何做(zuo)到的？

打(da)破(po)矩阵乘法50年最快記(ji)錄(lu)

矩阵乘法是代数中最簡(jian)单的操(cao)作之一，通(tong)常在高中数学課(ke)上教(jiao)授(shou)。但在课堂(tang)之外(wai)，这个不起(qi)眼(yan)的数学运算在當(dang)代数字世界有著(zhe)巨大的影响力(li)，在现代计算機(ji)中无處(chu)不在。

3*3矩阵相乘的计算

矩阵乘法被用于处理智能手机上的图像(xiang)，識(shi)別(bie)語(yu)音(yin)命(ming)令(ling)，为计算机游戏生成图形(xing)，运行模擬(ni)以預(yu)測(ce)天氣(qi)，压縮(suo)数據(ju)和視(shi)頻(pin)以在互(hu)聯(lian)网上共(gong)享(xiang)等，应用極(ji)为广泛。

世界各地(di)的公司(si)花(hua)費(fei)了大量的时间和金錢(qian)来开发计算硬(ying)件(jian)，以有效地进行矩阵乘法。因此(ci)，即使是对矩阵乘法效率的微(wei)小改进也会产生广泛的影响。

几个世纪以来，数学家们認(ren)为，标准的矩阵乘法算法是人们在效率方面所能达到的最佳(jia)狀(zhuang)態(tai)。

但在1969年，德国数学家Volken Strassen震(zhen)驚(jing)了数学界，他(ta)表明确实存(cun)在更(geng)好(hao)的算法。

此前的矩阵乘法的标准算法與(yu)Strassen的算法相比，后者在乘2x2矩阵时少(shao)用了一个标量乘法（7次而不是8次）。就整体计算效率而言(yan)，乘法比加法重(zhong)要(yao)得多。

通过研究非常小的矩阵（大小为2x2），他发现了一种巧(qiao)妙(miao)的方法来组合矩阵的條(tiao)目，从而产生一种更快的算法。尽管经过几十(shi)年的研究，这个问题的更大版(ban)本仍然沒(mei)有得到解决--以至于人们不知(zhi)道如何有效地将两个小到3x3的矩阵相乘。

在Nature的新论文中，我们探(tan)討(tao)了现代人工智能技术如何推进新矩阵乘法算法的自动发现。AlphaTensor发现了在许多矩阵大小上比现有技术水(shui)平(ping)更有效的算法。我们的人工智能设计的算法优于人类设计的算法，这是在算法发现领域的一个重大进步(bu)。

AI推动算法发现的自动化

首(shou)先，我们将寻找矩阵乘法的有效算法问题转化为一个单人游戏。在这个游戏中，棋盤(pan)是一个三(san)維(wei)张量（数字阵列(lie)），记录了当前算法離(li)正确的程度。

通过一组与算法指令相对应的允(yun)许移动，玩(wan)家試(shi)图修(xiu)改张量并将其(qi)条目清(qing)零。当玩家成功(gong)做到这一点时，对于任何一对矩阵来说，都会产生一个可证明正确的矩阵乘法算法，而其效率則(ze)由(you)将张量清零所需的步驟(zhou)数来体现。

这个游戏具有令人难以置(zhi)信(xin)的挑战性--要考(kao)慮(lv)的可能算法的数量遠(yuan)远大于宇(yu)宙(zhou)中的原子(zi)数量，即使是对于矩阵乘法的小案例(li)。与几十年来一直是人工智能挑战的围棋游戏相比，我们的游戏每(mei)一步可能的动作数量要大30个数量級(ji)。

从本質(zhi)上講(jiang)，要玩好这个游戏，相当于要在「巨大的干草(cao)堆(dui)中找出最小的那(na)根(gen)针」。

为了应对这个明顯(xian)不同(tong)于傳(chuan)统游戏的领域的挑战，我们开发了多个關(guan)鍵(jian)组件，包括(kuo)一个新的神经网络架构，其中包括特(te)定问题的归納(na)偏(pian)見(jian)，一个生成有用的合成数据的程序，以及一个利用问题的对称性的配(pei)方。

然后，我们利用强化学习训练了一个AlphaTensor智能体来玩一个单人游戏（Tensor Game），开始时没有任何关于现有矩阵乘法算法的知识。

AlphaTensor在TensorGame中的目标则是在有限(xian)因子空间內(nei)找到张量分解 (Tensor Decomposition)。

在介绍张量分解之前，我们可能需要先简单地了解一下张量是什(shen)麽(me)，然后再(zai)考虑张量分解有什么用途(tu)。

从初(chu)中到大学，我们接觸(chu)最多的可能只(zhi)是标量（scalar）、向(xiang)量（vector）和矩阵（matrix），而张量则不那么常见，但实际上，标量是第0階(jie)张量，向量是第1阶张量，矩阵是第2阶张量，第3阶或阶数更高的张量被称为高阶张量（higher-order tensor），一般(ban)提到的张量都是特指高阶张量。

我们也知道，在一个矩阵中，某(mou)一元素(su)的位(wei)置可以说成“第几行第几列”的形式，要表达某一元素的位置需要两个索引(yin)构成的组合 ，类似(si)地，在一个第3阶张量里面，表达某一元素的位置需要三个索引构成的组合 。

在处理稀(xi)疏(shu)矩阵和稀疏张量时，用索引来标记元素的位置会帶(dai)来很(hen)多便(bian)利。另(ling)外，阶数的张量可以理解为矩阵的维泛化，在这里，阶数其实就是空间维度（spatial dimension），张量可以被视为多维数组。

张量分解从本质上来说是矩阵分解的高阶泛化。

对矩阵分解有所了解的读者可能知道，矩阵分解有三个很明显的用途，即降(jiang)维处理、缺失(shi)数据填(tian)補(bu)和隱(yin)性关系挖(wa)掘(jue)，而张量分解也能夠(gou)很好地滿(man)足(zu)这些用途。

为了解决TensorGame并找到有效的矩阵乘法算法，我们开发了一个DRL智能体AlphaTensor。

通过学习，AlphaTensor隨(sui)着时间的推移逐(zhu)漸(jian)改进，重新发现了歷(li)史上的快速矩阵乘法算法，如Strassen的算法，最終(zhong)超越(yue)了人类的直覺(jiao)领域，发现的算法比以前已知的更快。

由AlphaTensor玩的单人游戏，目标是找到一个正确的矩阵乘法算法。游戏的状态是一个由数字组成的立方体数组（显示(shi)为灰(hui)色(se)为0，藍(lan)色为1，綠(lv)色为-1），代表着要做的剩(sheng)余(yu)工作。

例如，如果学校(xiao)里教的传统算法是用100次乘法对一个4x5乘以5x5的矩阵进行乘法，而这个数字在人类的聰(cong)明才(cai)智下被減(jian)少到80次，AlphaTensor已经找到了只用76次乘法就能完(wan)成同样操作的算法。

除(chu)此之外，AlphaTensor的算法自50年前发现以来，首次在有限域中改进了Strassen的两级算法。这些小矩阵的乘法算法可以作为基元来乘以任意大小的大得多的矩阵。

此外，AlphaTensor還(hai)发现了一组具有最先进复杂度的多样化算法--每种大小的矩阵乘法算法多达数千种，表明矩阵乘法算法的空间比以前想(xiang)象的要豐(feng)富(fu)。

在这个丰富的空间中的算法具有不同的数学和实践屬(shu)性。利用这种多样性，我们对AlphaTensor进行了調(tiao)整，以专门寻找在特定硬件上速度快的算法，如Nvidia V100 GPU，和谷(gu)歌(ge)TPU v2。

这些算法在相同的硬件上比常用的算法快10-20%，这展示了AlphaTensor在优化任意目标上的靈(ling)活(huo)性。

AlphaTensor的目标是对应于算法的运行时间。当发现一个正确的矩阵乘法算法时，会在目标硬件上进行基准测试，然后反(fan)饋(kui)给AlphaTensor，以便在目标硬件上学习更有效的算法。

未来的研究和应用

从数学的角(jiao)度来看，我们的结果可以指导复杂性理论的进一步研究，其目的是确定解决计算问题的最快算法。

通过以比以前的方法更有效的方式探索可能的算法空间，AlphaTensor有助(zhu)于推进我们对矩阵乘法算法的丰富性的理解。了解这个空间可能会釋(shi)放出新的结果，幫(bang)助确定矩阵乘法的渐进复杂性，这是计算机科学中最基本的开放问题之一。

因为矩阵乘法是许多计算任务的核(he)心(xin)组成部分，涵(han)蓋(gai)了计算机图形、数字通信、神经网络训练和科学计算，AlphaTensor发现的算法可以使这些领域的计算效率大大提升(sheng)。

图为AlphaTensor网络架构

AlphaTensor在考虑任何类型(xing)的目标方面的灵活性也可以刺(ci)激(ji)新的应用，以设计优化能源(yuan)使用和数值(zhi)穩(wen)定性等指标的算法，帮助防(fang)止(zhi)小的四(si)舍(she)五(wu)入(ru)錯(cuo)誤(wu)随着算法的工作而滾(gun)雪(xue)球(qiu)。

雖(sui)然我们在这里集(ji)中讨论了矩阵乘法这一特殊(shu)问题，但我们希望(wang)我们的论文能够啟(qi)发其他人使用人工智能来指导其他基本计算任务的算法发现。

我们的研究还表明，AlphaZero是一个强大的算法，可以远远超出传统游戏的领域，帮助解决数学中的开放问题。

在我们的研究基础上，我们希望能够推动更多的工作--应用人工智能来帮助社(she)会解决数学和整个科学领域的一些最重要的挑战。

參(can)考資(zi)料(liao)：

https://www.nature.com/articles/s41586-022-05172-4

https://www.newscientist.com/article/2340343-deepmind-ai-finds-new-way-to-multiply-numbers-and-speed-up-computers/返(fan)回(hui)搜狐(hu)，查(zha)看更多

責(ze)任编辑：