Différenciation automatique - Automatic differentiation

En mathématiques et de calcul formel , la différentiation automatique ( AD ), également appelée différenciation algorithmique , la différenciation de calcul , auto-différenciation , ou simplement autodiff , est un ensemble de techniques pour évaluer la dérivée d'une fonction spécifiée par un programme informatique. AD exploite le fait que tout programme informatique, aussi compliqué soit-il, exécute une séquence d'opérations arithmétiques élémentaires (addition, soustraction, multiplication, division, etc.) et de fonctions élémentaires (exp, log, sin, cos, etc.). En appliquant à plusieurs reprises la règle de la chaîne à ces opérations, des dérivées d'ordre arbitraire peuvent être calculées automatiquement, avec précision à la précision de travail, et en utilisant au plus un petit facteur constant plus d'opérations arithmétiques que le programme original.

Figure 1 : Comment la différenciation automatique se rapporte à la différenciation symbolique

La différenciation automatique est distincte de la différenciation symbolique et de la différenciation numérique (la méthode des différences finies). La différenciation symbolique peut conduire à un code inefficace et se heurte à la difficulté de convertir un programme informatique en une seule expression, tandis que la différenciation numérique peut introduire des erreurs d'arrondi dans le processus de discrétisation et d'annulation. Les deux méthodes classiques ont des problèmes avec le calcul des dérivées plus élevées, où la complexité et les erreurs augmentent. Enfin, les deux méthodes classiques sont lentes à calculer les dérivées partielles d'une fonction par rapport à de nombreuses entrées, comme cela est nécessaire pour les algorithmes d' optimisation basés sur le gradient . La différenciation automatique résout tous ces problèmes.

La règle de la chaîne, l'accumulation avant et arrière

La décomposition des différentiels fournie par la règle de la chaîne est fondamentale pour l'AD . Pour la composition simple

{\begin{aligned}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{aligned}}

la règle de la chaîne donne

{\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}}

Habituellement, deux modes distincts d'AD sont présentés, l'accumulation directe (ou mode direct ) et l'accumulation inverse (ou mode inverse ). L'accumulation directe spécifie que l'on parcourt la règle de la chaîne de l'intérieur vers l'extérieur (c'est-à-dire d'abord calculer puis et enfin ), tandis que l'accumulation inverse a la traversée de l'extérieur vers l'intérieur (d'abord calculer puis et enfin ). Plus succinctement, ${\style d'affichage dw_{1}/dx}$ ${\style d'affichage dw_{2}/dw_{1}}$ $dy/dw_{2}$ $dy/dw_{2}$ ${\style d'affichage dw_{2}/dw_{1}}$ ${\style d'affichage dw_{1}/dx}$

l'accumulation en avant calcule la relation récursive : avec , et, ${\frac {dw_{i}}{dx}}={\frac {dw_{i}}{dw_{i-1}}}{\frac {dw_{i-1}}{dx}}$ ${\style d'affichage w_{3}=y}$
l'accumulation inverse calcule la relation récursive : avec . ${\frac {dy}{dw_{i}}}={\frac {dy}{dw_{i+1}}}{\frac {dw_{i+1}}{dw_{i}}}$ ${\style d'affichage w_{0}=x}$

Accumulation à terme

Figure 2 : Exemple d'accumulation à terme avec graphe de calcul

Dans l'accumulation directe AD, on fixe d'abord la variable indépendante par rapport à laquelle la différenciation est effectuée et on calcule la dérivée de chaque sous- expression de manière récursive. Dans un calcul sur papier, cela implique de substituer à plusieurs reprises la dérivée des fonctions internes dans la règle de la chaîne :

