AlphaTensor, bygger på AlphaZero, en agent som har vist overmenneskelige prestasjoner på brettspill, som sjakk, Go og shogi, og dette verket viser AlphaZeros reise fra å spille spill til å takle uløste matematiske problemer for første gang.
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 designet den persiske matematikeren Muhammad ibn Musa al-Khwarizmi nye algoritmer for å løse lineære og kvadratiske ligninger. Faktisk førte al-Khwarizmis navn, oversatt til latin som Algoritmi, 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.
De publiserte i Nature. AlphaTensor er 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å.
Opplært fra bunnen av oppdager AlphaTensor matrisemultiplikasjonsalgoritmer som er mer effektive enn eksisterende menneske- og datamaskindesignede algoritmer. Til tross for forbedring i forhold til kjente algoritmer, merker de at en begrensning ved AlphaTensor er behovet for å forhåndsdefinere et sett med potensielle faktoroppføringer F, som diskretiserer søkeområdet, men kan muligens føre til at effektive algoritmer går glipp av. En interessant retning for fremtidig forskning er å tilpasse AlphaTensor til å søke etter F. En viktig styrke ved AlphaTensor er dens fleksibilitet til å støtte komplekse stokastiske og ikke-differensierbare belønninger (fra tensorrangeringen til praktisk effektivitet på spesifikk maskinvare), i tillegg til å finne algoritmer for tilpassede operasjoner i et bredt spekter av rom (for eksempel begrensede felt). De tror dette vil anspore applikasjoner av AlphaTensor til å designe algoritmer som optimaliserer beregninger som vi ikke har vurdert her, for eksempel numerisk stabilitet eller energibruk.
Oppdagelsen av matrisemultiplikasjonsalgoritmer har vidtrekkende implikasjoner, ettersom matrisemultiplikasjon sitter i kjernen av mange beregningsoppgaver, for eksempel matriseinversjon, beregning av determinanten og løsning av lineære systemer.
Prosessen og fremdriften for å automatisere algoritmisk oppdagelse
Først konverterte de 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 forble en utfordring for AI i flere tiår, er antallet mulige trekk på hvert trinn i spillet deres 30 størrelsesordener større (over 10^33 for en av innstillingene de 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.
De 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.
Utforske innvirkningen på fremtidig forskning og applikasjoner
Fra et matematisk synspunkt kan resultatene deres 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, hjelper AlphaTensor med å 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 de 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. Forskningen deres 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 de å 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.
Natur – Oppdag raskere matrisemultiplikasjonsalgoritmer med forsterkende læring
Abstrakt
Å forbedre effektiviteten til algoritmer for grunnleggende beregninger kan ha en utbredt innvirkning, siden det kan påvirke den totale hastigheten til en stor mengde beregninger. Matrisemultiplikasjon er en slik primitiv oppgave, som forekommer i mange systemer - fra nevrale nettverk til vitenskapelige datarutiner. Den automatiske oppdagelsen av algoritmer ved hjelp av maskinlæring gir muligheten til å nå utover menneskelig intuisjon og utkonkurrere dagens beste menneskedesignede algoritmer. Det er imidlertid komplisert å automatisere prosedyren for oppdagelse av algoritmer, siden plassen med mulige algoritmer er enorm. Her rapporterer vi en dyp forsterkende læringstilnærming basert på AlphaZero1 for å oppdage effektive og beviselig korrekte algoritmer for multiplikasjon av vilkårlige matriser. Agenten vår, AlphaTensor, er opplært til å spille et enkeltspillerspill der målet er å finne tensordekomponeringer innenfor et begrenset faktorrom. AlphaTensor oppdaget algoritmer som overgår den toppmoderne kompleksiteten for mange matrisestørrelser. Spesielt relevant er tilfellet med 4 × 4 matriser i et begrenset felt, der AlphaTensors algoritme forbedrer Strassens to-nivå algoritme for første gang, så vidt vi vet, siden oppdagelsen for 50 år siden2. Vi viser videre fleksibiliteten til AlphaTensor gjennom forskjellige bruksområder: algoritmer med toppmoderne kompleksitet for strukturert matrisemultiplikasjon og forbedret praktisk effektivitet ved å optimalisere matrisemultiplikasjon for kjøretid på spesifikk maskinvare. Resultatene våre fremhever AlphaTensors evne til å akselerere prosessen med algoritmisk oppdagelse på en rekke problemer, og å optimalisere for ulike kriterier.
Brian Wang er en futuristisk tankeleder og en populær vitenskapsblogger med 1 million lesere per måned. Bloggen hans Nextbigfuture.com er rangert som #1 Science News Blog. Den dekker mange forstyrrende teknologi og trender, inkludert rom, robotikk, kunstig intelligens, medisin, anti-aging bioteknologi og nanoteknologi.
Han er kjent for å identifisere banebrytende teknologier, og er for tiden en av grunnleggerne av en oppstart og innsamling for høy potensielle selskaper i et tidlig stadium. Han er forskningssjef for allokasjoner for dype teknologiinvesteringer og en engelinvestor hos Space Angels.
Han er en hyppig foredragsholder i selskaper, og har vært TEDx -foredragsholder, høyttaler på Singularity University og gjest på mange intervjuer for radio og podcaster. Han er åpen for offentlige foredrag og rådgivning.
