Deep Mind AlphaTensor wird neue Algorithmen entdecken

Deep Mind hat AlphaZero auf die Mathematik ausgeweitet, um neue Möglichkeiten für Forschungsalgorithmen zu erschließen.

AlphaTensor baut auf AlphaZero auf, einem Agenten, der bei Brettspielen wie Schach, Go und Shogi übermenschliche Leistungen gezeigt hat, und diese Arbeit zeigt die Reise von AlphaZero vom Spielen bis hin zur erstmaligen Bewältigung ungelöster mathematischer Probleme.

Die alten Ägypter schufen einen Algorithmus, um zwei Zahlen zu multiplizieren, ohne dass ein Einmaleins erforderlich war, und 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 entwarf der persische Mathematiker Muhammad ibn Musa al-Khwarizmi neue Algorithmen zur Lösung linearer und quadratischer Gleichungen. Tatsächlich führte der Name von al-Khwarizmi, übersetzt ins Lateinische als Algoritmi, zu dem Begriff Algorithmus. Aber trotz der heutigen Vertrautheit mit Algorithmen – die in der gesamten Gesellschaft von der Algebra im Klassenzimmer bis hin zu modernster wissenschaftlicher Forschung verwendet werden – ist der Prozess der Entdeckung neuer Algorithmen unglaublich schwierig und ein Beispiel für die erstaunlichen Denkfähigkeiten des menschlichen Geistes.

Sie veröffentlichten in Nature. AlphaTensor ist das erste System der künstlichen Intelligenz (KI) zur Entdeckung neuartiger, effizienter und nachweislich korrekter Algorithmen für grundlegende Aufgaben wie die Matrixmultiplikation. Dies wirft Licht auf eine 50 Jahre alte offene Frage in der Mathematik, bei der es darum geht, den schnellsten Weg zur Multiplikation zweier Matrizen zu finden.

AlphaTensor wurde von Grund auf neu trainiert und entdeckt Matrixmultiplikationsalgorithmen, die effizienter sind als bestehende von Menschen und Computern entwickelte Algorithmen. Trotz der Verbesserung gegenüber bekannten Algorithmen stellen sie fest, dass eine Einschränkung von AlphaTensor in der Notwendigkeit besteht, einen Satz potenzieller Faktoreinträge F vorzudefinieren, was den Suchraum diskretisiert, aber möglicherweise dazu führen kann, dass effiziente Algorithmen übersehen werden. Eine interessante Richtung für die zukünftige Forschung ist die Anpassung von AlphaTensor für die Suche nach F. Eine wichtige Stärke von AlphaTensor ist seine Flexibilität, komplexe stochastische und nicht differenzierbare Belohnungen (vom Tensor-Rang bis zur praktischen Effizienz auf bestimmter Hardware) zusätzlich zum Finden von Algorithmen zu unterstützen für benutzerdefinierte Operationen in einer Vielzahl von Räumen (z. B. endliche Felder). Sie glauben, dass dies Anwendungen von AlphaTensor dazu anregen wird, Algorithmen zu entwerfen, die Metriken optimieren, die wir hier nicht berücksichtigt haben, wie z. B. numerische Stabilität oder Energieverbrauch.

Die Entdeckung von Matrizenmultiplikationsalgorithmen hat weitreichende Auswirkungen, da die Matrizenmultiplikation den Kern vieler Rechenaufgaben bildet, wie z. B. die Matrizeninversion, die Berechnung der Determinante und die Lösung linearer Systeme.

Der Prozess und Fortschritt der Automatisierung der algorithmischen Entdeckung
Erstens wandelten sie das Problem, effiziente Algorithmen für die Matrixmultiplikation zu finden, in ein Einzelspieler-Spiel um. In diesem Spiel ist das Brett ein dreidimensionaler Tensor (Zahlenfeld), der erfasst, wie weit der aktuelle Algorithmus von der Richtigkeit entfernt ist. Durch eine Reihe von zulässigen Zügen, die den Anweisungen des Algorithmus entsprechen, versucht der Spieler, den Tensor zu modifizieren und seine Einträge auf Null zu setzen. Wenn es dem Spieler gelingt, dies zu tun, führt dies zu einem nachweislich korrekten Matrixmultiplikationsalgorithmus für jedes Paar von Matrizen, und seine Effizienz wird durch die Anzahl der Schritte erfasst, die unternommen werden, um den Tensor auf Null zu setzen.

Dieses Spiel ist unglaublich herausfordernd – die Anzahl der zu berücksichtigenden möglichen Algorithmen ist viel größer als die Anzahl der Atome im Universum, selbst für kleine Fälle der Matrixmultiplikation. Im Vergleich zum Go-Spiel, das jahrzehntelang eine Herausforderung für die KI blieb, ist die Anzahl der möglichen Züge in jedem Schritt ihres Spiels um 30 Größenordnungen größer (über 10^33 für eine der von ihnen in Betracht gezogenen Einstellungen).

Um dieses Spiel gut zu spielen, muss man im Wesentlichen die kleinste Nadel in einem gigantischen Heuhaufen von Möglichkeiten identifizieren. Um die Herausforderungen dieser Domäne anzugehen, die sich erheblich von traditionellen Spielen unterscheidet, haben wir mehrere entscheidende Komponenten entwickelt, darunter eine neuartige neuronale Netzwerkarchitektur, die problemspezifische induktive Verzerrungen enthält, ein Verfahren zur Generierung nützlicher synthetischer Daten und ein Rezept zur Nutzung von Symmetrien der Problem.

