Descendre le gradient.

Imagine-toi, les yeux bandés, posé quelque part dans une cuvette. Tu veux atteindre le fond sans tricher. La seule chose que tu peux faire, c'est tâter la pente sous tes pieds et avancer dans la direction qui descend le plus. Tu fais un petit pas, tu retâtes, tu refais un petit pas. Tu vas finir au fond. C'est exactement ce que fait la descente de gradient.

Une dérivée, c'est une pente

Avant d'appliquer l'idée à $J(\theta_0, \theta_1)$ , une intuition rapide sur la dérivée. Pour une fonction $f(x)$ , la dérivée en un point donne la pente de la tangente à la courbe à cet endroit. Si la pente est positive, la courbe monte ; si elle est négative, elle descend ; si elle est nulle, on est sur un sommet ou un creux.

Pour $f(x) = x^2$ , la dérivée vaut $2x$ : continue et lisse partout. Pour $f(x) = |x|$ , la pente vaut $-1$ à gauche de zéro et $+1$ à droite, et au point $0$ lui-même on ne sait pas trancher : il y a un coin. C'est pour cette raison qu'on préfère MSE (lisse partout) au MAE (un coin en zéro) comme fonction de coût : un algorithme qui se base sur la pente déteste les coins.

Deux pentes, une par paramètre

Notre $J$ dépend de deux paramètres, pas d'un. Il faut donc calculer deux pentes : une dans la direction $\theta_0$ (dérivée partielle $\partial J / \partial \theta_0$ ) et une dans la direction $\theta_1$ (dérivée partielle $\partial J / \partial \theta_1$ ). Les deux sont obtenues en appliquant la règle de la chaîne à la formule du MSE. Le $1/2$ placé tout à l'heure dans $J$ s'annule contre le $2$ qui sort de la dérivation du carré, et il reste :

\frac{\partial J}{\partial \theta_0} = \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)})

\frac{\partial J}{\partial \theta_1} = \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)}) \cdot x^{(i)}

La première est la moyenne des erreurs signées, la seconde est la même moyenne pondérée par le kilométrage. Le kilométrage qui apparaît dans la seconde formule n'est pas un hasard : c'est lui qui donne du levier à la pente $\theta_1$ , et c'est lui qui causera des soucis plus tard.

La mise à jour simultanée

À chaque itération, on soustrait un petit pas dans la direction opposée à la pente. Le petit pas vaut $\alpha$ fois la pente. Il y a une subtilité importante : il faut utiliser la même valeur de $\theta$ pour calculer les deux gradients, avant de les appliquer. On calcule donc les deux « tmp » d'abord, puis on met à jour :

\mathrm{tmp}\theta_0 = \alpha \cdot \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)})

\mathrm{tmp}\theta_1 = \alpha \cdot \frac{1}{m} \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)}) \cdot x^{(i)}

\theta_0 := \theta_0 - \mathrm{tmp}\theta_0

\theta_1 := \theta_1 - \mathrm{tmp}\theta_1

Si tu mettais à jour $\theta_0$ d'abord puis calculais $\mathrm{tmp}\theta_1$ avec le nouveau $\theta_0$ , tu serais déjà parti dans une direction avant d'avoir mesuré la pente au point de départ. Ce n'est plus une descente propre, et le sujet 42 l'interdit explicitement.

α = 0.1

θ₀

θ₁

MSE

41 761 038,5833

Clique "Une itération" pour démarrer.

Itérations : 0

Pars de (0, 0). Clique 'Une itération' : un pas de descente de gradient, la ligne rouge se déplace, le coût baisse.

+Comment lire ce widget ?

Chaque clic exécute exactement une itération. Les deux gradients sont calculés avec les $\theta$ courants, puis appliqués simultanément. La courbe grise en bas montre la MSE à chaque itération : elle doit descendre, d'abord vite, puis de plus en plus lentement à mesure qu'on approche du fond.

Et maintenant ?

Tu sais descendre. Reste à choisir la taille du pas : trop petite, tu n'arrives jamais au fond ; trop grosse, tu rebondis en dehors de la cuvette. Le chapitre suivant s'attaque au réglage de $\alpha$ , et à un piège spécifique au jeu de données : les kilométrages sont tellement grands qu'ils font diverger l'algorithme dès la première itération si on ne fait rien.