Catégorie : Programmation

Selon Wikipedia, la dérivation automatique est algorithmique!

En mathématique et en calcul formel, la dérivation automatique (DA), également appelé dérivation algorithmique, dérivation formelle1,2, ou auto-dérivation est un ensemble de techniques d’évaluation de la dérivée d’une fonction par un programme informatique.

https://fr.wikipedia.org/wiki/Dérivation_automatique

Relevons d’abord une faute par rapport à l’anglais qui parle de la dérivée d’une fonction spécifiée par un programme informatique. Le mot “spécifiée” étant absent de la version française, le programme informatique s’entend comme l’outil contenant les techniques d’évaluation de la dérivée. La différence est de taille, mais dans les deux versions l’incohérence règne.

S’il s’agit de calcul formel au sens usuel, la fonction est donnée non sous la forme d’un programme impératif mais d’une expression formelle et on parle de dérivation symbolique. Sinon, il s’agit de la dérivation d’un programme, c’est-à-dire de dérivation algorithmique. Cependant, un programme peut être vu comme une expression particulière de type procédure, prenant comme entrées les paramètres et le corps de la fonction; et réciproquement, une expression peut être transformée en procédure selon un mécanisme d’évaluation (cf. l’article Computer_algebra de Wikipedia, section Expressions, paragraphe 2).

Pour résumer:

  • la dérivation algorithmique est une dérivation formelle opérant sur les expressions que constituent les éléments d’un programme.
  • la dérivation symbolique est une dérivation formelle opérant sur les expressions mathématiques classiques.

… et synonyme de dérivation formelle !!!

L’article se restreint aux mathématiques et au calcul formel. Ne sachant pas ce qu’est une dérivation automatique en mathématiques, on arrive au calcul formel et dans ce cadre, certes, la dérivation automatique est formelle! La boucle est-elle bouclée? Non, on y adjoint le terme auto-dérivation. L’auto-dérision serait-elle une dérision automatique? Décidément, ce premier paragraphe est à revoir. Hélas, le deuxième le conforte en une auto-satisfaction automatique.

…mais différente de la dérivation symbolique et de la dérivation numérique

La dérivation automatique est distincte de la dérivation symbolique et de la dérivation numérique (méthode des différences finies).

La dérivation symbolique est une dérivation automatique: sinon, je ne sais pas de quoi on parle, si ce n’est du lycéen sur ses exercices.

La dérivation numérique n’est pas automatiquement automatique mais sans doute la méthode la plus facilement automatisable. Et même elle devient, en abusant quelque peu, une dérivation algorithmique au grain le plus grossier…

Ces deux méthodes ne sont définies que par leurs défauts

La dérivation symbolique peut conduire à un code inefficace et se heurte à la difficulté de convertir un programme informatique en une seule expression, tandis que la dérivation numérique peut introduire des erreurs d’arrondi lors de la discrétisation et de l’annulation. Ces deux méthodes classiques ont par ailleurs des problèmes lors du calcul de dérivées d’ordre plus élevées, car la complexité et/ou les erreurs augmentent. Enfin, ces deux méthodes sont lentes pour calculer les dérivées partielles d’une fonction lorsque cette dernière dépend de nombreuses variables, comme cela est nécessaire pour les algorithmes d’optimisation par descente de gradient.

Idem

En quoi ces défauts empêchent-ils une méthode d’être automatique? Conduire à un code inefficace, c’est déjà arriver à un code!

Les idées présentées mériteraient d’être développées.

… et la dérivation automatique résout tous ces problèmes (sic)

Tout est dit dans ce titre, qui est la conclusion du deuxième paragraphe!

Ma conclusion: une entrée Wikipedia pour la dérivation algorithmique

Il faut redonner au terme automatique son sens usuel: automatique ne signifie pas algorithmique, sauf abusivement dans un contexte spécial. La dérivation algorithmique est une dérivation automatique de code. Il faut présenter les autres dérivations automatiques et montrer en quoi elles se distinguent, notamment leurs avantages et leurs inconvénients, et renvoyer à un article spécial pour la dérivation algorithmique, en évitant donc ce double biais: une équivalence usurpée avec une méthode et la relégation des méthodes concurrentes.