Anschließend trainierten sie einen AlphaTensor-Agenten mithilfe von Reinforcement Learning, um das Spiel zu spielen, wobei sie ohne Kenntnisse über bestehende Matrixmultiplikationsalgorithmen begannen. Durch Lernen verbessert sich AlphaTensor im Laufe der Zeit allmählich, entdeckt historische schnelle Matrixmultiplikationsalgorithmen wie den von Strassen wieder, übertrifft schließlich den Bereich der menschlichen Intuition und entdeckt Algorithmen schneller als bisher bekannt.

Untersuchung der Auswirkungen auf zukünftige Forschung und Anwendungen
Aus mathematischer Sicht können ihre Ergebnisse die weitere Forschung in der Komplexitätstheorie leiten, die darauf abzielt, die schnellsten Algorithmen zur Lösung von Rechenproblemen zu bestimmen. Durch die Erforschung des Raums möglicher Algorithmen auf effektivere Weise als frühere Ansätze trägt AlphaTensor dazu bei, unser Verständnis der Reichhaltigkeit von Matrixmultiplikationsalgorithmen zu erweitern. Das Verständnis dieses Raums kann neue Ergebnisse erschließen, um die asymptotische Komplexität der Matrixmultiplikation zu bestimmen, eines der grundlegendsten offenen Probleme in der Informatik.

Da die Matrixmultiplikation eine Kernkomponente in vielen Rechenaufgaben ist, die Computergrafik, digitale Kommunikation, neuronales Netzwerktraining und wissenschaftliches Rechnen umfassen, könnten die von AlphaTensor entdeckten Algorithmen Berechnungen in diesen Bereichen erheblich effizienter machen. Die Flexibilität von AlphaTensor, jede Art von Ziel zu berücksichtigen, könnte auch neue Anwendungen zum Entwerfen von Algorithmen anregen, die Metriken wie Energieverbrauch und numerische Stabilität optimieren und dabei helfen, kleine Rundungsfehler zu verhindern, die während der Arbeit eines Algorithmus auftreten.

Während sie sich hier auf das besondere Problem der Matrizenmultiplikation konzentrierten, hoffen wir, dass unser Artikel andere dazu inspirieren wird, KI zu verwenden, um die algorithmische Entdeckung für andere grundlegende Rechenaufgaben zu leiten. Ihre Forschung zeigt auch, dass AlphaZero ein leistungsstarker Algorithmus ist, der weit über die Domäne traditioneller Spiele hinaus erweitert werden kann, um bei der Lösung offener Probleme in der Mathematik zu helfen. Aufbauend auf unserer Forschung hoffen sie, eine größere Anzahl von Arbeiten voranzutreiben – die Anwendung von KI, um der Gesellschaft bei der Lösung einiger der wichtigsten Herausforderungen in der Mathematik und in den Wissenschaften zu helfen.

Natur – Entdeckung schnellerer Matrixmultiplikationsalgorithmen mit Verstärkungslernen

Abstrakt
Die Verbesserung der Effizienz von Algorithmen für grundlegende Berechnungen kann weitreichende Auswirkungen haben, da sie die Gesamtgeschwindigkeit einer großen Menge von Berechnungen beeinflussen kann. Die Matrixmultiplikation ist eine solche primitive Aufgabe, die in vielen Systemen vorkommt – von neuronalen Netzen bis hin zu wissenschaftlichen Rechenroutinen. Die automatische Entdeckung von Algorithmen mithilfe von maschinellem Lernen bietet die Aussicht, über die menschliche Intuition hinauszugehen und die derzeit besten von Menschen entwickelten Algorithmen zu übertreffen. Die Automatisierung des Algorithmuserkennungsverfahrens ist jedoch kompliziert, da der Raum möglicher Algorithmen enorm ist. Hier berichten wir über einen auf AlphaZero1 basierenden Deep-Reinforcement-Learning-Ansatz zur Entdeckung effizienter und nachweislich korrekter Algorithmen zur Multiplikation beliebiger Matrizen. Unser Agent, AlphaTensor, ist darauf trainiert, ein Einzelspieler-Spiel zu spielen, bei dem das Ziel darin besteht, Tensor-Zerlegungen innerhalb eines endlichen Faktorraums zu finden. AlphaTensor entdeckte Algorithmen, die die Komplexität des Standes der Technik für viele Matrixgrößen übertreffen. Besonders relevant ist der Fall von 4 × 4-Matrizen in einem endlichen Körper, wo der Algorithmus von AlphaTensor unseres Wissens zum ersten Mal seit seiner Entdeckung vor 50 Jahren den zweistufigen Algorithmus von Strassen verbessert2. Wir demonstrieren außerdem die Flexibilität von AlphaTensor durch verschiedene Anwendungsfälle: Algorithmen mit hochmoderner Komplexität für die strukturierte Matrixmultiplikation und verbesserte praktische Effizienz durch Optimierung der Matrixmultiplikation für die Laufzeit auf spezifischer Hardware. Unsere Ergebnisse unterstreichen die Fähigkeit von AlphaTensor, den Prozess der algorithmischen Entdeckung bei einer Reihe von Problemen zu beschleunigen und für verschiedene Kriterien zu optimieren.