Table Of Contents

Previous topic

Introduction aux algorithmes d’apprentissage profonds

Next topic

Introduction aux perceptrons multi-couches (réseaux de neurones à propagation avant)

This Page

English version

Introduction à l’apprentissage par descente de gradient

Considérons une fonction de coût C, qui associe un vecteur de paramètres \theta à un scalaire C(\theta), que nous voulons minimiser. En apprentissage machine, la fonction de coût est généralement la moyenne, ou l’espérance, de la fonction d’erreur L :

C(\theta) = \frac{1}{n} \sum_{i=1}^n L(f_\theta, z_i)

(c’est ce que l’on appelle l’erreur d’entraînement), ou

C(\theta) = \int L(f_\theta, z) P(z) dz

(c’est l’erreur de généralisation). En apprentissage supervisé, on a z=(x,y), et f_\theta(x) est une prédiction de y, indexée par les paramètres \theta.

Le gradient

Le gradient de la fonction C par rapport à un scalaire \theta est défini formellement comme suit :

\frac{\partial C(\theta)}{\partial \theta} =
  \lim_{\delta \theta \rightarrow 0}
  \frac{C(\theta + \delta \theta) - C(\theta)}{\delta \theta}

C’est-à-dire que c’est la variation \Delta C provoquée par un changement \Delta \theta, dans la limite où \Delta \theta est très petit.

Lorsque \theta est un vecteur, le gradient \frac{\partial C(\theta)}{\partial \theta} est un vecteur, contenant un élément \frac{\partial C(\theta)}{\partial \theta_i} pour chaque \theta_i, en considérant les autres paramètres fixés : on fait le changement \Delta \theta_i, et on mesure le \Delta C résultant. Lorsque \Delta \theta_i est petit, alors \frac{\Delta C}{\Delta \theta_i} devient \frac{\partial C(\theta)}{\partial \theta_i}.

Descente de gradient

Nous voulons trouver une valeur de \theta qui minimise C(\theta). Si nous arrivons à résoudre

\frac{\partial C(\theta)}{\partial \theta} = 0

alors nous pouvons trouver les minimums (et les maximums, et les points de selle), mais généralement nous ne sommes pas capables de trouver les solutions de cette équation, donc nous utilisons des méthodes numériques d’optimisation. La plupart de ces méthodes reposent sur l’idée de la descente locale : on modifie itérativement \theta pour diminuer C(\theta), jusqu’à ce que ça devienne impossible, c’est-à-dire que nous sommes arrivés à un minimum local (et peut-être global, avec de la chance).

La technique la plus simple, parmi les techniques d’optimisation à base de gradient, est la descente de gradient. Il existe de nombreuses variantes de descente de gradient, commençons par la descente de gradient ordinaire :

\theta^{k+1} = \theta^k - \epsilon_k  \frac{\partial C(\theta^k)}{\partial \theta^k}

\theta^k représente nos paramètres à l’itération k, et \epsilon_k est un scalaire appelé pas de gradient (learning rate), qui peut être fixé, adaptatif, ou déterminé par un échéancier (schedule).

Descente de gradient stochastique

Pour la descente de gradient stochastique, nous exploitons le fait que C est une moyenne sur des exemples généralement i.i.d. (indépendants et identiquement distribués) pour faire des mises à jour de \theta de manière beaucoup plus fréquente, à la limite (et dans le cas le plus commun) après chaque exemple :

\theta^{k+1} = \theta^k - \epsilon_k    \frac{\partial L(\theta^k,z)}{\partial \theta^k}

z est le prochain exemple dans l’ensemble d’entraînement, ou le prochain exemple tiré de la distribution d’entraînement dans le cas en ligne (online) (où l’on n’a pas accès à un ensemble d’entraînement de taille fixe, mais à un flux d’exemples provenant d’un processus de génération de données).

La descente de gradient stochastique (stochastic gradient descent, SGD) est un principe plus général, dans lequel la direction de la mise à jour est une variable aléatoire, dont l’espérance est le véritable gradient qui nous intéresse. Les conditions de convergence de la SGD sont similaires à celles de la descente de gradient, malgré la plus grande quantité de hasard.

La SGD peut être beaucoup plus rapide que la descente de gradient ordinaire (batch), parce que le nombre de mises à jour est beaucoup plus grand. C’est particulièrement vrai pour des jeux de données volumineux, ou pour le cas en ligne. En fait, dans les tâches d’apprentissage machine, on n’utilise la descente de gradient ordinaire (au lieu de stochastique) que lorsque la fonction à minimiser ne peut pas être décomposée comme ci-dessus (comme une moyenne).

