AlphaTensor: KI-System beschleunigt Matrixmultiplikation mit neuem Algorithmus

Inhaltsverzeichnis

(This article is also available in English.)

Mit AlphaTensor hat DeepMind Technologies ein KI-System vorgestellt, das eigenständig neuartige, effiziente und beweisbar korrekte Algorithmen für komplexe mathematische Aufgaben finden soll. AlphaTensor hat bereits einen neuen Algorithmus identifiziert, mit dem sich Matrixmultiplikationen schneller als bisher durchführen lassen, wie das Forschungsteam in einem bei Nature publizierten Fachartikel darlegt. Den Faktor gibt das Team mit zehn- bis zwanzigprozentiger Beschleunigung gegenüber bisherigen Standardverfahren an.

AlphaTensor baut auf AlphaZero auf, einem KI-Agenten, der sich bei Brettspielen wie Schach, Go und Shogi menschlichen Spielern als überlegen erwiesen hatte. Das durch den britischen KI-Forscher, Neurowissenschaftler und Computerspielentwickler Demosthenes "Demis" Hassabis gegründete Unternehmen hatte mit AlphaGo und AlphaFold bereits Meilensteine gesetzt. Als Ziel seines Unternehmens gibt Hassabis an, KI zu entwickeln, die grundlegende Probleme der Wissenschaft löst. Durch AlphaTensor gelingt DeepMind offenbar ein weiterer Durchbruch, nämlich Fortschritt in offenen Fragen der Mathematik durch Künstliche Intelligenz (KI) greifbar zu machen.

Auf der Suche nach schnelleren Algorithmen

Die Suche nach schnelleren Algorithmen zum Multiplizieren zweier Matrizen ist nicht trivial und beschäftigt die Fachwelt seit rund 50 Jahren: 1969 hatte der Mathematiker, Physiker und Philosoph Volker Strassen eine verbesserte Methode gefunden, um Matrizen der Größe zwei schneller zu multiplizieren als die bis dahin bekannten Standardverfahren. Der nach ihm benannte Strassen-Algorithmus gilt als bahnbrechend und kommt in der Praxis bis heute oft zum Einsatz.

Algorithmenfinden: Tensor-Spiel für den KI-Agenten

Das Team hatte das Problem, brauchbare Algorithmen für die Matrixmultiplikation zu finden, in ein Single-Player-Spiel übersetzt. Bei dem Spiel ist das "Brett" ein dreidimensionaler Tensor (Zahlenbereich), der erfasst, wie weit ein Algorithmus jeweils vom korrekten Ergebnis entfernt ist. Der Spieler versucht den Tensor so zu modifizieren, dass die Einträge darin "ausgenullt" werden. Die möglichen Spielzüge sind festgelegt und entsprechen algorithmischen Anweisungen. Gelingt dem Spieler ein gutes Spiel, ist das Ergebnis ein beweisbar korrekter Algorithmus zur Matrixmultiplikation (für jegliches Paar von Matrizen). Die Effizienz bemisst sich dabei an der Anzahl von Schritten, die nötig waren, um den Tensor zur Null hinzuführen.

