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 : 3 au 7 septembre

Lecture de l'article

Semaine 2 : 10 au 14 septembre

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 : 17 au 21 septembre

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

Semaine 4 : 24 au 28 septembre

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 : 3 au 6 octobre

Continuer l'implémentation du gradient stochastique

Semaine 6 : 8 au 12 octobre

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 : 15 au 20 octobre

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: 28 octobre au 2 novembre

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.

Semaine 9 : 5 au 9 novembre

Après plus ample recherche, un article intéressant fut trouver: Automatic early stopping using cross validation: quantifying the criteria par Lutz Prechelt. On y expérimente trois critères d'arrêt pour faire dur early stopping. Ils ont été développé avec l'idée d'un certaine tolérance face à une augmentation de la fonction objective moyenne de l'ensemble de validation. La première proposée est de forcer l'arrêt quand la proportion de la fonction objective moyenne de l'ensemble de validation sur son meilleur résultat (soit son minimum) dépasse un certain seuil. La seconde est de calculer la proportion de descente de la fonction objective moyenne de l'ensemble de "training" et d'en plus de considérer la proportion d'augmentation pour en faire une proportion qui provoquera aussi l'arrêt si elle dépasse un seuil. Puis, le dernier critère est d'arrêt le processus lorsqu'il y a k évaluations du critères auquel la fonction objective moyenne de la validation augmentent; ce critère est celui utilisé en python. Après discussion, il a été décidé de coder les critères d'arrêts pour voir le comportement de ceux-y

Semaine 10: 12 au 16 novembre

Une suite de péripities personnelles (notamment du bris de mon ordinateur) a fait que le codage des critère a été retardé. Par contre, quelque recherche et discussion ont permis une meilleur compréhension des critères et du domaine

Semaine 11: 19 au 23 novembre

Les critères ont été fait et un remaniement du code aussi du gradient stochastique. On peut aussi voir que le gradient stochastique bien que rapide est contraint par la quantité de paramètre à définir pour son bon comportement que ça soit par la définition du la longueur du pas, le nombre d'itération entre les évalutions d'un critères d'arrêt ou la tolérance de celui-ci. Ainsi, on peut donc considérer tester plusieurs longueurs de pas et avec cette étape terminée, passer au code du gradient stochastique moyenne.

Semaine 12 : 26 au 30 novembre

Un test avec avec 6 longueurs de pas a été fait avec l'aide de mini-batch de longueur 1000 et avec 150 epochs. Il fut intéressant de remarquer le comportement des différents graphiques il a été convenu de réessayer avec plus d'epoch. Puis, l'implémentation du gradient moyen stochastique de base a été fait sans trop de mal et il a été possible de voir une certaine rapidité de convergence lors des premières itération. Les résultats étaient pour l'instant que sur une petite portion des données et ainsi, une exécution avec l'ensemble sera nécessaire. De plus, pour vraiment bien comparer les résultat avec le gradient stochastique, une implémentation de mini-batch a été convenu de faire et sans oublier d'ajouter les critères d'arrêt implémentés dans les dernières semaines.

Semaine 13 : 3 au 7 décembre

>

Résumé du rapport final

les objectifs principaux du projet étaient l’implémentation de la méthode dugradient moyen stochastique, la vérification de l’article, étudier son utilisation sur des modèles dechoix discrets et de mettre au défi cette méthode sur des hypothèses relâchées et n’ont pas tousété atteints. On explique cela par le temps considérable qu’a pris l’apprentissage des concepts, ducode précédent et un peu du langage de programmation Julia et la programmation de nouvellestâches apparues durant le travail comme d’implémenter le gradient stochastique et un critèred’arrêt. À la base, je connaissais seulement quelques méthodes d’optimisation linéaire et nonlinéaire déterministes et donc, il faut admettre les méthodes stochastiques sont un peu moinsintuitives principalement par leur convergence en espérance et que certains comportements quivaut leur bonne performance ne sont pas encore tout à fait bien expliqués. Pour revenir au côtéprogrammation, on conviendra que de partir avec le code d’une autre personne peut être arduet dans mon cas, il est arrivé quelques fois, lorsque j’allais demander de l’aide, que le concepteur16 du code doive faire quelques réarrangements menant à un léger retardement. De plus, il fautmentionner qu’il y a eu quelques embuches en cours de route, comme le temps énorme queprenait l’exécution des méthodes sur mon ordinateur et ainsi que le bris de celui-ci. Néanmoins,la méthode du gradient stochastique et trois critères d’arrêt ont été achevés et sont fonctionnels.On en viendra à la conclusion que la terminaison des méthodes stochastiques comme le GS etGMS pose vraiment problème et qu’il serait vraiment intéressant de pousser la recherche. Il seraitenvisageable de tenter de développer un critère ne se basant pas sur un ensemble de validationou de voir à utiliser les propriétés statistiques de ces méthodes dérivant un test d’hypothèsestatistique ou un intervalle de confiance. Quoi qu’il en soit, il n’y a que l’implémentation dugradient moyen stochastique de base avec des expérimentations sur des données synthétiquesqui a été fait dans les objectifs ; on dit « de base » puisqu’il reste encore quelques modificationsà faire pour améliorer son efficacité et qu’il soit équivalent à ce qui a été utilisé dans l’article,soit d’ajouter : la recherche linéaire, la capacité à s’adapter à la structure du gradient, unerégularisation efficace et réévaluation du poids des premières itérations. Puis, pour être certaind’avoir complété l’implémentation, il sera nécessaire de tester avec d’autres données puisqueles données synthétiques ne sont pas représentatives d’une situation réelle. Il restera ensuitede procéder aux comparaisons avec les autres méthodes vues dans l’article et la vérificationde celui-ci sera terminée et analysée sur des modèles à choix discret. Si ces tests confirmentles performances du gradient stochastique, il serait intéressant de mettre à contribution cetteméthode pour estimer un modèle et tenter de prédire des choix discrets dans un vrai contexte.Puis, on a testé jusqu’ici avec un modèle Logit, mais on dispose maintenant d’un modèle Mixed-Logit et il serait donc possible de tester avec ce nouveau modèle. Ainsi après toutes ses étapes,il sera possible de s’amuser à relâcher les hypothèses, par exemple de convexité, et l’on auraenfin une bonne connaissance des capacités de la méthode du gradient moyen stochastique. Puis,pour les résultats des expérimentations du rapport, il donne un bon avant-goût de commentse comportera le GMS lorsqu’il se finit d’implémenter. On remarque, comme mentionné dansl’article, que la divergence est facile si le choix de la longueur est inadéquat, mais, pour unemême valeur de fonction d’objectif, il converge définitivement plus rapidement. Conséquemment,il reste beaucoup de travail à faire, mais ses performances sont encourageantes et ce projet mérited’être poursuivi selon les pistes évoquées dans cette conclusion, surtout celles qui permettraientde trouver un meilleur critère d’arrêt stochastique.