Ich versuche, automatische Differenzierung für ein Python-Statistikpaket zu implementieren (die Problemformulierung ähnelt den Formulierungsproblemen für Optimierungen). .
Der Berechnungsgraph wird mit Operatorenüberladen und Factory-Funktionen für Operationen wie sum (), exp () usw. erzeugt. Ich habe eine automatische Differenzierung für den Gradienten implementiert, indem ich eine umgekehrte Akkumulation verwende. Ich habe jedoch festgestellt, dass die automatische Differenzierung für die zweite Ableitung (Hessisch) viel schwieriger ist. Ich weiß, wie man die einzelnen Berechnungen des zweiten partiellen Gradienten macht, aber ich hatte Schwierigkeiten, eine intelligente Methode zu finden, um den Graphen zu durchlaufen und die Akkumulationen durchzuführen. Kennt jemand gute Artikel, die Algorithmen zur automatischen Unterscheidung für die zweite Ableitung oder Open-Source-Bibliotheken geben, die dasselbe implementieren, von dem ich vielleicht lernen möchte?
Zuerst müssen Sie entscheiden, ob Sie ein spärliches Hessian oder etwas näher zu einem völlig dichten Hessian berechnen möchten.
Wenn Sparse das ist, was Sie wollen, gibt es derzeit zwei konkurrierende Möglichkeiten, dies zu tun. Nur mit Hilfe des Berechnungsgraphen auf clevere Weise, einem umgekehrten Durchlauf des Berechnungsgraphen, können Sie die Hesse-Matrix mit dem Algorithmus edge_pushing berechnen:
Oder Sie können Graph-Färbetechniken ausprobieren, um Ihre hessische Matrix in eine Matrix mit weniger Spalten zu komprimieren, und dann die umgekehrte Akkumulation verwenden, um jede Spalte zu berechnen.
Wenn Sie einen dichten Hessian haben (was in der Praxis ungewöhnlich ist), dann ist es wahrscheinlich besser, eine Spalte der Hesse gleichzeitig zu berechnen, indem Sie die umgekehrte Kumulation verwenden (Suche nach BRUCE CHRISIANSON und umgekehrter Akkumulation).
Die übliche Methode zur Annäherung des Hessischen in 3 Dimensionen ist die BFGS
Die Methode L-BFGS ist ähnlich.
Hier finden Sie den Quellcode für den L-BFGS (der den Hessian als Zwischenergebnis berechnet zum Lösen von ODEs) in mehreren Sprachen (C #, C ++, VBA usw.), allerdings nicht in Python. Ich denke, es ist nicht leicht zu übersetzen.
Wenn Sie das alg aus einer anderen Sprache übersetzen, achten Sie besonders auf numerische Fehler und machen Sie eine Sensitivitätsanalyse (Sie müssen das Inverse der hessischen Matrix berechnen)
Tags und Links python math hessian-matrix