Implémentation de la différenciation automatique pour la dérivée seconde: algorithme pour parcourir le graphe de calcul?

Question

Je tente d'implémenter automatic differentiation pour un package de statistiques Python (la formulation du problème est similaire aux formulations de problèmes d'optimisation). Le graphique de calcul est généré en utilisant la surcharge d'opérateur et les fonctions d'usine pour des opérations comme sum(), exp(), etc. J'ai mis en place une différenciation automatique pour le gradient en utilisant l'accumulation inverse. Cependant, j'ai trouvé que la mise en œuvre de la différenciation automatique pour la dérivée seconde (la Hesse) était beaucoup plus difficile. Je sais comment faire les calculs individuels du 2e gradient partiel, mais j'ai eu du mal à trouver une façon intelligente de parcourir le graphique et de faire les accumulations. Est-ce que quelqu'un sait de bons articles qui donnent des algorithmes pour la différenciation automatique de la dérivée seconde ou des bibliothèques open source qui implémentent la même chose que je peux essayer d'apprendre?

Answer 1

D'abord, vous devez décider si vous vouloir o calculer un Hessian clairsemé ou quelque chose de plus près d'un Hessian complètement dense.

Si ce que vous voulez est clairsemé, il existe actuellement deux façons de le faire. 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

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

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.2603

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

Answer 2

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

Le procédé L-BFGS est similaire.

Here Vous pouvez trouver le code source du L-BFGS (qui calcule le Hessian comme résultat intermédiaire pour résoudre les ODE) dans plusieurs langages (C#, C++, VBA, etc.) mais pas en python. Je pense que ce n'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)