AlphaTensor, bygger på AlphaZero, en agent som har visat övermänskliga prestationer i brädspel, som schack, Go och shogi, och detta arbete visar AlphaZeros resa från att spela spel till att ta itu med olösta matematiska problem för första gången.
De forntida egyptierna skapade en algoritm för att multiplicera två tal utan att behöva en multiplikationstabell, och den grekiske matematikern Euclid beskrev en algoritm för att beräkna den största gemensamma divisorn, som fortfarande används idag.
Under den islamiska guldåldern designade den persiske matematikern Muhammad ibn Musa al-Khwarizmi nya algoritmer för att lösa linjära och kvadratiska ekvationer. Faktum är att al-Khwarizmis namn, översatt till latin som Algoritmi, ledde till termen algoritm. Men trots förtrogenhet med algoritmer idag – som används i hela samhället från klassrumsalgebra till avancerad vetenskaplig forskning – är processen att upptäcka nya algoritmer otroligt svår, och ett exempel på det mänskliga sinnets fantastiska resonemangsförmåga.
De publicerade i Nature. AlphaTensor är det första artificiella intelligenssystemet (AI) för att upptäcka nya, effektiva och bevisligen korrekta algoritmer för grundläggande uppgifter som matrismultiplikation. Detta belyser en 50 år gammal öppen fråga i matematik om att hitta det snabbaste sättet att multiplicera två matriser.
Utbildad från grunden upptäcker AlphaTensor matrismultiplikationsalgoritmer som är mer effektiva än befintliga mänskliga och datordesignade algoritmer. Trots förbättringar jämfört med kända algoritmer, noterar de att en begränsning av AlphaTensor är behovet av att fördefiniera en uppsättning potentiella faktorposter F, vilket diskretiserar sökutrymmet men kan möjligen leda till att effektiva algoritmer går miste om. En intressant riktning för framtida forskning är att anpassa AlphaTensor för att söka efter F. En viktig styrka med AlphaTensor är dess flexibilitet att stödja komplexa stokastiska och icke-differentiera belöningar (från tensorrankningen till praktisk effektivitet på specifik hårdvara), förutom att hitta algoritmer för anpassade operationer i en mängd olika utrymmen (som ändliga fält). De tror att detta kommer att sporra tillämpningar av AlphaTensor mot att designa algoritmer som optimerar mätvärden som vi inte övervägde här, såsom numerisk stabilitet eller energianvändning.
Upptäckten av matrismultiplikationsalgoritmer har långtgående implikationer, eftersom matrismultiplikation är kärnan i många beräkningsuppgifter, såsom matrisinversion, beräkning av determinanten och lösning av linjära system.
Processen och framstegen för att automatisera algoritmisk upptäckt
Först konverterade de problemet med att hitta effektiva algoritmer för matrismultiplikation till ett enspelarspel. I det här spelet är brädet en tredimensionell tensor (array av siffror), som fångar hur långt ifrån korrekt den aktuella algoritmen är. Genom en uppsättning tillåtna drag, motsvarande algoritminstruktioner, försöker spelaren modifiera tensorn och nollställa dess poster. När spelaren lyckas göra det resulterar detta i en bevisligen korrekt matrismultiplikationsalgoritm för valfritt matrispar, och dess effektivitet fångas av antalet steg som tas för att nollställa tensorn.
Det här spelet är otroligt utmanande – antalet möjliga algoritmer att överväga är mycket större än antalet atomer i universum, även för små fall av matrismultiplikation. Jämfört med spelet Go, som förblev en utmaning för AI i decennier, är antalet möjliga drag i varje steg i deras spel 30 storleksordningar större (över 10^33 för en av inställningarna de anser).
I grund och botten, för att spela det här spelet bra, måste man identifiera de minsta nålarna i en gigantisk höstack av möjligheter. För att ta itu med utmaningarna i denna domän, som avsevärt avviker från traditionella spel, utvecklade vi flera viktiga komponenter inklusive en ny neural nätverksarkitektur som innehåller problemspecifika induktiva fördomar, en procedur för att generera användbar syntetisk data och ett recept för att utnyttja symmetrierna i problem.
De tränade sedan en AlphaTensor-agent med hjälp av förstärkningsinlärning för att spela spelet, med början utan någon kunskap om befintliga matrismultiplikationsalgoritmer. Genom inlärning förbättras AlphaTensor gradvis över tiden, återupptäcker historiska snabba matrismultiplikationsalgoritmer som Strassens, överträffar så småningom den mänskliga intuitionens område och upptäcker algoritmer snabbare än tidigare känt.
Utforska inverkan på framtida forskning och tillämpningar
Ur en matematisk synvinkel kan deras resultat vägleda vidare forskning inom komplexitetsteori, som syftar till att bestämma de snabbaste algoritmerna för att lösa beräkningsproblem. Genom att utforska utrymmet för möjliga algoritmer på ett mer effektivt sätt än tidigare tillvägagångssätt, hjälper AlphaTensor till att främja vår förståelse av rikedomen hos matrismultiplikationsalgoritmer. Att förstå detta utrymme kan låsa upp nya resultat för att hjälpa till att bestämma den asymptotiska komplexiteten av matrismultiplikation, ett av de mest grundläggande öppna problemen inom datavetenskap.
Eftersom matrismultiplikation är en kärnkomponent i många beräkningsuppgifter, som omfattar datorgrafik, digital kommunikation, utbildning i neurala nätverk och vetenskaplig beräkning, kan AlphaTensor-upptäckta algoritmer göra beräkningar inom dessa områden betydligt effektivare. AlphaTensors flexibilitet att överväga alla typer av mål kan också stimulera till nya applikationer för att designa algoritmer som optimerar mätvärden som energianvändning och numerisk stabilitet, vilket hjälper till att förhindra små avrundningsfel från att snöa runt när en algoritm fungerar.
Medan de fokuserade här på det speciella problemet med matrismultiplikation, hoppas vi att vår artikel kommer att inspirera andra att använda AI för att vägleda algoritmisk upptäckt för andra grundläggande beräkningsuppgifter. Deras forskning visar också att AlphaZero är en kraftfull algoritm som kan utvidgas långt utanför domänen för traditionella spel för att hjälpa till att lösa öppna problem i matematik. Med utgångspunkt i vår forskning hoppas de kunna stimulera till ett större arbete – att tillämpa AI för att hjälpa samhället att lösa några av de viktigaste utmaningarna inom matematik och vetenskaper.
Nature – Upptäck snabbare matrismultiplikationsalgoritmer med förstärkningsinlärning
Abstrakt
Att förbättra effektiviteten hos algoritmer för grundläggande beräkningar kan ha en utbredd effekt, eftersom det kan påverka den totala hastigheten för en stor mängd beräkningar. Matrismultiplikation är en sådan primitiv uppgift, som förekommer i många system - från neurala nätverk till vetenskapliga beräkningsrutiner. Den automatiska upptäckten av algoritmer med hjälp av maskininlärning erbjuder möjligheten att nå bortom mänsklig intuition och överträffa de nuvarande bästa mänskligt designade algoritmerna. Att automatisera proceduren för upptäckt av algoritmer är dock komplicerad, eftersom utrymmet för möjliga algoritmer är enormt. Här rapporterar vi en djup förstärkningsinlärningsmetod baserad på AlphaZero1 för att upptäcka effektiva och bevisligen korrekta algoritmer för multiplikation av godtyckliga matriser. Vår agent, AlphaTensor, är utbildad för att spela ett enspelarspel där målet är att hitta tensornedbrytningar inom ett ändligt faktorutrymme. AlphaTensor upptäckte algoritmer som överträffar den senaste komplexiteten för många matrisstorlekar. Särskilt relevant är fallet med 4 × 4 matriser i ett ändligt fält, där AlphaTensors algoritm förbättrar Strassens tvånivåalgoritm för första gången, såvitt vi vet, sedan upptäckten för 50 år sedan2. Vi visar vidare flexibiliteten hos AlphaTensor genom olika användningsfall: algoritmer med toppmodern komplexitet för strukturerad matrismultiplikation och förbättrad praktisk effektivitet genom att optimera matrismultiplikation för körtid på specifik hårdvara. Våra resultat belyser AlphaTensors förmåga att påskynda processen för algoritmisk upptäckt av en rad problem och att optimera för olika kriterier.
Brian Wang är en futuristisk tankeledare och en populär vetenskapbloggare med 1 miljon läsare per månad. Hans blogg Nextbigfuture.com är rankad som nummer 1 Science News Blog. Den täcker många störande teknik och trender, inklusive rymd, robotik, artificiell intelligens, medicin, anti-aging bioteknik och nanoteknik.
Känd för att identifiera banbrytande teknik, han är för närvarande en av grundarna av en start och insamling för högpotentiella företag i ett tidigt skede. Han är forskningschef för tilldelningar för djupa teknikinvesteringar och en ängelinvesterare på Space Angels.
Han har ofta varit talare på företag och har varit TEDx -talare, talare vid Singularity University och gäst på många intervjuer för radio och podcaster. Han är öppen för offentliga tal och rådgivning.
