La mise en œuvre pour la différentiation automatique deuxième dérivé: algorithme pour parcourir le graphe de calcul?

Question

Je cherche à mettre en œuvre différenciation automatique pour un paquet de statistiques Python (la formulation du problème est similaires aux formulations de problèmes d'optimisation).

Le graphique de calcul est généré en utilisant des fonctions de surcharge d'opérateur et de l'usine pour des opérations telles que la somme (), exp (), etc. Je mis en oeuvre une différenciation automatique pour le gradient en utilisant accumulation inverse. Cependant, j'ai trouvé la différenciation automatique pour la mise en œuvre de la dérivée seconde (hessois) beaucoup plus difficile. Je sais comment faire les calculs individuels 2e gradient partiel, mais je l'ai eu du mal à venir avec une façon intelligente de parcourir le graphique et faire les accumulations. Ne sait quiconque de bons articles qui donnent des algorithmes de différenciation automatique pour la seconde bibliothèques de sources ouvertes dérivées ou qui mettent en œuvre la même que je peux essayer d'apprendre?

Answer 1

D'abord, vous devez décider si vous voulez o calculer une clairsemés ou quelque chose hessois plus proche d'un complètement dense hessois.

Si rares est ce que vous voulez, il existe actuellement deux façons de le faire concurrence. Utilisant uniquement le graphique de calcul d'une manière intelligente, un balayage inverse du graphe de calcul, vous pouvez calculer la matrice hessienne en utilisant l'algorithme de edge_pushing:

http://www.tandfonline.com/doi/full/10.1080/ 10556788.2011.580098

Vous pouvez essayer des techniques de coloration graphique pour compacter votre matrice hessienne dans une matrice de moins de colonnes, puis utilisez l'accumulation inverse pour calculer chaque colonne

http://citeseerx.ist.psu.edu/ viewdoc / résumé? doi = 10.1.1.66.2603

Si ce que vous voulez est un dense hessois (rare dans la pratique), alors votre probablement mieux de calculer une colonne du hessien à la fois avec l'accumulation inverse (recherche BRUCE CHRISTIANSON et de l'accumulation inverse)

Answer 2

La méthode habituelle pour approcher le hessien en 3 dimensions est le BFGS

La méthode L-BFGS de similaire.

vous pouvez trouver le code source pour le L-BFGS (qui calcule hessois comme résultat intermédiaire pour résoudre EDO) en plusieurs langues (C #, C ++, VBA, etc.) mais pas en python. Je pense qu'il est pas facile à traduire.

Si vous allez traduire le alg d'une autre langue, accorder une attention particulière aux erreurs numériques et faire une analyse de sensibilité (vous devrez calculer l'inverse de la matrice hessienne)