Deep Mind AlphaTensor zal nieuwe algoritmen ontdekken

Deep Mind heeft AlphaZero uitgebreid naar wiskunde om nieuwe mogelijkheden voor onderzoeksalgoritmen te ontsluiten.

AlphaTensor bouwt voort op AlphaZero, een agent die bovenmenselijke prestaties heeft geleverd in bordspellen, zoals schaken, Go en shogi, en dit werk toont de reis van AlphaZero van het spelen van games naar het voor het eerst aanpakken van onopgeloste wiskundige problemen.

De oude Egyptenaren creëerden een algoritme om twee getallen te vermenigvuldigen zonder dat een vermenigvuldigingstabel nodig was, en de Griekse wiskundige Euclid beschreef een algoritme om de grootste gemene deler te berekenen, dat nog steeds in gebruik is.

Tijdens de Islamitische Gouden Eeuw ontwierp de Perzische wiskundige Muhammad ibn Musa al-Khwarizmi nieuwe algoritmen om lineaire en kwadratische vergelijkingen op te lossen. In feite leidde de naam van al-Khwarizmi, in het Latijn vertaald als Algoritmi, tot de term algoritme. Maar ondanks de bekendheid met algoritmen van tegenwoordig - die in de hele samenleving worden gebruikt, van klasalgebra tot geavanceerd wetenschappelijk onderzoek - is het ontdekken van nieuwe algoritmen ongelooflijk moeilijk, en een voorbeeld van de verbazingwekkende redeneercapaciteiten van de menselijke geest.

Ze publiceerden in Nature. AlphaTensor is het eerste kunstmatige intelligentiesysteem (AI) voor het ontdekken van nieuwe, efficiënte en aantoonbaar correcte algoritmen voor fundamentele taken zoals matrixvermenigvuldiging. Dit werpt licht op een 50 jaar oude open vraag in de wiskunde over het vinden van de snelste manier om twee matrices te vermenigvuldigen.

AlphaTensor is helemaal opnieuw getraind en ontdekt algoritmen voor matrixvermenigvuldiging die efficiënter zijn dan bestaande door mensen en computers ontworpen algoritmen. Ondanks verbetering ten opzichte van bekende algoritmen, merken ze op dat een beperking van AlphaTensor de noodzaak is om vooraf een reeks potentiële factorinvoer F te definiëren, wat de zoekruimte discretiseert, maar mogelijk kan leiden tot het mislopen van efficiënte algoritmen. Een interessante richting voor toekomstig onderzoek is om AlphaTensor aan te passen om naar F te zoeken. Een belangrijke kracht van AlphaTensor is de flexibiliteit om complexe stochastische en niet-differentieerbare beloningen te ondersteunen (van de tensorrang tot praktische efficiëntie op specifieke hardware), naast het vinden van algoritmen voor aangepaste bewerkingen in een grote verscheidenheid aan ruimten (zoals eindige velden). Ze geloven dat dit toepassingen van AlphaTensor zal aanzetten tot het ontwerpen van algoritmen die meetwaarden optimaliseren die we hier niet hebben overwogen, zoals numerieke stabiliteit of energieverbruik.

De ontdekking van matrixvermenigvuldigingsalgoritmen heeft verstrekkende implicaties, aangezien matrixvermenigvuldiging de kern vormt van veel rekentaken, zoals matrixinversie, het berekenen van de determinant en het oplossen van lineaire systemen.

Het proces en de voortgang van het automatiseren van algoritmische ontdekking
Ten eerste hebben ze het probleem van het vinden van efficiënte algoritmen voor matrixvermenigvuldiging omgezet in een spel voor één speler. In dit spel is het bord een driedimensionale tensor (array van getallen), die aangeeft hoe ver het huidige algoritme niet correct is. Door middel van een reeks toegestane zetten, die overeenkomen met de instructies van het algoritme, probeert de speler de tensor te wijzigen en de invoer op nul te zetten. Wanneer de speler hierin slaagt, resulteert dit in een aantoonbaar correct matrixvermenigvuldigingsalgoritme voor elk paar matrices, en de efficiëntie ervan wordt bepaald door het aantal stappen dat is genomen om de tensor op nul te zetten.

Deze game is ongelooflijk uitdagend - het aantal mogelijke algoritmen om te overwegen is veel groter dan het aantal atomen in het universum, zelfs voor kleine gevallen van matrixvermenigvuldiging. Vergeleken met het spel Go, dat decennialang een uitdaging bleef voor AI, is het aantal mogelijke zetten bij elke stap van hun spel 30 ordes van grootte groter (meer dan 10^33 voor een van de instellingen die ze overwegen).

Om dit spel goed te spelen, moet je in wezen de kleinste naalden in een gigantische hooiberg aan mogelijkheden identificeren. Om de uitdagingen van dit domein aan te pakken, dat aanzienlijk afwijkt van traditionele games, hebben we meerdere cruciale componenten ontwikkeld, waaronder een nieuwe neurale netwerkarchitectuur die probleemspecifieke inductieve vooroordelen bevat, een procedure om bruikbare synthetische gegevens te genereren en een recept om gebruik te maken van symmetrieën van de probleem.

