Ist in Bezug auf die automatische Differenzierung die Quellcodetransformation (STC) effizienter als das Überladen von Operatoren (OO)?

12

Wir arbeiten an einem Bayes'schen Modell für einen Raum-Zeit-Prozess und verwenden einen No-U-Turn-Sampler (NUTS), für den ein Modell für die Log-Wahrscheinlichkeit und den Gradienten in Bezug auf die Modellparameter erforderlich ist. Um es kurz zu machen, wir haben eine ziemlich komplizierte log-Wahrscheinlichkeitsfunktion , die statistische Verteilungen, kronecker-Produkte, Exponentiale, Verhältnisse, if-else-Aussagen usw. umfasst und die wir bereitstellen müssen und die Steigung zu NUTS hat. Einige Pakete ( Stan und Julias MCMC ) verwenden nach meinem besten Wissen das Überladen von Operatoren, um den Gradienten automatisch zu ermitteln.f:RnR

Wenn wir in der Lage wären, eine eigene Verlaufsfunktion zu erstellen, möglicherweise mithilfe eines automatischen Diff-Tools für die Quellcodetransformation, würden wir eine bessere Leistung erzielen, oder wäre OO genauso gut oder besser?

Matthew Emmett
quelle

Antworten:

9

Die Umwandlung von Quelle zu Quelle gilt als Goldstandard in Bezug auf die Leistung. OO-Ansätze scheinen fast genauso gut zu sein, da es mehr OO-Pakete gibt und die Leistung nicht als wesentlicher Nachteil erwähnt wird. Wenn Sie eine OO-Bibliothek finden, die Ihnen für die Sprache, in der Sie arbeiten, gefällt, würde ich sie zuerst verwenden und später herausfinden, ob Sie unbedingt eine Umwandlung von Quelle zu Quelle benötigen und ob ein solches Tool vorhanden ist, das Ihren Anforderungen entspricht. Die typischen Kosten eines durch automatische Differenzierung erzeugten Derivats betragen ungefähr das Drei- bis Fünffache einer Funktionsbewertung, um die Dinge in Zusammenhang zu bringen.

Es gibt mehr OO-Pakete, da es einfacher ist, automatische Differenzierungstools mit Operatorüberladung zu implementieren, als die Übersetzung von Quelle zu Quelle. Das Implementieren eines Quell-zu-Quell-Übersetzers entspricht dem Schreiben eines Compilers: Der Quellcode muss analysiert und mit einem Token versehen werden, und anschließend müssen Transformationsregeln auf den resultierenden Ausdrucksbaum angewendet werden. Das Buch von Andreas Griewank, Bewertung von Derivaten: Prinzipien und Techniken der algorithmischen Differenzierung, 2. Auflage, befasst sich ausführlicher mit den Kompromissen.

Geoff Oxberry
quelle
Vielen Dank an Geoff, das hilft sehr, insbesondere Ihre Schätzung der typischen Kosten.
Matthew Emmett
1

Für die Gradientenberechnung verwenden Sie den umgekehrten Modus von AD. Dies erfordert in beiden Fällen den Aufbau eines Operandenstapels, in der OO-Version muss auch ein Operationsstapel aufgebaut werden, der im Reverse Traversal des Codes interpretiert werden muss. Quelltransformierter Code schreibt die Operationen in umgekehrter Reihenfolge als zusätzlichen kompilierten Quellcode aus. Der Aufwand, den Operations-Interpreter im Code zu haben, kann erheblich sein. Es gibt Vergleiche zwischen von Tapenade erzeugtem Code und Adol-C, die zugunsten von Tapenade herauskommen.

Lutz Lehmann
quelle