AI avslører nye muligheter i matrisemultiplikasjon

Matematikere elsker et godt puslespill. Selv noe så abstrakt som å multiplisere matriser (todimensjonale talltabeller) kan føles som et spill når du prøver å finne den mest effektive måten å gjøre det på. Det er litt som å prøve å løse en Rubiks kube med så få trekk som mulig – utfordrende, men forlokkende. Bortsett fra at for en Rubiks kube er antall mulige trekk ved hvert trinn 18; for matrisemultiplikasjon, selv i relativt enkle tilfeller, kan hvert trinn presentere mer enn 10¹² alternativer.

I løpet av de siste 50 årene har forskere nærmet seg dette problemet på mange måter, alt basert på datasøk hjulpet av menneskelig intuisjon. Forrige måned viste et team ved kunstig intelligens-selskapet DeepMind hvordan man kan takle problemet fra en ny retning, og rapporterte i en papir in Natur at de hadde trent opp et nevralt nettverk for å oppdage nye raske algoritmer for matrisemultiplikasjon. Det var som om AI hadde funnet en ukjent strategi for å løse en uhyrlig kompleks Rubiks kube.

"Det er et veldig pent resultat," sa Josh Alman, en informatiker ved Columbia University. Men han og andre matrisemultiplikasjonsspesialister understreket også at slik AI-hjelp vil utfylle i stedet for å erstatte eksisterende metoder - i det minste på kort sikt. "Det er som et proof of concept for noe som kan bli et gjennombrudd," sa Alman. Resultatet vil rett og slett hjelpe forskere på deres søken.

Som for å bevise poenget, tre dager etter Natur papiret kom ut, illustrerte et par østerrikske forskere hvordan nye og gamle metoder kan utfylle hverandre. De brukte et konvensjonelt datastøttet søk for å ytterligere forbedre en av algoritmene som det nevrale nettverket hadde oppdaget.

Resultatene tyder på at, i likhet med prosessen med å løse en Rubiks kube, vil veien til bedre algoritmer være full av vendinger.

Multiplisere matriser

Matrisemultiplikasjon er en av de mest grunnleggende og allestedsnærværende operasjonene i all matematikk. Å multiplisere et par n-av-n matriser, hver med n² elementer, multipliserer du og legger disse elementene sammen i bestemte kombinasjoner for å generere produktet, en tredje n-av-n matrise. Standardoppskriften for å multiplisere to n-av-n matriser krever n³ multiplikasjonsoperasjoner, så en 2-til-2-matrise, for eksempel, krever åtte multiplikasjoner.

For større matriser, med tusenvis av rader og kolonner, blir denne prosessen raskt tungvint. Men i 1969, matematikeren Volker Strassen oppdaget en prosedyre for å multiplisere et par 2-til-2 matriser ved å bruke syv i stedet for åtte multiplikasjonstrinn, på bekostning av å introdusere flere addisjonstrinn.

Strassens algoritme er unødvendig kronglete hvis du bare vil multiplisere et par 2-til-2 matriser. Men han innså at det også ville fungere for større matriser. Det er fordi elementene i en matrise i seg selv kan være matriser. For eksempel kan en matrise med 20,000 20,000 rader og 2 2 kolonner omformes som en 10,000-av-10,000-matrise hvis fire elementer hver er 5,000 5,000-x-2 2 matriser. Hver av disse matrisene kan deretter deles inn i fire XNUMX x XNUMX blokker, og så videre. Strassen kunne bruke metoden sin for å multiplisere XNUMX-til-XNUMX matriser på hvert nivå i dette nestede hierarkiet. Etter hvert som matrisestørrelsen øker, vokser besparelsene fra færre multiplikasjoner.

Strassens oppdagelse førte til et søk etter effektive algoritmer for matrisemultiplikasjon, som siden har inspirert to distinkte underfelt. Man fokuserer på et prinsippspørsmål: Hvis du ser for deg å multiplisere to n-av-n matriser og la n løpe mot det uendelige, hvordan skala antall multiplikasjonstrinn i raskest mulig algoritme med n? De nåværende rekord for den beste skaleringen, n^2.3728596, tilhører Alman og Virginia Vassilevska Williams, en informatiker ved Massachusetts Institute of Technology. (En nylig upublisert preprint rapporterte en liten forbedring ved hjelp av en ny teknikk.) Men disse algoritmene er av rent teoretisk interesse, og vant over metoder som Strassens kun for absurd store matriser.

Det andre delfeltet tenker i mindre skala. Rett etter Strassens arbeid, den israelske amerikanske dataforskeren Shmuel Winograd viste at Strassen hadde nådd en teoretisk grense: Det er ikke mulig å multiplisere 2-til-2 matriser med færre enn syv multiplikasjonstrinn. Men for alle andre matrisestørrelser forblir minimum antall nødvendige multiplikasjoner et åpent spørsmål. Og raske algoritmer for små matriser kan ha en større innvirkning, siden gjentatte iterasjoner av en slik algoritme kan slå Strassens algoritme når matriser av rimelig størrelse multipliseres.

