Introduction
Lors de la modélisation mathématique, pas nécessairement stochastique d’ailleurs, il n’est pas rare d’être confronté à un problème d’optimisation. On peut par exemple citer la minimisation des moindres carrés, la minimisation d’une forme quadratique sous contraintes linéaires comme pour l’allocation optimale d’actifs financier dans l’approche de Markowitz. Bref savoir minimiser, ou maximiser c’est égal, est très important.
Pour aurant, il n’est pas rare de rencontrer un problème d’optimisation qui n’admet pas de solution explicite. On aura alors recours à des techniques d’optimisation numérique dont la descente du gradient fait partie. Il y en a d’autre bien sûr mais nous nous restreindrons à cette dernière. Posons donc le cadre général de travail.
On considère le problème d’optimisation suivant
\[\begin{equation}
\underset{\theta \in \Theta}{\arg \min\ } f(\theta; \mathbf{x}), \qquad \Theta \subset \mathbb{R}^p,
\end{equation}\]
où ici \(\mathbf{x}\) est fixé et jouera bien souvent le rôle en statistique des données. Je vous laisse remarquer que l’estimateur du maximum de vraisemblance peut s’écrire sous cette forme. Notons également que puisque nous parlons de gradient cela suppose bien évidemment que \(f\) est différentiable. Pour simplifier les notations on utilisera le (léger) abus de notations
\[\begin{equation*}
\nabla f(\theta; \mathbf{x}) = \nabla_\theta f(\theta; \mathbf{x}) =
\left( \frac{\partial f(\theta; \mathbf{x})}{\partial \theta_1}, \ldots,
\frac{\partial f(\theta; \mathbf{x})}{\partial \theta_p}\right)^\top.
\end{equation*}\]
La descente du gradient
Sans plus attendre voici l’algorithme (itératif)
- On se donne une valeur initiale \(\theta_0 \in \Theta\) et l’on pose \(t \leftarrow 0\) ;
Tant que \(\|\nabla f(\theta_t; x)\| > \epsilon\) faire
- \(\theta_{t+1} \leftarrow \theta_t - \alpha \nabla f(\theta_t; x)\) ;
- \(t \leftarrow t + 1\) ;
Renvoyer \(\theta_{t+1}\).
Vous aurez remarqué que l’algorithme de descente du gradient est conditionné à trois “choix” de l’utilisateur :
- la précision attendue \(\epsilon > 0\) ;
- la valeur initiale \(\theta_0\) qui idéalement doit être bien choisie (mais bon on peut pas toujours hein ;-) ) ;
- le scalaire \(\alpha > 0\) qui est appelé le pas de l’itération dans la communauté optimisation et taux d’apprentissage (learning rate) en IA.
La version stochastique de l’algorithme précédent est utilisé lorsque le calcul du gradient \(\nabla f(\theta ; x)\) est très couteux comme cela peut être le cas lorsque les observations \(\mathbf{x} = (x_1, \ldots, x_n)^\top\) sont très nombreuses (le big data quoi !).
On supposera ici que l’on peut réécrire notre problème d’optimisation sous la forme
\[\begin{equation}
\underset{\theta \in \Theta}{\arg \min\ } \sum_{i=1}^n f(\theta; x_i), \qquad \Theta \subset \mathbb{R}^p.
\end{equation}\]
L’algorithme du gradient stochastique s’écrit alors
- On se donne une valeur initiale \(\theta_0 \in \Theta\) et l’on pose \(t \leftarrow 0\) ;
Tant qu’un minimum (approché) n’est pas atteint faire
Renvoyer \(\theta_{t+1}\).
Dans l’algorithme précédent, les ensembles \(I_1, \ldots, I_B\) forment une partition de \(\{1, \ldots, n\}\), et en plus des “choix utilisateur” liés à l’algorihtme du gradient on devra en plus choisir la taille \(B\) de la partition. En machine learning, lorsque l’algorithme a fait une itération de la boucle for on parle alors d’epoch (désolé pour le franglais mais visiblement en Machine Learning on aime bien !)
Application
- Ecrivez une fonction qui effectue l’algorithme de descente du gradient (classique)
- Testez votre fonction sur la fonction \(f(\theta; x) = 1 + \theta^2\) en prenant comme valeur initiale \(\theta_0 = 5\) et un taux d’apprentissage \(\alpha = 0.01\).
- Recommencez mais avec un taux d’apprentissage égal à \(\alpha = 1\). Commentez.
- Faites une représentation graphique de la fonction %%
\[\begin{equation}
%% f(\theta; x) = -\sin(0.5 \theta_1^2 - 0.25 \theta_2^2 + 3) \cos(2 \theta_1 + 1 - %%e^{\theta_2}), \qquad \theta \in [-2, 2]^2,
%%\end{equation}\begin{equation}
f(\theta; x) = (1.5 - \theta_1 + \theta_1 \theta_2)^2 +
(2.25 - \theta_1 + \theta_1 \theta_2^2)^2 +
(2.625 - \theta_1 + \theta_1 \theta_2^3)^2, \qquad \theta \in [-4.5, 4.5]^2,
\end{equation}\]
et testez votre fonction. Sur le graphique précédent vous superposerez la trajectoire issue de l’algorithme de descente du gradient. Vous ferez plusieurs tentatives avec des valeurs initiales différentes et commenterez.
- Implementez une version de la descente de gradient accélérée de Nesterov. Pour laquelle nous avons
\[\begin{align*}
\tilde{\theta}_{t+1} &\leftarrow \theta_t - \gamma v_t\\
v_{t+1} &\leftarrow \gamma v_t + \alpha \nabla f(\tilde{\theta}_{t+1}; \mathbf{x})\\
\theta_{t+1} &\leftarrow \theta_t - v_{t+1},
\end{align*}\]
où typiquement l’on choisit \(\gamma = 0.9\) et \(v_0 = 0\).
- On va maintentant s’intéresser au gradient stochastique. Implémentez une fonction faisant une descente du gradient stochastique. Vous autoriserez l’utilisateur à définir la taille du partitionnement \(B\).
- Rendez cette fonction encore plus puissante en implémentant le célèbre algorithme (du moins pour les réseaux de neurones) RMSprop donné par
\[\begin{align*}
\theta_{t+1} &\leftarrow \theta_t - \frac{\alpha}{\sqrt{g^2_t + \epsilon}} \nabla f(\theta_t; \mathbf{x}),\\
g^2_t &\leftarrow \gamma g^2_{t-1} + (1 - \gamma) \left(\nabla f(\theta_t; \mathbf{x}) \right)^2,
\end{align*}\]
où là encore on prendra typiquement \(\gamma = 0.9, \epsilon = 10^{-4}\) et \(g^2_0 = 0\).
- Application sur un jeu de données. Nous allons nous intéresser à la régression logistique pour laquelle le problème d’optimisation est le suivant
\[\begin{equation*}
\underset{\theta \in \Theta}{\arg \max\ } \sum_{i=1}^n y_i \log p(x_i; \theta) + (1 - y_i) \log (1 - p(x_i; \theta)),
\end{equation*}\]
où on a utilisé l’abus de notation \(\mathbf{x} = ((\mathbf{x}_1, y_1), \ldots, (\mathbf{x}_n, y_n))^\top\), \(\mathbf{x}_i \in \mathbb{R}^p\) et \(y_i \in \{0, 1\}\) et
\[\begin{equation*}
p(x; \theta) = \frac{1}{1 + \exp(x^\top \theta)}.
\end{equation*}\]
Nous allons donc utiliser la régression logistique sur deux applications :
- votre probabilité de valider votre année de Master 1 en utilisant l’historique des promotions précédentes (ici on aura donc \(\mathbf{x}_i = \text{notes au premier semestre de l'étudiant $i$}\) et \(y_i = 1_{\{\text{l'étudiant $i$ a validé son M1}\}}\))
- le jeu de données sonar disponible ici. Il s’agira ici de prédire si le sonar a rencontré un cylindre en pierre ou en métal.
Pour chaque jeu de données, vous utiliserez une descente du gradient classique, celle de Nesterov et la version stochastique.