AlphaTensor bygger på AlphaZero, en agent, der har vist overmenneskelige præstationer på brætspil, såsom skak, Go og shogi, og dette værk viser AlphaZero's rejse fra at spille spil til at tackle uløste matematiske problemer for første gang.
De gamle egyptere skabte en algoritme til at gange to tal uden at kræve en multiplikationstabel, og den græske matematiker Euklid beskrev en algoritme til at beregne den største fælles divisor, som stadig er i brug i dag.
Under den islamiske guldalder designede den persiske matematiker Muhammad ibn Musa al-Khwarizmi nye algoritmer til at løse lineære og kvadratiske ligninger. Faktisk førte al-Khwarizmis navn, oversat til latin som Algoritmi, til udtrykket algoritme. Men på trods af kendskabet til algoritmer i dag – brugt i hele samfundet fra klasseværelsesalgebra til banebrydende videnskabelig forskning – er processen med at opdage nye algoritmer utrolig vanskelig og et eksempel på det menneskelige sinds fantastiske ræsonnement.
De udgav i Nature. AlphaTensor er det første kunstig intelligens (AI) system til at opdage nye, effektive og beviseligt korrekte algoritmer til grundlæggende opgaver såsom matrixmultiplikation. Dette kaster lys over et 50 år gammelt åbent spørgsmål i matematik om at finde den hurtigste måde at gange to matricer på.
Trænet fra bunden opdager AlphaTensor matrixmultiplikationsalgoritmer, der er mere effektive end eksisterende menneske- og computerdesignede algoritmer. På trods af forbedring i forhold til kendte algoritmer, bemærker de, at en begrænsning ved AlphaTensor er behovet for at foruddefinere et sæt potentielle faktorindgange F, som diskretiserer søgerummet, men muligvis kan føre til at gå glip af effektive algoritmer. En interessant retning for fremtidig forskning er at tilpasse AlphaTensor til at søge efter F. En vigtig styrke ved AlphaTensor er dens fleksibilitet til at understøtte komplekse stokastiske og ikke-differentierbare belønninger (fra tensorrangen til praktisk effektivitet på specifik hardware) ud over at finde algoritmer til brugerdefinerede operationer i en bred vifte af rum (såsom begrænsede felter). De mener, at dette vil anspore applikationer af AlphaTensor til at designe algoritmer, der optimerer målinger, som vi ikke overvejede her, såsom numerisk stabilitet eller energiforbrug.
Opdagelsen af matrixmultiplikationsalgoritmer har vidtrækkende implikationer, da matrixmultiplikation er kernen i mange beregningsopgaver, såsom matrixinversion, beregning af determinanten og løsning af lineære systemer.
Processen og fremskridtet med at automatisere algoritmisk opdagelse
Først konverterede de problemet med at finde effektive algoritmer til matrixmultiplikation til et enkeltspillerspil. I dette spil er brættet en tredimensionel tensor (array af tal), der fanger, hvor langt fra korrekt den aktuelle algoritme er. Gennem et sæt tilladte træk, svarende til algoritme-instruktioner, forsøger spilleren at ændre tensoren og nulstille dens indtastninger. Når spilleren formår at gøre det, resulterer dette i en beviseligt korrekt matrixmultiplikationsalgoritme for ethvert par af matricer, og dens effektivitet fanges af antallet af trin, der tages for at nulstille tensoren.
Dette spil er utroligt udfordrende – antallet af mulige algoritmer at overveje er meget større end antallet af atomer i universet, selv for små tilfælde af matrixmultiplikation. Sammenlignet med spillet Go, som forblev en udfordring for AI i årtier, er antallet af mulige træk ved hvert trin i deres spil 30 størrelsesordener større (over 10^33 for en af de indstillinger, de overvejer).
I det væsentlige, for at spille dette spil godt, er man nødt til at identificere de mindste nåle i en gigantisk høstak af muligheder. For at tackle udfordringerne på dette domæne, som væsentligt afviger fra traditionelle spil, udviklede vi flere afgørende komponenter, herunder en ny neural netværksarkitektur, der inkorporerer problemspecifikke induktive skævheder, en procedure til at generere nyttige syntetiske data og en opskrift til at udnytte symmetrierne i problem.
De trænede derefter en AlphaTensor-agent ved at bruge forstærkningslæring til at spille spillet, startende uden nogen viden om eksisterende matrixmultiplikationsalgoritmer. Gennem læring forbedres AlphaTensor gradvist over tid, genopdager historiske hurtige matrixmultiplikationsalgoritmer som Strassens, og til sidst overgår den menneskelige intuitions område og opdager algoritmer hurtigere end tidligere kendt.
Udforskning af indvirkningen på fremtidig forskning og applikationer
Fra et matematisk synspunkt kan deres resultater guide yderligere forskning i kompleksitetsteori, som har til formål at bestemme de hurtigste algoritmer til løsning af beregningsmæssige problemer. Ved at udforske rummet af mulige algoritmer på en mere effektiv måde end tidligere tilgange hjælper AlphaTensor med at fremme vores forståelse af rigdommen af matrixmultiplikationsalgoritmer. At forstå dette rum kan låse op for nye resultater for at hjælpe med at bestemme den asymptotiske kompleksitet af matrixmultiplikation, et af de mest fundamentale åbne problemer inden for datalogi.
Fordi matrixmultiplikation er en kernekomponent i mange beregningsopgaver, der spænder over computergrafik, digital kommunikation, neural netværkstræning og videnskabelig databehandling, kunne AlphaTensor-opdagede algoritmer gøre beregninger på disse områder betydeligt mere effektive. AlphaTensors fleksibilitet til at overveje enhver form for mål kunne også anspore til nye applikationer til at designe algoritmer, der optimerer metrikker såsom energiforbrug og numerisk stabilitet, og hjælper med at forhindre små afrundingsfejl fra snebold, da en algoritme fungerer.
Mens de her fokuserede på det særlige problem med matrixmultiplikation, håber vi, at vores papir vil inspirere andre til at bruge AI til at guide algoritmisk opdagelse til andre grundlæggende beregningsopgaver. Deres forskning viser også, at AlphaZero er en kraftfuld algoritme, der kan udvides langt ud over traditionelle spils domæne for at hjælpe med at løse åbne problemer i matematik. Med udgangspunkt i vores forskning håber de at anspore til et større arbejde – at anvende AI til at hjælpe samfundet med at løse nogle af de vigtigste udfordringer inden for matematik og på tværs af videnskaberne.
Natur – Opdag hurtigere matrixmultiplikationsalgoritmer med forstærkningslæring
Abstrakt
Forbedring af effektiviteten af algoritmer til grundlæggende beregninger kan have en udbredt effekt, da det kan påvirke den samlede hastighed af en stor mængde beregninger. Matrixmultiplikation er en sådan primitiv opgave, der forekommer i mange systemer - fra neurale netværk til videnskabelige computerrutiner. Den automatiske opdagelse af algoritmer ved hjælp af maskinlæring giver mulighed for at nå ud over menneskelig intuition og udkonkurrere de nuværende bedste menneskedesignede algoritmer. At automatisere algoritmeopdagelsesproceduren er imidlertid indviklet, da rummet af mulige algoritmer er enormt. Her rapporterer vi en dyb forstærkende læringstilgang baseret på AlphaZero1 for at opdage effektive og beviseligt korrekte algoritmer til multiplikation af vilkårlige matricer. Vores agent, AlphaTensor, er uddannet til at spille et singleplayer-spil, hvor målet er at finde tensor-nedbrydninger inden for et begrænset faktorrum. AlphaTensor opdagede algoritmer, der overgår den avancerede kompleksitet for mange matrixstørrelser. Særligt relevant er tilfældet med 4 × 4 matricer i et begrænset felt, hvor AlphaTensors algoritme forbedrer Strassens to-niveau algoritme for første gang, så vidt vi ved, siden dens opdagelse for 50 år siden2. Vi viser yderligere fleksibiliteten af AlphaTensor gennem forskellige use-cases: Algoritmer med state-of-the-art kompleksitet til struktureret matrix multiplikation og forbedret praktisk effektivitet ved at optimere matrix multiplikation til runtime på specifik hardware. Vores resultater fremhæver AlphaTensors evne til at accelerere processen med algoritmisk opdagelse af en række problemer og til at optimere til forskellige kriterier.
Brian Wang er en futuristisk tankeleder og en populær Science blogger med 1 million læsere om måneden. Hans blog Nextbigfuture.com er rangeret som #1 Science News Blog. Det dækker mange forstyrrende teknologi og tendenser, herunder rum, robotik, kunstig intelligens, medicin, anti-aging bioteknologi og nanoteknologi.
Han er kendt for at identificere banebrydende teknologier og er i øjeblikket medstifter af en opstart og fundraiser til virksomheder med et højt potentiale på et tidligt stadium. Han er forskningschef for tildelinger til dybe teknologiske investeringer og en engelinvestor hos Space Angels.
Han har været en hyppig foredragsholder i virksomheder og har været TEDx -højttaler, en Singularity University -højttaler og gæst ved adskillige interviews til radio og podcasts. Han er åben for offentlige taler og rådgivende engagementer.
