Rétropropagation dans une couche convolutive - DRAFT eq# à revoir

En travaillant sur le cours de Stanford CS231n: Convolutional Neural Networks for Visual Recognition, je me suis heurté au manque d’information pour coder la rétropropagation dans une couche convolutive. Cet article présente les étapes de la construction de la solution mathématique et la mise en place de l’algorithme pour répondre à ce problème.

convnet bp sand

Introduction

Motivation

Le but de cet article est de présenter la rétropropagation du gradient dans une couche convolutive. La sortie de cette couche ira dans une fonction d’activation de type relu, et l’on suppose que l’on reçoit le gradient dy rétropropagé depuis cette fonction d’activation. Ayant trouvé peu d’informations détaillées sur le processus et les mathématiques sous-jacentes, cet article détaille pas à pas les étapes de la mise en place d’une solution informatique pour le calcul de ce gradient. On suppose que le lecteur est déjà familier des notions de propagation et rétropropagation dans les réseaux neuronaux, des graphes de calculs et du calcul des gradients de tenseurs.

conv layer graph

Notations utilisées

On note * le produit de convolution entre deux tenseurs, typiquement une entrée xet un filtre w

  • Dans le cas où les tenseurs sont de même taille et avec une ou deux dimensions, cela correspond à la somme de produits de chacun des éléments terme à terme
  • Si le filtre w est plus petit que x, on obtient une “carte d’activation” y où chacun des termes correspond au produit de convolution d’un sous ensemble de x avec w, w se déplaçant sur toute la surface de x.
  • Si x et w ont plus de deux dimensions on ne considère que les deux dernières dimensions pour effectuer les déplacements du sous ensemble choisi, les produits de convolution se feront sur une dimension supplementaire correspondant à la profondeur.

Les variables et notations utilisées correspondent à l’excellent cours de Stanford et aux exercices de l’assignment 2. Un descriptif du fonctionnement de la propagation dans une couche convolutive est proposé dans cette vidéo et un petit exemple de mise en application dans cet article.

conv layer diagram

Objectif

On cherche à calculer comment se rétropropage le gradient dans le cas suivant:

On dispose d’une entrée x de N points, chacun avec C canaux, une hauteur de H, et une largeur de W. On effectue un produit de convolution avec F filtres différents w, sur l’intégralité de la profondeur C, chaque filtre a pour hauteur HH et comme largeur WW.

Entrées:

  • x: données d’entrée de dimensions (N, C, H, W)
  • w: poids de filtres de dimensions (F, C, HH, WW)
  • b: Biais de dimensions (F,)
  • conv_param: un dictionnaire de paramètres avec les entrées suivantes:
    • ‘stride’: Le nombre de pixel entre deux zones successives d’application du filtre (identiques en largeur et en hauteur).
    • ‘pad’: Le nombre de pixel pour effectuer un remplissage à 0 (“0-padding”) autour de l’entrée. Ce remplissage est fait de manière symétrique selon les différents axes.

Sortie:

  • out: Données de sortie de dimension (N, F, H’, W’) où H’ and W’ sont définis par:
    • H’ = 1 + (H + 2 * pad - HH) / stride
    • W’ = 1 + (W + 2 * pad - WW) / stride
  • cache: données mémorisées pour la rétropropagation (x, w, b, conv_param)

Propagation

Cas général simplifié où N=1, C=1, F=1

N=1 une seule entrée, C=1 un seul canal, F=1 un seul filtre.

conv 2D

  • $x$ : $H \times W$
  • $x’ = x$ avec padding
  • $w$ : $HH \times WW$
  • $b$ biais : scalaire
  • $y$ : $H’\times W’$
  • stride $s$

$\forall (i,j) \in [1,H’] \times [1,W’]$

Cas particulier: stride=1, pad=0, et pas de biais

Rétropropagation

On connait

$dy = \left(\frac{\partial L}{\partial y_{ij}}\right)$

On cherche $dx$, $dw$ et $db$, dérivées partielles respectives de notre fonction de coût dont le gradient a été rétropropagé jusqu’à y.

Cas d’un vecteur d’entrée x à 1 dimension

Pour essayer d’avoir une première intuition du résultat et voir comment les choses se mettent en place, on va se limiter dans un premier temps à un exemple très simple.

En entrée

En sortie

Propagation - convolution avec le filtre w, stride = 1, padding = 0

Rétropropagation

On connait le gradient de notre fonction de coût L par rapport à y:

En fait $dy = \frac{\partial L}{\partial y}$, dérivée d’un scalaire par rapport à un vecteur s’écrit avec la notation du Jacobien:

dy a les mêmes dimensions que y, écriture sous forme vectorielle:

On cherche

db

Et la composée de fonction s’écrit sous la forme (en incorporant la formule de propagation (1)):

dw

On peut remarquer que dw correspond au produit de convolution de x avec dy comme filtre, à voir si cela se généralise avec une dimension supplémentaire.

dx

Donne encore un produit de convolution, un peu particulier cette fois, il faudrait considérer dy avec un padding à 0 de taille 1, et en faire le produit convolutif avec un filtre w inversé du type $(w_2, w_1)$

On va essayer de généraliser ces résultats en choisissant comme x et w des matrices de petites tailles.

