AI avslöjar nya möjligheter i matrismultiplikation

Matematiker älskar ett bra pussel. Till och med något så abstrakt som att multiplicera matriser (tvådimensionella tabeller med tal) kan kännas som ett spel när du försöker hitta det mest effektiva sättet att göra det. Det är lite som att försöka lösa en Rubiks kub i så få drag som möjligt – utmanande, men lockande. Förutom att för en Rubiks kub är antalet möjliga drag vid varje steg 18; för matrismultiplikation, även i relativt enkla fall, kan varje steg presentera mer än 10¹² alternativ.

Under de senaste 50 åren har forskare närmat sig detta problem på många sätt, allt baserat på datorsökningar med hjälp av mänsklig intuition. Förra månaden visade ett team på artificiell intelligens-företaget DeepMind hur man tacklar problemet från ett nytt håll, och rapporterade i en papper in Natur att de framgångsrikt hade tränat ett neuralt nätverk för att upptäcka nya snabba algoritmer för matrismultiplikation. Det var som om AI:n hade hittat en okänd strategi för att lösa en monstruöst komplex Rubiks kub.

"Det är ett mycket snyggt resultat," sa Josh Alman, en datavetare vid Columbia University. Men han och andra matrismultiplikationsspecialister betonade också att sådan AI-hjälp kommer att komplettera snarare än ersätta befintliga metoder - åtminstone på kort sikt. "Det är som ett proof of concept för något som kan bli ett genombrott," sa Alman. Resultatet kommer helt enkelt att hjälpa forskare i deras sökande.

Som för att bevisa poängen, tre dagar efter Natur ett par österrikiska forskare illustrerade hur nya och gamla metoder kan komplettera varandra. De använde en konventionell datorstödd sökning för att förbättra ytterligare en av algoritmerna som det neurala nätverket hade upptäckt.

Resultaten tyder på att, liksom processen att lösa en Rubiks kub, kommer vägen till bättre algoritmer att vara full av vändningar.

Multiplicera matriser

Matrismultiplikation är en av de mest grundläggande och allestädes närvarande operationerna i all matematik. Att multiplicera ett par n-förbi-n matriser, var och en med n² element multiplicerar du och lägger ihop dessa element i speciella kombinationer för att generera produkten, en tredje n-förbi-n matris. Standardreceptet för att multiplicera två n-förbi-n matriser kräver n³ multiplikationsoperationer, så en 2-till-2-matris, till exempel, kräver åtta multiplikationer.

För större matriser, med tusentals rader och kolumner, blir denna process snabbt besvärlig. Men 1969, matematikern Volker Strassen upptäckte ett förfarande för att multiplicera ett par 2 gånger 2 matriser med hjälp av sju istället för åtta multiplikationssteg, till priset av att införa fler additionssteg.

Strassens algoritm är onödigt krystad om du bara vill multiplicera ett par 2 gånger 2 matriser. Men han insåg att det också skulle fungera för större matriser. Det beror på att elementen i en matris själva kan vara matriser. Till exempel kan en matris med 20,000 20,000 rader och 2 2 kolumner ombildas som en 10,000-av-10,000-matris vars fyra element var och en är 5,000 5,000-x-2 2 matriser. Var och en av dessa matriser kan sedan delas in i fyra XNUMX XNUMX gånger XNUMX XNUMX block, och så vidare. Strassen kunde tillämpa sin metod för att multiplicera XNUMX-av-XNUMX matriser på varje nivå i denna kapslade hierarki. När matrisstorleken ökar, växer besparingarna från färre multiplikationer.

Strassens upptäckt ledde till ett sökande efter effektiva algoritmer för matrismultiplikation, vilket sedan dess inspirerat till två distinkta delfält. Man fokuserar på en principfråga: Om du tänker dig att multiplicera två n-förbi-n matriser och låt n springa mot oändligheten, hur blir antalet multiplikationssteg i snabbast möjliga algoritmskala med n? De nuvarande rekord för bästa skalning, n^2.3728596, tillhör Alman och Virginia Vassilevska Williams, en datavetare vid Massachusetts Institute of Technology. (En nyligen opublicerad preprint rapporterade en liten förbättring med en ny teknik.) Men dessa algoritmer är av rent teoretiskt intresse och vinner över metoder som Strassens endast för absurt stora matriser.

Det andra delfältet tänker i mindre skala. Strax efter Strassens arbete, den israelisk amerikanske datavetaren Shmuel Winograd visade att Strassen hade nått en teoretisk gräns: Det är inte möjligt att multiplicera 2 gånger 2 matriser med färre än sju multiplikationssteg. Men för alla andra matrisstorlekar förblir det minsta antalet nödvändiga multiplikationer en öppen fråga. Och snabba algoritmer för små matriser kan ha en stor inverkan, eftersom upprepade iterationer av en sådan algoritm kan slå Strassens algoritm när matriser av rimlig storlek multipliceras.

