Reinforcement Learning entdeckt den Matrixmultiplikationsalgorithmus, DeepMind erscheint auf dem Cover von Nature und bringt AlphaTensor auf den Markt

Algorithmen helfen Mathematikern seit Tausenden von Jahren bei der Durchführung grundlegender Operationen. Vor langer Zeit erfanden die alten Ägypter einen Algorithmus zur Multiplikation zweier Zahlen, ohne dass eine Multiplikationstabelle erforderlich war. Der griechische Mathematiker Euklid beschrieb einen Algorithmus zur Berechnung des größten gemeinsamen Teilers, der noch heute verwendet wird. Während des islamischen Goldenen Zeitalters entwickelte der persische Mathematiker Muhammad ibn Musa al-Khwarizmi einen neuen Algorithmus zur Lösung linearer und quadratischer Gleichungen, der tiefgreifende Auswirkungen auf die spätere Forschung haben sollte.

Tatsächlich gibt es ein Sprichwort über die Entstehung des Wortes Algorithmus: Das Wort al-Khwarizmi im Namen des persischen Mathematikers Muhammad ibn Musa al-Khwarizmi wird ins Lateinische als Algoritmi übersetzt, was zur Einführung von führt Algorithmus 1. Wort. Obwohl wir heute mit Algorithmen sehr vertraut sind, können wir sie im Unterricht lernen und begegnen ihnen oft im Bereich der wissenschaftlichen Forschung. Es scheint, dass die gesamte Gesellschaft Algorithmen verwendet, aber der Prozess der Entdeckung neuer Algorithmen ist sehr schwierig . ​

Jetzt nutzt DeepMind KI, um neue Algorithmen zu entdecken.

Im Titelpapier der neuesten Ausgabe von Nature „Entdeckung schnellerer Matrixmultiplikationsalgorithmen mit Verstärkungslernen“ schlug DeepMind AlphaTensor vor und gab an, dass es der erste sei, der neuartige, effiziente und nachweisbare Algorithmen für grundlegende Aufgaben wie die Matrixmultiplikation entdecke . Künstliches Intelligenzsystem mit korrektem Algorithmus. Einfach ausgedrückt: Mit AlphaTensor können Sie neue Algorithmen entdecken. Die Forschung wirft Licht auf ein 50 Jahre altes ungelöstes Problem in der Mathematik: den schnellsten Weg zu finden, zwei Matrizen zu multiplizieren.

• Papieradresse: https://www.nature.com/articles/s41586-022-05172-4
• GitHub-Adresse: https:/ /github.com/deepmind/alphatensor ​

AlphaTensor basiert auf AlphaZero, einem Agenten, der Menschen bei Brettspielen wie Schach, Go und Shogi schlagen kann. Diese Arbeit demonstriert den Übergang von AlphaZero vom Einsatz für Spiele zum ersten Einsatz zur Lösung ungelöster mathematischer Probleme. ​

Matrixmultiplikation

Matrixmultiplikation ist eine der einfachsten Operationen in der Algebra und wird typischerweise im Mathematikunterricht der Oberstufe gelehrt. Aber auch außerhalb des Klassenzimmers hatte diese bescheidene mathematische Operation einen enormen Einfluss auf die heutige digitale Welt und ist in der modernen Computerwelt allgegenwärtig.

Beispiel für die Multiplikation zweier 3x3-Matrizen. ​

Ihnen ist vielleicht nicht aufgefallen, dass sich überall in unserem Leben die Matrixmultiplikation verbirgt, etwa bei der Bildverarbeitung in Smartphones, der Erkennung von Sprachbefehlen, der Erstellung von Grafiken für Computerspiele usw. Dahinter steckt alles. Unternehmen auf der ganzen Welt sind bereit, viel Zeit und Geld in die Entwicklung von Computerhardware zu investieren, um die Matrixmultiplikation effizient zu lösen. Daher können selbst kleine Verbesserungen der Matrixmultiplikationseffizienz weitreichende Auswirkungen haben.

