Transformation of linearized computational graphs driven by the associativity of the chain rule

Mosenkis, Viktor; Naumann, Uwe (Thesis advisor); Steihaug, Trond (Thesis advisor)

Aachen (2017, 2018)
Doktorarbeit

Dissertation, RWTH Aachen University, 2017

Kurzfassung

Effiziente Berechnung von Ableitungen mathematischer Funktionen, die durch Implementierung in einer Programmiersprache gegeben sind, wird immer wichtiger in verschiedenen Bereichen von Industrie und Forschung. Nichtdestotrotz bleibt die effiziente und zuverlässige Berechnung von Ableitungen eine große Herausforderung. In der Vergangenheit wurden oft finite Differenzen zur Approximation von Sensitivitätsinformation verwendet. Dieses Verfahren hat jedoch zwei entscheidende Nachteile. Das erste Problem ist, dass in vielen Fällen die Annäherung der Tangente durch die Sekante nicht genau genug ist. Das zweite Problem ist, dass die Berechnungskosten für die Berechnung der dichtbesetzten Jacobi Matrix proportional zu der Anzahl der Eingaben dieser Funktion ist. Um beiden Problemen zu begegnen, wird deswegen Für die Berechnung der Sensitivitätsinformation wird daher immer öfter Algorithmisches (oder Automatisches) Differenzieren (AD) verwendet. AD ist eine Sammlung von Techniken, die eine exakte Berechnung von Ableitungsinformation der Funktion F, die durch ein Computer-Programm geben ist, erlauben. Die verschieden AD Techniken werden oft durch Eliminations-Methoden auf dem linearisierten gerichteten azyklischem Graphen (linearized directed acyclic graphs=l-DAGs) beschrieben. L-DAGs sind Berechnungsgraphen, bei denen die Kantengewichte den lokalen partiellen Ableitungen der zugehörigen Operationen entsprechen. Die am meisten verwendeten Eliminations-Methoden sind Kanten- und Knotenelimination. Für die Berechnung der Jacobi Matrix mit Hilfe der Knoten- oder Kanteneliminationen müssen sämtliche Zwischenknoten bzw. -kanten eliminiert werden, so dass ein bipartiter Graph entsteht. Beide Techniken basieren auf der lokalen Ausnutzung der Kettenregel. Die Knotenelimination kann durch eine Folge von Kanteneliminationen ausgedrückt werden, und ist somit ein Spezialfall der Kantenelimination. Assoziativität der Kettenregel erlaubt die Ausführung der Kanten- und Knotenelimination in verschiedenen Rheinfolgen. Als Kanten- bzw. Knoteneliminationsproblem (vertex elimination = VE bzw. edge elimination=EE) versteht man also die Suche nach einer Sequenz von Kanten- bzw. Knoteneliminationen, bei der die Anzahl der durchgeführten Multiplikationen minimal ist. Will man nur Jakobi-Matrix-Vektor-Produkte bestimmen, und nicht die gesamte Jakobi-Matrix, so sieht man sich mit dem Problem der minimalen Kantenanzahl konfrontiert (minimum edge count=MEC). Bei dem MEC Problem versucht man, eine Sequenz von Kanten- bzw. Knoteneliminationen zu finden, so dass die Anzahl der Kanten im resultierenden Graphen minimal ist. Es wird vermutet, dass alle oben genannten Probleme NP-Schwer sind. In der Praxis verwendet man daher Greedy-ähnliche Algorithmen, um schnell eine ”fast” optimale L¨osung zu finden. Branch-and-Bound Methoden werden verwendet, falls eine exakte L¨osung gebraucht wird. Das Ziel dieser Dissertation ist es, die Weiterentwicklung dieser Algorithmen voranzutreiben. Es wird daher zuerst versucht, die Struktur des Problems besser zu verstehen. Dafür werden einige Eigenschaften der l-DAGs und der Eliminationsmethoden bewiesen. Diese Eigenschaften bilden die Basis alle weiteren Ergebnisse, zusätzlich erlauben sie den Suchraum für die Branchand-Bound Algorithmen signifikant zu verkleinern. Ein sehr großer Teil dieser Arbeit widmet sich der Entwicklung eines neuen Algorithmus für die Berechnung der unteren Schranken für die oben genannten Probleme. Es wird gezeigt, dass der neue Ansatz in den meisten Fällen bessere untere Schranken liefert, als die bisher existierenden Algorithmen. An dieser Stelle sei angemerkt, dass es die bisher einzigen Schranken für das MEC Problem sind. Ein weiteres Ergebnis dieser Dissertation sind Optimalität erhaltende Eliminationen. Bei Branch-and-Bound Algorithmen erlauben diese eine deutliche Reduzierung des Suchraums, auch die Greedy-ähnliche Algorithmen lassen sich dadurch verbessern. Ebenso lassen sich durch die Optimalität erhaltende Eliminationen Kantenelimination besser einsetzen. Aufgrund des deutlich größeren Suchraums, findet Kantenelimination bisher kaum Verwendung in der Praxis. In dieser Arbeit wird gezeigt, dass Verwendung von Kanteneliminationen dennoch sinnvoll ist: durch das Mischen von Kanten- und Knoteneliminationen können einerseits bessere Ergebnisse erzielt werden, d.h. berechnete Lösung benötigt weniger Multiplikationen, andererseits lässt sich so die Lösung schneller finden.