Comprendre la différenciation automatique en 30 lignes de Python

 (vmartin.fr)
3 points par GN⁺ 2023-08-27 | 1 commentaires | Partager sur WhatsApp
  • Implémente directement la différenciation automatique, au cœur de l’entraînement des réseaux de neurones, avec une classe Tensor pour scalaires, afin de montrer comment le calcul des valeurs et celui des dérivées s’enchaînent sur un même graphe de calcul
  • Avec des variables Python ordinaires, seul le résultat de z = x + y reste disponible et la relation disparaît ; Tensor doit donc stocker à la fois la valeur et l’historique des opérations
  • Children(a, b, op) et les appels récursifs à forward() permettent de construire un graphe de calcul en arbre binaire ; en redéfinissant l’addition et la multiplication, on peut recalculer l’expression plus tard même si les valeurs sont injectées après coup
  • grad(deriv_to) pose la dérivée par rapport à soi-même à 1, et par rapport à un autre scalaire à 0, puis applique récursivement les règles de dérivation des opérations de base pour construire un nouveau graphe de calcul
  • L’implémentation ne gère que les scalaires et peut être lente ; la prise en charge des tableaux, l’élagage des multiplications par zéro, le traitement des nœuds constants et un cache pour réduire les calculs répétés restent des pistes d’amélioration

Avec des variables Python ordinaires, la relation disparaît

  • Si l’on calcule x = 3, y = 5, z = x + y, il ne reste dans z que la valeur résultante 8
  • Même si la valeur de x ou y change ensuite, z ne permet pas de retrouver de quelles variables il a été construit
  • Comme la relation entre les variables n’est pas conservée, il devient difficile de calculer automatiquement la dérivée par rapport à une variable donnée

Préserver l’historique des opérations avec Tensor

  • Le nouveau type Tensor stocke une valeur (value) et redéfinit les opérateurs pour renvoyer un nouveau Tensor quand on effectue un calcul entre Tensor
  • La première implémentation redéfinit seulement __add__, ce qui permet à Tensor(3) + Tensor(5) de produire T:8
  • À ce stade, z ne conserve toujours pas l’historique des opérations indiquant qu’il est le résultat de x + y

Graphe de calcul et forward()

  • Pour conserver l’historique des opérations, l’auteur introduit Children = namedtuple('Children', ['a', 'b', 'op'])
    • a : tenseur d’entrée gauche
    • b : tenseur d’entrée droit
    • op : opération réelle comme np.add ou np.multiply
  • Chaque Tensor peut contenir non seulement une valeur numérique, mais aussi children, ce qui permet de constituer un graphe de calcul sous forme d’arbre binaire
  • forward() visite récursivement les nœuds enfants pour calculer la valeur réelle
    • Avec x = Tensor(3), y = Tensor(5), puis z1 = x + y, z2 = z1 * y, on obtient T:40
    • On peut aussi construire d’abord le graphe avec x = Tensor(None), y = Tensor(None), puis affecter plus tard x.value = 3, y.value = 5 et appeler z2.forward() pour obtenir T:40

Construire la différenciation automatique comme un graphe de calcul

  • La différenciation automatique est implémentée en ajoutant une règle de dérivation pour chaque opération de base prise en charge par Tensor
  • grad(self, deriv_to) parcourt récursivement le graphe de calcul et décompose une fonction complexe en combinaison de fonctions simples
  • Les règles de base sont les suivantes
    • dériver un tenseur par rapport à lui-même donne Tensor(1)
    • dériver un scalaire sans enfant par rapport à un autre tenseur donne Tensor(0)
    • addition : (a + b)' = a' + b'
    • multiplication : (ab)' = a'b + ab'
  • Si l’on dérive z2 = (x + y) * y par rapport à y, le résultat g n’est pas une simple valeur, mais un nouveau graphe de calcul représentant la dérivée partielle
    • Formellement, g = ∂z2/∂y = x + 2*y
    • Quand x = 3 et y = 5, la valeur de g est 13

Extension à la soustraction, la division et la fonction exponentielle

  • Pour traiter des expressions plus complexes, Tensor est étendu avec la soustraction, la division, la fonction exponentielle et l’opérateur unaire négatif
  • grad() reçoit les règles de dérivation correspondant à chaque opération
    • soustraction : (a - b)' = a' - b'
    • division : (a/b)' = (a'b - ab') / b²
    • fonction exponentielle : exp(a)' = a' * exp(a)
  • forward() est aussi modifié pour gérer les opérations qui n’ont besoin que d’un seul terme
    • par exemple, exp(a) n’a pas besoin d’un second terme b
    • -x est traité sous la forme 0 - x

Formule d’exemple et vérification avec Sympy

  • L’expression suivante est écrite avec Tensor, puis ses dérivées partielles par rapport à x et y sont calculées
z = (12 - (x * e^y)) / (45 + x * y * e^-x)
  • Dans le code, cela s’écrit ainsi