Cas d’une entrée x à 2 dimensions

En entrée

En sortie

De nouveau on va prendre le cas le plus simple, stride de 1 et pas de padding. Donc $y$ aura pour dimension $3 \times 3$

Propagation

Ce qui nous donne:

En écriture indicielle:

Rétropropagation

On connait:

db

En utilisant la convention d’Einstein pour alléger les notations (la répétition d’un indice indique la somme sur l’ensemble de la plage de valeurs de cet indice)

On a une double somme sur i et j, et $\forall (i,j)$ on a $\frac{\partial y_{ij}}{\partial b}=1$, donc

dw

On cherche

En incorporant l’équation (2) on obtient:

Tous les termes $\frac{\partial w_{kl}}{\partial w_{mn}}$ sont nuls sauf pour $(k,l) = (m,n)$ où cela vaut 1, cas qui n’apparaît qu’une seule fois dans la double somme.

D’où:

En remplaçant dans (3) on obtient:

Si l’on compare cette équation avec l’équation 2 qui donne la formule d’un produit de convolution, on retrouve une structure similaire où dy joue le rôle de filtre que l’on applique sur x.

dx

En utilisant la loi de composition comme pour (3) on obtient:

Cette fois ci on cherche

En incorporant l’équation (2) on obtient:

On a

Dans notre exemple on a

Donc lorsque l’on fait $k=m-i+1$, on va sortir un peu de l’intervalle de valeurs, $(m-i+1) \in [-1,4]$, donc pour garder la cohérence dans la formule (5) on va étendre la matrice $w$ avec des $0$ dès que les valeurs des indices sortiront de l’intervalle de définition.

De nouveau, dans la double somme de (5), on peut avoir une seule dérivée partielle de x qui soit égale à 1, lorsque l’on a (6), donc en remplaçant dans (5):

où $w$ représente notre filtre initial étendu avec des 0, lorsque l’on sort de son intervalle de définition.

En injectant cette formule dans (4) on obtient:

On va visualiser ce que cela nous donne sur quelques valeurs choisies pour les indices. Par exemple

En utilisant $*$ pour notation du produit de convolution, on a:

Comme les valeurs de $dy$ ne changent pas on va se limiter aux valeurs des indices de w. Pour $dx_{22}$ : $3-i,3-j$

Donc on a un produit de convolution entre dy et une matrice w’ de type:

Autre exemple pour essayer de clarifier les choses: $dx_{43}$, de nouveau on se limite aux valeurs des indices: $4-i,3-j$

Et du coup pour finir $dx_{44}$

Donc on voit bien apparaître un filtre w inversé. On obtient cette fois ci un produit convolutif entre $dy$ avec une bordure de 0 et $w’$, notre $w$ inversé, qui se déplace sur cette matrice avec un pas (stride) de 1.

Résumé des équations de rétropropagation

Cas général et prise en compte des profondeurs

Les choses se complexifient encore un peu plus lorsque l’on cherche à prendre en compte la profondeur de C canaux de x et celle de F filtres de y.

Entrées

  • x: données d’entrée de dimensions (C, H, W)
  • w: poids de filtres de dimensions (F, C, HH, WW)
  • b: Biais de dimensions (F,)

Sortie:

  • y: Données de sortie de dimension (F, H’, W’)

Les équations mathématiques multiplient les indices et en deviennent difficilement lisibles. Par exemple la propagation dans ce cas de figure donne:

db

Le calcul de db reste simple et chaque $b_f$ correspond à une carte d’activation $y_f$:

dw

En injectant (9), comme la double somme n’est pas faite sur les indices de dy, on peut écrire:

Algorithme

Pour la programmation, plutôt que de détailler l’ensemble des équations, ce qui peut certainement se faire avec un peu (beaucoup) de rigueur, on va se limiter aux intuitions que l’on a percées grâce aux exemples précédents. Et essayer de généraliser en jouant sur les dimensions. On peut comparer nos résultats avec un calcul numérique des gradients, ce qui permettra de valider la solution.

Cette solution se limite au cas où l’on a un stride = 1

Comparaison avec le calcul numérique du gradient

Testing conv_backward_naive function
dx error:  7.489787768926947e-09
dw error:  1.381022780971562e-10
db error:  1.1299800330640326e-10

Erreur proche de 0 à chaque fois, ce qui valide notre algorithme ! :)

Généralisation pour tout stride - Nouvel article?

Dans cette version on regarde la contribution de chaque volume d’entrée au résultat y et on rétropropage en calculant des produits de convolution entre volumes de tailles identiques. Dans ce cas on a dx_input_volume = dy[i,j] . w (. est ici un simple produit). On cumule ensuite toutes les contributions dx qui participent aux mêmes indices. Finalement c’est beaucoup plus simple dans la mise en oeuvre que la version mathématique appliquée sur l’ensemble des valeurs de x.

Voici une version sans vectorisation, particulièrement lente, mais cela permet de voir comment les choses se mettent en place. Que ce soit pour dw ou dx, on se limite pour le coeur du calcul à l’influence du produit de convolution de deux éléments de taille identique (qui donnent un scalaire), et on cumule ensuite lors des déplacements du filtre sur l’entrée x pendant la propagation.

pour x et w de mêmes dimensions, y est un scalaire:

Références