Dessverre er det store antallet muligheter. Selv for 3-av-3-matriser, "overskrider antallet mulige algoritmer antallet atomer i universet," sa Alhussein Fawzi, en DeepMind-forsker og en av lederne for det nye arbeidet.

Stilt overfor denne svimlende menyen med alternativer, har forskere gjort fremskritt ved å transformere matrisemultiplikasjon til det som virker som et helt annet matematisk problem - et som er lettere å håndtere for datamaskiner. Det er mulig å representere den abstrakte oppgaven med å multiplisere to matriser som en spesifikk type matematisk objekt: en tredimensjonal rekke tall kalt en tensor. Forskere kan deretter dele denne tensoren opp i en sum av elementære komponenter, kalt "rank-1" tensorer; hver av disse vil representere et annet trinn i den tilsvarende matrisemultiplikasjonsalgoritmen. Det betyr at å finne en effektiv multiplikasjonsalgoritme er å minimere antall ledd i en tensor-dekomponering - jo færre ledd, jo færre trinn er involvert.

På denne måten har forskere oppdaget nytt algoritmer som formerer seg n-av-n matriser som bruker færre enn standarden n³ multiplikasjonstrinn for mange små matrisestørrelser. Men algoritmer som overgår ikke bare standarden, men også Strassens algoritme for små matriser har holdt seg utenfor rekkevidde - til nå.

Spill på

DeepMind-teamet nærmet seg problemet ved å gjøre tensordekomponering til et enkeltspillerspill. De startet med en dyp læringsalgoritme som stammet fra AlphaGo - en annen DeepMind AI som i 2016 lærte å spille brettspillet Go godt nok til å slå de beste menneskelige spillerne.

Alle dyplæringsalgoritmer er bygget rundt nevrale nettverk: nett av kunstige nevroner sortert i lag, med forbindelser som kan variere i styrke som representerer hvor mye hver nevron påvirker de i neste lag. Styrken til disse forbindelsene justeres over mange iterasjoner av en treningsprosedyre, der det nevrale nettverket lærer å transformere hver inngang det mottar til en utgang som hjelper algoritmen med å oppnå sitt overordnede mål.

I DeepMinds nye algoritme, kalt AlphaTensor, representerer inngangene trinn på veien til et gyldig matrisemultiplikasjonsskjema. Den første inngangen til det nevrale nettverket er den originale matrisemultiplikasjonstensoren, og dens utgang er rang-1-tensoren som AlphaTensor har valgt for sitt første trekk. Algoritmen trekker denne rang-1-tensoren fra den første inngangen, og gir en oppdatert tensor som mates tilbake til nettverket som en ny inngang. Prosessen gjentas til til slutt hvert element i starttensoren har blitt redusert til null, noe som betyr at det ikke er flere rang-1-tensorer å ta ut.

På det tidspunktet har det nevrale nettverket oppdaget en gyldig tensor-dekomponering, siden det er matematisk garantert at summen av alle rang-1-tensorene er nøyaktig lik starttensoren. Og trinnene det tok for å komme dit kan oversettes tilbake til trinn i den tilsvarende matrisemultiplikasjonsalgoritmen.

Her er spillet: AlphaTensor dekomponerer gjentatte ganger en tensor til et sett med rang-1-komponenter. Hver gang blir AlphaTensor belønnet hvis den finner en måte å redusere antall trinn på. Men snarveier til seier er ikke i det hele tatt intuitive, akkurat som du noen ganger må kryptere et perfekt ordnet ansikt på en Rubiks kube før du kan løse hele greia.

Teamet hadde nå en algoritme som teoretisk sett kunne løse problemet deres. De måtte bare trene det først.

Nye veier

Som alle nevrale nettverk trenger AlphaTensor mye data å trene på, men tensordekomponering er et notorisk vanskelig problem. Det var få eksempler på effektive nedbrytninger som forskerne kunne mate nettverket. I stedet hjalp de algoritmen med å komme i gang ved å trene den på det mye enklere omvendte problemet: å legge sammen en haug med tilfeldig genererte rang-1-tensorer.

"De bruker det enkle problemet til å produsere mer data for det vanskelige problemet," sa Michael Littman, en informatiker ved Brown University. Å kombinere denne baklengs treningsprosedyren med forsterkende læring, der AlphaTensor genererte sine egne treningsdata mens den tullet rundt på jakt etter effektive dekomponeringer, fungerte mye bedre enn hver treningsmetode alene.

DeepMind-teamet trente AlphaTensor til å dekomponere tensorer som representerer multiplikasjonen av matriser opp til 12 x 12. Den søkte raske algoritmer for å multiplisere matriser av vanlige reelle tall og også algoritmer som er spesifikke for en mer begrenset innstilling kjent som modulo 2 aritmetikk. (Dette er matematikk basert på bare to tall, så matriseelementer kan bare være 0 eller 1, og 1 + 1 = 0.) Forskere starter ofte med denne mer begrensede, men fortsatt enorme plassen, i håp om at algoritmer som oppdages her kan tilpasses til arbeid med matriser av reelle tall.

