Update vom 18. Oktober 2022:
Die beiden Forscher Manuel Kauers und Jakob Moosbauer von der Johannes Kepler Universität Linz haben den Matrizenmultiplikationsrekord von Deepmind laut ihres Papers schon wieder gebrochen. Sie entwickelten einen Weg, eine 5×5-Matrix-Multiplikation in 95 Schritten durchzuführen - ein Schritt weniger als Deepminds Rekord von Anfang Oktober mit 96 Schritten. Der ursprüngliche Wert lag bei 98 Multiplikationen. Die österreichischen Forscher setzten auf Deepminds Arbeit auf.
Ursprünglicher Artikel vom 6. Oktober 2022:
AlphaTensor: Neue Deepmind-KI soll Computer effizienter multiplizieren lassen
Deepminds KI-System AlphaTensor entdeckt automatisch neue Algorithmen, die in der IT allgegenwärtige Matrizen-Multiplikationen beschleunigen könnten.
Computer können Zahlen schneller addieren als multiplizieren. Das ist insofern ein Problem, als viele mathematische Aufgaben in der Informatik über sogenannte Matrizen-Multiplikationen verarbeitet werden, etwa beim maschinellen Lernen, bei der Generierung von Computergrafiken, für Simulationen aller Art oder bei der Komprimierung von Daten.
Schon kleine Effizienzgewinne bei der Matrix-Multiplikation könnten daher große Wirkung erzielen. Mathematiker sind entsprechend seit Jahrzehnten auf der Suche nach effizienteren Algorithmen für die Matrix-Multiplikation.
1969 entwickelte der deutsche Mathematiker Volker Strassen einen besonders effizienten Algorithmus, der 4×4-Matrix-Multiplikationen mit 49 statt 64 Multiplikationen lösen konnte. Das ist rund 50 Jahre her, doch Strassens Algorithmus ist bis heute im Einsatz, da er bislang nicht übertroffen wurde.
Von AlphaZero zu AlphaTensor: Der Algorithmus als Spiel
Deepminds KI-System AlphaTensor, das auf der universellen Brettspiel-KI AlphaZero basiert, hat laut Deepmind jetzt einen neuen Algorithmus entdeckt, der schneller sein soll als Strassens Algorithmus und laut Deepmind-CEO Demis Hassabis das "Potenzial zur Effizienzsteigerung um zehn bis 20 Prozent bei Billionen von Berechnungen pro Tag" hat.
Since 1969 Strassen’s algorithm has famously stood as the fastest way to multiply 2 matrices - but with #AlphaTensor we’ve found a new algorithm that’s faster, with potential to improve efficiency by 10-20% across trillions of calculations per day! https://t.co/nLvFbEDBuO
— Demis Hassabis (@demishassabis) October 5, 2022
Für das Training von AlphaTensor verwandelte das Deepmind-Forschungsteam das Problem der Matrix-Muliplikation in eine Art 3D-Brettspiel, bei dem jeder Zug in einem Baustein eines neuen Algorithmus resultiert. Belohnt wurde AlphaTensor, das bei jedem Zug zwischen Billionen Zügen auswählen musste, wenn es einen neuen Algorithmus in möglichst wenig Schritten generierte. Das Spiel nennt Deepmind "Tensor Game".
Weniger Rechenschritte bis zum Ergebnis
Deepmind ließ AlphaTensor maximal 5×5-Eingabematrizen verarbeiten. Dabei entdeckte AlphaTensor eigenständig Strassens Algorithmus und weitere schon bekannte Verfahren. Das KI-System entwickelte zudem neue Algorithmen, die laut Deepmind effizienter sind als bislang existierende.
So lag der Rekord bei einer 5×5-Matrix bislang bei 80 Multiplikationen, ein neuer AlphaTensor-Algorithmus benötigt nur 76. Die eingangs erwähnte 4×4-Multiplikation, die Strassen auf 49 Schritte reduzierte, optimiert AlphaTensor auf 47 Schritte. Solche Effizienzsteigerungen erzielten von AlphaTensor generierte Algorithmen für mehr als 70 Matrix-Multiplikationen.
Die Deepmind-Forschenden zeigen sich erstaunt von der schieren Menge an möglichen Wegen, Matrizen zu multiplizieren. Zudem kann AlphaTensor Hardware-spezifische Algorithmen entwickeln, die etwa auf Googles TPUs und Nvidias V100, die häufig für maschinelles Lernen verwendet werden, bis zu 20 Prozent schneller laufen sollen als derzeit verwendete Algorithmen.
KI für die Wissenschaft
Für Deepmind ist AlphaTensor insbesondere eine weitere Demonstration, wie Fortschritt bei Künstlicher Intelligenz für Fortschritt in anderen wissenschaftlichen Disziplinen sorgen kann. Die Arbeit zeige zudem, dass das eigentlich für traditionelle Spiele entwickelte AlphaZero-System weit über diesen Bereich hinaus mathematische Probleme lösen könne.
"Dieses Papier ist ein Meilenstein in der Mission von Deepmind, die Wissenschaft voranzubringen und die grundlegendsten Probleme mithilfe von KI zu lösen", schreibt Deepmind.
Prof. Dr. Markus Bläser, Professor für Computational Complexity an der Universität des Saarlandes, hebt die Methode, Multiplikationsalgorithmen automatisch an ausgewählte Hardware anzupassen, positiv hervor, da dies "für einen Menschen sehr schwierig wäre".
Ansonsten trage Deepminds Arbeit zum theoretischen Verständnis der Matrixmultiplikation bei kleinen Matrizen bei. Eine Verbesserung gegenüber Strassens Algorithmus bringe nur die neue obere Schranke für die Multiplikation von Matrizen der Größe vier.
"Um die theoretische Komplexität der Matrixmultiplikation besser zu verstehen, sind die Teilprobleme, die man in der aktuellen Forschung dazu betrachtet, hingegen so groß und komplex, dass ich hier momentan keine Einsatzmöglichkeiten für eine automatische Suche sehe", sagt Bläser.
Prof. Dr. Holger Hoos, Professor für KI und maschinelles Lernen an der RWTH und an der Universität Leiden, bezeichnet Deepminds Arbeit als "interessant, aber nicht bahnbrechend". Die Beschleunigung gegenüber bekannten Verfahren sei relativ klein. Er gehe nicht davon aus, dass die automatisch konstruierten Algorithmen unmittelbar in praktische Anwendungen eingehen.
"Die Arbeit ist zweifellos für Experten im automatischen Algorithmendesign wie mich und meine Kollegen von technischem Interesse, ich erwarte aber nicht, dass unmittelbar darauf aufbauend wirkliche Durchbrüche in der Forschung oder Praxis erzielt werden", sagt Hoos, der den methodischen Ansatz "zweifelsohne interessant" findet.
