Differenziazione automatica - Automatic differentiation

In matematica e algebra informatica , la differenziazione automatica ( AD ), chiamata anche differenziazione algoritmica , differenziazione computazionale , auto-differenziazione , o semplicemente autodiff , è un insieme di tecniche per valutare la derivata di una funzione specificata da un programma per computer. AD sfrutta il fatto che ogni programma per computer, per quanto complicato, esegue una sequenza di operazioni aritmetiche elementari (addizione, sottrazione, moltiplicazione, divisione, ecc.) e funzioni elementari (exp, log, sin, cos, ecc.). Applicando ripetutamente la regola della catena a queste operazioni, le derivate di ordine arbitrario possono essere calcolate automaticamente, con precisione alla precisione di lavoro e utilizzando al massimo un piccolo fattore costante più operazioni aritmetiche rispetto al programma originale.

Figura 1: In che modo la differenziazione automatica si collega alla differenziazione simbolica

La differenziazione automatica è distinta dalla differenziazione simbolica e dalla differenziazione numerica (il metodo delle differenze finite). La differenziazione simbolica può portare a codice inefficiente e deve affrontare la difficoltà di convertire un programma per computer in una singola espressione, mentre la differenziazione numerica può introdurre errori di arrotondamento nel processo di discretizzazione e cancellazione. Entrambi i metodi classici hanno problemi con il calcolo di derivate più elevate, dove la complessità e gli errori aumentano. Infine, entrambi i metodi classici sono lenti nel calcolare le derivate parziali di una funzione rispetto a molti input, come è necessario per gli algoritmi di ottimizzazione basati su gradiente . La differenziazione automatica risolve tutti questi problemi.

La regola della catena, accumulazione diretta e inversa

Fondamentale per AD è la scomposizione dei differenziali prevista dalla regola della catena . Per la composizione semplice

{\begin{allineato}y&=f(g(h(x)))=f(g(h(w_{0})))=f(g(w_{1}))=f(w_ {2})=w_{3}\\w_{0}&=x\\w_{1}&=h(w_{0})\\w_{2}&=g(w_{1})\\ w_{3}&=f(w_{2})=y\end{allineato}}

la regola della catena dà

{\frac {dy}{dx}}={\frac {dy}{dw_{2}}}{\frac {dw_{2}}{dw_{1}}}{\frac {dw_{1 }}{dx}}={\frac {df(w_{2})}{dw_{2}}}{\frac {dg(w_{1})}{dw_{1}}}{\frac {dh (w_{0})}{dx}}

Di solito, vengono presentate due modalità distinte di AD, accumulazione diretta (o modalità diretta ) e accumulazione inversa (o modalità inversa ). L'accumulazione diretta specifica che si attraversa la regola della catena dall'interno all'esterno (cioè prima calcola e poi e infine ), mentre l'accumulazione inversa ha l'attraversamento dall'esterno all'interno (prima calcola e poi e infine ). Più succintamente, $dw_{1}/dx$ $dw_{2}/dw_{1}$ $dy/dw_{2}$ $dy/dw_{2}$ $dw_{2}/dw_{1}$ $dw_{1}/dx$

l'accumulazione diretta calcola la relazione ricorsiva: con , e, ${\frac {dw_{i}}{dx}}={\frac {dw_{i}}{dw_{i-1}}}{\frac {dw_{i-1}}{dx}}$ $w_{3}=y$
l'accumulazione inversa calcola la relazione ricorsiva: con . ${\frac {dy}{dw_{i}}}={\frac {dy}{dw_{i+1}}}{\frac {dw_{i+1}}{dw_{i}}}$ $w_{0}=x$

Accumulo in avanti

Figura 2: Esempio di accumulazione forward con grafico computazionale

In avanti accumulo dC, una prima fissa la variabile indipendente rispetto al quale avviene la differenziazione e calcola la derivata di ciascuna sub- espressione ricorsivo. In un calcolo con carta e penna, ciò comporta la sostituzione ripetuta della derivata delle funzioni interne nella regola della catena:

