Introductie
Wiskundigen houden van een goede puzzel. Zelfs zoiets abstracts als het vermenigvuldigen van matrices (tweedimensionale tabellen met getallen) kan aanvoelen als een spel als je probeert de meest efficiënte manier te vinden om het te doen. Het lijkt een beetje op het oplossen van een Rubik's Cube in zo weinig mogelijk zetten - uitdagend, maar aantrekkelijk. Behalve dat voor een Rubik's Cube het aantal mogelijke zetten bij elke stap 18 is; voor matrixvermenigvuldiging kan elke stap, zelfs in relatief eenvoudige gevallen, meer dan 10 opleveren12 opties.
In de afgelopen 50 jaar hebben onderzoekers dit probleem op vele manieren benaderd, allemaal gebaseerd op computeronderzoeken ondersteund door menselijke intuïtie. Vorige maand liet een team van het kunstmatige-intelligentiebedrijf DeepMind zien hoe het probleem vanuit een nieuwe richting kan worden aangepakt papier in NATUUR dat ze met succes een neuraal netwerk hadden getraind om nieuwe snelle algoritmen voor matrixvermenigvuldiging te ontdekken. Het was alsof de AI een onbekende strategie had gevonden om een monsterlijk complexe Rubik's Cube op te lossen.
"Het is een heel mooi resultaat," zei Jos Alman, een computerwetenschapper aan de Columbia University. Maar hij en andere specialisten op het gebied van matrixvermenigvuldiging benadrukten ook dat dergelijke AI-ondersteuning bestaande methoden eerder zal aanvullen dan vervangen, althans op korte termijn. "Het is als een proof of concept voor iets dat een doorbraak zou kunnen worden," zei Alman. Het resultaat helpt onderzoekers eenvoudigweg bij hun zoektocht.
Als om het punt te bewijzen, drie dagen na de NATUUR paper uitkwam, illustreerden een paar Oostenrijkse onderzoekers hoe nieuwe en oude methoden elkaar zouden kunnen aanvullen. Ze gebruikten een conventionele computerondersteunde zoekactie om verder verbeteren een van de algoritmen die het neurale netwerk had ontdekt.
De resultaten suggereren dat, net als bij het oplossen van een Rubik's Cube, het pad naar betere algoritmen vol bochten en bochten zal zijn.
Matrices vermenigvuldigen
Matrixvermenigvuldiging is een van de meest fundamentele en alomtegenwoordige bewerkingen in de hele wiskunde. Om een paar te vermenigvuldigen nPern matrixen, elk met n2 elementen, je vermenigvuldigt en voegt deze elementen samen in bepaalde combinaties om het product te genereren, een derde nPern Matrix. Het standaardrecept voor twee vermenigvuldigen nPern matrixen vereist n3 vermenigvuldigingsbewerkingen, dus een matrix van 2 bij 2 vereist bijvoorbeeld acht vermenigvuldigingen.
Voor grotere matrices, met duizenden rijen en kolommen, wordt dit proces al snel omslachtig. Maar in 1969, de wiskundige Volker Strassen ontdekte een werkwijze voor het vermenigvuldigen van een paar 2-bij-2 matrices met behulp van zeven in plaats van acht vermenigvuldigingsstappen, ten koste van het introduceren van meer optelstappen.
Het algoritme van Strassen is nodeloos ingewikkeld als je gewoon een paar 2-bij-2 matrices wilt vermenigvuldigen. Maar hij realiseerde zich dat het ook zou werken voor grotere matrices. Dat komt omdat de elementen van een matrix zelf matrices kunnen zijn. Een matrix met 20,000 rijen en 20,000 kolommen kan bijvoorbeeld opnieuw worden voorgesteld als een 2-bij-2 matrix waarvan de vier elementen elk 10,000 bij 10,000 matrices zijn. Elk van deze matrices kan vervolgens worden onderverdeeld in vier blokken van 5,000 bij 5,000, enzovoort. Strassen kon zijn methode toepassen om matrices van 2 bij 2 te vermenigvuldigen op elk niveau van deze geneste hiërarchie. Naarmate de matrix groter wordt, groeien de besparingen door minder vermenigvuldigingen.
De ontdekking van Strassen leidde tot een zoektocht naar efficiënte algoritmen voor matrixvermenigvuldiging, die sindsdien twee verschillende subgebieden heeft geïnspireerd. De ene richt zich op een principekwestie: als je je voorstelt twee te vermenigvuldigen nPern matrixen en laat n rennen naar oneindig, hoe schaalt het aantal vermenigvuldigingsstappen in het snelst mogelijke algoritme mee n? De huidig record voor de beste schaal, n2.3728596, behoort toe aan Alman en Virginia Vassilevska Williams, een computerwetenschapper aan het Massachusetts Institute of Technology. (Een recent niet gepubliceerd preprint meldde een kleine verbetering met behulp van een nieuwe techniek.) Maar deze algoritmen zijn van puur theoretisch belang en winnen het van methoden zoals die van Strassen alleen voor absurd grote matrices.
Het tweede deelgebied denkt op kleinere schaal. Kort na het werk van Strassen kwam de Israëlisch-Amerikaanse computerwetenschapper Shmuel Winograd vertoonde dat Strassen een theoretische limiet had bereikt: het is niet mogelijk om 2-bij-2 matrices te vermenigvuldigen met minder dan zeven vermenigvuldigingsstappen. Maar voor alle andere matrixgroottes blijft het minimum aantal vereiste vermenigvuldigingen een open vraag. En snelle algoritmen voor kleine matrices kunnen een buitenmaatse impact hebben, aangezien herhaalde iteraties van zo'n algoritme het Strassen-algoritme kunnen verslaan wanneer matrices van redelijk formaat worden vermenigvuldigd.
Helaas is het aantal mogelijkheden enorm. Zelfs voor matrices van 3 bij 3 "overtreft het aantal mogelijke algoritmen het aantal atomen in het universum", zei Alhussein Fawzi, een DeepMind-onderzoeker en een van de leiders van het nieuwe werk.
Geconfronteerd met dit duizelingwekkende menu van opties, hebben onderzoekers vooruitgang geboekt door matrixvermenigvuldiging om te zetten in wat een totaal ander wiskundig probleem lijkt - een probleem dat gemakkelijker te hanteren is voor computers. Het is mogelijk om de abstracte taak van het vermenigvuldigen van twee matrices voor te stellen als een specifiek soort wiskundig object: een driedimensionale reeks getallen die een tensor wordt genoemd. Onderzoekers kunnen deze tensor vervolgens opsplitsen in een som van elementaire componenten, "rang-1" tensoren genoemd; elk van deze vertegenwoordigt een andere stap in het corresponderende algoritme voor matrixvermenigvuldiging. Dat betekent dat het vinden van een efficiënt vermenigvuldigingsalgoritme neerkomt op het minimaliseren van het aantal termen in een tensorontleding: hoe minder termen, hoe minder stappen.
Zo hebben onderzoekers nieuwe ontdekt algoritmen dat vermenigvuldigen nPern matrices met minder dan de standaard n3 vermenigvuldigingsstappen voor veel kleine matrixgroottes. Maar algoritmen die niet alleen beter presteren dan de standaard, maar ook beter presteren dan het algoritme van Strassen voor kleine matrices, zijn tot nu toe buiten bereik gebleven.
Game On
Het DeepMind-team benaderde het probleem door tensorontbinding om te zetten in een spel voor één speler. Ze begonnen met een deep learning-algoritme dat afstamt van AlphaGo - een andere DeepMind AI die in 2016 het bordspel Go leren spelen goed genoeg om de beste menselijke spelers te verslaan.
Alle deep learning-algoritmen zijn gebouwd rond neurale netwerken: webben van kunstmatige neuronen die in lagen zijn gesorteerd, met verbindingen die in sterkte kunnen variëren en die aangeven in welke mate elk neuron die in de volgende laag beïnvloedt. De sterkte van deze verbindingen wordt aangepast tijdens vele iteraties van een trainingsprocedure, waarbij het neurale netwerk leert elke input die het ontvangt om te zetten in een output die het algoritme helpt zijn algemene doel te bereiken.
In het nieuwe algoritme van DeepMind, genaamd AlphaTensor, vertegenwoordigen de invoer stappen op weg naar een geldig matrixvermenigvuldigingsschema. De eerste invoer in het neurale netwerk is de oorspronkelijke matrixvermenigvuldigingstensor en de uitvoer is de rang-1 tensor die AlphaTensor heeft gekozen voor zijn eerste zet. Het algoritme trekt deze tensor van rang 1 af van de initiële invoer, wat een bijgewerkte tensor oplevert die als nieuwe invoer in het netwerk wordt teruggevoerd. Het proces herhaalt zich totdat uiteindelijk elk element in de starttensor tot nul is teruggebracht, wat betekent dat er geen rang-1 tensoren meer zijn om uit te schakelen.
Op dat moment heeft het neurale netwerk een geldige tensorontleding ontdekt, omdat het wiskundig gegarandeerd is dat de som van alle tensoren van rang 1 precies gelijk is aan de begintensor. En de stappen die nodig waren om daar te komen, kunnen worden terugvertaald in stappen van het overeenkomstige algoritme voor matrixvermenigvuldiging.
Hier is het spel: AlphaTensor ontleedt herhaaldelijk een tensor tot een set rang-1 componenten. Elke keer wordt AlphaTensor beloond als het een manier vindt om het aantal stappen te verminderen. Maar snelkoppelingen naar de overwinning zijn helemaal niet intuïtief, net zoals je soms een perfect geordend gezicht op een Rubik's Cube moet klauteren voordat je de hele zaak kunt oplossen.
Het team had nu een algoritme dat in theorie hun probleem zou kunnen oplossen. Ze moesten het gewoon eerst trainen.
Nieuwe paden
Zoals alle neurale netwerken heeft AlphaTensor veel gegevens nodig om op te trainen, maar de ontleding van tensoren is een notoir moeilijk probleem. Er waren weinig voorbeelden van efficiënte decomposities die de onderzoekers het netwerk konden voeden. In plaats daarvan hielpen ze het algoritme op weg door het te trainen op het veel eenvoudigere inverse probleem: het optellen van een aantal willekeurig gegenereerde tensoren van rang 1.
"Ze gebruiken het gemakkelijke probleem om meer gegevens te produceren voor het moeilijke probleem," zei Michaël Littman, een computerwetenschapper aan de Brown University. Het combineren van deze achterwaartse trainingsprocedure met versterkend leren, waarbij AlphaTensor zijn eigen trainingsgegevens genereerde terwijl het blunderde op zoek naar efficiënte decomposities, werkte veel beter dan beide trainingsmethoden afzonderlijk.
Het DeepMind-team heeft AlphaTensor getraind om tensoren te ontleden die de vermenigvuldiging van matrices tot 12 bij 12 vertegenwoordigen. Het zocht naar snelle algoritmen voor het vermenigvuldigen van matrices van gewone reële getallen en ook naar algoritmen die specifiek zijn voor een meer beperkte instelling die bekend staat als modulo 2-rekenkunde. (Dit is wiskunde gebaseerd op slechts twee getallen, dus matrixelementen kunnen alleen 0 of 1 zijn, en 1 + 1 = 0.) Onderzoekers beginnen vaak met deze meer beperkte maar nog steeds enorme ruimte, in de hoop dat hier ontdekte algoritmen kunnen worden aangepast aan werken aan matrices van reële getallen.
Na training herontdekte AlphaTensor het algoritme van Strassen binnen enkele minuten. Vervolgens ontdekte het tot duizenden nieuwe snelle algoritmen voor elke matrixgrootte. Deze waren anders dan de bekendste algoritmen, maar hadden hetzelfde aantal vermenigvuldigingsstappen.
In enkele gevallen versloeg AlphaTensor zelfs bestaande records. De meest verrassende ontdekkingen vonden plaats in modulo 2-rekenkunde, waar het een nieuw algoritme vond voor het vermenigvuldigen van 4-bij-4 matrices in 47 vermenigvuldigingsstappen, een verbetering ten opzichte van de 49 stappen die nodig zijn voor twee iteraties van het algoritme van Strassen. Het versloeg ook het bekendste algoritme voor 5-bij-5 modulo 2-matrices, waardoor het aantal vereiste vermenigvuldigingen van het vorige record van 98 naar 96 werd teruggebracht. (Maar dit nieuwe record loopt nog steeds achter op de 91 stappen die nodig zouden zijn om Strassen's algoritme met behulp van 5-bij-5 matrices.)
Het nieuwe spraakmakende resultaat zorgde voor veel opwinding, met sommige onderzoekers veel lof voor de op AI gebaseerde verbetering van de status quo. Maar niet iedereen in de matrixvermenigvuldigingsgemeenschap was zo onder de indruk. "Ik had het gevoel dat het een beetje overhyped was", zei Vassilevska Williams. “Het is een ander hulpmiddel. Het is niet zo van: 'Oh, de computers verslaan de mensen', weet je?"
Onderzoekers benadrukten ook dat onmiddellijke toepassingen van het recordbrekende 4-bij-4-algoritme beperkt zouden zijn: niet alleen is het alleen geldig in modulo 2-rekenkunde, maar in het echte leven zijn er naast snelheid ook belangrijke overwegingen.
Fawzi was het ermee eens dat dit echt nog maar het begin is. "Er is veel ruimte voor verbetering en onderzoek, en dat is een goede zaak", zei hij.
Een laatste draai
De grootste kracht van AlphaTensor ten opzichte van gevestigde computerzoekmethoden is ook de grootste zwakte: het wordt niet beperkt door menselijke intuïtie over hoe goede algoritmen eruit zien, dus het kan zijn keuzes niet verklaren. Dat maakt het moeilijk voor onderzoekers om te leren van de prestaties.
Maar dit is misschien niet zo'n groot nadeel als het lijkt. Een paar dagen na het AlphaTensor-resultaat, de wiskundige Manuel Kauers en zijn afstudeerder Jakob Moosbauer, beiden van de Johannes Kepler Universiteit Linz in Oostenrijk, rapporteerden weer een stap voorwaarts.
Introductie
Toen de DeepMind-paper uitkwam, waren Kauers en Moosbauer bezig met het zoeken naar nieuwe vermenigvuldigingsalgoritmen met behulp van een conventionele computerondersteunde zoekopdracht. Maar in tegenstelling tot de meeste van dergelijke zoekopdrachten, die opnieuw beginnen met een nieuw leidend principe, werkt hun methode door herhaaldelijk een bestaand algoritme aan te passen in de hoop er meer vermenigvuldigingsbesparingen uit te persen. Met het algoritme van AlphaTensor voor 5-bij-5 modulo 2-matrices als uitgangspunt, ontdekten ze tot hun verrassing dat hun methode het aantal stappen van vermenigvuldiging na slechts enkele seconden rekentijd terugbracht van 96 naar 95.
AlphaTensor heeft hen ook indirect geholpen om nog een verbetering te realiseren. Eerder hadden Kauers en Moosbauer niet de moeite genomen om de ruimte van 4-bij-4 matrices te verkennen, in de overtuiging dat het niet mogelijk zou zijn om twee iteraties van het algoritme van Strassen te verslaan. Het AlphaTensor-resultaat bracht hen ertoe om te heroverwegen, en na een week van rekentijd vanaf nul, leverde hun methode een ander algoritme op van 47 stappen dat niets te maken had met het algoritme dat AlphaTensor had ontdekt. "Als iemand ons had verteld dat er iets te ontdekken valt voor 4-bij-4, dan hadden we dat eerder kunnen doen", aldus Kauers. “Maar oké, nou, zo werkt het.”
Littman verwacht meer van dergelijke verrassingen en vergelijkt de situatie met de eerste keer dat een hardloper een mijl in minder dan vier minuten aflegde, een prestatie die algemeen als onmogelijk werd beschouwd. "Mensen hadden zoiets van 'Oh, wacht, we kunnen dit', en nu kunnen veel mensen het," zei hij.
Vooruitkijkend hoopt Fawzi AlphaTensor te generaliseren om een breder scala aan wiskundige en computationele taken aan te pakken, net zoals zijn voorloper AlphaGo zich uiteindelijk vertakte naar andere spellen.
Kauers ziet dit als de ware lakmoesproef voor de toepassing van machine learning bij het ontdekken van nieuwe algoritmen. Hij wijst erop dat de zoektocht naar algoritmen voor snelle matrixvermenigvuldiging een combinatorisch probleem is waarvoor computeronderzoek, met of zonder menselijke hulp, zeer geschikt is. Maar niet alle wiskundige problemen zijn zo gemakkelijk vast te pinnen. Als machine learning een kwalitatief nieuw algoritmisch idee kan ontdekken, zei hij, "zou dit een game changer zijn."
