AlphaTensor temelji na AlphaZero, agentu, ki je pokazal nadčloveško zmogljivost pri družabnih igrah, kot so šah, Go in shogi, in to delo prikazuje pot AlphaZero od igranja iger do prvega reševanja nerešenih matematičnih problemov.
Stari Egipčani so ustvarili algoritem za množenje dveh števil brez potrebe po množilni tabeli, grški matematik Evklid pa je opisal algoritem za izračun največjega skupnega delitelja, ki je v uporabi še danes.
Med islamsko zlato dobo je perzijski matematik Muhammad ibn Musa al-Khwarizmi oblikoval nove algoritme za reševanje linearnih in kvadratnih enačb. Pravzaprav je al-Khwarizmijevo ime, prevedeno v latinščino kot Algoritmi, vodilo do izraza algoritem. Toda kljub današnjemu poznavanju algoritmov – ki se uporabljajo v vsej družbi od algebre v razredu do vrhunskih znanstvenih raziskav – je proces odkrivanja novih algoritmov neverjetno težak in je primer neverjetnih sposobnosti sklepanja človeškega uma.
Objavili so v Nature. AlphaTensor je prvi sistem umetne inteligence (AI) za odkrivanje novih, učinkovitih in dokazljivo pravilnih algoritmov za temeljne naloge, kot je množenje matrik. To osvetljuje 50 let staro odprto vprašanje v matematiki o iskanju najhitrejšega načina za množenje dveh matrik.
Izurjen iz nič, AlphaTensor odkrije algoritme množenja matrik, ki so učinkovitejši od obstoječih človeških in računalniško zasnovanih algoritmov. Kljub izboljšanju v primerjavi z znanimi algoritmi ugotavljajo, da je omejitev AlphaTensorja potreba po vnaprejšnji določitvi nabora možnih faktorskih vnosov F, ki diskretizira iskalni prostor, vendar lahko vodi do izgube učinkovitih algoritmov. Zanimiva usmeritev za prihodnje raziskave je prilagoditev AlphaTensorja za iskanje F. Ena od pomembnih prednosti AlphaTensorja je njegova prilagodljivost pri podpiranju kompleksnih stohastičnih in nediferencialnih nagrad (od ranga tenzorja do praktične učinkovitosti na specifični strojni opremi) poleg iskanja algoritmov za operacije po meri v najrazličnejših prostorih (kot so končna polja). Menijo, da bo to spodbudilo aplikacije AlphaTensorja k oblikovanju algoritmov, ki optimizirajo meritve, ki jih tukaj nismo upoštevali, kot sta numerična stabilnost ali poraba energije.
Odkritje algoritmov za množenje matrik ima daljnosežne posledice, saj je množenje matrik v središču številnih računalniških nalog, kot je inverzija matrike, računanje determinante in reševanje linearnih sistemov.
Postopek in napredek avtomatizacije algoritemskega odkrivanja
Najprej so problem iskanja učinkovitih algoritmov za množenje matrik pretvorili v igro za enega igralca. V tej igri je tabla tridimenzionalni tenzor (niz števil), ki zajame, kako daleč od pravilnega je trenutni algoritem. Z naborom dovoljenih potez, ki ustrezajo navodilom algoritma, poskuša igralec spremeniti tenzor in izničiti njegove vnose. Ko igralec to uspe, ima za posledico dokazano pravilen algoritem množenja matrik za kateri koli par matrik, njegova učinkovitost pa je zajeta s številom korakov, opravljenih za izničenje tenzorja.
Ta igra je neverjetno zahtevna – število možnih algoritmov, ki jih je treba upoštevati, je veliko večje od števila atomov v vesolju, tudi za majhne primere množenja matrik. V primerjavi z igro Go, ki je desetletja ostajala izziv za AI, je število možnih potez na vsakem koraku njihove igre za 30 velikosti večje (nad 10^33 za eno od nastavitev, ki jih upoštevajo).
V bistvu je treba za dobro igranje te igre identificirati najmanjše iglice v ogromnem kupu sena možnosti. Da bi se spopadli z izzivi tega področja, ki se bistveno razlikuje od tradicionalnih iger, smo razvili več ključnih komponent, vključno z novo arhitekturo nevronske mreže, ki vključuje induktivne pristranskosti, specifične za problem, postopek za ustvarjanje uporabnih sintetičnih podatkov in recept za izkoriščanje simetrije problem.
Nato so za igranje igre usposobili agenta AlphaTensor z uporabo ojačevalnega učenja, pri čemer so začeli brez kakršnega koli znanja o obstoječih algoritmih množenja matrik. Skozi učenje se AlphaTensor sčasoma postopoma izboljšuje, ponovno odkriva zgodovinske hitre algoritme množenja matrik, kot je Strassenov, sčasoma preseže področje človeške intuicije in odkriva algoritme hitreje, kot je bilo znano prej.
Raziskovanje vpliva na prihodnje raziskave in aplikacije
Z matematičnega vidika lahko njihovi rezultati vodijo nadaljnje raziskave v teoriji kompleksnosti, katere cilj je določiti najhitrejše algoritme za reševanje računalniških problemov. Z raziskovanjem prostora možnih algoritmov na učinkovitejši način kot prejšnji pristopi AlphaTensor pomaga izboljšati naše razumevanje bogastva algoritmov za množenje matrik. Razumevanje tega prostora lahko odklene nove rezultate za pomoč pri določanju asimptotične kompleksnosti množenja matrik, enega najbolj temeljnih odprtih problemov v računalništvu.
Ker je množenje matrike osrednja komponenta v številnih računalniških nalogah, ki zajemajo računalniško grafiko, digitalne komunikacije, usposabljanje nevronskih mrež in znanstveno računalništvo, bi lahko algoritmi, ki jih je odkril AlphaTensor, naredili izračune na teh področjih bistveno učinkovitejše. Prilagodljivost AlphaTensorja za upoštevanje kakršnih koli ciljev bi lahko spodbudila tudi nove aplikacije za oblikovanje algoritmov, ki optimizirajo metrike, kot sta poraba energije in numerična stabilnost, kar pomaga preprečiti majhne napake pri zaokroževanju, ki nastanejo med delovanjem algoritma.
Medtem ko so se tukaj osredotočili na poseben problem množenja matrik, upamo, da bo naš članek navdihnil druge pri uporabi umetne inteligence za vodenje algoritemskega odkrivanja za druge temeljne računalniške naloge. Njihova raziskava tudi kaže, da je AlphaZero zmogljiv algoritem, ki ga je mogoče razširiti daleč izven domene tradicionalnih iger in tako pomaga pri reševanju odprtih problemov v matematiki. Na podlagi naše raziskave upajo, da bodo spodbudili večji obseg dela – uporabo umetne inteligence za pomoč družbi pri reševanju nekaterih najpomembnejših izzivov v matematiki in v znanostih.
Narava – Odkrivanje hitrejših algoritmov množenja matrik z učenjem okrepitve
Minimalizem
Izboljšanje učinkovitosti algoritmov za temeljne izračune ima lahko širok vpliv, saj lahko vpliva na splošno hitrost velikega števila izračunov. Množenje matrik je ena takih primitivnih nalog, ki se pojavlja v številnih sistemih – od nevronskih mrež do znanstvenih računalniških rutin. Samodejno odkrivanje algoritmov z uporabo strojnega učenja ponuja možnost, da presežemo človeško intuicijo in presežemo trenutno najboljše algoritme, ki jih je oblikoval človek. Vendar pa je avtomatizacija postopka odkrivanja algoritmov zapletena, saj je prostora možnih algoritmov ogromno. Tukaj poročamo o pristopu učenja z globoko okrepitvijo, ki temelji na AlphaZero1 za odkrivanje učinkovitih in dokazljivo pravilnih algoritmov za množenje poljubnih matrik. Naš agent, AlphaTensor, je usposobljen za igranje igre za enega igralca, kjer je cilj najti tenzorske razgradnje znotraj končnega faktorskega prostora. AlphaTensor je odkril algoritme, ki prekašajo najsodobnejšo kompleksnost za številne velikosti matrik. Posebej pomemben je primer 4 × 4 matrik v končnem polju, kjer AlphaTensorjev algoritem prvič izboljša Strassenov dvonivojski algoritem, kolikor nam je znano, od njegovega odkritja pred 50 leti2. Nadalje prikazujemo prilagodljivost AlphaTensorja skozi različne primere uporabe: algoritme z najsodobnejšo kompleksnostjo za strukturirano množenje matrik in izboljšano praktično učinkovitost z optimizacijo množenja matrik za čas izvajanja na specifični strojni opremi. Naši rezultati poudarjajo sposobnost AlphaTensorja, da pospeši proces algoritemskega odkrivanja vrste problemov in optimizira za različna merila.
Brian Wang je vodja futurističnih misli in priljubljen znanstveni bloger z 1 milijonom bralcev na mesec. Njegov blog Nextbigfuture.com je na prvem mestu na spletnem mestu Science News Blog. Zajema številne moteče tehnologije in trende, vključno z vesoljem, robotiko, umetno inteligenco, medicino, biotehnologijo proti staranju in nanotehnologijo.
Znan po prepoznavanju najsodobnejših tehnologij, je trenutno soustanovitelj zagona in zbiranja sredstev za velika potencialna podjetja v zgodnji fazi. Je vodja raziskav za dodelitve za globoke tehnološke naložbe in investitor angelov pri Space Angels.
Pogost govornik v korporacijah, bil je govornik TEDx, govornik univerze Singularity in gost številnih intervjujev za radio in podcaste. Odprt je za javno nastopanje in svetovanje.
