Minimisation d'une fonction par descente de gradient stochastique

Dans ce TP, on aborde un ingrédient essentiel pour le perceptron et plus généralement, dans tous les réseaux de neurones et même bien au-delà, la descente de gradient stochastique. C'est un algorithme qui détermine un minimum d'une fonction. Nous allons en manipuler une version très simple.
On suppose que l'on minimise une fonction d'une seule variable, soit f(x), x pouvant prendre sa valeur dans un certain intervalle [x_min, x_max]. On suppose que f est dérivable sur cet intervalle et on note f' sa dérivée.
Remarque : cette algorithme trouve un minimum local de f.

Principe de la descente de gradient stochastique

Supposons que l'on veuille trouver un minimum d'une fonction f à valeur réelle. Comme on l'a vu en cours, le principe de cette méthode est :

1. partir d'un point du domaine de définition de la fonction x₀ ;
2. regarder de quel côté (gauche ou droite) f décroît en x₀ ;
3. faire un petit déplacement dans cette direction en apportant une correction à x₀ ce qui fournit x₁. Cette correction est : - η f' (x₀). On peut prendre η=0,01 ;
4. continuer ainsi à corriger x_t pour obtenir x_t+1. Cette correction est : - η f' (x_t) ;
5. s'arrêter quand f'(x_t) est (presque) nul. En pratique, on s'arrêtera quand |f'(x)| sera inférieur à 0,1.

Programmation de la descente de gradient stochastique

Écrire un script python qui réalise une descente de gradient stochastique. On s'exercera sur la fonction f(x) = 0,3x² - 2x + 4 avec x ∈ [-10, 10].
On définira une fonction (python) f (x) qui renvoie la valeur de la fonction (mathématique) f en x :

def f (x):
    return (0.3 * x * x - 2 * x + 4)

De même, vous définirez une fonction (python) df (x) qui renvoie la valeur de la dérivée de f en x. (Je vous laisse calculer la dérivée de f.)

Ensuite, vous réalisez la descente de gradient stochastique. Vous prendrez η=0,01 (par exemple).
Par exemple, vous pouvez arrêter les itérations quand la dérivée est inférieure à 0,1.
En partant de x₀ = -5, vous devriez obtenir exactement la même séquence d'itérés que moi et donc réaliser 651 itérations et atteindre x=3,17 (arrondi au centième).

Test de votre programme

Une fois que votre programme fonctionne, vous l'utiliserez pour trouver un minimum pour la fonction f (x) = 0,2 x⁵ - 1,1 x³ + 0,7 x² - x + 1,2.

Comme on l'a dit, l'algorithme de descente de gradient stochastique trouve un minimum local. Recherchez un minimum local pour différentes valeurs de x₀ ∈ [-2, 3] (par exemple, vous prenez x₀ = -2, puis -1, puis 0, puis 1, puis 2, puis 3) ; pour chaque valeur de x₀, affichez le minimum trouvé. Que constatez-vous ?

Pour votre information, j'affiche le graphe de cette fonction :

Ce graphe est-il cohérent avec les minima que vous avez trouvés ?

Utilisation de votre programme

De la même manière, vous chercherez les minima de la fonction : g(x) = x⁷/20 + x⁶/5 - 0,4375 x⁵ - 2,0125 x⁴ - 0,4375 x³ + 2,7125 x² + 0,825 x - 0,9 pour x ∈ [-3, 3[. Votre programme doit afficher les abscisses des minima.

Pour finir

Le source de votre programme doit respecter les points suivants :

• il doit commencer par un commentaire indiquant son titre, son objet, ses auteurs, la date de réalisation.
• Chaque fonction doit commencer par un commentaire indiquant au minimum ce que fait la fonction, le sens des paramètres, les pré-conditions et ce que la fonction retourne.
• Le type des paramètres des fonctions doit être indiqué, ainsi que le type de la valeur retournée.

Pour finir, vous m'envoyez votre/vos script(s) par email, en mettant votre binôme en cc.