Tyvärr är det stora antalet möjligheter enormt. Även för 3-av-3-matriser, "överstiger antalet möjliga algoritmer antalet atomer i universum," sa Alhussein Fawzi, en DeepMind-forskare och en av ledarna för det nya arbetet.

Inför denna svindlande meny med alternativ har forskare gjort framsteg genom att omvandla matrismultiplikation till vad som verkar vara ett helt annat matematiskt problem - ett som är lättare för datorer att hantera. Det är möjligt att representera den abstrakta uppgiften att multiplicera två matriser som en specifik typ av matematiskt objekt: en tredimensionell matris av tal som kallas en tensor. Forskare kan sedan dela upp denna tensor i en summa av elementära komponenter, kallade "rank-1"-tensorer; var och en av dessa kommer att representera ett annat steg i den motsvarande matrismultiplikationsalgoritmen. Det betyder att att hitta en effektiv multiplikationsalgoritm innebär att minimera antalet termer i en tensorupplösning - ju färre termer, desto färre inblandade steg.

På så sätt har forskare upptäckt nytt algoritmer som förökar sig n-förbi-n matriser som använder färre än standarden n³ multiplikationssteg för många små matrisstorlekar. Men algoritmer som överträffar inte bara standarden utan även Strassens algoritm för små matriser har varit utom räckhåll — tills nu.

Spel på

DeepMind-teamet närmade sig problemet genom att förvandla tensornedbrytning till ett enspelarspel. De började med en algoritm för djupinlärning som härstammar från AlphaGo - en annan DeepMind AI som 2016 lärt sig spela brädspelet Go tillräckligt bra för att slå de bästa mänskliga spelarna.

Alla djupinlärningsalgoritmer är uppbyggda kring neurala nätverk: vävar av artificiella neuroner sorterade i lager, med anslutningar som kan variera i styrka som representerar hur mycket varje neuron påverkar dem i nästa lager. Styrkan i dessa anslutningar justeras över många iterationer av en träningsprocedur, under vilken det neurala nätverket lär sig att omvandla varje input som det tar emot till en utdata som hjälper algoritmen att uppnå sitt övergripande mål.

I DeepMinds nya algoritm, kallad AlphaTensor, representerar ingångarna steg på vägen till ett giltigt matrismultiplikationsschema. Den första ingången till det neurala nätverket är den ursprungliga matrismultiplikationstensorn, och dess utgång är den rank-1-tensor som AlphaTensor har valt för sitt första drag. Algoritmen subtraherar denna rang-1-tensor från den initiala ingången, vilket ger en uppdaterad tensor som matas tillbaka till nätverket som en ny ingång. Processen upprepas tills varje element i starttensorn har reducerats till noll, vilket betyder att det inte finns fler rank-1-tensorer att ta ut.

Vid den tidpunkten har det neurala nätverket upptäckt en giltig tensornedbrytning, eftersom det är matematiskt garanterat att summan av alla rang-1-tensorer är exakt lika med starttensorn. Och stegen det tog för att komma dit kan översättas tillbaka till steg i motsvarande matrismultiplikationsalgoritm.

Här är spelet: AlphaTensor sönderdelar upprepade gånger en tensor till en uppsättning rank-1-komponenter. Varje gång blir AlphaTensor belönad om den hittar ett sätt att minska antalet steg. Men genvägar till seger är inte alls intuitiva, precis som du ibland måste klämma in ett perfekt ordnat ansikte på en Rubiks kub innan du kan lösa det hela.

Teamet hade nu en algoritm som teoretiskt kunde lösa deras problem. De var bara tvungna att träna det först.

Nya vägar

Liksom alla neurala nätverk behöver AlphaTensor mycket data att träna på, men tensorupplösning är ett notoriskt svårt problem. Det fanns få exempel på effektiva nedbrytningar som forskarna kunde mata nätverket med. Istället hjälpte de algoritmen att komma igång genom att träna den på det mycket lättare omvända problemet: att lägga ihop ett gäng slumpmässigt genererade rank-1-tensorer.

"De använder det enkla problemet för att producera mer data för det svåra problemet," sa Michael Littman, en datavetare vid Brown University. Att kombinera denna bakåtriktade träningsprocedur med förstärkningsinlärning, där AlphaTensor genererade sin egen träningsdata när den blundade och letade efter effektiva nedbrytningar, fungerade mycket bättre än båda träningsmetoderna för sig.

DeepMind-teamet tränade AlphaTensor att bryta ner tensorer som representerar multiplikationen av matriser upp till 12 gånger 12. Den sökte snabba algoritmer för att multiplicera matriser av vanliga reella tal och även algoritmer specifika för en mer begränsad inställning som kallas modulo 2-aritmetik. (Detta är matematik baserat på endast två tal, så matriselement kan bara vara 0 eller 1, och 1 + 1 = 0.) Forskare börjar ofta med detta mer begränsade men fortfarande enorma utrymme, i hopp om att algoritmer som upptäckts här kan anpassas till arbeta på matriser av reella tal.