Seit Jahrhunderten betrachten Mathematiker den Standard-Matrixmultiplikationsalgorithmus als den effizientesten Algorithmus. Doch 1969 schockierte der deutsche Mathematiker Volken Strassen die mathematische Welt, indem er bewies, dass es tatsächlich einen besseren Algorithmus gab.

Vergleicht man den Standardalgorithmus mit dem Strassen-Algorithmus, so erfordert letzterer eine Multiplikationsoperation weniger, nämlich 7-mal, während ersterer 8-mal erfordert, und die Gesamteffizienz wird erheblich verbessert. ​

Durch das Studium sehr kleiner Matrizen (Größe 2x2) entdeckte Strassen eine clevere Möglichkeit, die Terme der Matrix zu kombinieren, um einen schnelleren Algorithmus zu erstellen. In den folgenden Jahrzehnten haben Forscher größere Matrizen untersucht, und selbst die Suche nach einer effizienten Methode zur Multiplikation von 3x3-Matrizen konnte noch nicht gelöst werden.

Neue Forschungsergebnisse von DeepMind untersuchen, wie moderne KI-Technologie die automatische Entdeckung neuer Matrixmultiplikationsalgorithmen vorantreibt. Basierend auf Fortschritten in der menschlichen Intuition ist der von AlphaTensor entdeckte Algorithmus für größere Matrizen effizienter als viele SOTA-Methoden. Die Studie zeigt, dass von KI entworfene Algorithmen die von Menschen entwickelten übertreffen, ein wichtiger Fortschritt auf dem Gebiet der Algorithmenentdeckung.

Der Prozess und Fortschritt der Automatisierung der Algorithmuserkennung

Umsetzen Sie zunächst das Problem der Entdeckung effizienter Algorithmen für die Matrixmultiplikation in ein Einzelspielerspiel. Unter anderem ist Board ein dreidimensionaler Tensor (Zahlenarray), der verwendet wird, um zu erfassen, wie korrekt der aktuelle Algorithmus ist. Durch eine Reihe erlaubter Bewegungen, die den Anweisungen des Algorithmus entsprechen, versucht der Spieler, den Tensor zu ändern und seine Einträge auf Null zurückzusetzen.

Wenn dem Spieler dies gelingt, wird für jedes Matrizenpaar ein nachweislich korrekter Matrixmultiplikationsalgorithmus generiert, und seine Effizienz wird an der Anzahl der Schritte gemessen, die zum Nullsetzen des Tensors unternommen werden.

Dieses Spiel ist sehr anspruchsvoll und die Anzahl der möglichen Algorithmen, die berücksichtigt werden müssen, ist weitaus größer als die Anzahl der Atome im Universum, selbst für einen so kleinen Fall wie die Matrixmultiplikation. Im Vergleich zum Go-Spiel, das seit Jahrzehnten eine KI-Herausforderung darstellt, verfügt das Spiel über 30 Größenordnungen mehr mögliche Züge pro Zug (eine von DeepMind berücksichtigte Einstellung war 10^33+.)

Um dieses Problem zu lösen, wurde DeepMind entwickelt mehrere Schlüsselkomponenten zur Bewältigung der Herausforderungen einer Domäne, die sich deutlich von herkömmlichen Spielen unterscheidet, darunter eine neue neuronale Netzwerkarchitektur, die problemspezifische induktive Vorurteile beinhaltet, ein Verfahren zur Generierung nützlicher synthetischer Daten und eine Methode zur Ausnutzung von Problemsymmetrien.

Als nächstes trainierte DeepMind einen Reinforcement-Learning-Agenten, AlphaTensor, um das Spiel zu spielen, ohne Kenntnisse über bestehende Matrixmultiplikationsalgorithmen zu haben. Durch Lernen verbessert sich AlphaTensor im Laufe der Zeit allmählich, indem es historisch schnelle Matrixalgorithmen (wie den Strassen-Algorithmus) wiederentdeckt und Algorithmen entdeckt, die schneller sind als bisher bekannt.

AlphaTensor Ein Einzelspielerspiel, bei dem das Ziel darin besteht, den richtigen Matrixmultiplikationsalgorithmus zu finden. Der Spielstatus ist eine kubische Zahlenanordnung (Grau steht für 0, Blau steht für 1 und Grün steht für - 1), die die verbleibende noch zu erledigende Arbeit darstellt. ​