Descente de gradient stochastique par mini-lots

C’est une variante de la SGD, dans laquelle on obtient la direction de la mise à jour en prenant la moyenne de l’erreur sur un petit nombre d’exemples (mini-lot, ou minibatch) B (par exemple, 10, 20 ou 100). L’avantage principal est qu’au lieu d’effectuer B produits vecteur-matrice, on peut souvent faire un produit matrice-matrice, la première matrice ayant B rangées, ce qui peut être implémenté de façon beaucoup plus efficace (parfois 2 à 10 fois plus rapide, selon la taille des matrices).

La SGD par mini-lots a l’avantage de travailler avec un estimé du gradient qui est moins bruité (de moins en moins bruité lorsque B augmente). Par contre, lorsque la taille du lot augmente, le nombre de mises à jour diminue par rapport au nombre de calculs faits (à la limite, cela devient très inefficace, autant que la descente de gradient ordinaire). Il y a un compromis optimal (en terme d’efficacité computationnelle), qui peut varier selon la distribution des données et les particularités de la classe de fonctions considérée, ainsi que de la manière dont les calculs sont réalisés (l’architecture matérielle et le parallélisme peuvent faire une différence).

Inertie (momentum)

Une autre variation, dont l’esprit est similaire à celui de la SGD par mini-lots, est l’utilisation d’un terme dit d’inertie (momentum): l’idée est de calculer à la volée une moyenne mobile des gradients précédents, et d’utiliser cette moyenne mobile, et non le gradient de l’exemple courant, dans la formule de mise à jour. La moyenne mobile est généralement une moyenne mobile exponentielle :

\Delta \theta^{k+1} = \alpha \Delta \theta^k + (1-\alpha) \frac{\partial L(\theta^k,z)}{\partial \theta^k}

\alpha est un hyper-paramètre contrôlant le poids relatif des gradients plus ancients par rapport aux plus récents.

Choisir l’échéancier du pas de gradient

Si le pas de gradient est trop grand – plus grand que le double de la plus grande valeur propre de la dérivée seconde (hessienne) de C –, alors les mises à jour font augmenter le coût au lieu de le diminuer. Si le pas de gradient est trop petit, la convergence est plus lente.

Les choix d’échéancier du pas de gradient (\epsilon_k) sont les suivants:

  • Valeur constante, \epsilon_k = \epsilon_0 : c’est le choix le plus commun. En théorie, il donne un poids exponentiellement plus grand aux exemples les plus récents, et il est particulièrement adapté dans un environnement non stationnaire, où la distribution peut changer. Il est très robuste, mais l’erreur arrête de diminué après un certain temps, alors qu’un pas de gradient plus petit pourrait donner une solution plus précise (s’approcher un peu plus du minimum).

  • Diminution en 1/k : \epsilon_k = \epsilon_0 \frac{\tau}{\tau + k}. Il est garanti que cet échéancier arrivera à converger asymptotiquement (lorsque k \rightarrow \infty), car il satisfait aux conditions suivantes :

    \sum_{k=1}^\infty \epsilon_k = \infty

    \sum_{k=1}^\infty \epsilon_k^2 < \infty

    Cette garantie est vraie quel que soit \tau, mais \epsilon_0 doit être assez petit pour éviter de diverger (lorsque l’erreur augmente au lieu de diminuer).

    Un des inconvénients est l’ajout d’un nouvel hyper-paramètre \tau. Un autre problème est que, malgré les garanties, un mauvais choix de \tau peut entraîner une convergence très lente.

Graphes de flot, dérivée en chaîne et rétropropagation : calcul efficace du gradient

Considérons une fonction (dans notre cas, ce sera L(\theta,z)) de plusieurs arguments, nous voulons calculer sa valeur, ainsi que celle de sa dérivée (son gradient) par rapport à certains de ses arguments. Nous allons décomposer le calcul de la fonction en termes de calculs élémentaires, pour lesquels les dérivées partielles sont faciles à calculer, formant ainsi un graphe de flot (comme déjà mentionné ici). Un graphe de flot est un graphe dirigé acyclique, où chaque nœud représente le résultat d’un calcul qui est effectué sur les valeurs associées aux nœuds du graphe qui lui sont connectés. Le graphe a des nœuds d’entrée (sans prédécesseurs), et des nœuds de sortie (sans sucesseurs).

