Implementazione della differenziazione automatica per la derivata 2: algoritmo per attraversare il grafico computazionale?

Question

Sto tentando di implementare automatic differentiation per un pacchetto di statistiche Python (la formulazione del problema è simile alle formulazioni del problema di ottimizzazione).

Il grafico computazionale viene generato utilizzando l'overloading dell'operatore e le funzioni di fabbrica per operazioni come sum(), exp(), ecc. Ho implementato la differenziazione automatica per il gradiente utilizzando l'accumulo inverso. Tuttavia, ho trovato molto più difficile implementare la differenziazione automatica per la seconda derivata (l'Hessiana). So come eseguire i singoli calcoli del 2 ° gradiente parziale, ma ho avuto problemi a trovare un modo intelligente per attraversare il grafico e fare gli accumuli. Qualcuno sa di buoni articoli che forniscono algoritmi per la differenziazione automatica per la seconda libreria derivata o open source che implementa lo stesso da cui posso provare a imparare?

Answer 1

In primo luogo è necessario decidere se si vuoi o calcolare una povera iuta o qualcosa di più vicino a una iuta completamente densa.

Se lo sparse è ciò che si desidera, attualmente esistono due modi competitivi per farlo. Solo utilizzando il grafico di calcolo in un modo intelligente, un sol colpo d'inversione del grafico di calcolo è possibile calcolare la matrice Hessiana utilizzando l'algoritmo edge_pushing:

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

Oppure si può provare le tecniche di colorazione dei grafi per compattare il matrice Hessiana in una matrice di un minor numero di colonne, quindi utilizzare accumulo inverso per calcolare ogni colonna

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

Se quello che vuoi è una tela di iuta densa (inusuale in pratica) e poi il probabilmente meglio di calcolare una colonna della dell'Assia a un tempo utilizzando l'accumulo inverso (ricerca di BRUCE CHRISTIANSON e accumulo inverso)

Answer 2

Il metodo usuale per approssimare dell'Hessiana in 3 dimensioni è il BFGS

Il metodo L-BFGS è simile.

Here è possibile trovare il codice sorgente per L-BFGS (che calcola l'Hessian come risultato intermedio per la risoluzione di ODE) in diverse lingue (C#, C++, VBA, ecc.) Anche se non in python. Penso che non sia facile da tradurre.

Se avete intenzione di tradurre l'alg da un'altra lingua, con particolare attenzione agli errori numerici e fare un'analisi di sensibilità (è necessario calcolare l'inverso della matrice Hessiana)