Vervolgens trainden ze een AlphaTensor-agent met behulp van wapeningsleren om het spel te spelen, te beginnen zonder enige kennis van bestaande matrixvermenigvuldigingsalgoritmen. Door te leren verbetert AlphaTensor in de loop van de tijd geleidelijk, waarbij historische snelle matrixvermenigvuldigingsalgoritmen zoals die van Strassen opnieuw worden ontdekt, en uiteindelijk het rijk van de menselijke intuïtie overtreffen en algoritmen sneller ontdekken dan voorheen bekend was.

Onderzoek naar de impact op toekomstig onderzoek en toepassingen
Vanuit wiskundig oogpunt kunnen hun resultaten als leidraad dienen voor verder onderzoek in de complexiteitstheorie, die tot doel heeft de snelste algoritmen te bepalen voor het oplossen van computationele problemen. Door de ruimte van mogelijke algoritmen op een effectievere manier te verkennen dan eerdere benaderingen, helpt AlphaTensor ons inzicht in de rijkdom van matrixvermenigvuldigingsalgoritmen te vergroten. Inzicht in deze ruimte kan nieuwe resultaten opleveren voor het helpen bepalen van de asymptotische complexiteit van matrixvermenigvuldiging, een van de meest fundamentele open problemen in de informatica.

Omdat matrixvermenigvuldiging een kerncomponent is in veel computertaken, waaronder computergraphics, digitale communicatie, neurale netwerktraining en wetenschappelijk computergebruik, zouden door AlphaTensor ontdekte algoritmen berekeningen op deze gebieden aanzienlijk efficiënter kunnen maken. De flexibiliteit van AlphaTensor om elk soort doelstelling te overwegen, zou ook kunnen leiden tot nieuwe toepassingen voor het ontwerpen van algoritmen die statistieken zoals energieverbruik en numerieke stabiliteit optimaliseren, en helpen voorkomen dat kleine afrondingsfouten sneeuwballen terwijl een algoritme werkt.

Hoewel ze zich hier concentreerden op het specifieke probleem van matrixvermenigvuldiging, hopen we dat ons artikel anderen zal inspireren om AI te gebruiken om algoritmische ontdekkingen te begeleiden voor andere fundamentele rekentaken. Hun onderzoek toont ook aan dat AlphaZero een krachtig algoritme is dat tot ver buiten het domein van traditionele games kan worden uitgebreid om open problemen in de wiskunde op te lossen. Voortbouwend op ons onderzoek hopen ze een groter oeuvre aan te moedigen door AI toe te passen om de samenleving te helpen bij het oplossen van enkele van de belangrijkste uitdagingen in de wiskunde en in de wetenschappen.

Natuur - Snellere algoritmen voor matrixvermenigvuldiging ontdekken met versterkingsleren

Abstract
Het verbeteren van de efficiëntie van algoritmen voor fundamentele berekeningen kan een wijdverbreide impact hebben, omdat het de algehele snelheid van een groot aantal berekeningen kan beïnvloeden. Matrixvermenigvuldiging is zo'n primitieve taak die in veel systemen voorkomt, van neurale netwerken tot wetenschappelijke computerroutines. De automatische ontdekking van algoritmen met behulp van machine learning biedt het vooruitzicht om verder te reiken dan de menselijke intuïtie en beter te presteren dan de huidige beste door mensen ontworpen algoritmen. Het automatiseren van de algoritme-ontdekkingsprocedure is echter ingewikkeld, omdat de ruimte van mogelijke algoritmen enorm is. Hier rapporteren we een diepgaande leeraanpak op basis van AlphaZero1 voor het ontdekken van efficiënte en aantoonbaar correcte algoritmen voor de vermenigvuldiging van willekeurige matrices. Onze agent, AlphaTensor, is getraind om een ​​spel voor één speler te spelen waarbij het doel is om tensordecomposities te vinden binnen een eindige factorruimte. AlphaTensor ontdekte algoritmen die de state-of-the-art complexiteit voor veel matrixgroottes overtreffen. Bijzonder relevant is het geval van 4 × 4-matrices in een eindig veld, waar het algoritme van AlphaTensor voor het eerst, voor zover wij weten, sinds de ontdekking ervan 50 jaar geleden het Strassen-algoritme op twee niveaus verbetert2. We demonstreren verder de flexibiliteit van AlphaTensor door middel van verschillende use-cases: algoritmen met ultramoderne complexiteit voor gestructureerde matrixvermenigvuldiging en verbeterde praktische efficiëntie door matrixvermenigvuldiging te optimaliseren voor runtime op specifieke hardware. Onze resultaten benadrukken het vermogen van AlphaTensor om het proces van algoritmische ontdekking van een reeks problemen te versnellen en te optimaliseren voor verschillende criteria.