Første utvidelse av AlphaZero til matematikk åpner for nye muligheter for forskning

Algoritmer har hjulpet matematikere med å utføre grunnleggende operasjoner i tusenvis av år. De gamle egypterne skapte en algoritme for å multiplisere to tall uten å kreve en multiplikasjonstabell, og den greske matematikeren Euclid beskrev en algoritme for å beregne den største felles divisoren, som fortsatt er i bruk i dag. 

Under den islamske gullalderen, persisk matematiker Muhammad ibn Musa al-Khwarizmi utviklet nye algoritmer for å løse lineære og kvadratiske ligninger. Faktisk, al-Khwarizmis navn, oversatt til latin som Algoritmer, førte til begrepet algoritme. Men til tross for kjennskap til algoritmer i dag – brukt i hele samfunnet fra klasseromsalgebra til banebrytende vitenskapelig forskning – er prosessen med å oppdage nye algoritmer utrolig vanskelig, og et eksempel på menneskesinnets fantastiske resonneringsevner. 

I vår papir, publisert i dag i Nature, vi introduserer AlphaTensor, det første kunstig intelligens (AI) systemet for å oppdage nye, effektive og beviselig riktige algoritmer for grunnleggende oppgaver som matrisemultiplikasjon. Dette kaster lys over et 50 år gammelt åpent spørsmål i matematikk om å finne den raskeste måten å multiplisere to matriser på.

Denne artikkelen er et springbrett i DeepMinds oppdrag for å fremme vitenskapen og låse opp de mest grunnleggende problemene ved bruk av AI. Systemet vårt, AlphaTensor, bygger på AlphaZero, en agent som har vist overmenneskelige prestasjoner på brettspill, som sjakk, Go og shogi, og dette verket viser reisen til AlphaZero fra å spille spill til å takle uløste matematiske problemer for første gang. 

Matriksmultiplikasjon

Matrisemultiplikasjon er en av de enkleste operasjonene i algebra, vanligvis undervist i matematikktimer på videregående skole. Men utenfor klasserommet har denne ydmyke matematiske operasjonen enorm innflytelse i den moderne digitale verdenen og er allestedsnærværende i moderne databehandling. 

Denne operasjonen brukes til å behandle bilder på smarttelefoner, gjenkjenne talekommandoer, generere grafikk for dataspill, kjøre simuleringer for å forutsi været, komprimere data og videoer for deling på internett og mye mer. Bedrifter over hele verden bruker store mengder tid og penger på å utvikle datamaskinvare for å effektivt multiplisere matriser. Så selv mindre forbedringer av effektiviteten til matrisemultiplikasjon kan ha en utbredt innvirkning.

I århundrer trodde matematikere at standardmatrisemultiplikasjonsalgoritmen var den beste man kunne oppnå med tanke på effektivitet. Men i 1969, den tyske matematikeren Volken Strassen sjokkerte det matematiske miljøet ved å vise at det finnes bedre algoritmer.

Gjennom å studere veldig små matriser (størrelse 2×2), oppdaget han en genial måte å kombinere oppføringene til matrisene for å gi en raskere algoritme. Til tross for flere tiår med forskning etter Strassens gjennombrudd, har større versjoner av dette problemet forblitt uløst – i den grad det ikke er kjent hvor effektivt det er mulig å multiplisere to matriser som er så små som 3×3. 

I artikkelen vår undersøkte vi hvordan moderne AI-teknikker kan fremme den automatiske oppdagelsen av nye matrisemultiplikasjonsalgoritmer. Med utgangspunkt i utviklingen av menneskelig intuisjon, oppdaget AlphaTensor algoritmer som er mer effektive enn den nyeste teknologien for mange matrisestørrelser. Våre AI-designede algoritmer utkonkurrerer de menneskeskapte, noe som er et stort skritt fremover innen algoritmisk oppdagelse. 

Prosessen og fremdriften for å automatisere algoritmisk oppdagelse

Først konverterte vi problemet med å finne effektive algoritmer for matrisemultiplikasjon til et enkeltspillerspill. I dette spillet er brettet en tredimensjonal tensor (array av tall), som fanger opp hvor langt fra riktig den gjeldende algoritmen er. Gjennom et sett med tillatte trekk, tilsvarende algoritmeinstruksjoner, prøver spilleren å modifisere tensoren og nullstille oppføringene. Når spilleren klarer å gjøre det, resulterer dette i en beviselig korrekt matrisemultiplikasjonsalgoritme for et hvilket som helst matrisepar, og effektiviteten fanges opp av antall trinn som tas for å nullstille tensoren.