Wie Hassabis und sein Team im Artikel beschreiben, ist das Spiel ausgesprochen anspruchsvoll. Denn die Anzahl möglicher Algorithmen, die es in Betracht zu ziehen gilt, sei vielleicht "größer als die Anzahl der Atome im Universum", sogar bereits für kleinere Fälle von Matrixmultiplikation [Anm. Red.: allerdings wird die Anzahl der Atome im Universum auf 10⁸⁴ bis 10⁸⁹ geschätzt, sodass Hassabis' Angaben ein wenig hoch gegriffen scheinen – wenngleich Diskussionen laufen, dass die Anzahl digitaler Bits die Anzahl der Atome auf der Erde eines Tages übersteigen könnte]. Verglichen mit Go, woran die KI-Forschung sich vor AlphaGo lange die Zähne ausbiss, sei die Dimension möglicher Spielzüge bei jedem Zug um dreißig Größenordnungen größer (10³³). Das Team hat offenbar mittels Deep Reinforcement Learning (DRL) einen KI-Agenten trainiert, der zunächst keine Ahnung von Matrixmultiplikationsalgorithmen hatte und dann mit der Zeit seine Fähigkeiten verbesserte, historisch schon vorhandene Algorithmen zur rascheren Matrixmultiplikation aufspürte (wie den von Strassen) und zunehmend Ergebnisse lieferte, die über bekannte menschliche Einsicht hinausgehen, und das mit gehörigem Tempo.

Die vorgestellten Ergebnisse stellen laut DeepMind-Team eine signifikante Beschleunigung zahlreicher Rechenoperationen in Informatik und KI in Aussicht, zumindest laut den Verfassern des Blogbeitrags und des Fachartikels. Vor allem sollen sie zunächst ein Beitrag zur Komplexitätsforschung sein. Hierzu ist anzumerken, dass das Paper sich speziell mit Matrixmultiplikation befasst, einer einfachen Algebraoperation, die in der IT und digitalen Welt vielen Prozessen zugrunde liegt.

Das Erkennen von Sprachbefehlen, das Erstellen von Computerspielgrafiken, Simulationen für die Wettervorhersage, das Komprimieren von Daten und zahlreiche weitere Prozesse beruhen darauf. Daher könnten schon kleine Verbesserungen bei dem grundlegenden Rechenvorgang weitreichende Auswirkungen haben. Effizientere Rechenvorgänge nehmen weniger Zeit in Anspruch und benötigen somit unter anderem auch weniger Energie und Ressourcen.

Tragweite für Informatik und Ingenieurswissenschaften

Auf Twitter und in anderen Kanälen hat sich die Community in ersten Statements bereits teils euphorisch geäußert, wobei die Meinungen nicht ganz einhellig sind, aber durchweg Anerkennung zollen. Manche sehen in der Studie bereits einen großen Durchbruch für die KI-gestützte Fortentwicklung von Technik, Mathematik und KI sowie Machine Learning. Zur Tragweite und zum Potenzial des vorgestellten Modells haben sich auch zwei deutsche Forscher zu Wort gemeldet, deren ausführliche Stellungnahmen Heise vorliegen.

Markus Bläser ist Professor für Computational Complexity an der Universität des Saarlandes in Saarbrücken, er gilt als Experte für algebraische Algorithmen und Komplexität. Laut ihm ist das theoretische Verständnis der Komplexität der Matrixmultiplikation sowie die Entwicklung schneller, praktischer Algorithmen von großem Interesse, da die Matrixmultiplikation als Grundlage zahlreicher Operationen dient und in der angewandten Mathematik, der Informatik, aber auch in den Ingenieurswissenschaften breite Anwendung findet. Bläser zufolge findet die vorliegende Arbeit des DeepMind-Teams mit Machine-Learning-Methoden einige neue obere Schranken für die Multiplikation kleiner Matrizen. Das trage zum theoretischen Verständnis der Matrixmultiplikation bei.

"Optimierungen nutzen, die für Menschen schwierig wären"

Eine Verbesserung gegenüber Strassens Algorithmus bringe allerdings zunächst nur die neue obere Schranke für die Multiplikation von Matrizen der Größe vier. Eine Einschränkung nimmt Bläser darin wahr, dass der Algorithmus nur funktioniert, wenn bestimmte Rechengesetze in Kraft sind, die beispielsweise nicht für die reellen Zahlen gelten. Interessanter hingegen erscheint dem Komplexitätsforscher die im zweiten Teil der Arbeit beschriebene Methode, Multiplikationsalgorithmen "automatisch direkt an bestimmte Hardwarestrukturen anzupassen und so Optimierungen innerhalb des Systems auszunutzen, was für einen Menschen sehr schwierig wäre". Die Teilprobleme, die Forscherinnen und Forscher aktuell untersuchen, sind Bläser zufolge jedoch aktuell so groß, dass er hier – zumindest zur jetzigen Zeit – noch keine Einsatzmöglichkeiten für eine automatische Suche sieht.

Auch Holger Hoos, Professor für Machine Learning an der Universität Leiden sowie Inhaber eines Lehrstuhls für KI an der Rheinisch-Westfälischen Technischen Hochschule Aachen (RWTH), beschreibt Matrixmultiplikation als eine fundamentale Operation für Informatikanwendungen. Eine praktisch relevante Beschleunigung des Multiplizierens von Matrizen wäre daher "von erheblicher Bedeutung". Die von DeepMind eingesetzte Methode des Deep Reinforcement Learning hält er in dem Zusammenhang für neu und interessant. Insgesamt dämpft er aber die Euphorie über die Resultate der Studie, die in seinen Augen "leicht zu überschätzen" sei.

Automatisches Design von Algorithmen: nicht ganz neu

Das automatische Design von Algorithmen, basierend auf Machine Learning, sei eben keine ganz neue Entwicklung. Der Ansatz werde seit über zehn Jahren erforscht und hat bereits zu neuen Algorithmen geführt – unter anderem für das "notorisch schwierige Erfüllbarkeitsproblem" in der Aussagenlogik, das in der Informatik intensiv studiert wird. Dieses Problem habe wichtige Anwendung bei der Verifikation und beim Testen von Hard- und Software. Hoos kennt weitere Beispiele aus dem Design von Algorithmen zum Lösen mathematischer Optimierungsfragen aus Industrie und Wissenschaft, als Minenfeld kommt ihm hierbei das Mixed Integer Programming in den Sinn.

Die Anwendung des automatischen Algorithmendesigns auf Matrixmultiplikation ist neu und der methodische Ansatz wirkt vielversprechend. Allerdings sieht Hoos "noch keine Anzeichen für einen Durchbruch im Bereich der automatischen Algorithmenkonstruktion". Bedeutsam dürfte hier eine praktische Unterscheidung sein: So hatte die Forschung zur Verbesserung von Matrixmultiplikations-Algorithmen sich bislang vorrangig auf Verfahren konzentriert, die mathematisch beweisbare Beschleunigungen für beliebig große Matrizen ergeben. Die dabei gefundenen Algorithmen sind in der Praxis nahezu unbedeutsam, da ihre Vorteile "erst für astronomisch große Matrizen zutage treten", wie Hoos einwendet.

Was bedeutet das konkret?

Der Ansatz der Autoren der AlphaTensor-Studie hingegen ziele auf Algorithmen für praktisch relevante Matrixgrößen ab. Das zeichnet ihn gegenüber der bisherigen Forschung aus, wenngleich numerische Stabilität "nur am Rande berücksichtigt" werde. Der Experte hegt daher keine übergroßen Erwartungen, sondern geht davon aus, dass die automatisch entdeckten Algorithmen nicht direkt in praktische Anwendungen eingehen werden. Hoos lässt sich von der im Paper angegebenen Beschleunigung nicht vom Hocker reißen: Diese sei gegenüber bekannten Verfahren relativ klein. "Für Matrizen der Größe 8192 beträgt sie etwas über vier Prozent, und für die Größe 20.480 auf einer handelsüblichen GPU bereits nur noch knapp über zwei Prozent", erläutert er in seiner Stellungnahme. In bisher bekannten Beispielen zur automatischen Algorithmenkonstruktion seien hingegen oftmals Beschleunigungen um den Faktor zwei bis fünfzig gemessen worden, also um hunderte bis zehntausende Prozent.

Ein Manko des veröffentlichten Artikels sieht Hoos darin, dass die Autoren "keine Ergebnisse bezüglich des Effekts des Einsatzes der automatisch konstruierten Algorithmen für tatsächliche Anwendungen angeben". Vorläufig bleibt daher die Frage noch offen, was die neuen Erkenntnisse für Computergrafik, wissenschaftliche Simulation oder Machine Learning konkret bedeuten. Die Arbeit ist in den Augen der konsultierten Experten "interessant, aber nicht bahnbrechend", da der methodische Ansatz spezifisch auf die Matrixmultiplikation ausgelegt sei. "Die Arbeit ist zweifellos für Experten im automatischen Algorithmendesign wie mich und meine Kollegen von technischem Interesse", schließt Hoos seine Stellungnahme. Wer in dem Bereich forscht, wird mit der Arbeit etwas anfangen können. Darauf aufbauende echte Durchbrüche in Forschung und Praxis erwarte er jedoch nicht.

Zu den Quellen: DeepMind, Nature and beyond

Mit dem Suchbegriff AlphaTensor eröffnet sich auf Twitter ein Kaleidoskop an Kurzkommentaren aus Forschung und Community: Wer sich berufen fühlt, kann dort mitdiskutieren. Spannend wäre, was Strassen selbst über die Neuentdeckung denkt: Der 1936 geborene Forscher soll sich seit seiner Emeritierung allerdings primär mit der Theorie der Quantenphysik befassen.

Die Ergebnisse des DeepMind-Teams sind ein solider Beitrag auf dem Weg zur Erforschung automatisierter Algorithmendesigns, hier stellen sie nach Experten wie dem Kognitionswissenschaftler und KI-Forscher Joscha Bach aber erst den Anfang dar. Das Optimieren ganzer Algorithmen birgt Potenzial, insbesondere in der flankierenden Entwicklung neuer Hardware, so Bach gegenüber Heise. AlphaZero ist jedenfalls ein starker Algorithmus, dessen Einsatzzweck durch Erweiterungen über das Entwickeln von Spielen hinausreicht.

Wer sich ein genaueres Bild machen möchte, kann sich das bei Nature veröffentlichte Forschungspaper zu AlphaTensor selbst zu Gemüte führen – es ist frei zugänglich und lässt sich wahlweise im Browser lesen oder als PDF herunterladen. Eine kompaktere Version findet sich im DeepMind-Blog. Empfehlenswert ist auch ein Artikel in der MIT Technology Review, der eine erste Einschätzung bietet: "DeepMind's game-playing AI has beaten a 50-year-old record in computer science".

Wie wir nach der Veröffentlichung der deutschen Version dieses Artikels erfahren haben, hat ein Forscherteam am California Institute of Technology (CalTech) unter der Leitung von Prof. Anima Anandkumar vor vier Jahren StrassenNet entwickelt. Ihr Artikel ist lesenswert:

(sih)