AI afslører nye muligheder i matrixmultiplikation

Matematikere elsker et godt puslespil. Selv noget så abstrakt som at multiplicere matricer (todimensionelle tabeller med tal) kan føles som et spil, når du prøver at finde den mest effektive måde at gøre det på. Det er lidt som at prøve at løse en Rubik's Cube i så få træk som muligt - udfordrende, men dragende. Bortset fra at for en Rubik's Cube er antallet af mulige træk ved hvert trin 18; til matrixmultiplikation, selv i relativt simple tilfælde, kan hvert trin præsentere mere end 10¹² valgmuligheder.

I løbet af de sidste 50 år har forskere grebet dette problem an på mange måder, alt baseret på computersøgninger hjulpet af menneskelig intuition. I sidste måned viste et team hos den kunstige intelligens-virksomhed DeepMind, hvordan man tackler problemet fra en ny retning, og rapporterede i en papir in Natur at de med succes havde trænet et neuralt netværk til at opdage nye hurtige algoritmer til matrixmultiplikation. Det var, som om AI'en havde fundet en ukendt strategi til at løse en monstrøst kompleks Rubik's Cube.

"Det er et meget pænt resultat," sagde Josh Alman, en datalog ved Columbia University. Men han og andre matrix-multiplikationsspecialister understregede også, at sådan AI-assistance vil supplere snarere end erstatte eksisterende metoder - i det mindste på kort sigt. "Det er som et proof of concept for noget, der kunne blive et gennembrud," sagde Alman. Resultatet vil simpelthen hjælpe forskere på deres søgen.

Som for at bevise pointen, tre dage efter Natur papir udkom, illustrerede et par østrigske forskere, hvordan nye og gamle metoder kunne supplere hinanden. De brugte en konventionel computerstøttet søgning til forbedre yderligere en af ​​de algoritmer, som det neurale netværk havde opdaget.

Resultaterne tyder på, at vejen til bedre algoritmer, ligesom processen med at løse en Rubiks terning, vil være fuld af drejninger.

Multiplikation af matricer

Matrixmultiplikation er en af ​​de mest fundamentale og allestedsnærværende operationer i al matematik. At gange et par n-ved-n matricer, hver med n² elementer, multiplicerer du og lægger disse elementer sammen i bestemte kombinationer for at generere produktet, en tredjedel n-ved-n matrix. Standardopskriften på at gange to n-ved-n matricer kræver n³ multiplikationsoperationer, så en 2-til-2 matrix, for eksempel, kræver otte multiplikationer.

For større matricer, med tusindvis af rækker og kolonner, bliver denne proces hurtigt besværlig. Men i 1969, matematikeren Volker Strassen opdagede en procedure til at multiplicere et par 2-til-2-matricer ved hjælp af syv i stedet for otte multiplikationstrin, på bekostning af at indføre flere additionstrin.

Strassens algoritme er unødvendigt indviklet, hvis du bare vil gange et par 2-til-2 matricer. Men han indså, at det også ville fungere for større matricer. Det er fordi elementerne i en matrix i sig selv kan være matricer. For eksempel kan en matrix med 20,000 rækker og 20,000 kolonner genfortolkes som en 2-til-2 matrix, hvis fire elementer hver er 10,000-x-10,000 matricer. Hver af disse matricer kan derefter underinddeles i fire 5,000 x 5,000 blokke og så videre. Strassen kunne anvende sin metode til at multiplicere 2-til-2 matricer på hvert niveau i dette indlejrede hierarki. Efterhånden som matrixstørrelsen øges, vokser besparelsen ved færre multiplikationer.

Strassens opdagelse førte til en søgen efter effektive algoritmer til matrixmultiplikation, som siden har inspireret to forskellige underfelter. Man fokuserer på et principspørgsmål: Hvis du forestiller dig at gange to n-ved-n matricer og lad n løbe mod det uendelige, hvordan skalaer antallet af multiplikationstrin i den hurtigst mulige algoritme med n? Det nuværende rekord for den bedste skalering, n^2.3728596, tilhører Alman og Virginia Vassilevska Williams, en datalog ved Massachusetts Institute of Technology. (En nylig upubliceret fortryk rapporterede om en lille forbedring ved hjælp af en ny teknik.) Men disse algoritmer er af rent teoretisk interesse og vinder over metoder som Strassens kun for absurd store matricer.

Det andet underfelt tænker i mindre skala. Kort efter Strassens arbejde, den israelske amerikanske datalog Shmuel Winograd viste at Strassen havde nået en teoretisk grænse: Det er ikke muligt at multiplicere 2-til-2 matricer med færre end syv multiplikationstrin. Men for alle andre matrixstørrelser forbliver det mindste antal nødvendige multiplikationer et åbent spørgsmål. Og hurtige algoritmer til små matricer kan have en større indvirkning, da gentagne iterationer af en sådan algoritme kan slå Strassens algoritme, når rimelig størrelse matricer multipliceres.

