DeepMind: Verbesserungen bei der Effizienz von Algorithmen

„Matrixmultiplikation ist in der Tat eine fundamentale Operation, die in vielen Informatikanwendungen eine wichtige Rolle spielt. Eine praktisch relevante, erhebliche Beschleunigung bei der Multiplikation von Matrizen wäre daher von erheblicher Bedeutung.“

„Die Verwendung von ‚deep reinforcement learning‘ in diesem Zusammenhang ist neu und interessant. In zwei wichtigen Punkten sind die Resultate der aktuellen Studie allerdings in ihrer Bedeutung leicht zu überschätzen.“

„Zum einen ist das automatische Design von Algorithmen basierend auf maschinellem Lernen und komplexen Optimierungsverfahren keineswegs eine neue Entwicklung. In der Tat wird dieser Ansatz seit über zehn Jahren erforscht und hat zum Beispiel zu neuen Algorithmen für das notorisch schwierige Erfüllbarkeitsproblem in der Aussagenlogik geführt, eines der am intensivsten studierten Probleme in der gesamten Informatik. Dieses Problem hat wichtige Anwendungen bei der Verifikation und beim Testen von Hard- und Software. Weitere Beispiele finden sich im Design von Algorithmen für die Lösung mathematischer Optimierungsprobleme – sogenannter mixed integer programming-Probleme –, die in der Industrie und Wissenschaft breit eingesetzt werden. Meine eigene Forschungsgruppe arbeitet seit ungefähr 15 Jahren in diesem Bereich, und wir stehen in engem Kontakt mit anderen Forschern, die ebenfalls in dieser Richtung tätig sind, woraus sich ein recht guter Überblick über die gesamte Forschungsrichtung ergibt. Auch in der automatischen Optimierung von Algorithmen für bestimmte Hardwareplattformen gibt es etliche Arbeiten, die klar zeigen, dass dies möglich ist und praktisch bedeutsam sein kann. Kurz zusammengefasst mag die Anwendung von automatischem Algorithmendesign auf Matrixmultiplikation durchaus neu sein und der methodische Ansatz zweifelsohne interessant, aber ich sehe keine Anzeichen für einen Durchbruch im Bereich der automatischen Algorithmenkonstruktion.“

„Zum zweiten hat die Forschung zur Verbesserung von Matrixmultiplikations-Algorithmen sich bislang hauptsächlich auf Verfahren konzentriert, die mathematisch beweisbare Beschleunigungen für beliebig große Matrizen ergeben. Wie auch in der aktuellen Studie korrekt konstatiert, sind die dabei gefunden Algorithmen allerdings praktisch unbedeutsam, da ihre Vorteile erst für astronomisch große Matrizen zu Tage treten. Der Ansatz der Autoren der aktuellen Studie hingegen zielt auf Algorithmen für bestimmte, praktisch relevante Matrixgrößen ab. Dies ist interessant, aber auch gegenüber der bisherigen Forschung auf diesem Gebiet weniger allgemein, insbesondere, da das praktisch wichtige Kriterium der numerischen Stabilität nur am Rande berücksichtigt wird. Obwohl ich kein Experte für Matrixmultiplikation bin, würde ich daher nicht erwarten, dass die automatisch konstruierten Algorithmen direkt in praktische Anwendungen eingehen; die Autoren geben leider keine Ergebnisse bezüglich des Effekts des Einsatzes der automatisch konstruierten Matrixmultiplikations-Algorithmen für tatsächliche Anwendungen, etwa im Bereich Computergraphik, wissenschaftliche Simulation oder maschinelles Lernen an.“

„Die in Abbildung 5 der Studie gezeigte Beschleunigung gegenüber einem bekannten Verfahren ist relativ klein: Für Matrizen der Größe 8192 beträgt sie etwas über vier Prozent, und für Größe 20.480 auf einer handelsüblichen GPU (graphics processing unit, ein Grafikprozessor; Anm. d. Red.) bereits nur noch knapp über zwei Prozent. In den zuvor genannten, vorher bekannten Beispielen zur automatischen Algorithmenkonstruktion wurden im Vergleich dazu vielfach Beschleunigungen um Faktoren zwischen 2 und 50 gemessen – also um hunderte bis zehntausende Prozent.“

„Insgesamt betrachte ich die aktuelle Arbeit als interessant, aber nicht als bahnbrechend. Teile des methodischen Ansatzes sind sehr spezifisch für die Matrixmultiplikation, diese könnten für Algorithmiker und Mathematiker, die auf diesem Gebiet arbeiten, sehr interessant sein. Andere Teile sind allgemeiner, allerdings auch schon im Wesentlichen aus vorherigen Arbeiten von Experten bei DeepMind bekannt. 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.“

„Ein Hinweis zu Beginn: Ich bin kein Experte auf dem Gebiet des Machine-Learnings, sondern für algebraische Algorithmen und Komplexität und äußere mich daher nur zu diesen Aspekten.“

„Die Matrixmultiplikation ist eine fundamentale Operation im Bereich der linearen Algebra. Sie bildet die Grundlage für viele weitere Matrixoperationen und findet breite Anwendung zum Beispiel in der angewandten Mathematik, der Informatik und den Ingenieurswissenschaften. Daher ist sowohl das theoretische Verständnis der Komplexität der Matrixmultiplikation als auch die Entwicklung von schnellen praktischen Algorithmen von großem Interesse.“

„Algorithmisch gesehen besitzt die Matrixmultiplikation eine Besonderheit, die das automatische Finden von Algorithmen vereinfacht: Wenn ich einen Algorithmus habe, der Matrizen fester (kleiner) Größe multipliziert, so kann man daraus einen Algorithmus konstruieren, der beliebig große Matrizen multipliziert. Dies hat man in der Vergangenheit schon mit Optimierungsverfahren aus der Numerik sowie SAT-Solvern erfolgreich versucht. Darüber hinaus sind die Algorithmen, die die Matrizen fester Größe multiplizieren, sehr strukturiert, sie sind im Wesentlichen nur eine Reihe von Zahlen.“

„In seiner bahnbrechenden Arbeit von 1969 hat Volker Strassen eine verbesserte Methode gefunden, die Matrizen der Größe zwei schneller multipliziert als das Standardverfahren. Der resultierende Algorithmus wird heute oft in der Praxis verwendet. In der jetzt vorliegenden Arbeit werden nun mit Machine-Learning-Methoden einige neue obere Schranken für die Multiplikation kleiner Matrizen gefunden. Dies trägt zu unserem theoretischen Verständnis der Matrixmultiplikation bei. Eine Verbesserung gegenüber Strassens Algorithmus bringt aber erst einmal nur die neue obere Schranke für die Multiplikation von Matrizen der Größe vier.“

„Der Algorithmus funktioniert allerdings nur über bestimmten Rechenstrukturen und zum Beispiel nicht über den reellen Zahlen. Viel interessanter erscheint mir hingegen 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.“

„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.“