Efter träning återupptäckte AlphaTensor Strassens algoritm inom några minuter. Den upptäckte sedan upp till tusentals nya snabba algoritmer för varje matrisstorlek. Dessa skilde sig från de mest kända algoritmerna men hade samma antal multiplikationssteg.

I några få fall slog AlphaTensor till och med befintliga rekord. Dess mest överraskande upptäckter hände i modulo 2 aritmetik, där den hittade en ny algoritm för att multiplicera 4-av-4 matriser i 47 multiplikationssteg, en förbättring jämfört med de 49 steg som krävs för två iterationer av Strassens algoritm. Den slog också den mest kända algoritmen för 5 gånger 5 modulo 2-matriser, vilket minskade antalet nödvändiga multiplikationer från det tidigare rekordet på 98 till 96. (Men detta nya rekord ligger fortfarande efter de 91 steg som skulle krävas för att slå Strassens algoritm använder 5-av-5-matriser.)

Det nya högprofilerade resultatet skapade mycket spänning, med några forskare beröm för den AI-baserade förbättringen av status quo. Men inte alla i matrismultiplikationsgemenskapen var så imponerade. "Jag kände att det var lite överhypad," sa Vassilevska Williams. "Det är ett annat verktyg. Det är inte som "Åh, datorerna slår människorna", du vet?"

Forskare betonade också att omedelbara tillämpningar av den rekordstora 4-av-4-algoritmen skulle vara begränsade: Det är inte bara giltigt i modulo 2-aritmetik, utan i verkligheten finns det viktiga överväganden förutom hastighet.

Fawzi höll med om att detta verkligen bara är början. "Det finns mycket utrymme för förbättringar och forskning, och det är bra", sa han.

En sista vändning

AlphaTensors största styrka i förhållande till väletablerade datorsökningsmetoder är också dess största svaghet: Den är inte begränsad av mänsklig intuition om hur bra algoritmer ser ut, så den kan inte förklara sina val. Det gör det svårt för forskare att lära av dess prestationer.

Men detta kanske inte är en så stor nackdel som det verkar. Några dagar efter AlphaTensor-resultatet, matematikern Manuel Kauers och hans doktorand Jakob Moosbauer, båda vid Johannes Kepler University Linz i Österrike, rapporterade ytterligare ett steg framåt.

När DeepMind-tidningen kom ut var Kauers och Moosbauer i färd med att söka efter nya multiplikationsalgoritmer med hjälp av en konventionell datorstödd sökning. Men till skillnad från de flesta sådana sökningar, som börjar på nytt med en ny vägledande princip, fungerar deras metod genom att upprepade gånger justera en befintlig algoritm i hopp om att pressa ut fler multiplikationsbesparingar ur den. Med utgångspunkt i AlphaTensors algoritm för 5-av-5 modulo 2-matriser, blev de förvånade över att deras metod minskade antalet multiplikationssteg från 96 till 95 efter bara några sekunders beräkning.

AlphaTensor hjälpte dem också att göra ytterligare en förbättring indirekt. Tidigare hade Kauers och Moosbauer inte brytt sig om att utforska utrymmet med 4-av-4-matriser, eftersom de trodde att det inte skulle vara möjligt att slå två iterationer av Strassens algoritm. AlphaTensor-resultatet fick dem att ompröva, och efter en veckas beräkningstid från början visade deras metod upp en annan 47-stegsalgoritm som inte var relaterad till den som AlphaTensor hade upptäckt. "Om någon hade sagt till oss att det finns något att upptäcka för 4-av-4, kunde vi ha gjort det tidigare," sa Kauers. "Men okej, det är så det fungerar."

Littman förväntar sig fler sådana överraskningar, och liknar situationen vid första gången en löpare slutade en mil på under fyra minuter, en bedrift som allmänt sett hade ansetts omöjlig. "Folk var som, 'Åh, vänta, vi kan göra det här', och nu kan många människor göra det," sa han.

Ser fram emot hoppas Fawzi kunna generalisera AlphaTensor för att ta itu med ett bredare utbud av matematiska och beräkningsuppgifter, precis som dess förfader AlphaGo så småningom förgrenade sig till andra spel.

Kauers ser detta som det sanna lackmustestet för tillämpningen av maskininlärning för att upptäcka nya algoritmer. Han påpekar att strävan efter snabba matrismultiplikationsalgoritmer är ett kombinatoriskt problem som datorsökningar, med eller utan mänsklig hjälp, är väl lämpade för. Men alla matematiska problem är inte så lätta att slå fast. Om maskininlärning kan upptäcka en kvalitativt ny algoritmisk idé, sa han, "det här skulle då vara en spelförändring."