Desværre er det store antal muligheder enormt. Selv for 3-til-3-matricer, "overstiger antallet af mulige algoritmer antallet af atomer i universet," sagde Alhussein Fawzi, en DeepMind-forsker og en af ​​lederne af det nye arbejde.

Stillet over for denne svimlende menu af muligheder har forskere gjort fremskridt ved at transformere matrixmultiplikation til, hvad der ser ud til at være et helt andet matematisk problem - et, der er lettere for computere at håndtere. Det er muligt at repræsentere den abstrakte opgave at multiplicere to matricer som en specifik slags matematisk objekt: en tredimensionel række af tal kaldet en tensor. Forskere kan derefter dele denne tensor op i en sum af elementære komponenter, kaldet "rang-1" tensorer; hver af disse vil repræsentere et forskelligt trin i den tilsvarende matrixmultiplikationsalgoritme. Det betyder, at det at finde en effektiv multiplikationsalgoritme svarer til at minimere antallet af led i en tensor-nedbrydning - jo færre led, jo færre trin involveret.

På den måde har forskere opdaget nyt algoritmer der formerer sig n-ved-n matricer, der bruger færre end standarden n³ multiplikationstrin for mange små matrixstørrelser. Men algoritmer, der overgår ikke kun standarden, men også Strassens algoritme for små matricer, har været uden for rækkevidde - indtil nu.

Så er spillet i gang

DeepMind-teamet nærmede sig problemet ved at omdanne tensor-nedbrydning til et singleplayer-spil. De startede med en dyb læringsalgoritme, der stammede fra AlphaGo - en anden DeepMind AI, der i 2016 lært at spille brætspillet Go godt nok til at slå de bedste menneskelige spillere.

Alle deep learning algoritmer er bygget op omkring neurale netværk: spind af kunstige neuroner sorteret i lag, med forbindelser, der kan variere i styrke, hvilket repræsenterer, hvor meget hver neuron påvirker dem i det næste lag. Styrken af ​​disse forbindelser er justeret over mange iterationer af en træningsprocedure, hvor det neurale netværk lærer at transformere hvert input, det modtager, til et output, der hjælper algoritmen med at nå sit overordnede mål.

I DeepMinds nye algoritme, kaldet AlphaTensor, repræsenterer inputs trin på vejen til et gyldigt matrix multiplikationsskema. Det første input til det neurale netværk er den originale matrixmultiplikationstensor, og dens output er rang-1-tensoren, som AlphaTensor har valgt til sit første træk. Algoritmen trækker denne rang-1-tensor fra det oprindelige input, hvilket giver en opdateret tensor, der føres tilbage til netværket som et nyt input. Processen gentages, indtil hvert element i starttensoren er blevet reduceret til nul, hvilket betyder, at der ikke er flere rang-1 tensorer at tage ud.

På det tidspunkt har det neurale netværk opdaget en gyldig tensor-nedbrydning, da det er matematisk garanteret, at summen af ​​alle rang-1 tensorer er nøjagtigt lig med starttensoren. Og de trin, det tog for at nå dertil, kan oversættes tilbage til trin i den tilsvarende matrixmultiplikationsalgoritme.

Her er spillet: AlphaTensor dekomponerer gentagne gange en tensor til et sæt af rang-1 komponenter. Hver gang bliver AlphaTensor belønnet, hvis den finder en måde at reducere antallet af trin på. Men genveje til sejr er slet ikke intuitive, ligesom du nogle gange skal scramble et perfekt ordnet ansigt på en Rubik's Cube, før du kan løse det hele.

Holdet havde nu en algoritme, der teoretisk kunne løse deres problem. De skulle bare træne det først.

Nye veje

Som alle neurale netværk har AlphaTensor brug for en masse data at træne på, men tensor-nedbrydning er et notorisk svært problem. Der var få eksempler på effektive nedbrydninger, som forskerne kunne fodre netværket med. I stedet hjalp de algoritmen med at komme i gang ved at træne den på det meget nemmere omvendte problem: at tilføje en masse tilfældigt genererede rang-1 tensorer.

"De bruger det nemme problem til at producere flere data til det svære problem," sagde Michael Littman, en datalog ved Brown University. Kombinationen af ​​denne baglæns træningsprocedure med forstærkningslæring, hvor AlphaTensor genererede sine egne træningsdata, mens den tumlede rundt på udkig efter effektive nedbrydninger, fungerede meget bedre end hver af træningsmetoderne alene.

DeepMind-teamet trænede AlphaTensor til at nedbryde tensorer, der repræsenterer multiplikationen af ​​matricer op til 12 gange 12. Den søgte hurtige algoritmer til at multiplicere matricer af almindelige reelle tal og også algoritmer, der er specifikke for en mere begrænset indstilling kendt som modulo 2 aritmetik. (Dette er matematik baseret på kun to tal, så matrixelementer kan kun være 0 eller 1, og 1 + 1 = 0.) Forskere starter ofte med dette mere begrænsede, men stadig enorme rum, i håb om, at algoritmer, der er opdaget her, kan tilpasses til arbejde på matricer af reelle tal.