{\begin{allineato}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{n-1}}}{\frac {\partial w_{n-1}}{\partial x}}\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{ n-1}}{\partial w_{n-2}}}{\frac {\partial w_{n-2}}{\partial x}}\right)\\[6pt]&={\frac {\ parziale y}{\parziale w_{n-1}}}\left({\frac {\partial w_{n-1}}{\parziale w_{n-2}}}\left({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&= \cdots \end{allineato}}

Questo può essere generalizzato a più variabili come prodotto matriciale di Jacobiani .

Rispetto all'accumulazione inversa, l'accumulazione a termine è naturale e di facile attuazione in quanto il flusso di informazioni derivate coincide con l'ordine di valutazione. Ogni variabile $w$ è aumentata con la sua derivata $ẇ$ (memorizzata come valore numerico, non come espressione simbolica),

{\dot {w}}={\frac {\partial w}{\partial x}}

come indicato dal punto. Le derivate vengono quindi calcolate in sincronia con le fasi di valutazione e combinate con altre derivate tramite la regola della catena.

Consideriamo ad esempio la funzione:

{\begin{allineato}z&=f(x_{1},x_{2})\\&=x_{1}x_{2}+\sin x_{1}\\&=w_{1} w_{2}+\sin w_{1}\\&=w_{3}+w_{4}\\&=w_{5}\end{allineato}}

Per chiarezza, le singole sottoespressioni sono state etichettate con le variabili

w i

.

La scelta della variabile indipendente a cui effettuare la differenziazione influenza i valori di seme $ẇ 1$ e $ẇ 2$ . Dato l'interesse per la derivata di questa funzione rispetto a $x 1$ , i valori del seme dovrebbero essere impostati a:

{\begin{allineato}{\dot {w}}_{1}={\frac {\partial x_{1}}{\partial x_{1}}}=1\\{\dot {w }}_{2}={\frac {\partial x_{2}}{\partial x_{1}}}=0\end{allineato}}

Con i valori di inizializzazione impostati, i valori si propagano utilizzando la regola della catena come mostrato. La Figura 2 mostra una rappresentazione grafica di questo processo come grafico computazionale.

Operazioni per calcolare il valore	Operazioni per calcolare la derivata
$w_{1}=x_{1}$	${\dot {w}}_{1}=1$ (seme)
$w_{2}=x_{2}$	${\dot {w}}_{2}=0$ (seme)
$w_{3}=w_{1}\cdot w_{2}$	${\dot {w}}_{3}=w_{2}\cdot {\dot {w}}_{1}+w_{1}\cdot {\dot {w}}_{2}$
$w_{4}=\sin w_{1}$	${\dot {w}}_{4}=\cos w_{1}\cdot {\dot {w}}_{1}$
$w_{5}=w_{3}+w_{4}$	${\dot {w}}_{5}={\dot {w}}_{3}+{\dot {w}}_{4}$

Per calcolare il gradiente di questa funzione di esempio, che richiede le derivate di $f$ rispetto non solo a $x 1$ ma anche a $x 2$ , viene eseguita una scansione aggiuntiva sul grafo computazionale utilizzando i valori seme . ${\dot {w}}_{1}=0;{\dot {w}}_{2}=1$

La complessità computazionale di uno sweep di accumulazione in avanti è proporzionale alla complessità del codice originale.

L'accumulo in avanti è più efficiente dell'accumulo inverso per le funzioni $f : R n \to R m$ con $m ≫ n$ poiché sono necessarie solo $n$ scansioni, rispetto a $m$ scansioni per l'accumulo inverso.

Accumulo inverso

Figura 3: Esempio di accumulazione inversa con grafico computazionale

Al contrario accumulo dC, la variabile dipendente da differenziato è fisso e il derivato viene calcolato rispetto alle ciascun sub espressione ricorsivo. In un calcolo con carta e penna, la derivata delle funzioni esterne viene ripetutamente sostituita nella regola della catena:

{\frac {\partial y}{\partial x}}={\frac {\partial y}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x }}=\left({\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac { \partial w_{1}}{\partial x}}=\left(\left({\frac {\partial y}{\partial w_{3}}}{\frac {\partial w_{3}}{\ parziale w_{2}}}\right){\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}} =\cdots

$Nell'accumulazione$ inversa, la quantità di interesse è l' aggiunto , indicato con una barra ( $w̄$ ); è una derivata di una variabile dipendente scelta rispetto a una sottoespressione $w$ :

{\bar {w}}={\frac {\parziale y}{\parziale w}}

L'accumulo inverso attraversa la regola della catena dall'esterno all'interno o, nel caso del grafico computazionale in Figura 3, dall'alto verso il basso. La funzione di esempio ha un valore scalare, e quindi c'è solo un seme per il calcolo della derivata ed è necessaria solo una scansione del grafico computazionale per calcolare il gradiente (a due componenti). Questa è solo metà del lavoro rispetto all'accumulazione diretta, ma l'accumulazione inversa richiede la memorizzazione delle variabili intermedie $w i$ e delle istruzioni che le hanno prodotte in una struttura dati nota come lista di Wengert (o "nastro"), che può consumare una memoria significativa se il grafico computazionale è grande. Questo può essere mitigato in una certa misura memorizzando solo un sottoinsieme delle variabili intermedie e quindi ricostruendo le variabili di lavoro necessarie ripetendo le valutazioni, una tecnica nota come rimaterializzazione . Il checkpoint viene utilizzato anche per salvare gli stati intermedi.

Le operazioni per il calcolo del derivato mediante accumulazione inversa sono riportate nella tabella sottostante (si noti l'ordine inverso):

Operazioni per calcolare la derivata: ${\bar {w}}_{5}=1{\text{ (seme)}}$; ${\bar {w}}_{4}={\bar {w}}_{5}$; ${\bar {w}}_{3}={\bar {w}}_{5}$; ${\bar {w}}_{2}={\bar {w}}_{3}\cdot w_{1}$; ${\bar {w}}_{1}={\bar {w}}_{3}\cdot w_{2}+{\bar {w}}_{4}\cdot \cos w_{ 1}$

Il grafico del flusso di dati di un calcolo può essere manipolato per calcolare il gradiente del suo calcolo originale. Questo viene fatto aggiungendo un nodo aggiunto per ogni nodo primario, connesso da archi aggiunti paralleli agli archi primari ma fluiscono nella direzione opposta. I nodi nel grafico aggiunto rappresentano la moltiplicazione per le derivate delle funzioni calcolate dai nodi nel primale. Ad esempio, l'aggiunta nella primale causa il fanout nell'aggiunta; fanout nel primordiale causa addizione nell'aggiunto; una funzione unaria $y = f (x)$ nelle cause $primarie x̄ = ȳ f'(x)$ nell'aggiunto; eccetera.

L'accumulo inverso è più efficiente dell'accumulo in avanti per le funzioni $f : R n \to R m$ con $m ≪ n$ poiché sono necessarie solo $m$ scansioni, rispetto a $n$ scansioni per l'accumulo in avanti.

La modalità inversa AD è stata pubblicata per la prima volta nel 1976 da Seppo Linnainmaa .

La retropropagazione degli errori nei percettroni multistrato, una tecnica utilizzata nell'apprendimento automatico , è un caso speciale di modalità inversa AD.

Oltre l'accumulo diretto e inverso

L'accumulazione diretta e inversa sono solo due modi (estremi) di attraversare la regola della catena. Il problema di calcolare uno Jacobiano completo di $f : R n \to R m$ con un numero minimo di operazioni aritmetiche è noto come problema di accumulazione jacobiana ottimale (OJA), che è NP-completo . Al centro di questa dimostrazione è l'idea che possono esistere dipendenze algebriche tra le parziali locali che etichettano i bordi del grafo. In particolare, due o più etichette di bordo possono essere riconosciute uguali. La complessità del problema è ancora aperta se si assume che tutte le etichette di bordo siano uniche e algebricamente indipendenti.

Differenziazione automatica tramite numeri doppi

La differenziazione automatica in modalità diretta si ottiene aumentando l' algebra dei numeri reali e ottenendo una nuova aritmetica . Un componente aggiuntivo viene aggiunto a ogni numero per rappresentare la derivata di una funzione al numero e tutti gli operatori aritmetici vengono estesi per l'algebra aumentata. L'algebra aumentata è l'algebra dei numeri doppi .

Sostituisci ogni numero con il numero , dove è un numero reale, ma è un numero astratto con la proprietà (un infinitesimo ; vedi Analisi infinitesimale liscia ). Usando solo questo, l'aritmetica regolare dà $\,x$ $x+x'\varepsilon$ $x'$ $\varepsilon$ $\varepsilon ^{2}=0$

{\begin{allineato}(x+x'\varepsilon)+(y+y'\varepsilon)&=x+y+(x'+y')\varepsilon \\(x+x'\varepsilon) \cdot (y+y'\varepsilon )&=xy+xy'\varepsilon +yx'\varepsilon +x'y'\varepsilon ^{2}=xy+(xy'+yx')\varepsilon \end{allineato} }

e similmente per sottrazione e divisione.

Ora, i polinomi possono essere calcolati in questa aritmetica aumentata. Se , allora $P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}$

{\begin{allineato}P(x+x'\varepsilon)&=p_{0}+p_{1}(x+x'\varepsilon)+\cdots +p_{n}(x+x' \varepsilon )^{n}\\&=p_{0}+p_{1}x+\cdots +p_{n}x^{n}+p_{1}x'\varepsilon +2p_{2}xx'\ varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon \\&=P(x)+P^{(1)}(x)x'\varepsilon \end{allineato}}

dove denota la derivata di rispetto al suo primo argomento, e , chiamato seme , può essere scelto arbitrariamente.

P^{(1)}

P

x'

La nuova aritmetica consiste di coppie ordinate , elementi scritti , con aritmetica ordinaria sulla prima componente e aritmetica di differenziazione del primo ordine sulla seconda componente, come descritto sopra. L'estensione dei risultati di cui sopra sui polinomi alle

funzioni analitiche fornisce un elenco dell'aritmetica di base e alcune funzioni standard per la nuova aritmetica:

{\displaystyle\langle x,x'\rangle}

{\begin{allineato}\left\langle u,u'\right\rangle +\left\langle v,v'\right\rangle &=\left\langle u+v,u'+v'\ right\rangle \\\left\langle u,u'\right\rangle -\left\angle v,v'\right\rangle &=\left\angle uv,u'-v'\right\rangle \\\ left\langle u,u'\right\rangle *\left\langle v,v'\right\rangle &=\sinistra\angle uv,u'v+uv'\right\rangle \\\left\angle u, u'\right\rangle /\left\langle v,v'\right\rangle &=\left\langle {\frac {u}{v}}, {\frac {u'v-uv'}{v^ {2}}}\right\rangle \quad (v\neq 0)\\\sin \left\langle u,u'\right\rangle &=\left\langle \sin(u),u'\cos( u)\right\rangle \\\cos \left\langle u,u'\right\rangle &=\left\langle \cos(u),-u'\sin(u)\right\rangle \\\exp \left\langle u,u'\right\rangle &=\left\langle \exp u,u'\exp u\right\rangle \\\log \left\langle u,u'\right\rangle &=\ left\langle \log(u),u'/u\right\rangle \quad (u>0)\\\left\langle u,u'\right\rangle ^{k}&=\left\langle u^ {k},ku^{k-1}u'\right\rangle \quad (u\neq 0)\\\left|\left\langle u,u'\right\rangle \right|&=\left\ langle \left|u\right|, u'{\mbox{segno}}u\right\rangle \quad (u\neq 0)\end{allineato}}

e in generale per la funzione primitiva ,

g

g(\langle u,u'\rangle,\langle v,v'\rangle)=\langle g(u,v),g_{u}(u,v)u'+g_{v}( u,v)v'\rangle

dove e sono le derivate di rispetto al primo e al secondo argomento, rispettivamente.

g_{u}

g_{v}

g

Quando un'operazione aritmetica di base binaria viene applicata ad argomenti misti, la coppia e il numero reale, il numero reale viene prima elevato a . La derivata di una funzione nel punto si trova ora calcolando usando l'aritmetica sopra, che dà come risultato. $\langle u,u'\rangle$ $c$ ${\displaystyle\langle c,0\rangle}$ $f:\mathbb {R} \to \mathbb {R}$ $x_{0}$ $f(\langle x_{0},1\rangle)$ $\langle f(x_{0}),f'(x_{0})\rangle$

Argomenti e funzioni vettoriali

Le funzioni multivariate possono essere gestite con la stessa efficienza e meccanismi delle funzioni univariate adottando un operatore derivativo direzionale. Cioè, se è sufficiente calcolare , la derivata direzionale di at nella direzione , questa può essere calcolata utilizzando la stessa aritmetica di cui sopra. Se si desiderano tutti gli elementi di , sono necessarie le valutazioni delle funzioni. Si noti che in molte applicazioni di ottimizzazione, la derivata direzionale è effettivamente sufficiente. $y'=\nabla f(x)\cdot x'$ $y'\in \mathbb {R} ^{m}$ $f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}$ $x\in \mathbb {R} ^{n}$ $x'\in \mathbb {R} ^{n}$ $(\langle y_{1},y'_{1}\rangle,\ldots,\langle y_{m},y'_{m}\rangle)=f(\langle x_{1},x '_{1}\rangle ,\ldots ,\langle x_{n},x'_{n}\rangle )$ $\nabla f$ $n$

Ordine elevato e molte variabili

L'aritmetica di cui sopra può essere generalizzata per calcolare il secondo ordine e le derivate superiori di funzioni multivariate. Tuttavia, le regole aritmetiche si complicano rapidamente: la complessità è quadratica nel massimo grado di derivata. Invece, può essere utilizzata l'algebra dei polinomi di Taylor troncati . L'aritmetica risultante, definita su numeri duali generalizzati, consente un calcolo efficiente utilizzando funzioni come se fossero un tipo di dati. Una volta noto il polinomio di Taylor di una funzione, le derivate sono facilmente estraibili.

Implementazione

L'AD in avanti è implementato da un'interpretazione non standard del programma in cui i numeri reali sono sostituiti da numeri doppi, le costanti vengono elevate a numeri doppi con un coefficiente zero epsilon e le primitive numeriche vengono sollevate per operare su numeri doppi. Questa interpretazione non standard viene generalmente implementata utilizzando una delle due strategie: trasformazione del codice sorgente o sovraccarico dell'operatore .

Trasformazione del codice sorgente (SCT)

Figura 4: Esempio di come potrebbe funzionare la trasformazione del codice sorgente

Il codice sorgente di una funzione è sostituito da un codice sorgente generato automaticamente che include istruzioni per il calcolo dei derivati intercalati con le istruzioni originali.

La trasformazione del codice sorgente può essere implementata per tutti i linguaggi di programmazione ed è anche più semplice per il compilatore eseguire ottimizzazioni del tempo di compilazione. Tuttavia, l'implementazione dello stesso strumento AD è più difficile.

Sovraccarico operatore (OO)

Figura 5: Esempio di come potrebbe funzionare il sovraccarico dell'operatore

L'overload dell'operatore è una possibilità per il codice sorgente scritto in un linguaggio che lo supporta. Gli oggetti per i numeri reali e le operazioni matematiche elementari devono essere sovraccaricati per soddisfare l'aritmetica aumentata illustrata sopra. Ciò non richiede alcuna modifica nella forma o nella sequenza delle operazioni nel codice sorgente originale per differenziare la funzione, ma spesso richiede modifiche nei tipi di dati di base per i numeri e i vettori per supportare l'overload e spesso comporta anche l'inserimento di speciali operazioni di segnalazione.

Il sovraccarico dell'operatore per l'accumulo in avanti è facile da implementare ed è possibile anche per l'accumulo inverso. Tuttavia, gli attuali compilatori sono in ritardo nell'ottimizzazione del codice rispetto all'accumulo in avanti.

L'overloading degli operatori, sia per l'accumulo in avanti che per quello inverso, può essere adatto ad applicazioni in cui gli oggetti sono vettori di numeri reali piuttosto che scalari. Questo perché il nastro comprende quindi operazioni vettoriali; questo può facilitare implementazioni computazionalmente efficienti in cui ogni operazione vettoriale esegue molte operazioni scalari. Le tecniche di differenziazione algoritmica vettoriale aggiunta (vettore AAD) possono essere utilizzate, ad esempio, per differenziare i valori calcolati dalla simulazione Monte-Carlo.

Esempi di implementazioni con sovraccarico dell'operatore della differenziazione automatica in C++ sono le librerie Adept e Stan .

Guarda anche

Programmazione differenziabile

Appunti

Riferimenti

Ulteriori letture

Rall, Louis B. (1981). Differenziazione automatica: tecniche e applicazioni . Appunti delle lezioni di Informatica. 120 . Springer . ISBN 978-3-540-10861-0.
Griewank, Andreas; Walter, Andrea (2008). Valutare i derivati: principi e tecniche di differenziazione algoritmica . Altri titoli in matematica applicata. 105 (2a ed.). SIAM . ISBN 978-0-89871-659-7. Archiviato dall'originale il 23/03/2010 . Estratto il 21-10-2009 .
Neidinger, Richard (2010). "Introduzione alla differenziazione automatica e alla programmazione orientata agli oggetti MATLAB" (PDF) . Recensione SIAM . 52 (3): 545–563. CiteSeerX 10.1.1.362.6580 . doi : 10.1137/080743627 . Estratto il 15/03/2013 .
Naumann, Uwe (2012). L'arte di differenziare i programmi per computer . Software-Ambienti-strumenti. SIAM . ISBN 978-1-611972-06-1.
Henrard, Marc (2017). Spiegazione della differenziazione algoritmica in finanza . Spiegazione dell'ingegneria finanziaria. Palgrave Macmillan . ISBN 978-3-319-53978-2.

link esterno

www.autodiff.org , Un "sito di accesso a tutto ciò che vuoi sapere sulla differenziazione automatica"
Differenziazione automatica di programmi OpenMP paralleli
Differenziazione automatica, modelli C++ e fotogrammetria
Differenziazione automatica, approccio al sovraccarico dell'operatore
Calcola derivati analitici di qualsiasi programma Fortran77, Fortran95 o C tramite un'interfaccia basata sul web Differenziazione automatica dei programmi Fortran
Descrizione e codice di esempio per la differenziazione automatica in avanti in Scala
estensioni di differenziazione automatica finmath-lib , Differenziazione automatica per variabili casuali (implementazione Java della differenziazione automatica stocastica).
Differenziazione algoritmica aggiunta: calibrazione e teorema della funzione implicita
Articolo e

implementazione della differenziazione automatica basata su modelli C++

Tangente Fonte-to-Source Derivati debuggable

[1] , Greci esatti di primo e secondo ordine per differenziazione algoritmica

[2] , Differenziazione algoritmica aggiunta di un'applicazione accelerata da GPU

[3] , Metodi aggiunti nel supporto di strumenti software di finanza computazionale per la differenziazione algoritmicaop

Languages

In other projects