Matrixcalculus
von Prof. Dr. Joachim Giesen
Screenshot der Seite matrixcalculus.org
Dem berühmten Physiker Richard Feynman wird das Zitat “Calculus is the language god talks” zugeschrieben. Calculus ist der englische Ausdruck für Analysis (Integral- und Differentialrechnung), die uns schon in der Schule im Rahmen der Kurvendiskussion begegnet. Die Extrempunkte einer differenzierbaren Funktion können über ihre Ableitungen charakterisiert werden. In einem lokalen Extremum verschwindet die Ableitung der Funktion und das Extremum ist ein lokales Minimum, falls die zweite Ableitung der Funktion an dieser Stelle positiv ist. Ist die zweite Ableitung negativ, dann ist das Extremum ein lokales Maximum. Diese Einsicht hat weitreichende Folgen und viele Anwendungen. In Wirtschaft und Technik sucht man oft nach einer optimalen Lösung, zum Beispiel können Kosten minimiert oder der Gewinn maximiert werden. Auch in der Physik spielen Extremalprinzipen eine zentrale Rolle. In der klassischen Mechanik können Bewegungsgleichungen aus dem Prinzip der kleinsten Wirkung abgeleitet werden.
Auch wir sind über Optimierungsprobleme zu der Aufgabe gekommen, Ableitungen ausrechnen zu müssen. Unsere Optimierungsprobleme kommen aus dem Gebiet des maschinellen Lernens, das sich grob gesagt damit beschäftigt, aus beobachteten Daten ein Modell für die Vorhersage zukünftiger Daten abzuleiten. Ein Standardansatz ist, das Modell unter Benutzung der Daten aus einer vorgegebenen Klasse von Modellen auszuwählen. Die Auswahl trifft man mit Hilfe eines Optimierungsproblems, z.B. indem man die sogenannte Likelihood des Modells unter den gegebenen Daten maximiert, oder eine Verlustfunktion auf der Klasse der Modelle minimiert.
Optimierungsprobleme aus dem maschinellen Lernen sind oft in der Sprache der linearen Algebra geschrieben. Die zu optimierende Funktion ist also eine Funktion von Vektoren oder Matrizen. Ein einfaches Beispiel ist die lineare Regression, in der man mit Hilfe der Methode der kleinsten Quadrate eine lineare Funktion an gegebene Datenpunkte anpasst (Abbildung 1).
Abbildung 1: A ist eine Matrix, in deren Spalten die Datenpunkte stehen und y der Vektor der entsprechenden Funktionswerte. Ziel ist es, den Parametervektor x zu finden, der den quadratischen Fehler minimiert.
In einem konkreten Problem haben die Vektoren und Matrizen, die in den Problemen des maschinellen Lernens auftreten, feste Werte und feste Dimensionen. Zu Beispiel könnte es sein, dass wir an 314 Datenpunkten mit jeweils 42 numerischen Werten für Eigenschaften (z.B. Höhe, Breite, Länge, Gewicht und ähnliches) jeweils einen numerischen Wert beobachtet haben. Die Datenpunkte können wir in einer Daten- oder Merkmalsmatrix A mit den Dimensionen 42 × 314 und die Beobachtungen in einem Vektor y der Dimension 42 zusammenfassen. Für die Datenmatrix und den Beobachtungsvektor können wir dann eine lineare Regression durchführen, d.h. das zugehörige Optimierunsgproblem lösen. Zur Lösung brauchen wir einen Lösungsalgorithmus. Diesen Algorithmus wollen wir nicht jedes Mal neu schreiben, wenn sich Daten oder Dimensionen ändern. Wir wollen einen Algorithmus, dem wir eine beliebige Datenmatrix A und einen passenden Beobachtungsvektor y übergeben, aus denen der Algorithmus dann die Lösung des Regressionsproblems berechnet. Wir wollen also eine abstrakte Formulierung des Algorithmus für abstrakte Datenmatrizen A und Beobachtungsvektoren y, den wir mit konkreten Werten für A und y instanziieren können.
Die meisten Optimierungsalgorithmen des maschinellen Lernens benutzen Ableitungen der zu optimierenden Funktion, die auch Zielfunktion des Problems genannt wird. Die Grundidee ist, dass man immer ein kleines Stück in Richtung der Ableitung geht bis man ein Optimum, in dem die Ableitung verschwindet, gefunden hat. Für den Optimierungsalgorithmus brauchen wir also die Ableitung der Zielfunktion. Diese Ableitung würden wir gerne wieder in der Sprache der linearen Algebra schreiben, d.h. wieder als eine Funktion der Vektor- und Matrixsymbole, die schon in der Zielfunktion vorkommen. Ein Matrixcalculus ist ein Algorithmus, der die Ableitung einer Funktion, die in der Sprache der linearen Algebra gegeben ist, auch in der Sprache der linearen Algebra ausgibt.
Zu unserem Erstaunen, war das Matrixcalculus Problem, also das Finden eines Matrixcalculus Algorithmus, vor kurzem noch nicht gelöst, obwohl die Analysis schon vor mehr als 350 Jahren von Isaac Newton und Gottfried Wilhem Leibniz enwickelt wurde und die formale Sprache der linearen Algebra auch schon älter als hundert Jahre ist. Bislang wurden bekannte, händisch oder halbautomatisch berechnete Ableitungen in einem Matrix Cookbook oder auf Wikipedia tabelliert. Dabei hat es durchaus schon Versuche gegeben, das Matrixcalculus Problem zu lösen. Das Interesse am Matrixcalculus rührt daher, dass es hocheffiziente Softwarebibliotheken zur Auswertung von Ausdrücken in der formalen Sprache der linearen Algebra gibt. Diese Softwarebibliotheken möchte man gerne direkt nutzen, wenn man einen Optimierungsalgorithmus implementiert, da die Implementierung dadurch erheblich schneller werden kann.
Wir konnten das Matrixcalculus Problem dann tatsächlich lösen und haben unsere Lösung implementiert. Die Implementierung steht als Webservice unter www.matrixcalculus.orgExterner Link zur Verfügung (Abbildung 2). Dieser Webservice wurde in den letzten Jahren jeweils über 30.000-mal weltweit von Universitäten aus aller Welt und großen Internetkonzernen wie Google oder Facebook genutzt.
Abbildung 2: Screenshot des Matrixcalculus Webservices
Unsere Lösung basiert auf der Einsicht, dass die formale Sprache der linearen Algebra nicht wirklich für das algorithmische Problem des Ableitens geeignet ist. Ableitungen lassen sich viel einfacher in der Sprache von Tensoren, das sind Verallgemeinerungen von Vektoren und Matrizen, ausrechnen. Deshalb übersetzen wir zunächst Ausdrücke, die in der formalen Sprache der linearen Algebra gegeben sind, in Tensorausdrücken, die wir dann ganz einfach ableiten können. Die Ableitung liegt danach als Tensorausdruck vor, den wir dann wieder in die Sprache der linearen Algebra übersetzen. Die Rückübersetzung ist der eigentlich schwierige Teil, den wir mit Hilfe eines Systems von Übersetzungsregeln lösen.
Joachim Giesen, Univ.-Prof. Dr.
Professur für Theoretische Informatik II