{\begin{aligned}{\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 {\ partiel y}{\partial w_{n-1}}}\gauche({\frac {\partial w_{n-1}}{\partial w_{n-2}}}\gauche({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&= \cdots \end{aligné}}

Cela peut être généralisé à plusieurs variables en tant que produit matriciel de Jacobiens .

Par rapport à l'accumulation inverse, l'accumulation avant est naturelle et facile à mettre en œuvre car le flux d'informations dérivées coïncide avec l'ordre d'évaluation. Chaque variable $w$ est augmentée avec son dérivé $W$ (stocké en tant que valeur numérique, et non pas une expression symbolique),

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

comme indiqué par le point. Les dérivées sont ensuite calculées en synchronisation avec les étapes d'évaluation et combinées avec d'autres dérivées via la règle de la chaîne.

A titre d'exemple, considérons la fonction :

{\begin{aligned}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{aligned}}

Pour plus de clarté, les sous-expressions individuelles ont été étiquetées avec les variables

w i

.

Le choix de la variable indépendante à laquelle est effectuée la différenciation affecte les semences des valeurs $W 1$ et $W 2$ . Compte tenu de l'intérêt pour la dérivée de cette fonction par rapport à $x 1$ , les valeurs de départ doivent être définies sur :

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

Avec les valeurs de départ définies, les valeurs se propagent à l'aide de la règle de chaîne comme indiqué. La figure 2 montre une représentation graphique de ce processus sous forme de graphique informatique.

Opérations pour calculer la valeur	Opérations pour calculer la dérivée
${\style d'affichage w_{1}=x_{1}}$	${\dot {w}}_{1}=1$ (planter)
${\style d'affichage w_{2}=x_{2}}$	${\dot {w}}_{2}=0$ (planter)
$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}$
${\style d'affichage w_{5}=w_{3}+w_{4}}$	${\dot {w}}_{5}={\dot {w}}_{3}+{\dot {w}}_{4}$

Pour calculer le gradient de cet exemple de fonction, qui nécessite les dérivées de $f$ par rapport non seulement à $x 1$ mais également à $x 2$ , un balayage supplémentaire est effectué sur le graphe de calcul en utilisant les valeurs de départ . ${\dot {w}}_{1}=0;{\dot {w}}_{2}=1$

La complexité de calcul d'un balayage d'accumulation vers l'avant est proportionnelle à la complexité du code d'origine.

L'accumulation directe est plus efficace que l'accumulation inverse pour les fonctions $f : R n \to R m$ avec $m ≫ n$ car seuls $n$ balayages sont nécessaires, contre $m$ balayages pour l'accumulation inverse.

Cumul inversé

Figure 3 : Exemple d'accumulation inversée avec graphe de calcul

Dans l'accumulation inverse AD, la variable dépendante à différencier est fixe et la dérivée est calculée par rapport à chaque sous- expression de manière récursive. Dans un calcul sur papier, la dérivée des fonctions externes est substituée à plusieurs reprises dans la règle de la chaîne :

{\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}}{\ partiel w_{2}}}\right){\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}} =\cdots

En accumulation inverse, la quantité d'intérêt est l' adjointe , notée par une barre ( $w̄$ ) ; c'est une dérivée d'une variable dépendante choisie par rapport à une sous-expression $w$ :

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

L'accumulation inverse traverse la règle de la chaîne de l'extérieur vers l'intérieur, ou dans le cas du graphique de calcul de la figure 3, de haut en bas. L'exemple de fonction est à valeur scalaire, et il n'y a donc qu'une seule graine pour le calcul de la dérivée, et un seul balayage du graphique de calcul est nécessaire pour calculer le gradient (à deux composants). Ce n'est que la moitié du travail par rapport à l'accumulation directe, mais l'accumulation inverse nécessite le stockage des variables intermédiaires $w i$ ainsi que les instructions qui les ont produites dans une structure de données connue sous le nom de liste de Wengert (ou "bande"), qui peut consomment beaucoup de mémoire si le graphe de calcul est grand. Cela peut être atténué dans une certaine mesure en stockant uniquement un sous-ensemble des variables intermédiaires, puis en reconstruisant les variables de travail nécessaires en répétant les évaluations, une technique connue sous le nom de rematérialisation . Le point de contrôle est également utilisé pour enregistrer les états intermédiaires.

Les opérations de calcul de la dérivée par accumulation inversée sont présentées dans le tableau ci-dessous (notez l'ordre inversé) :

Opérations pour calculer la dérivée: ${\bar {w}}_{5}=1{\text{ (graine)}}$; ${\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}$

Le graphique de flux de données d'un calcul peut être manipulé pour calculer le gradient de son calcul d'origine. Ceci est fait en ajoutant un nœud adjoint pour chaque nœud primaire, connecté par des arêtes adjointes qui sont parallèles aux arêtes primaires mais s'écoulent dans la direction opposée. Les nœuds du graphe adjoint représentent la multiplication par les dérivées des fonctions calculées par les nœuds du primal. Par exemple, l'addition dans le primal provoque un déploiement dans l'adjoint ; l'épanouissement dans le primal provoque l'addition dans l'adjoint ; une fonction unaire $y = f (x)$ dans les causes primaires $x̄ = ȳ f'(x)$ dans l'adjoint ; etc.

L' accumulation inverse est plus efficace que l' accumulation proposées pour cette fonction $f : R n \to R m$ avec $m « n$ que seulement $m$ balayages sont nécessaires, par rapport à $n$ balayages pour l' accumulation de l' avant.

Le mode inverse AD a été publié pour la première fois en 1976 par Seppo Linnainmaa .

La rétropropagation des erreurs dans les perceptrons multicouches, une technique utilisée en apprentissage automatique , est un cas particulier de l'AD en mode inverse.

Au-delà de l'accumulation avant et arrière

L'accumulation directe et inverse ne sont que deux manières (extrêmes) de franchir la règle de la chaîne. Le problème du calcul d'un Jacobien complet de $f : R n \to R m$ avec un nombre minimum d'opérations arithmétiques est connu sous le nom de problème d' accumulation Jacobienne optimale (OJA), qui est NP-complet . Au centre de cette preuve se trouve l'idée que des dépendances algébriques peuvent exister entre les partiels locaux qui étiquettent les arêtes du graphe. En particulier, deux étiquettes de bord ou plus peuvent être reconnues comme égales. La complexité du problème est encore ouverte si l'on suppose que toutes les étiquettes d'arêtes sont uniques et algébriquement indépendantes.

Différenciation automatique à l'aide de nombres doubles

La différenciation automatique en mode direct est accomplie en augmentant l' algèbre des nombres réels et en obtenant une nouvelle arithmétique . Un composant supplémentaire est ajouté à chaque nombre pour représenter la dérivée d'une fonction au nombre, et tous les opérateurs arithmétiques sont étendus pour l'algèbre augmentée. L'algèbre augmentée est l'algèbre des nombres duels .

Remplacez chaque nombre par le nombre , où est un nombre réel, mais est un nombre abstrait avec la propriété (un infinitésimal ; voir Lisser l'analyse infinitésimale ). En utilisant seulement ceci, l'arithmétique régulière donne ${\style d'affichage \,x}$ $x+x'\varepsilon$ ${\style d'affichage x'}$ $\varepsilon$ $\varepsilon ^{2}=0$

{\begin{aligned}(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{aligned} }

et de même pour la soustraction et la division.

Maintenant, les polynômes peuvent être calculés dans cette arithmétique augmentée. Si , alors $P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}$

{\begin{aligned}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{aligned}}

où désigne la dérivée de par rapport à son premier argument, et , appelé germe , peut être choisi arbitrairement.

{\style d'affichage P^{(1)}}

{\style d'affichage P}

{\style d'affichage x'}

La nouvelle arithmétique se compose de paires ordonnées , d'éléments écrits , avec une arithmétique ordinaire sur la première composante, et une arithmétique de différenciation de premier ordre sur la seconde composante, comme décrit ci-dessus. L'extension des résultats ci-dessus sur les polynômes aux

fonctions analytiques donne une liste de l'arithmétique de base et de quelques fonctions standard pour la nouvelle arithmétique :

\langle x,x'\rangle

{\begin{aligned}\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\langle v,v'\right\rangle &=\left\langle uv,u'-v'\right\rangle \\\ left\langle u,u'\right\rangle *\left\langle v,v'\right\rangle &=\left\langle uv,u'v+uv'\right\rangle \\\left\langle 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\ angle \gauche|u\droit|, u'{\mbox{sign}}u\right\rangle \quad (u\neq 0)\end{aligned}}

et en général pour la fonction primitive ,

{\style d'affichage 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

où et sont les dérivées de par rapport à ses premier et deuxième arguments, respectivement.

g_{u}

{\style d'affichage g_{v}}

{\style d'affichage g}

Lorsqu'une opération arithmétique de base binaire est appliquée à des arguments mixtes (la paire et le nombre réel), le nombre réel est d'abord élevé à . La dérivée d'une fonction au point est maintenant trouvée en calculant en utilisant l'arithmétique ci-dessus, ce qui donne comme résultat. $\langle u,u'\rangle$ ${\style d'affichage c}$ $\langle c,0\rangle$ $f:\mathbb {R} \to \mathbb {R}$ ${\style d'affichage x_{0}}$ $f(\langle x_{0},1\rangle )$ $\langle f(x_{0}),f'(x_{0})\rangle$

Arguments et fonctions vectoriels

Les fonctions multivariées peuvent être traitées avec la même efficacité et les mêmes mécanismes que les fonctions univariées en adoptant un opérateur dérivé directionnel. Autrement dit, s'il suffit de calculer , la dérivée directionnelle de à dans la direction , cela peut être calculé en utilisant la même arithmétique que ci-dessus. Si tous les éléments de sont souhaités, des évaluations de fonction sont nécessaires. Notez que dans de nombreuses applications d'optimisation, la dérivée directionnelle est en effet suffisante. $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$ ${\style d'affichage n}$

Ordre élevé et nombreuses variables

L'arithmétique ci-dessus peut être généralisée pour calculer les dérivées de second ordre et supérieures de fonctions multivariées. Cependant, les règles arithmétiques se compliquent rapidement : la complexité est quadratique au plus haut degré de dérivée. Au lieu de cela, l' algèbre polynomiale de Taylor tronquée peut être utilisée. L'arithmétique résultante, définie sur des nombres doubles généralisés, permet un calcul efficace en utilisant des fonctions comme s'il s'agissait d'un type de données. Une fois que le polynôme de Taylor d'une fonction est connu, les dérivées sont facilement extraites.

Mise en œuvre

L'AD en mode direct est implémentée par une interprétation non standard du programme dans laquelle les nombres réels sont remplacés par des nombres doubles, les constantes sont élevées à des nombres doubles avec un coefficient epsilon nul et les primitives numériques sont élevées pour fonctionner sur des nombres doubles. Cette interprétation non standard est généralement implémentée à l'aide de l'une des deux stratégies suivantes : transformation du code source ou surcharge d'opérateur .

Transformation de code source (SCT)

Figure 4 : Exemple de la façon dont la transformation du code source pourrait fonctionner

Le code source d'une fonction est remplacé par un code source généré automatiquement qui comprend des instructions de calcul des dérivées entrelacées avec les instructions d'origine.

La transformation du code source peut être implémentée pour tous les langages de programmation, et il est également plus facile pour le compilateur d'optimiser le temps de compilation. Cependant, la mise en œuvre de l'outil AD lui-même est plus difficile.

Surcharge de l'opérateur (OO)

Figure 5 : Exemple de comment la surcharge d'opérateur pourrait fonctionner

La surcharge d'opérateurs est une possibilité pour le code source écrit dans un langage le supportant. Les objets pour les nombres réels et les opérations mathématiques élémentaires doivent être surchargés pour prendre en charge l'arithmétique augmentée décrite ci-dessus. Cela ne nécessite aucun changement dans la forme ou la séquence d'opérations dans le code source d'origine pour que la fonction soit différenciée, mais nécessite souvent des modifications des types de données de base pour les nombres et les vecteurs afin de prendre en charge la surcharge et implique souvent également l'insertion d'opérations de marquage spéciales.

La surcharge de l'opérateur pour l'accumulation avant est facile à mettre en œuvre, et également possible pour l'accumulation inverse. Cependant, les compilateurs actuels sont à la traîne dans l'optimisation du code par rapport à l'accumulation en avant.

La surcharge d'opérateurs, pour l'accumulation directe et inverse, peut être bien adaptée aux applications où les objets sont des vecteurs de nombres réels plutôt que des scalaires. En effet, la bande comporte alors des opérations vectorielles ; cela peut faciliter des implémentations efficaces en termes de calcul où chaque opération vectorielle effectue de nombreuses opérations scalaires. Des techniques de différenciation algorithmique adjointe vectorielle (AAD vectorielle) peuvent être utilisées, par exemple, pour différencier des valeurs calculées par simulation Monte-Carlo.

Les bibliothèques Adept et Stan sont des exemples d'implémentations surchargées d'opérateurs de la différenciation automatique en C++ .

Voir également

Programmation différentiable

Remarques

Les références

Lectures complémentaires

Rall, Louis B. (1981). Différenciation automatique : techniques et applications . Notes de cours en informatique. 120 . Springer . ISBN 978-3-540-10861-0.
Griewank, Andreas; Walther, Andréa (2008). Évaluation des dérivés : principes et techniques de différenciation algorithmique . Autres titres en mathématiques appliquées. 105 (2e éd.). SIAM . ISBN 978-0-89871-659-7. Archivé de l'original le 2010-03-23 . Récupéré le 2009-10-21 .
Neidinger, Richard (2010). "Introduction à la différenciation automatique et à la programmation orientée objet MATLAB" (PDF) . Revue SIAM . 52 (3) : 545-563. CiteSeerX 10.1.1.362.6580 . doi : 10.1137/080743627 . Récupéré le 15/03/2013 .
Naumann, Uwe (2012). L'art de différencier les programmes informatiques . Logiciels-Environnements-outils. SIAM . ISBN 978-1-611972-06-1.
Henriard, Marc (2017). Différenciation algorithmique en finance expliquée . Ingénierie financière expliquée. Palgrave Macmillan . ISBN 978-3-319-53978-2.

Liens externes

www.autodiff.org , Un "site d'accès à tout ce que vous voulez savoir sur la différenciation automatique"
Différenciation automatique des programmes OpenMP parallèles
Différenciation automatique, modèles C++ et photogrammétrie
Différenciation automatique, approche de surcharge de l'opérateur
Calculer les dérivés analytiques de n'importe quel programme Fortran77, Fortran95 ou C via une interface Web Différenciation automatique des programmes Fortran
Description et exemple de code pour la différenciation automatique directe dans Scala
extensions de différenciation automatique finmath-lib , Différenciation automatique pour variables aléatoires (implémentation Java de la différenciation automatique stochastique).
Différenciation algorithmique adjointe : étalonnage et théorème des fonctions implicites
Article de différenciation automatique basé sur des modèles C++ et implémentation
Tangent Source-to-Source débogable dérivés
[1] , Grecs exacts du premier et du deuxième ordre par différenciation algorithmique
[2] , Différenciation algorithmique adjointe d'une application accélérée par GPU
[3] , Méthodes Adjointes dans le Support d'Outils Logiciels de Finance Computationnelle pour la Différenciation Algorithmique

Languages

In other projects