Algorithme du gradient
Nous avons donc une fonction J que nous souhaitons minimiser. Les mathématiques vont nous venir en aide.
Le gradient
Regardons cette courbe et imaginons qu'elle représente une fonction J, elle convexe ou dit plus simplement, il y a un seul point (en rouge) qui est le minimum de notre fonction.
Imaginons que je pars du haut à gauche de ma courbe et que je laisse tomber une balle, elle va très vite tomber puis remonter un petit peu lentement sur la droite, puis remonter encore plus lentement vers la gauche etc., puis se stabiliser au 'fond'.
Et c'est assez similaire à ce que va faire notre algorithme !
La courbe plus haut n'a qu'une seule variable x, on peut l'écrire sous la forme f(x), or rappelons nous que nous utilisons plusieurs variables B dans notre fonction J : J(B0,B1,B2...). C'est un peu plus compliqué mais pas tellement, par exemple si nous n'avions que deux variables, on peut s'imaginer une fonction J(B0,B1) qui prendrait la forme d'un bol, on s'imagine alors de nouveau ce qui se passerait si on jettait une bille dans notre bol et comment elle va tomber au fond du bol qui serait le minimum de notre fonction.
Algorithme du gradient
Notre algorithme du gradient a le même comportement que la bille, il va chercher un minimum de notre fonction de coût en prenant un point au hasard et en 'descendant' petit à petit. Pour savoir 'par où' descendre nous allons utiliser le gradient.
Le gradient d'une fonction est la même chose que la dérivée d'une fonction, sauf que la dérivée travaille sur une seule variable et le gradient sur plusieurs. Par exemple, le gradient d'une fonction à deux variables f(x,y) est un vecteur de 2 fonctions : la dérivée partielle en x et la dérivée partielle en y. Un exemple :
f(x,y) = x2 + xy + y3
Dérivée partielle en x : 2x + y + 0
Dérivée partielle en y : 0 + x + 3y2
Les mathématiciens ont observé que si l'on est sur un point de notre fonction et que l'on va dans la direction opposée du gradient, on s'approche vite du minimum ! L'idée est donc de prendre un point au hasard et d'avancer dans la direction opposée du gradient.
Pour ne pas aller ni trop vite ni trop lentement on va utiliser un taux d'apprentissage ou learning rate et le multiplier au gradient. On répète cette étape jusqu'à s'approcher du minimum. Voilà la formule
Pour chaque B de J(B0,B1,B), mettre à jour :
B = B - α * dérivée_en_B_de_J
Prenons l'exemple de notre fonction à une seule variable (on va donc travailler simplement avec la dérivée)
f(x) = x2
f'(x) = 2x (dérivée en x de f)
Et prenons un point au hasard et un taux d'apprentissage
x=8
α = 0,15
f '(8) = 2*8 = 16
On modifie x := 8 - α * 16 = 8 - 2,4 = 5,6
f ' (5,6) = 2*5,6 = 11,2
x:= 5,6 - 0,15 * 11,2 = 5,6-1,68 = 3,92
Et ainsi de suite, l'algorithme s'arrêtant quand on ne fait plus vraiment de progrès.
Attention à ne pas choisir un taux d'apprentissage trop petit de risque de prendre trop de temps !
Ou de prendre un taux d'apprentissage trop grand, rater la sortie et devoir faire demi-tour !
Limites
Les exemples de fonctions que nous avons présentés sont des cas simples utilisés à des fins d'exemple, notre fonction de coût n'aura pas toujours cette forme idéale de bol !
Il se peut donc que l'algorithme mette beaucoup de temps à trouver le minimum ou pire qu'il ne trouve pas le bon !
Salaire et démographie
Présentation des données
Régression Linéaire
Gradient descent
Résultats et autres régressions