x = Tensor(3)
y = Tensor(5)
z = (Tensor(12) - (x * y.exp())) / (Tensor(45) + x * y * (-x).exp())
  • Les valeurs calculées des dérivées partielles sont les suivantes
    • z.grad(x) → T:-3.34729777301069
    • z.grad(y) → T:-9.70176956641438
  • Le résultat obtenu avec Sympy via diff() et evalf() pour la même expression est identique
    • avec xs = 3, ys = 5, la dérivée par rapport à x vaut -3.34729777301069
    • la dérivée par rapport à y vaut -9.70176956641438

Limites de cette implémentation simple et pistes d’optimisation

  • Cette implémentation se rapproche d’un système de différenciation automatique dans sa forme la plus simple, mais elle peut aussi être très lente
  • La classe actuelle ne gère que les scalaires
    • pour devenir une bibliothèque plus utile, elle devrait ajouter la prise en charge des opérations sur des tableaux de taille arbitraire
  • Le graphe de calcul laisse entrevoir plusieurs optimisations possibles
    • dans un nœud de multiplication, si l’un des enfants vaut 0, il n’est pas nécessaire de poursuivre l’exploration en profondeur
    • si un nœud et ses enfants ne dépendent pas du tenseur cible de dérivation x, ce nœud peut être considéré comme une constante et le parcours peut s’arrêter là
    • quand une même opération se répète, un cache peut éviter d’exécuter plusieurs fois le même calcul

À lire aussi