Chaque nœud du graphe de flot est associé à une expression symbolique, qui définit comment sa valeur est calculée à partir des valeurs de ses enfants (les nœuds qui lui servent d’entrées). Nous nous concentrerons sur l’utilisation des graphes de flot pour un calcul efficace du gradient, plus particulièrement du gradient d’un nœud de sortie particulier, scalaire (noté L ici, on s’intéresse au gradient d’une fonction d’erreur par rapport aux paramètres). À chaque nœud, nous associerons :

  • la valeur du nœud,
  • l’expression symbolique qui spécifie comment calculer la valeur du nœud à partir des valeurs de ses prédécesseurs (ses enfants),
  • la dérivée partielle de L par rapport à la valeur du nœud,
  • l’expression symbolique qui spécifie comment calculer la valeur de cette dérivée partielle, à partir des valeurs de ses prédécesseurs.

Soit L le nœud de sortie scalaire du graphe de flot, considérons un nœud arbitraire u, dont les parent (les nœuds qui prennent comme entrée la valeur calculée par u) sont v_i. En plus de la valeur u (c’est un abus de notation) associée au nœud u, nous allons aussi associer à chaque nœud u une dérivée partielle : \frac{\partial L}{\partial u}.

La règle de dérivation en chaîne spécifie comment la dérivée partielle \frac{\partial L}{\partial u} pour un nœud u peut être obtenue, de manière récursive, à partir des dérivées partielles \frac{\partial L}{\partial v_i} pour ses parents v_i :

\frac{\partial L}{\partial u} = \sum_i \frac{\partial L}{\partial v_i} \frac{\partial v_i}{\partial u}

Notons que la récursion commence à \frac{\partial L}{\partial L} = 1, pour le nœud racine du graphe (dans le cas général, c’est bien un graphe et non un arbre, car il peut y avoir plusieurs chemins entre un nœud donné et le nœud racine, ou sortie). Notons aussi que chaque \frac{\partial v_i}{\partial u} est une expression (à laquelle correspond une valeur, lorsque les valeurs d’entrée sont données) associée à un arc du graphe (et chaque arc est associé à une dérivée partielle de ce type).

On remarque que les calculs de gradient utilisés dans cette méthode vont exactement dans le sens opposé des calculs utilisés pour calculer L. En fait, on dit que les gradients sont rétropropagés, en suivant les arcs dans le sens inverse. L’utilisation de cette procédure pour calculer le gradient dans le cas de réseaux de neurones (sans récurrence) multi-couches est appelée l’algorithme de la rétropropagation du gradient.

Dans l’exemple vu plus tôt, L=sin(a^2+b/a), et il y a deux chemins de a vers L.

Cette méthode nous donne certaines garanties. Si le calcul de L s’exprime par n calculs, matérialisés par n nœuds (et que le calcul chaque nœud requiert un temps constant) et m arcs, alors le calcul de toutes les dérivées partielles \frac{\partial L}{\partial u} requiert (au plus) O(m) calculs, en utilisant la récursion ci-dessus (en général, le nombre d’entrées d’un nœud est borné, et c’est aussi O(n)). De plus, c’est aussi une borne inférieure, c’est-à-dire qu’il n’est pas possible de calculer le gradient plus vite (à une constante additive et multiplicative près).

Notons enfin qu’il existe de nombreuses manières de calculer ces gradients, et qu’alors que l’algorithme ci-dessus est le plus rapide, il est facile d’écrire une récursion, apparemment simple, qui serait exponentiellement plus lente, c’est-à-dire en O(2^n). De manière générale, \frac{\partial L}{\partial u} peut être écrite comme la somme, sur tous les chemins du graphe de u à L, du produit des dérivées partielles selon chaque chemin.

Illustrons cela avec un graphe qui a la structure suivante :

x_t = f(x_{t-1}, y_{t-1})

y_t = g(x_{t-1}, y_{t-1})

où il existe p = n/2 paires de nœuds (x_t,y_t), terminant par L=h(x_p,y_p), et dont les nœuds d’entrée sont x_0 et y_0. Le nombre de chemins de x_0 à L est 2^{p} = 2^{n/2} = (\sqrt{2})^n. Par construction, à chaque fois que l’on ajoute une paire de nœuds, le nombre de chemins est doublé.