Descente de gradient

Motivation

Trouver les valeurs de paramètres minimisant un coût.

Analyse

L'algorithme de descente de gradient consiste, si l'on considère :

• une fonction hypothèse h=θ
• une fonction de coût J(θ)

à changer (simultanément) les θ_n en fonction de la pente (dérivée) induite par le coût :

Itérer jusqu'à convergence {
  θ_j:=θ_j−α∂/(∂θ_j) J(θ)
}

où α est le taux d'apprentissage (learning rate) à régler, déterminant la taille des "sauts" lors de la descente.

Si l'on dispose de capacités de calcul matriciel rapides, on peut effectuer l'opération équivalente de manière vectorisée.

Notes

• Sa complexité en O(kn^2) fait qu'elle est adaptée même si n est grand (contrairement à l'équation normale).
• Si votre α est trop grand (votre saut trop rapide), vous pouvez vous retrouver à remonter ("sauter" de l'autre côté du trou) et donc diverger au lieu de converger.
• Pour être sûr de converger (ou comprendre pourquoi on ne converge pas), il peut être utile de tracer J(θ) et s'assurer qu'elle tend bien vers 0.
• Si des caractéristiques sont trop différentes (ayant une échelle ou un type différent), il pourra être nécessaire de les adapter :
  • Rééchelonnage (feature scaling) sur 0..1 : x'=x/(max(x)-min(x))
  • Recentrage autour de la moyenne (mean normalization) : x'=(x-bar x)/(max(x)-min(x)) ou de l'écart type : x'=(x-bar x)/σ
• Afin d'éviter toutes erreurs de descente, on pourra aussi mettre en place une "vérification de gradient" (gradient checking) qui permettra de contrôler la valeur de la pente (dérivée) trouvée. En effet si l'on considère un ε petit (10^-4 par ex) : d/(dθ) J(θ) ~~ (J(θ+ε)-J(θ-ε))/(2ε). Bien sûr cette vérification ne devra être utilisée que lors d'une phase de mise au point, puis désactivée une fois le gradient vérifié.
• D'autres algorithmes (plus complexes) d'optimisation évitent ces problèmes : un bon α est déterminé automatiquement et la convergence arrive donc rapidement :
  • Gradient conjugué
  • BFGS
  • L-BFGS
• Une version plus performante (mais moins précise) est la descente de gradient stochastique, où l'on met à jour les paramètres en fonction d'un seul échantillon de données (x) à chaque fois, au lieu de tous.

Voir

• Ruder, Sebastian: "An overview of gradient descent optimization algorithms", 2016-01-16