AlphaTensor ist ein künstliches Intelligenzsystem, das von DeepMind entwickelt wurde, um mithilfe von bestärkendem Lernen effiziente Matrixmultiplikationsalgorithmen zu entdecken. Das System wurde 2022 vorgestellt, basierte auf AlphaZero und formulierte die Suche nach Matrixmultiplikationsalgorithmen als ein Einzelspieler-Spiel namens TensorGame.
AlphaTensor wurde entwickelt, um neue Wege zur Multiplikation von Matrizen mit weniger skalaren Multiplikationsoperationen zu suchen. Die Matrixmultiplikation ist eine grundlegende Operation in der linearen Algebra, der numerischen Analysis, dem wissenschaftlichen Rechnen, der Computergrafik und dem maschinellen Lernen. Das System entdeckte tausende Matrixmultiplikationsalgorithmen, darunter Algorithmen, die bekannte, von Menschen entwickelte Methoden wiederentdeckten, sowie andere, die für bestimmte Matrixgrößen und mathematische Umgebungen frühere bekannte Ergebnisse verbesserten.
Hintergrund
Die Matrixmultiplikation ist eine der grundlegenden Operationen im numerischen Rechnen. Der Standardalgorithmus zur Multiplikation zweier quadratischer Matrizen hat eine kubische Zeitkomplexität, während schnellere Algorithmen wie der Strassen-Algorithmus die Anzahl der Multiplikationsoperationen durch komplexere algebraische Zerlegungen reduzieren. Die Suche nach optimalen Matrixmultiplikationsalgorithmen kann schwierig sein, da sie die Durchsuchung eines großen Raums möglicher Tensordekompositionen umfasst.
AlphaTensor näherte sich diesem Problem, indem es die Algorithmenentdeckung als TensorGame darstellte, bei dem jeder Zug einer Operation entspricht, die einen die Matrixmultiplikation repräsentierenden Tensor reduziert. Das Ziel des Spiels ist es, eine Zerlegung mit niedrigem Rang des Matrixmultiplikationstensors zu finden, was einem effizienten Multiplikationsalgorithmus entspricht.
Entwicklung
AlphaTensor wurde von DeepMind entwickelt und in einem im Oktober 2022 in Nature veröffentlichten Artikel beschrieben. Das System baute auf dem Ansatz des bestärkenden Lernens auf, der in AlphaZero verwendet wurde und zuvor auf Spiele wie Go, Schach und Shogi angewendet worden war. Anders als bei diesen Spielen umfasste TensorGame einen sehr großen Suchraum, was Änderungen an der Suchmethode im AlphaZero-Stil und an der Architektur des neuronalen Netzes erforderte.
DeepMind veröffentlichte den Quellcode und die im Zusammenhang mit der Veröffentlichung entdeckten Algorithmen über ein öffentliches GitHub-Repository.
Ergebnisse
AlphaTensor entdeckte Matrixmultiplikationsalgorithmen sowohl über der Standardarithmetik als auch über endlichen Körpern. Ein weithin berichtetes Ergebnis war eine Methode zur Multiplikation von 4 × 4-Matrizen über dem Körper mit zwei Elementen unter Verwendung von 47 Multiplikationsoperationen, was die 49 Operationen verbesserte, die bei der rekursiven Anwendung des Strassen-Algorithmus in dieser Umgebung erforderlich sind.
Das System fand auch Algorithmen, die für bestimmte Computerhardware optimiert waren, einschließlich Algorithmen, die für Grafikprozessoren und Tensor Processing Units entwickelt wurden. DeepMind gab an, dass einige der hardwarespezifischen Algorithmen die praktische Ausführungszeit im Vergleich zu häufig verwendeten Algorithmen auf der getesteten Hardware verbesserten.
Bedeutung
AlphaTensor wurde als Beispiel dafür beschrieben, maschinelles Lernen nicht nur zur Anwendung bestehender Algorithmen, sondern auch zur Unterstützung bei der Entdeckung neuer Algorithmen zu nutzen. Die Arbeit stand in Verbindung mit breiterer Forschung zur Algorithmenentdeckung, zum automatisierten maschinellen Lernen, zur Programmsynthese und zur Theorie der Berechnungskomplexität, insbesondere zum offenen Problem der Bestimmung der optimalen Komplexität der Matrixmultiplikation.
AlphaTensor wurde später Teil einer breiteren Gruppe von Google-DeepMind-Systemen für Algorithmen- und Mathematikentdeckung, neben Systemen wie AlphaDev und AlphaEvolve.
Siehe auch
Referenzen
- DeepMind, 'AlphaTensor', 2022.
- Nature-Artikel, Oktober 2022.
Externe Links
- Offizielle Website
- alphatensor auf GitHub