1 commentaires

 
GN⁺ 2023-08-27
Avis de Hacker News

  • J’aime ce genre de petites démos de code élégantes. Elles permettent de comprendre un concept en mettant vraiment les mains dedans
    Les puzzles GPU et les puzzles de tenseurs de Sasha Rush sont des exemples similaires
    https://github.com/srush/GPU-Puzzles
    https://github.com/srush/Tensor-Puzzles

  • Si vous croyez avoir entièrement compris la différentiation automatique avec seulement ça, vous vous trompez vous-même
    Quand le graphe est un arbre, tout est très simple comme dans cet article. Mais si le graphe est un graphe orienté acyclique plus général, par exemple x = 5; y = 2x; z = xy, l’implémentation reste très simple, mais comprendre pourquoi elle est correcte ne l’est pas. Si vous pensez que ce n’est « qu’une règle de dérivation en chaîne ordinaire », vous vous trompez là aussi vous-même
    L’une des premières explications a été donnée par Paul Werbos, qui a appelé la règle nécessaire la règle de dérivation en chaîne des dérivées ordonnées et l’a démontrée par induction à partir de la règle de dérivation en chaîne ordinaire. Mais elle ne découle tout de même pas immédiatement de façon évidente de la règle de dérivation en chaîne ordinaire. Si quelqu’un croit le contraire, j’aimerais qu’il prouve que j’ai tort ; j’en serais très heureux

    • Alors où peut-on en lire davantage ? Les personnes qui ont créé des frameworks comme autograd, PyTorch ou mxnet ont bien dû l’apprendre en détail quelque part, et je suis curieux de connaître ces sources. Pour autant que je sache, mxnet vient du monde académique, probablement de CMU
    • Honnêtement, je ne sais pas vraiment ce que les gens attendent dans ce genre de discussion, et je me demande si c’est parce que l’abstraction implicite des dérivées ordonnées n’est pas idéale
      Si l’on applique la règle de dérivation en chaîne ordinaire le long des arêtes d’un graphe de calcul, c’est-à-dire d’un graphe orienté acyclique, on obtient la bonne valeur à chaque étape. La seule règle supplémentaire nécessaire est du genre : « si une variable est utilisée plusieurs fois dans le calcul, autrement dit si plusieurs arêtes partent du même nœud ou, en sens inverse, si plusieurs arêtes y arrivent, il faut additionner les gradients calculés séparément ». Et cela me semble aussi assez élémentaire et intuitif
      Par exemple, si l’on passe z à la fois comme x et comme y dans f(x, y), alors d/dz f(z, z) = f_x(z, z) + f_y(z, z), où les indices désignent les dérivées partielles. Pour moi, cette manière de voir est mathématiquement plus simple que de mélanger les deux et de faire comme si cela « dépassait la règle de dérivation en chaîne », et elle semble aussi plus proche de l’implémentation réelle, en particulier de ce que fait PyTorch, que je connais le mieux
    • La règle de dérivation en chaîne étant définie pour les dérivées partielles, techniquement, on peut toujours considérer qu’il s’agit simplement de la règle de dérivation en chaîne

  • La différentiation automatique donne l’impression d’être magique
    Beaucoup d’informaticiens ont été fascinés par le sujet et ont écrit des articles qui présentent la technique dans une perspective plus large. Mon article en fait partie, et inclut aussi une « variante du pauvre » qui utilise les nombres complexes sans surcharge d’opérateurs
    https://pizzaseminar.speicherleck.de/automatic-differentiati...

    • En 1994-1995, quand je faisais du machine learning, je ne connaissais pas la différentiation automatique, et le professeur qui avait conçu la fonction objectif calculait lui-même les dérivées analytiques. Je ne l’ai découverte qu’il y a quelques années, et en repensant au temps passé à apprendre suffisamment Mathematica à la fin des années 90 pour produire moi-même des dérivées analytiques, cela m’a stupéfié
    • Cela semble remonter à l’approximation des dérivées par pas complexe de J. Martins, P. Sturdza et J. Alonso, en 2003. L’article vaut la peine d’être lu
      [0] : https://doi.org/10.1145/838250.838251
    • Ça donne vraiment l’impression d’être magique. J’aimerais connaître des ressources d’introduction à la rétropropagation écrites dans un esprit similaire

  • J’ai une implémentation de la différentiation automatique en Python en 26 lignes : https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...

    • Le format court, c’est bien, mais mon cerveau semble fonctionner beaucoup mieux quand il y a une quantité raisonnable d’espaces. Il faudrait que je m’entraîne un peu à ces autres styles

  • C’est très proche des techniques utilisées dans les systèmes d’ingénierie à base de connaissances, où l’on parle de suivi des dépendances. Combiné à la mise en cache des nœuds ou des tenseurs, cela permet de réduire la quantité de calcul, ce qui est particulièrement utile pour les grands modèles 3D paramétriques
    Lorsqu’on récupère une valeur, on appelle récursivement l’arbre binaire/de dépendances pour vérifier quelles variables ont changé, et on ne recalcule que ce qui est nécessaire. Avec des objets et attributs Python personnalisés dotés de méthodes __set__ et __get__, on peut en faire une fonctionnalité intégrée d’un modèle orienté objet
    x = Tensor(3)
    y = Tensor(5)
    z = x + y
    print(x, y) # 3, 5
    print(z) # 8
    x.value = 4 # lors de l’affectation de la valeur, rien n’est recalculé
    print(z) # 9, car les dépendances modifiées sont recalculées au moment où la valeur est récupérée

  • Andrej Karpathy a une vidéo intéressante où il construit un moteur autograd, et elle est assez éclairante
    https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7
    Dépôt :
    https://github.com/karpathy/micrograd

  • Les variantes de différentiation automatique que je connais ne construisent pas de graphe de calcul. Elles calculent plutôt la valeur à la volée.

    • Tu penses probablement à la différentiation automatique en mode direct. Elle est plus utile quand la dimension de sortie de la fonction est relativement grande, et elle diffère de la différentiation automatique en mode inverse, plus utile quand la dimension de sortie est relativement petite.
      Les deux fonctionnent, mais selon la situation l’une est plus efficace que l’autre. Dans des cas comme « l’entraînement de réseaux de neurones », on optimise souvent une unique sortie de perte sur de nombreuses cibles, donc on utilise généralement le mode inverse.

  • J’aimerais qu’on appelle simplement la différentiation automatique règle de la chaîne numérique, ou au moins qu’on l’explique ainsi. Littéralement, c’est tout ce que c’est, avec quelques astuces pour éviter de calculer explicitement les matrices jacobiennes dans certaines opérations, et ce serait bien plus clair.

    • L’« autodiff » expliquée ici et la plus souvent utilisée dans les implémentations de la rétropropagation est la différentiation automatique en mode inverse, mais il existe aussi un mode direct et des stratégies entre ces deux extrêmes. Au final, tout se ramène à la règle de la chaîne, mais le choix de la méthode au niveau algorithmique n’est jamais trivial.
      En pratique, si l’on demande d’utiliser la règle de la chaîne pour propager les gradients à travers un graphe de calcul, la plupart des gens penseraient intuitivement au mode direct par défaut. Moi aussi.
      https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo...
      Vu sous cet angle, il semble utile d’employer ce terme pour désigner une méthode particulière d’accumulation des gradients en parcourant les formules fournies par la règle de la chaîne.
    • Techniquement, c’est faux. La règle de la chaîne numérique utilise les différences finies, et les erreurs s’accumulent au fil des calculs.
      Voir la section « Différences avec d’autres méthodes » : https://en.m.wikipedia.org/wiki/Automatic_differentiation
      Comme le disent des commentaires voisins, l’essentiel est que l’implémentation compte vraiment et mérite d’être étudiée. Dire que la différentiation automatique est un ensemble de méthodes pour implémenter la règle de la chaîne, c’est acceptable ; dire que c’est « simplement » la règle de la chaîne numérique, c’est faux.
    • C’est peut-être plus exact, mais je n’appellerais pas ça plus clair.

  • Où est le problème, puisque la différentiation automatique n’est rien d’autre que la lentille cartésienne de la matrice jacobienne et de la différentielle totale dans la catégorie des fonctions lisses ? https://www.youtube.com/watch?v=ne99laPUxN4

  • Je me demande pourquoi la classe s’appelle Tensor. Y a-t-il une manière de considérer une expression ou sa dérivée comme un tenseur ? Ou bien est-ce parce qu’un scalaire est aussi un tenseur, et que cela peut être étendu pour prendre en charge d’autres types de tenseurs ?

    • Je peux me tromper, mais mathématiquement, il me semble qu’on appelle un objet 2D une matrice, et un objet en 3D ou plus un tenseur.
      Comme l’algorithme de différentiation automatique décrit fonctionne pour des objets de dimension supérieure arbitraire, appeler ces objets des tenseurs semble logique.