Etter trening gjenoppdaget AlphaTensor Strassens algoritme i løpet av minutter. Deretter oppdaget den opptil tusenvis av nye raske algoritmer for hver matrisestørrelse. Disse var forskjellige fra de mest kjente algoritmene, men hadde samme antall multiplikasjonstrinn.

I noen få tilfeller slo AlphaTensor til og med eksisterende rekorder. Dens mest overraskende oppdagelser skjedde i modulo 2-aritmetikk, der den fant en ny algoritme for å multiplisere 4-til-4-matriser i 47 multiplikasjonstrinn, en forbedring i forhold til de 49 trinnene som kreves for to iterasjoner av Strassens algoritme. Den slo også den mest kjente algoritmen for 5-av-5 modulo 2-matriser, og reduserte antallet nødvendige multiplikasjoner fra den forrige rekorden på 98 til 96. (Men denne nye rekorden ligger fortsatt bak de 91 trinnene som ville være nødvendig for å slå Strassens algoritme som bruker 5 x 5 matriser.)

Det nye profilerte resultatet skapte mye spenning, med noen forskere heaping ros for AI-basert forbedring av status quo. Men ikke alle i matrisemultiplikasjonssamfunnet var så imponert. "Jeg følte at det var litt overhypet," sa Vassilevska Williams. «Det er et annet verktøy. Det er ikke sånn «Å, datamaskinene slår menneskene,» vet du?»

Forskere understreket også at umiddelbare anvendelser av den rekordstore 4-by-4-algoritmen ville være begrenset: Ikke bare er den gyldig bare i modulo 2-aritmetikk, men i det virkelige liv er det viktige hensyn i tillegg til hastighet.

Fawzi var enig i at dette egentlig bare er begynnelsen. "Det er mye rom for forbedring og forskning, og det er en god ting," sa han.

En siste vri

AlphaTensors største styrke i forhold til veletablerte datasøkemetoder er også dens største svakhet: Den er ikke begrenset av menneskelig intuisjon om hvordan gode algoritmer ser ut, så den kan ikke forklare valgene sine. Det gjør det vanskelig for forskere å lære av prestasjoner.

Men dette er kanskje ikke en så stor ulempe som det ser ut til. Noen dager etter AlphaTensor-resultatet, matematikeren Manuel Kauers og hans hovedfagsstudent Jakob Moosbauer, begge ved Johannes Kepler University Linz i Østerrike, rapporterte om et nytt skritt fremover.

Da DeepMind-artikkelen kom ut, var Kauers og Moosbauer i ferd med å søke etter nye multiplikasjonsalgoritmer ved å bruke et konvensjonelt datastøttet søk. Men i motsetning til de fleste slike søk, som starter på nytt med et nytt veiledende prinsipp, fungerer metoden deres ved å gjentatte ganger justere en eksisterende algoritme i håp om å presse flere multiplikasjonsbesparelser ut av den. Ved å ta utgangspunkt i AlphaTensors algoritme for 5-til-5 modulo 2-matriser, ble de overrasket over å finne at metoden deres reduserte antall multiplikasjonstrinn fra 96 ​​til 95 etter bare noen få sekunders beregning.

AlphaTensor hjalp dem også med å gjøre en annen forbedring indirekte. Tidligere hadde Kauers og Moosbauer ikke brydd seg om å utforske rommet til 4 x 4 matriser, og trodde at det ikke ville være mulig å slå to iterasjoner av Strassens algoritme. AlphaTensor-resultatet fikk dem til å revurdere, og etter en uke med beregningstid fra bunnen av, viste metoden deres en annen 47-trinns algoritme som ikke var relatert til den AlphaTensor hadde oppdaget. "Hvis noen hadde fortalt oss at det er noe å oppdage for 4-av-4, kunne vi ha gjort det tidligere," sa Kauers. "Men ok, vel, det er sånn det fungerer."

Littman forventer flere slike overraskelser, og sammenligner situasjonen med første gang en løper fullførte en mil på under fire minutter, en bragd som i stor grad ble ansett som umulig. "Folk sa: 'Å, vent, vi kan gjøre dette', og nå kan mange mennesker gjøre det," sa han.

Ser frem til, håper Fawzi å generalisere AlphaTensor til å takle et bredere spekter av matematiske og beregningsmessige oppgaver, akkurat som dens stamfar AlphaGo til slutt forgrenet seg til andre spill.

Kauers ser på dette som den sanne lakmustesten for bruk av maskinlæring for å oppdage nye algoritmer. Han påpeker at jakten på raske matrisemultiplikasjonsalgoritmer er et kombinatorisk problem som datasøk, med eller uten menneskelig assistanse, egner seg godt til. Men ikke alle matematiske problemer er så lette å finne. Hvis maskinlæring kan oppdage en kvalitativt ny algoritmisk idé, sa han, "ville dette være en game changer."