Efter træning genopdagede AlphaTensor Strassens algoritme inden for få minutter. Den opdagede derefter op til tusindvis af nye hurtige algoritmer for hver matrixstørrelse. Disse var forskellige fra de bedst kendte algoritmer, men havde det samme antal multiplikationstrin.

I nogle få tilfælde slog AlphaTensor endda eksisterende rekorder. Dens mest overraskende opdagelser skete i modulo 2 aritmetik, hvor den fandt en ny algoritme til at multiplicere 4-til-4 matricer i 47 multiplikationstrin, en forbedring i forhold til de 49 trin, der kræves for to iterationer af Strassens algoritme. Det slog også den bedst kendte algoritme for 5-til-5 modulo 2-matricer, hvilket reducerede antallet af nødvendige multiplikationer fra den tidligere rekord på 98 til 96. (Men denne nye rekord halter stadig bagefter de 91 trin, der ville være påkrævet for at slå Strassens algoritme ved hjælp af 5-til-5-matricer.)

Det nye højprofilerede resultat skabte en masse begejstring, med nogle forskere høster ros for den AI-baserede forbedring af status quo. Men ikke alle i matrixmultiplikationsfællesskabet var så imponerede. "Jeg følte, at det var lidt overhypet," sagde Vassilevska Williams. "Det er et andet værktøj. Det er ikke sådan, "Åh, computerne slår menneskene," ved du?"

Forskere understregede også, at umiddelbare anvendelser af den rekordstore 4-til-4-algoritme ville være begrænset: Ikke kun er den kun gyldig i modulo 2-aritmetik, men i det virkelige liv er der vigtige overvejelser udover hastighed.

Fawzi var enig i, at dette virkelig kun er begyndelsen. "Der er meget plads til forbedringer og forskning, og det er en god ting," sagde han.

Et sidste twist

AlphaTensors største styrke i forhold til veletablerede computersøgningsmetoder er også dens største svaghed: Den er ikke begrænset af menneskelig intuition om, hvordan gode algoritmer ser ud, så den kan ikke forklare sine valg. Det gør det svært for forskere at lære af dets resultater.

Men dette er måske ikke så stor en ulempe, som det ser ud til. Et par dage efter AlphaTensor-resultatet, matematikeren Manuel Kauers og hans kandidatstuderende Jakob Moosbauer, begge fra Johannes Kepler University Linz i Østrig, rapporterede om endnu et skridt fremad.

Da DeepMind-papiret udkom, var Kauers og Moosbauer i gang med at søge efter nye multiplikationsalgoritmer ved hjælp af en konventionel computerstøttet søgning. Men i modsætning til de fleste sådanne søgninger, som starter forfra med et nyt vejledende princip, fungerer deres metode ved gentagne gange at justere en eksisterende algoritme i håb om at presse flere multiplikationsbesparelser ud af den. Ved at tage udgangspunkt i AlphaTensors algoritme for 5-til-5 modulo 2-matricer, blev de overraskede over at opdage, at deres metode reducerede antallet af multiplikationstrin fra 96 ​​til 95 efter blot et par sekunders beregning.

AlphaTensor hjalp dem også indirekte med endnu en forbedring. Tidligere havde Kauers og Moosbauer ikke gidet at udforske rummet af 4 x 4 matricer, idet de troede, at det ikke ville være muligt at slå to iterationer af Strassens algoritme. AlphaTensor-resultatet fik dem til at genoverveje, og efter en uges beregningstid, der startede fra bunden, viste deres metode en anden 47-trins algoritme, der ikke var relateret til den, AlphaTensor havde opdaget. "Hvis nogen havde fortalt os, at der er noget at opdage for 4-til-4, kunne vi have gjort det tidligere," sagde Kauers. "Men okay, det er sådan det virker."

Littman forventer flere sådanne overraskelser, idet han sammenligner situationen med første gang, en løber færdiggjorde en mile på under fire minutter, en bedrift, der i vid udstrækning var blevet anset for umulig. "Folk tænkte: 'Åh, vent, vi kan gøre det her', og nu kan mange mennesker gøre det," sagde han.

Ser frem til, håber Fawzi at generalisere AlphaTensor til at tackle en bredere række af matematiske og beregningsmæssige opgaver, ligesom dens forfader AlphaGo til sidst forgrenede sig til andre spil.

Kauers ser dette som den sande lakmustest for anvendelsen af ​​maskinlæring til at opdage nye algoritmer. Han påpeger, at jagten på hurtige matrixmultiplikationsalgoritmer er et kombinatorisk problem, som computersøgninger, med eller uden menneskelig assistance, er velegnet til. Men ikke alle matematiske problemer er så lette at fastlægge. Hvis maskinlæring kan opdage en kvalitativt ny algoritmisk idé, sagde han, "det ville så være en game changer."