L’article n’est pas seul en cause: rechercher “algorithmic differentiation” ou “computational differentiation” sur Wikipedia donne “Automatic_differentiation”. C’est équivalent, vous dit-on.

On doit s’appuyer sur le schéma pertinent faisant intervenir la dérivation symbolique et la dérivation algorithmique et le détailler. Cf. bouton ci-dessous.

simulation numérique et dérivation automatique

Les opérateurs associatifs du C++ sont asociaux

Le C++ a le défaut d’être un peu binaire… dans sa façon de traiter les opérations n-aires qui se moque bien de l’intention associative du programmeur. Faut-il attendre un compilateur quantique avec états non-binaires pour traiter ensemble les opérandes associées par les parenthèses? 😉

Le problème

Bien que les opérateurs + et * soient associatifs du point de vue mathématique, le C++ traite leurs opérandes 2 par 2 de gauche à droite. Ainsi a+b+c+d est vu comme: ((a+b)+c)+d.

sans qu’il y ait moyen de spécifier que l’on veut une somme de quatre opérandes autrement que par l’appel, moins expressif, d’une fonction comme sum(a,b,c,d), Certes, par le moyen classique des expression-templates, on pourrait aboutir au résultat voulu, mais au prix de perdre le respect des parenthèses. Par exemple, dans le cas où le programmeur écrirait (a+b+c)+d, une expression-template pourrait grouper les trois premiers termes, mais finirait par y agréger le quatrième. A moins d’ajouter au standard C++ un opérateur d’appel externe (static operator ()), qui opérerait sur le résultat de a+b+c, il n’y a aucun moyen de garder trace des parenthèses.

Ceci est un problème sérieux pour une interface de programmation, car il est important de respecter l’intention exprimée par l’utilisateur.

Proposition pour le C++

Soit un type Expr sur lequel nous proposons la possibilité de définir l’opérateur + suivant:

enum ExprOperator { ..., OpSum, ... OpProduct, ...};
struct Expr { ExprOperator; std::vector<Expr> operands;};
std::vector<Expr> to_vector(Expr... ee);

Expr operator+(Expr e, Expr... ee) // <- proposition
{
    return Expr { OpSum, to_vector(e,ee...) };
}

A noter: ce programme compile, mais l’opérateur+ n’est compris qu’avec deux arguments, ce qui est un peu limité pour un deuxième argument variadique. Nous voulons qu’il soit accepté pour ce qu’il est. Avec ceci, nous sommes capables de traduire (a+b+c)+d en Expr{OpSum,{Expr{OpSum,{a,b,c}},d} respectant l’original.

Bien sûr, toutes les variantes prenant const Expr& et Expr&& sont possibles.

Conversions implicites ou opérations avec d’autres types

Bien souvent, ayant une variable a de type Expr, nous voulons lui ajouter un type numérique, par exemple 1, comme dans a+1 ou 1+a sans préciser a+Expr(1) ou Expr(1)+a, ce qui ruinerait l’élégance de notre expression. L’opérateur + binaire permet classiquement de traiter cela. Comment le généraliser à une somme à opérandes multiples, comme dans 1+a+b ou a+1+b?

Nous proposons d’utiliser les concepts en permettant d’écrire:

Expr operator+(Expr e, auto convertible_to<Expr>... ee)

Le problème est que nous n’avons pas toujours un type Expr en première position, comme dans le cas 1+a+b. Nous proposons donc que le C++ interprète cette définition comme: opérandes multiples dont un de type Expr et les autres de type convertible_to<Expr>.

Une façon peut-être plus acceptable pour les compilateurs serait d’écrire:

Expr operator+(auto convertible_to<Expr>... ee1, Expr e, auto convertible_to<Expr>... ee2)

dans lequel e serait la première parmi les opérandes qui soit de type Expr.

Cette possibilité serait réservée aux opérateurs associatifs non booléens (+,*,…). Pour les opérateurs booléens, une meilleure proposition est envisagée.