Descente de gradient¶
Python works with packages. A large number of packages can be dowloaded all together in the Anaconda environment. Start downloading here (version >3) https://www.anaconda.com/download/ Anaconda comes with
- Spyder, a GUI for python
- Jupyter Notebook, how to create great documents
Enjoy!
Bee careful :
- Python is sensible to spaces in the beginning of lines,
- Python is sensible to number type : $3$ and $3.$ are totally different: integer and float types.
import warnings
warnings.filterwarnings('ignore')
Plaçons-nous dans le cadre suivant : on considère $h:\mathbb{R}⟶\mathbb{R}$ une fonction dérivable sur $\mathbb{R}$ (sa dérivée existe en tout point de $\mathbb{R}$), dont on veut déterminer le minimum. On suppose que ce minimum existe et qu’il est unique, c’est-à-dire qu’il n’existe qu’un $x_{min}\in\mathbb{R}$ tel que $x_{min}=arg\min_x(h(x))$. On suppose que $x_{min}$ est inconnu et impossible à déterminer de manière exacte et on va donc en chercher une valeur approchée. Introduisons maintenant une méthode très utilisée en analyse de données pour réaliser ce genre de recherche et appelée méthode de descente de gradient. Son principe général est le suivant :
- Partons d’un point $x_0∈\mathbb{R}$
- Calculons $x_1=x_0−s*h′(x_0)$
- Et ainsi de suite… $s$ est un paramètre réel positif et est appelé pas de descente. Après plusieurs étapes, on récupère une valeur approchée de $x_min$. Tout au long de cette partie, nous allons prendre comme exemple la fonction suivante : $$h:x⟼\frac{1}{4}x^4+(x−1)^2$$
1) Donner l’équation que doit vérifier $x_{min}$, le minimum de cette fonction (donner juste l’équation, sans essayer de la résoudre).
$$x_{min}^3+2(x_{min}-1)=0$$
2) Justifier le fait que le $x_{min}$ qui vérifie l’équation précédente est effectivement le minimum de la fonction $h$ (et non un maximum).
$h''(x)<0$ quelque soit $x$. Donc $h$ est bien minimum en $x_{min}$
3) Ecrire une fonction, appelée descente() qui, étant donné une fonction dérivée $f′$, une valeur initiale $x_0$ et un pas $s$, calcule une valeur approchée de $x_{min}$ (le point ou le minimum de la fonction $f$ est atteint) à $\epsilon$ près, initialisé à $10^{-5}$, pour un nombre maximum d'itérations $N_{iter}$, initialisé à $1000$. Cette fonction doit aussi dire si elle a convergé, ou pas.
import numpy as np
def descente(f_prime,x_0,s,eps=1e-5,N_it=1000):
x = x_0
err = eps+1
it = 1
while it<N_it and err>eps:
x_old = x
x = x_old - s*f_prime(x_old)
err = np.abs(x-x_old)
it = it+1
if it==N_it:
print("No convergence")
else:
print("Convergence")
return(x)
4) Tester votre fonction descente sur la fonction $h$ avec comme point de départ $x_0=0$, comme précision $\epsilon=10^{−5}$ et comme nombre maximum d'itérations $N_{iter}=1000$. Les valeurs suivantes pour le pas $s$ : $0.01,0.1,0.25,0.5$. Que remarquez-vous ?
def h(x):
return(x**4/4+(x-1)**2)
def h_prime(x):
return(x**3+2*(x-1))
steps = [0.01,0.1,0.25,0.5]
x_0 = 0
x_min_estimates = [0]*len(steps)
for s_id in list(range(len(steps))):
x_min_estimates[s_id]=descente(f_prime=h_prime,x_0=x_0,s=steps[s_id])
print(x_min_estimates)
5) Créer une fonction descente_2 qui print à chaque itération la valeur de l'erreur commise et tester cette fonction sur le même jeu de paramètres que précédemment en modifiant $N_{it}=5$ et $x_0=1$. Que remarquez-vous ?
import numpy as np
def descente_2(f_prime,x_0,s,eps=1e-5,N_it=10):
x = x_0
err = eps+1
it = 1
while it<N_it and err>eps:
x_old = x
x = x_old - s*f_prime(x_old)
err = np.abs(x-x_old)
print(err)
it = it+1
if it==N_it:
print("-----! No convergence !-----")
else:
print("Convergence")
return(x)
res = descente_2(f_prime=h_prime,x_0=x_0,s=1)
6) Modifier la fonction descente() en créant desctente_3() pour qu'elle renvoit le nombre d'itérations nécessaires à la convergence. Commenter.
import numpy as np
def descente_3(f_prime,x_0,s,eps=1e-5,N_it=1000):
x = x_0
err = eps+1
it = 1
while it<N_it and err>eps:
x_old = x
x = x_old - s*f_prime(x_old)
err = np.abs(x-x_old)
it = it+1
return(it)
steps = [0.01,0.1,0.25,0.5]
x_0 = 0
x_min_estimates = [0]*len(steps)
for s_id in list(range(len(steps))):
x_min_estimates[s_id]=descente_3(f_prime=h_prime,x_0=x_0,s=steps[s_id])
print(x_min_estimates)
7) Tracer le nombre d'itérations nécessaires pour trouver le minimum de $h$ en fonction du pas $s\in]0,0.55]$, on prendra 100 points équitablement répartis sur cet intervalle. Commenter et donner une valeur optimale, en terme du nombre d'itérations, pour le pas de descente.
steps = np.linspace(0,0.55,101)[1:101]
iterats = [0]*100
for s_id in list(range(len(steps))):
iterats[s_id]=descente_3(f_prime=h_prime,x_0=x_0,s=steps[s_id])
import matplotlib.pyplot as plt
fig = plt.figure()
plt.plot(steps,iterats, color='red', marker='*',linewidth=2, markersize=2)
fig.suptitle("Nombre d'itérations en fonction du pas de gradient", fontsize=20)
plt.xlabel('Pas du gradient', fontsize=18)
plt.ylabel("Nombre d'itérations", fontsize=16)
plt.show()