Wenn beispielsweise der in der Schule gelehrte traditionelle Algorithmus 4x5- und 5x5-Matrizen mit 100 Multiplikationen multiplizieren kann, kann menschlicher Einfallsreichtum diese Zahl auf das 80-fache reduzieren. Im Vergleich dazu führt der von AlphaTensor entdeckte Algorithmus dieselbe Operation mit nur 76 Multiplikationen durch, wie in der Abbildung unten gezeigt.

Zusätzlich zu den oben genannten Beispielen verbessert der von AlphaTensor entdeckte Algorithmus erstmals auch den Strassen-Algorithmus zweiter Ordnung in einem endlichen Körper. Diese Algorithmen zum Multiplizieren kleiner Matrizen können als Grundelemente zum Multiplizieren größerer Matrizen beliebiger Größe verwendet werden.

AlphaTensor hat außerdem einen vielfältigen Satz von Algorithmen mit SOTA-Komplexität entdeckt, mit bis zu Tausenden von Matrixmultiplikationsalgorithmen jeder Größe, was darauf hindeutet, dass der Raum der Matrixmultiplikationsalgorithmen umfangreicher ist als bisher angenommen.

Algorithmen in diesem reichhaltigen Bereich haben unterschiedliche mathematische und praktische Eigenschaften. DeepMind nutzte diese Vielfalt und optimierte AlphaTensor, um speziell Algorithmen zu entdecken, die auf bestimmter Hardware (z. B. Nvidia V100 GPU, Google TPU v2) schnell laufen. Diese Algorithmen führen große Matrixmultiplikationen 10–20 % schneller durch als häufig verwendete Algorithmen auf derselben Hardware und demonstrieren damit die Flexibilität von AlphaTensor bei der Optimierung beliebiger Ziele.

AlphaTensor hat ein Ziel, das der Laufzeit des Algorithmus entspricht. Wenn der richtige Matrixmultiplikationsalgorithmus gefunden wird, wird er auf der angegebenen Hardware verglichen und dann an AlphaTensor zurückgemeldet, um einen effizienteren Algorithmus auf der angegebenen Hardware zu erlernen.

Auswirkungen auf zukünftige Forschung und Anwendungen

Aus mathematischer Sicht können die Ergebnisse von DeepMind als Leitfaden für weitere Forschungen zur Komplexitätstheorie dienen, die darauf abzielt, die schnellsten Algorithmen zur Lösung von Rechenproblemen zu identifizieren. AlphaTensor trägt dazu bei, unser Verständnis des Reichtums von Matrixmultiplikationsalgorithmen zu vertiefen, indem es den Raum möglicher Algorithmen effizienter als frühere Methoden erforscht.

Da die Matrixmultiplikation außerdem eine Kernkomponente vieler Computeraufgaben wie Computergrafik, digitale Kommunikation, Training neuronaler Netze und wissenschaftliches Rechnen ist, können die von AlphaTensor entdeckten Algorithmen die Recheneffizienz in diesen Bereichen erheblich verbessern.

Obwohl sich dieser Artikel nur auf das spezifische Problem der Matrixmultiplikation konzentriert, hofft DeepMind, mehr Menschen dazu zu inspirieren, KI als Steuerung für die Algorithmenerkennung für andere grundlegende Computeraufgaben zu verwenden. Darüber hinaus zeigen die Untersuchungen von DeepMind auch, dass der leistungsstarke Algorithmus von AlphaZero weit über den Bereich traditioneller Spiele hinausgeht und zur Lösung offener Probleme im Bereich der Mathematik beitragen kann.

Auf der Grundlage ihrer Forschung hofft DeepMind, in Zukunft mehr künstliche Intelligenz einzusetzen, um der Gesellschaft bei der Lösung einiger der wichtigsten Herausforderungen in Mathematik und Naturwissenschaften zu helfen.

Das obige ist der detaillierte Inhalt vonReinforcement Learning entdeckt den Matrixmultiplikationsalgorithmus, DeepMind erscheint auf dem Cover von Nature und bringt AlphaTensor auf den Markt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!