Einleitung
Mathematiker lieben ein gutes Puzzle. Sogar etwas so Abstraktes wie das Multiplizieren von Matrizen (zweidimensionale Zahlentabellen) kann sich wie ein Spiel anfühlen, wenn Sie versuchen, den effizientesten Weg dafür zu finden. Es ist ein bisschen wie der Versuch, einen Rubik's Cube in so wenigen Zügen wie möglich zu lösen – herausfordernd, aber verlockend. Abgesehen davon, dass bei einem Rubik's Cube die Anzahl der möglichen Züge bei jedem Schritt 18 beträgt; Bei der Matrixmultiplikation kann selbst in relativ einfachen Fällen jeder Schritt mehr als 10 darstellen12 Optionen.
In den letzten 50 Jahren haben Forscher dieses Problem auf vielfältige Weise angegangen, alle basierend auf Computersuchen, unterstützt durch menschliche Intuition. Letzten Monat zeigte ein Team des Unternehmens für künstliche Intelligenz DeepMind, wie man das Problem aus einer neuen Richtung angehen kann, und berichtete in a Krepppapier in Natur dass sie ein neuronales Netzwerk erfolgreich darauf trainiert hatten, neue schnelle Algorithmen für die Matrixmultiplikation zu entdecken. Es war, als hätte die KI eine unbekannte Strategie gefunden, um einen ungeheuer komplexen Rubik's Cube zu lösen.
„Das ist ein sehr ordentliches Ergebnis“, sagte er Josh Alma, Informatiker an der Columbia University. Aber er und andere Matrixmultiplikationsspezialisten betonten auch, dass eine solche KI-Unterstützung bestehende Methoden eher ergänzen als ersetzen wird – zumindest kurzfristig. „Es ist wie ein Machbarkeitsnachweis für etwas, das ein Durchbruch werden könnte“, sagte Alman. Das Ergebnis wird den Forschern einfach bei ihrer Suche helfen.
Wie um den Punkt zu beweisen, drei Tage nach dem Natur herauskam, veranschaulichten zwei österreichische Forscher, wie sich neue und alte Methoden ergänzen könnten. Dazu nutzten sie eine herkömmliche computergestützte Suche weiter verbessern einer der Algorithmen, die das neuronale Netzwerk entdeckt hatte.
Die Ergebnisse deuten darauf hin, dass der Weg zu besseren Algorithmen ebenso wie das Lösen eines Rubik's Cube voller Drehungen und Wendungen sein wird.
Matrizen multiplizieren
Die Matrixmultiplikation ist eine der grundlegendsten und allgegenwärtigsten Operationen in der gesamten Mathematik. Um ein Paar zu multiplizieren n-By-n Matrizen, jeweils mit n2 Elemente multiplizieren und addieren Sie diese Elemente in bestimmten Kombinationen, um das Produkt zu erzeugen, ein Drittel n-By-n Matrix. Das Standardrezept zum Multiplizieren von zwei n-By-n Matrizen erfordert n3 Multiplikationsoperationen, sodass beispielsweise eine 2-mal-2-Matrix acht Multiplikationen erfordert.
Bei größeren Matrizen mit Tausenden von Zeilen und Spalten wird dieser Vorgang schnell umständlich. Aber 1969 der Mathematiker Volker Strassen ein Verfahren entdeckt zum Multiplizieren eines Paares von 2-mal-2-Matrizen unter Verwendung von sieben statt acht Multiplikationsschritten auf Kosten der Einführung weiterer Additionsschritte.
Der Algorithmus von Strassen ist unnötig kompliziert, wenn Sie nur ein Paar 2-mal-2-Matrizen multiplizieren möchten. Aber er erkannte, dass es auch für größere Matrizen funktionieren würde. Das liegt daran, dass die Elemente einer Matrix selbst Matrizen sein können. Beispielsweise kann eine Matrix mit 20,000 Zeilen und 20,000 Spalten als 2-mal-2-Matrix neu gedacht werden, deren vier Elemente jeweils 10,000-mal-10,000-Matrizen sind. Jede dieser Matrizen kann dann in vier 5,000-mal-5,000-Blöcke unterteilt werden und so weiter. Strassen könnte seine Methode anwenden, um 2-mal-2-Matrizen auf jeder Ebene dieser verschachtelten Hierarchie zu multiplizieren. Mit zunehmender Matrixgröße wachsen die Einsparungen durch weniger Multiplikationen.
Die Entdeckung von Strassen führte zu einer Suche nach effizienten Algorithmen für die Matrixmultiplikation, die seitdem zwei unterschiedliche Teilgebiete inspiriert hat. Man konzentriert sich auf eine Grundsatzfrage: Wenn Sie sich vorstellen, zwei zu multiplizieren n-By-n Matrizen und lassen n gegen unendlich laufen, wie skaliert die Anzahl der Multiplikationsschritte im schnellstmöglichen Algorithmus mit n? Das derzeitiger Rekord für die beste Skalierung, n2.3728596, gehört Alman und Virginia Vassilevska Williams, Informatiker am Massachusetts Institute of Technology. (Eine kürzlich unveröffentlichte Preprint berichteten von einer winzigen Verbesserung durch eine neue Technik.) Aber diese Algorithmen sind von rein theoretischem Interesse und siegen gegenüber Methoden wie dem von Strassen nur für absurd große Matrizen.
Das zweite Teilgebiet denkt in kleineren Maßstäben. Bald nach Strassens Arbeit kam der israelisch-amerikanische Informatiker Shmuel Winograd zeigte dass Strassen eine theoretische Grenze erreicht hatte: Es ist nicht möglich, 2-mal-2-Matrizen mit weniger als sieben Multiplikationsschritten zu multiplizieren. Aber für alle anderen Matrixgrößen bleibt die minimale Anzahl der erforderlichen Multiplikationen eine offene Frage. Und schnelle Algorithmen für kleine Matrizen könnten einen übergroßen Einfluss haben, da wiederholte Iterationen eines solchen Algorithmus den Algorithmus von Strassen schlagen könnten, wenn Matrizen angemessener Größe multipliziert werden.
Leider ist die schiere Anzahl an Möglichkeiten riesig. Selbst für 3-mal-3-Matrizen „übersteigt die Anzahl möglicher Algorithmen die Anzahl der Atome im Universum“, sagte er Alhussein Fawzi, ein DeepMind-Forscher und einer der Leiter der neuen Arbeit.
Angesichts dieser schwindelerregenden Auswahl an Optionen haben Forscher Fortschritte gemacht, indem sie die Matrizenmultiplikation in ein scheinbar völlig anderes mathematisches Problem umgewandelt haben – eines, das für Computer einfacher zu handhaben ist. Es ist möglich, die abstrakte Aufgabe, zwei Matrizen zu multiplizieren, als eine bestimmte Art von mathematischem Objekt darzustellen: ein dreidimensionales Array von Zahlen, das als Tensor bezeichnet wird. Forscher können diesen Tensor dann in eine Summe elementarer Komponenten zerlegen, die als „Rang-1“-Tensoren bezeichnet werden; jede davon repräsentiert einen anderen Schritt in dem entsprechenden Matrixmultiplikationsalgorithmus. Das bedeutet, dass das Finden eines effizienten Multiplikationsalgorithmus darauf hinausläuft, die Anzahl der Terme in einer Tensorzerlegung zu minimieren – je weniger Terme, desto weniger Schritte sind erforderlich.
Auf diese Weise haben Forscher Neues entdeckt Algorithmen die sich vermehren n-By-n Matrizen mit weniger als dem Standard n3 Multiplikationsschritte für viele kleine Matrixgrößen. Aber Algorithmen, die nicht nur den Standard, sondern auch Strassens Algorithmus für kleine Matrizen übertreffen, blieben unerreichbar – bis jetzt.
Spiel weiter
Das DeepMind-Team ging das Problem an, indem es die Tensorzerlegung in ein Einzelspieler-Spiel verwandelte. Sie begannen mit einem Deep-Learning-Algorithmus, der von AlphaGo abstammt – einer weiteren DeepMind-KI aus dem Jahr 2016 lernte das Brettspiel Go zu spielen gut genug, um die besten menschlichen Spieler zu schlagen.
Alle Deep-Learning-Algorithmen basieren auf neuronalen Netzwerken: Netze aus künstlichen Neuronen, die in Schichten sortiert sind, wobei die Verbindungen unterschiedlich stark sein können, um darzustellen, wie stark jedes Neuron die in der nächsten Schicht beeinflusst. Die Stärke dieser Verbindungen wird über viele Iterationen eines Trainingsverfahrens optimiert, während dessen das neuronale Netzwerk lernt, jede Eingabe, die es erhält, in eine Ausgabe umzuwandeln, die dem Algorithmus hilft, sein Gesamtziel zu erreichen.
Im neuen Algorithmus von DeepMind mit dem Namen AlphaTensor stellen die Eingaben Schritte auf dem Weg zu einem gültigen Matrixmultiplikationsschema dar. Die erste Eingabe in das neuronale Netzwerk ist der ursprüngliche Matrixmultiplikationstensor, und seine Ausgabe ist der Rang-1-Tensor, den AlphaTensor für seinen ersten Zug ausgewählt hat. Der Algorithmus subtrahiert diesen Rang-1-Tensor von der anfänglichen Eingabe und ergibt einen aktualisierten Tensor, der als neue Eingabe in das Netzwerk zurückgeführt wird. Der Vorgang wiederholt sich, bis schließlich jedes Element im Starttensor auf Null reduziert wurde, was bedeutet, dass es keine Rang-1-Tensoren mehr zu entfernen gibt.
An diesem Punkt hat das neuronale Netzwerk eine gültige Tensorzerlegung entdeckt, da mathematisch garantiert ist, dass die Summe aller Rang-1-Tensoren genau gleich dem Starttensor ist. Und die Schritte, die nötig waren, um dorthin zu gelangen, können in Schritte des entsprechenden Matrixmultiplikationsalgorithmus zurückübersetzt werden.
Hier ist das Spiel: AlphaTensor zerlegt einen Tensor wiederholt in eine Menge von Rang-1-Komponenten. AlphaTensor wird jedes Mal belohnt, wenn es einen Weg findet, die Anzahl der Schritte zu reduzieren. Aber Abkürzungen zum Sieg sind überhaupt nicht intuitiv, genauso wie Sie manchmal ein perfekt geordnetes Gesicht auf einem Rubik's Cube durcheinander bringen müssen, bevor Sie das Ganze lösen können.
Das Team hatte nun einen Algorithmus, der theoretisch ihr Problem lösen könnte. Sie mussten es nur erst trainieren.
Neue Wege
Wie alle neuronalen Netze benötigt AlphaTensor viele Daten zum Trainieren, aber die Tensorzerlegung ist ein notorisch schwieriges Problem. Es gab nur wenige Beispiele für effiziente Zerlegungen, die die Forscher in das Netzwerk einspeisen konnten. Stattdessen halfen sie dem Algorithmus beim Einstieg, indem sie ihn auf das viel einfachere inverse Problem trainierten: das Addieren einer Reihe zufällig generierter Rang-1-Tensoren.
„Sie verwenden das einfache Problem, um mehr Daten für das schwierige Problem zu produzieren“, sagte er Michael Littmann, Informatiker an der Brown University. Die Kombination dieses Rückwärtstrainingsverfahrens mit Reinforcement Learning, bei dem AlphaTensor seine eigenen Trainingsdaten generierte, während es herumstolperte und nach effizienten Zerlegungen suchte, funktionierte viel besser als jede Trainingsmethode für sich allein.
Das DeepMind-Team trainierte AlphaTensor, um Tensoren zu zerlegen, die die Multiplikation von Matrizen bis zu 12-mal-12 darstellen. Es wurde nach schnellen Algorithmen zum Multiplizieren von Matrizen gewöhnlicher reeller Zahlen und auch nach Algorithmen gesucht, die für eine eingeschränktere Einstellung, die als Modulo-2-Arithmetik bekannt ist, spezifisch sind. (Dies ist Mathematik, die auf nur zwei Zahlen basiert, sodass Matrixelemente nur 0 oder 1 und 1 + 1 = 0 sein können.) Forscher beginnen oft mit diesem eingeschränkteren, aber immer noch riesigen Raum, in der Hoffnung, dass die hier entdeckten Algorithmen daran angepasst werden können Arbeit an Matrizen reeller Zahlen.
Nach dem Training entdeckte AlphaTensor den Algorithmus von Strassen innerhalb von Minuten wieder. Anschließend wurden bis zu Tausende neuer schneller Algorithmen für jede Matrixgröße entdeckt. Diese unterschieden sich von den bekanntesten Algorithmen, hatten aber die gleiche Anzahl an Multiplikationsschritten.
In einigen Fällen schlug AlphaTensor sogar bestehende Rekorde. Seine überraschendsten Entdeckungen geschahen in der Modulo-2-Arithmetik, wo es einen neuen Algorithmus zum Multiplizieren von 4-mal-4-Matrizen in 47 Multiplikationsschritten fand, eine Verbesserung gegenüber den 49 Schritten, die für zwei Iterationen des Strassen-Algorithmus erforderlich waren. Es schlug auch den bekanntesten Algorithmus für 5-mal-5-Modulo-2-Matrizen und reduzierte die Anzahl der erforderlichen Multiplikationen vom vorherigen Rekord von 98 auf 96. (Aber dieser neue Rekord hinkt immer noch hinter den 91 Schritten hinterher, die zum Schlagen erforderlich wären Strassens Algorithmus unter Verwendung von 5-mal-5-Matrizen.)
Das neue hochkarätige Ergebnis sorgte für viel Aufregung, mit einige Forscher viel Lob für die KI-basierte Verbesserung des Status quo. Aber nicht alle in der Matrixmultiplikationsgemeinschaft waren so beeindruckt. „Ich hatte das Gefühl, dass es ein bisschen übertrieben war“, sagte Vassilevska Williams. „Es ist ein weiteres Werkzeug. Es ist nicht so, ‚Oh, die Computer schlagen die Menschen‘, weißt du?“
Die Forscher betonten auch, dass die unmittelbaren Anwendungen des rekordverdächtigen 4-mal-4-Algorithmus begrenzt wären: Er ist nicht nur in der Modulo-2-Arithmetik gültig, sondern im wirklichen Leben gibt es neben der Geschwindigkeit wichtige Überlegungen.
Fawzi stimmte zu, dass dies wirklich nur der Anfang ist. „Es gibt viel Raum für Verbesserungen und Forschung, und das ist gut so“, sagte er.
Eine letzte Wendung
Die größte Stärke von AlphaTensor im Vergleich zu etablierten Computersuchmethoden ist auch seine größte Schwäche: Es ist nicht durch die menschliche Intuition eingeschränkt, wie gute Algorithmen aussehen, also kann es seine Entscheidungen nicht erklären. Das macht es den Forschern schwer, aus ihren Errungenschaften zu lernen.
Dies ist jedoch möglicherweise kein so großer Nachteil, wie es scheint. Wenige Tage nach dem AlphaTensor-Ergebnis, dem Mathematiker Manuel Kauer und sein Doktorand Jakob Moosbauer, beide von der Johannes Kepler Universität Linz in Österreich, meldeten einen weiteren Schritt nach vorne.
Einleitung
Als das DeepMind-Papier herauskam, waren Kauers und Moosbauer gerade dabei, mit einer herkömmlichen computergestützten Suche nach neuen Multiplikationsalgorithmen zu suchen. Aber im Gegensatz zu den meisten solchen Suchen, die mit einem neuen Leitprinzip neu beginnen, funktioniert ihre Methode, indem sie einen bestehenden Algorithmus wiederholt optimiert, in der Hoffnung, mehr Multiplikationseinsparungen daraus zu ziehen. Sie nahmen den Algorithmus von AlphaTensor für 5-mal-5-Modulo-2-Matrizen als Ausgangspunkt und stellten überrascht fest, dass ihre Methode die Anzahl der Multiplikationsschritte nach nur wenigen Sekunden Berechnung von 96 auf 95 reduzierte.
AlphaTensor verhalf ihnen auch indirekt zu einer weiteren Verbesserung. Zuvor hatten Kauers und Moosbauer sich nicht die Mühe gemacht, den Raum von 4-mal-4-Matrizen zu erkunden, da sie glaubten, dass es nicht möglich sein würde, zwei Iterationen von Strassens Algorithmus zu schlagen. Das AlphaTensor-Ergebnis veranlasste sie, es noch einmal zu überdenken, und nach einer Woche Rechenzeit, die von vorne anfing, ergab ihre Methode einen weiteren 47-Schritte-Algorithmus, der nichts mit dem von AlphaTensor entdeckten zu tun hatte. „Wenn uns jemand gesagt hätte, dass es bei 4-by-4 etwas zu entdecken gibt, hätten wir das früher tun können“, sagte Kauers. „Aber gut, so funktioniert es.“
Littman erwartet weitere solcher Überraschungen und vergleicht die Situation mit dem ersten Mal, als ein Läufer eine Meile in weniger als vier Minuten beendete, eine Leistung, die allgemein als unmöglich galt. "Die Leute sagten: 'Oh, warte, wir können das tun', und jetzt können es viele Leute tun", sagte er.
Mit Blick auf die Zukunft hofft Fawzi, AlphaTensor zu verallgemeinern, um ein breiteres Spektrum mathematischer und rechnerischer Aufgaben zu bewältigen, so wie sich sein Vorfahr AlphaGo schließlich auf andere Spiele ausgeweitet hat.
Kauers sieht darin den wahren Lackmustest für die Anwendung des maschinellen Lernens zur Entdeckung neuer Algorithmen. Er weist darauf hin, dass die Suche nach schnellen Matrixmultiplikationsalgorithmen ein kombinatorisches Problem ist, für das Computersuchen mit oder ohne menschliche Unterstützung gut geeignet sind. Aber nicht alle mathematischen Probleme sind so einfach zu fassen. Wenn maschinelles Lernen eine qualitativ neue algorithmische Idee entdecken kann, sagte er, „wäre dies ein Game Changer.“
