Thèse de Manuel Loth

Algorithmes d'Ensembles Actifs pour le LASSO

Le LASSO est une méthode de régression ajoutant à la méthode des moindres-carrés une contrainte ou une pénalisation sur la norme l1 du coefficient linéaire. Cette contrainte a un effet de sélection de variable et de régularisation sur l'estimateur. Un estimateur LASSO est défini comme étant la solution d'un problème pouvant être vu comme un programme quadratique. Cette thèse se base sur deux algorithmes dédiés à la résolution du LASSO publiés en 2000 par M. Osbourne et alii. L'un, une méthode par homotopie, a été reformulé en 2004 par J. Friedman et alii sous le nom de LAR-LASSO (ou LARS), s'imposant alors comme la méthode standard. Le second, présenté comme une méthode d'ensemble actif, fût largement ignoré, semble-t-il pour deux raisons: une application apparemment limitée à la formulation "contrainte", et une compréhension plus difficile de l'algorithme. Nous reformulons donc le principe général du second, que nous baptisons "Descente sur Ensemble Actif" (DEA) et sa dérivation sur le LASSO, ainsi que la méthode par homotopie que nous mettons en évidence comme directement dérivée de la DEA. La formulation simplifiée des deux méthodes permet d'en améliorer la compréhension, mais aussi l'efficacité en temps de calcul. Elle met en outre en évidence l'applicabilité de la DEA sur la formulation "pénalisée" du LASSO, donnant un algorithme plus simple encore. Enfin, elle conduit à une analyse et un traitement de cas limites dans lesquels ces algorithmes peuvent échouer. Nous proposons ensuite une application directe du LASSO sur un nombre infini de variables formant un espace multidimensionel, et étudions l'adaptation des algorithmes d'ensemble actifs dans ce cadre.

Jury

Directeur de Thèse : Philippe Preux, Professeur, Université Lille 3 Rapporteurs : Stéphane Canu, Professeur, INSA Rouen Patrick Gallinari, Professeur, Université Paris 6 Membres : Antoine Cornuéjols, Professeur, AgroParisTech Paris Marc Sebban, Professeur, Université Saint-Etienne

Thèse de l'équipe soutenue le 08/07/2011