IFT3150 - Projet Informatique

Implémentation de la méthode du gradient moyen stochastique

Par Lauranne Deaudelin

Superviseur: Prof. Fabian Bastin

Énoncé du projet

Sous la supervision du Professeur Fabian Bastin du département d’informatique et recherche opérationnelle, le projet consiste à implémenter la méthode expliquée dans l’article Minimizing finite sums with the stochastic average gradient par Mark Schmid, Nicolas Le Roux et Francis Bach parue en mars 2017 dans le journal Mathematical Programming (Volume 162(1–2) pp 83-112). L’implémentation pourra ainsi permettre de vérifier la performance observée dans l’article, son utilisation sur divers problèmes d’optimisation, principalement des modèles de choix discrets et si possible, de mettre au défi cette méthode sur des hypothèses relâchées. La méthode sera programmée avec le langage Julia et fera suite à deux projets effectués antérieurement par deux étudiants, Jean Laprés-Chartrand et Alexandre Brillante.

Description détaillée

Pour décrire le projet de façon plus détaillée, il consiste à fournir une extension à la méthode du gradient stochastique à partir de l'article paru dans le Mathematical Programming. Cette méthode appelée le gradient moyen stochastique (de l'anglais stochastic average gradient) ressemble à la méthode du gradient stochastique, cependant il garde en mémoire la valeur du gradient précédent et il fait en quelque sorte la moyenne des gradients. La bonne convergence de cette méthode est atteinte sous des hypothèses générales de convexité, de différentiabilité où chaque gradient est Lipschitz-continue et de l'existence d'un optimum. Comme la partie du gradient stochastique a été déjà programmée par Alexandre Brillante et Jean Laprés-Chartrand en Julia, ce sera aussi en ce langage de programmation que l'extension du gradient moyen stochastique sera programmée. Julia est un langage de programmation dynamique de haut niveau et haute performance pour le calcul numérique. La suite du travail sera de valider l'implémentation de la méthode des données tests et réelles sur des modèles de choix discrets. Puis quand l'implémentation sera satisfaisante et validée, nous pourrons nous permettre de la comparer aux autres méthodes déjà en notre possession, notamment le gradient stochastique. L'idée est de faire la vérification des performances et résultats obtenus dans l'article. Si la progression du projet le permet, une vérification de la robustesse pourrait être fait. La démonstration de la convergence et les expérimentations de la méthode ne se fait que sur des hypothèses précises auxquelles il serait intéressant relâcher pour voir le comportement de celle-ci. Bien sûr, avant d'en venir à l'implémentation, la validation et la comparaison, un processus d'apprentissage devra se faire. Alors, il faudra approfondir les bases du gradient stochastique, certains concepts sur les applications, soit les modèles à choix discrets, et un rafraîchissement du langage de programmation Julia.

L'article:
Schmidt, M., Le Roux, N. & Bach, F. Math. Program. (2017) 162: 83. https://doi.org/10.1007/s10107-016-1030-6

Plan de développement

Voici seulement une ébauche du plan qui reste à confirmer et à "dater".
Date de début: 4 septembre

Plan pour le mois de septembre:

À planifier

Date de fin et présentation: À définir

Rapports d'avancement

À chaque semaine, il y aura une brève description de ce qui a été fait et des avancements.

Semaine 1

Lecture de l'article

Semaine 2

Lecture des deux premiers chapitre du livre Discrete Choice Methods with Simulation
Train, Kenneth, Discrete Choice Methods with Simulation, 2ième édition, Cambridge University Press, 2009

Semaine 3

Mise en place du site web et prendre connaissance du gradient stochastique

Semaine 4

Pour se familliariser avec le gradient stochastique et le code déjà en place, j'ai commencé à implémenter la version de base avec un pas fixe. Il y a eu quelque défis dans la compréhension du code, car le concept de batch implémenter ainsi que le modèle (Logit) ne sont pas induitifs. J'ai du demander de l'aide au concepteur du code.

Semaine 5

Continuer l'implémentation du gradient stochastique

Semaine 6

Terminer l'implémentation du gradient stochastique, mais on cherche le meilleur pas fixe. La façon de déterminer était par cadriage et en observant graphiquement les différences de la fonction objective selon les différents pas. On remarque la fonction objective agie d'une façon particulière. Cela est du par la convexivité des données et de la caractéristique lisse du modèle obtenue de celles-ci. Après discussion, on conclut que cette façon de faire n'est pas idéal qu'un critère d'arrêt par cross validation pourrait mieux pour la méthode et ainsi analyser les différentes performance du pas fixe.

Semaine 7

Recherche sur la cross-validation, mais je me suis principalement concentré sur ma préparation à l'intra et mes travaux dans mes autres cours

Semaine de lecture

Implémentation du critère d'arrêt par la cross-validation. J'ai commencé par observer graphique le comportement de deux modèles fait par différent sous-ensemble des données; soit un ensemble d'entraînement et un ensemble de validation. Après correction du code, on réalise que, par la façon que les données sont générées, il n'y a aucun différence ce qui fait un critères d'arrêt par le cross validation serait inefficase puisque nous rencontrions jamais de différence pour avoir un arrêt. Puis, si on revient à la source de ce qu'est le gradient stochastique, ce critère d'arrêt fait perdre sa propriété première soit sa vitesse calculatoire. On ralentit le code en place en le forcant à évaluer deux fonctions objectifs qui ont autant de termes à évaluer qu'il y a de données dans les ensembles d'entraînement et de la validation. Ainsi, il faudra faire des recherches sur les critères d'arrêt en apprentissage machine auquel la méthode du gradient stochastique est régulièrement utilisée

Semaine 8

Recherche dans la littérature et parmis le personnel enseignant pour avoir réponse au critère d'arrêt. Après avoir demander à un étudiant travaillant au Mila et au professeur Ioannis Mitliagkas, il propose trois approches pour le critère d'arrêt surtout vu en apprentissage machine: 1) Faire l'évaluation moins fréquemment. 2) Ne prendre qu'un sous ensemble de notre ensemble de validation. 3) Prendre encore un sous ensemble de notre ensemble de validation, mais de travailler en mini batch.

Par contre, la façon de faire la plus fréquente est de faire un early stop.

Résumé du rapport final