Dette spillet er utrolig utfordrende – antallet mulige algoritmer å vurdere er mye større enn antallet atomer i universet, selv for små tilfeller av matrisemultiplikasjon. Sammenlignet med spillet Go, som gjensto en utfordring for AI i flere tiår, antall mulige trekk ved hvert trinn i spillet vårt er 30 størrelsesordener større (over 10³³ for en av innstillingene vi vurderer).

I hovedsak, for å spille dette spillet godt, må man identifisere de minste nålene i en gigantisk høystakk av muligheter. For å takle utfordringene til dette domenet, som i betydelig grad avviker fra tradisjonelle spill, utviklet vi flere viktige komponenter, inkludert en ny nevrale nettverksarkitektur som inkluderer problemspesifikke induktive skjevheter, en prosedyre for å generere nyttige syntetiske data, og en oppskrift for å utnytte symmetriene til problem.

Vi trente deretter en AlphaTensor-agent ved å bruke forsterkningslæring for å spille spillet, og startet uten kunnskap om eksisterende matrisemultiplikasjonsalgoritmer. Gjennom læring forbedrer AlphaTensor seg gradvis over tid, gjenoppdager historiske raske matrisemultiplikasjonsalgoritmer som Strassens, og overgår til slutt riket av menneskelig intuisjon og oppdager algoritmer raskere enn tidligere kjent.

For eksempel, hvis den tradisjonelle algoritmen som læres på skolen multipliserer en 4×5 med 5×5 matrise ved å bruke 100 multiplikasjoner, og dette tallet ble redusert til 80 med menneskelig oppfinnsomhet, har AlphaTensor funnet algoritmer som gjør den samme operasjonen med bare 76 multiplikasjoner. 

Utover dette eksemplet forbedrer AlphaTensors algoritme Strassens to-nivå algoritme i et begrenset felt for første gang siden oppdagelsen for 50 år siden. Disse algoritmene for å multiplisere små matriser kan brukes som primitiver for å multiplisere mye større matriser av vilkårlig størrelse. 

Dessuten oppdager AlphaTensor også et mangfoldig sett med algoritmer med toppmoderne kompleksitet – opptil tusenvis av matrisemultiplikasjonsalgoritmer for hver størrelse, noe som viser at plassen til matrisemultiplikasjonsalgoritmer er rikere enn tidligere antatt. 

Algoritmer i dette rike rommet har forskjellige matematiske og praktiske egenskaper. Ved å utnytte dette mangfoldet tilpasset vi AlphaTensor for å spesifikt finne algoritmer som er raske på en gitt maskinvare, for eksempel Nvidia V100 GPU og Google TPU v2. Disse algoritmene multipliserer store matriser 10-20 % raskere enn de vanlige algoritmene på samme maskinvare, noe som viser AlphaTensors fleksibilitet i å optimalisere vilkårlige mål.

Utforske innvirkningen på fremtidig forskning og applikasjoner

Fra et matematisk ståsted kan resultatene våre veilede videre forskning innen kompleksitetsteori, som tar sikte på å bestemme de raskeste algoritmene for å løse beregningsproblemer. Ved å utforske rommet til mulige algoritmer på en mer effektiv måte enn tidligere tilnærminger, kan AlphaTensor bidrar til å fremme vår forståelse av rikdommen til matrisemultiplikasjonsalgoritmer. Å forstå dette rommet kan låse opp nye resultater for å hjelpe med å bestemme den asymptotiske kompleksiteten til matrisemultiplikasjon, et av de mest grunnleggende åpne problemene innen informatikk. 

Fordi matrisemultiplikasjon er en kjernekomponent i mange beregningsoppgaver, som spenner over datagrafikk, digital kommunikasjon, nevrale nettverkstrening og vitenskapelig databehandling, kan AlphaTensor-oppdagede algoritmer gjøre beregninger i disse feltene betydelig mer effektive. AlphaTensors fleksibilitet til å vurdere alle slags mål kan også stimulere til nye applikasjoner for å designe algoritmer som optimerer beregninger som energibruk og numerisk stabilitet, og hjelper til med å forhindre små avrundingsfeil fra snøball når en algoritme fungerer.

Mens vi her fokuserte på det spesielle problemet med matrisemultiplikasjon, håper vi at papiret vårt vil inspirere andre til å bruke AI for å veilede algoritmisk oppdagelse for andre grunnleggende beregningsoppgaver. Vår forskning viser også at AlphaZero er en kraftig algoritme som kan utvides langt utover domenet til tradisjonelle spill for å hjelpe til med å løse åpne problemer i matematikk. Med utgangspunkt i forskningen vår håper vi å stimulere til et større arbeid – å bruke AI for å hjelpe samfunnet med å løse noen av de viktigste utfordringene innen matematikk og på tvers av vitenskapene.