Hessisk automatisk differentiering

Inom tillämpad matematik är hessisk automatisk differentiering tekniker baserade på automatisk differentiering (AD) som beräknar andraderivatan av en $n$ -dimensionell funktion, känd som den hessiska matrisen .

När man undersöker en funktion i närheten av en punkt kan man förkasta många komplicerade globala aspekter av funktionen och exakt approximera den med enklare funktioner. Den kvadratiska approximationen är den bäst passande kvadratiska i närheten av en punkt och används ofta inom teknik och vetenskap. För att beräkna den kvadratiska approximationen måste man först beräkna dess gradient och hessiska matris.

Låt ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} } ,$ för varje $x\in \mathbb {R} ^{n }$ den hessiska matrisen $H(x)\in \mathbb {R} ^{n\ gånger n}$ är andra ordningens derivata och är en symmetrisk matris.

Produkter med omvänd hessisk vektor

För en given $u\in \mathbb {R} ^{n}$ beräknar denna metod effektivt den hessiska vektorprodukten $H(x)u$ . Kan alltså användas för att beräkna hela hessian genom att beräkna ${\displaystyle H(x)e_{i}} ,$ för $i=1,\ldots ,n$ .

Metoden fungerar genom att först använda framåt AD för att utföra ${\displaystyle f(x)\rightarrow u^{T}\nabla f(x)} ,$ därefter beräknar metoden sedan gradient av $u^{T}\nabla f(x)$ med omvänd AD för att ge $\nabla \left(u\cdot \nabla f(x)\right)=u^{T}H(x)=(H(x)u)^{T}$ . Båda dessa två steg kommer vid en kostnad som är proportionell mot att utvärdera funktionen, så hela Hessian kan utvärderas till en kostnad som är proportionell mot n utvärderingar av funktionen.

Omvänd hessian: Edge_Pushing

En algoritm som beräknar hela Hessian med ett svep framåt och ett bakåt av beräkningsgrafen är Edge_Pushing. Edge_Pushing är resultatet av att tillämpa den omvända gradienten på beräkningsgrafen för gradienten. Naturligtvis har denna graf n utmatningsnoder, så på sätt och vis måste man tillämpa den omvända gradientmetoden på varje utgående nod. Edge_Pushing gör detta genom att ta hänsyn till överlappande beräkningar.

Exempel på utförande av Edge_Pushing

Algoritmens indata är beräkningsgrafen för funktionen. Efter ett föregående svep framåt där alla mellanvärden i beräkningsgrafen beräknas, initierar algoritmen ett svep bakåt av grafen. När man möter en nod som har en motsvarande olinjär elementär funktion skapas en ny olinjär kant mellan nodens föregångare, vilket indikerar att det finns olinjär interaktion mellan dem. Se exempelbilden till höger. Till denna olinjära kant finns en kantvikt som är den andra ordningens partiella derivata av den olinjära noden i förhållande till dess föregångare. Denna olinjära kant skjuts sedan ned till ytterligare föregångare på ett sådant sätt att när den når de oberoende noderna, är dess kantvikt den andra ordningens partiella derivata av de två oberoende noderna den ansluter.

Graffärgningstekniker för hessianer

Graffärgningsteknikerna utforskar gleshetsmönster för den hessiska matrisen och billiga hessiska vektorprodukter för att få hela matrisen. Således är dessa tekniker lämpade för stora, glesa matriser. Den allmänna strategin för en sådan färgningsteknik är som följer.

1. Få det globala sparsitetsmönstret för $H$
2. Använd en graffärgningsalgoritm som låter oss komprimera sparsitetsstrukturen.
3. För varje önskad punkt $x\in \mathbb {R} ^{n}$ beräkna numeriska poster i den kompakta matrisen.
4. Återställ den hessiska matrisen från den kompakta matrisen.

Steg ett och två behöver bara utföras en gång och brukar bli kostsamma. När man vill beräkna hessian på flera punkter (som i en optimeringsrutin), upprepas steg 3 och 4.

Färgat sparsitetsmönster av den hessiska matrisen

Den kompakta hessiska matrisen

Som ett exempel visar figuren till vänster gleshetsmönstret för den hessiska matrisen där kolumnerna har färgats på ett sådant sätt att kolumner av samma färg kan slås samman utan att det uppstår en kollision mellan elementen.

Det finns ett antal färgningstekniker, var och en med en specifik återhämtningsteknik. För en omfattande undersökning, se. Det har varit framgångsrika numeriska resultat av sådana metoder.