Das Verarbeiten von Bildern auf einem Mobiltelefon, die Grafik bei Computerspielen, Spracherkennung und auch Wettersimulationen sind alle auf bestimmte Rechenoperationen angewiesen: die Matrizenmultiplikationen. Abhängig davon, wie groß die Matrizen sind, die dabei miteinander multipliziert werden sollen, ist diese Aufgabe mehr oder weniger komplex.
Um bei Matrizenmultiplikationen schnell auf ein richtiges Ergebnis zu kommen, braucht es möglichst effiziente Rechenwege und Algorithmen. Jahrhunderte hat es in diesem Bereich wenig Fortschritt gegeben, bis der deutsche Mathematiker Volker Strassen im Jahr 1969 gezeigt hat, dass Matrizenmultiplikationen in weniger Schritten gelöst werden können als bis zu diesem Zeitpunkt angenommen. Der Mathematiker erfand damals den Strassen-Algorithmus.
System lernt Effizienz
Über 50 Jahre später fand das lernfähige System AlphaTensor der britischen Firma DeepMind nun noch effizientere Algorithmen für vergleichsweise kleine und damit in der Praxis auch tatsächlich relevante Matrizenmultiplikationen.
Gelungen ist das der künstlichen Intelligenz mit Deep Reinforcement Learning in einer Art Spiel, das laut den Expertinnen und Experten von DeepMind Ähnlichkeiten mit Schach aufweist – mit viel mehr möglichen Spielzügen und einem dreidimensionalen Spielfeld. Bei jedem Spielzug oder Rechenschritt analysiert das System, ob es näher an der Lösung der Aufgabe ist als zuvor. So lernt es, nach und nach die effizientesten Algorithmen zu finden.
Übertrifft aktuellen Forschungsstand
Das System AlphaTensor wurde zu Beginn der Untersuchungen mit keinen Informationen über Matrizenmultiplikationen versorgt. Alle Algorithmen aus dem System basieren auf dessen eigenen Erfahrungen und auf den zuvor schon durchgeführten Rechnungen. Schnell konnte AlphaTensor dann Algorithmen erstellen, die bereits dem aktuellen Stand der Forschung entsprechen. Bald darauf gelang es dem System sogar, diese noch zu übertreffen.
Die Expertinnen und Experten von DeepMind stellen das System aktuell in einer neuen Studie im Fachjournal Nature vor. Matrizenrechnungen, die mit traditionellen Verfahren einhundert Multiplikationen umfassen, konnten durch große Bemühungen und menschliches Knowhow bereits in 80 Multiplikationen gelöst werden. AlphaTensor gelang es in nur 76 Multiplikationen.
Erfahrungen von Schach und GO
Dass sich mit Reinforcement Learning Erstaunliches schaffen lässt, hat DeepMind bereits mehrfach unter Beweis gestellt. Schon vor rund fünf Jahren konnte sich das Programm AlphaZero innerhalb weniger Stunden Schach selbst beibringen und danach das bis dahin beste Programm für Computerschach problemlos übertrumpfen.
Auch beim Spiel GO konnten die KI-Programme der Firma DeepMind in der Vergangenheit bereits triumphieren, obwohl das Spiel für Computer jahrzehntelang eine Herausforderung darstellte. Bei den Matrizenmultiplikationen und AlphaTensor ist die Zahl der potenziellen Möglichkeiten und „Spielzüge“ nun sogar über 30 Größenordnungen (x 1030) höher.
Für mehr Effizienz
Mit AlphaTensor möchten die Expertinnen und Experten künftig weiter ergründen, wie effizient die Lösung bestimmter Matrizenmultiplikationen werden kann. Schon die bisherigen Ergebnisse können laut ihnen aber bereits zu „signifikant größerer Effizienz und Schnelligkeit“ bei einigen Computerprogrammen und Rechenaufgaben führen.
AlphaTensor kann laut den Autorinnen und Autoren außerdem Algorithmen finden, die für den Einsatz mit bestimmter Hardware optimiert sind und daher auf dieser Hardware – zum Beispiel speziellen Grafikkarten – zehn bis zwanzig Prozent schneller arbeiten.
Generell hoffen die Autorinnen und Autoren, dass AlphaTensor als Grundlage dient, um künftig auch für Rechenaufgaben und mathematische Probleme, die nichts mit Matrizen zu tun haben, möglichst effiziente Algorithmen zu finden.