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. / The LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares methodThe LASSO is a regression method that adds a constraint or penalization of the l1 norm of the coefficient to the least-squares method. This constraint has variable-selection and a regularization effects over the estimator. The LASSO estimator is defined as a solution to a minimization problem that can be seen as a quadratic program. This thesis is based on two algorithms designed for solving the LASSO, that were published in 2000 by Osbourne et alii. One, an homotopy method, was re-formulated and popularized in 2004 by J. Friedman et alii under the name of LAR-LASSO (or LARS). The second, presented as an active set method, was largely ignored, for two main reasons: its apparent limitation to the constrained formulation, and a more difficult understanding of the algorithm. We re-formulate its general principle, under the name of "Active Set Descent", and its derivation for the LASSO problem, as well as the homotopy method, that appears as a direct extension of ASD. The simplified formulation of both methods yields a better understanding, and also a lower complexity, in terms of computation time. It also shows the direct appliability of ASD to the penalized formulation of the LASSO, in a even simpler algorithm than for the constrained one. Finally, it facilitates the analysis and workarounds of degenerate situations in which the algorithms may fail. We then propose a direct application of the LASSO on an infinite number of variables forming a multidimensional space, and study the adaptation of active set algorithms on this framework.

Cette thèse aborde le calcul de l'opérateur LASSO (Least Absolute Shrinkage and Selection Operator), ainsi que des problématiques qui lui sont associées, dans le domaine de la régression. Cet opérateur a suscité une attention croissante depuis son introduction par Robert Tibshirani en 1996, par sa capacité à produire ou identi fier des modèles linéaires parcimonieux à partir d'observations bruitées, la parcimonie signi fiant que seules quelques unes parmi de nombreuses variables explicatives apparaissent dans le modèle proposé. Cette sélection est produite par l'ajout à la méthode des moindres-carrés d'une contrainte ou pénalisation sur la somme des valeurs absolues des coe fficients linéaires, également appelée norme l1 du vecteur de coeffi cients. Après un rappel des motivations, principes et problématiques de la régression, des estimateurs linéaires, de la méthode des moindres-carrés, de la sélection de modèle et de la régularisation, les deux formulations équivalentes du LASSO contrainte ou régularisée sont présentées; elles dé finissent toutes deux un problème de calcul non trivial pour associer un estimateur à un ensemble d'observations et un paramètre de sélection. Un bref historique des algorithmes résolvant ce problème est dressé, et les deux approches permettant de gérer la non-di fferentiabilité de la norme l1 sont présentées, ainsi que l'équivalence de ces problèmes avec un programme quadratique. La seconde partie se concentre sur l'aspect pratique des algorithmes de résolution du LASSO. L'un d'eux, proposé par Michael Osborne en 2000, est reformulé. Cette reformulation consiste à donner une défi nition et explication générales de la méthode d'ensemble actif, qui généralise l'algorithme du simplex à la programmation convexe, puis à la spéci fier progressivement pour la programmation LASSO, et à adresser les questions d'optimisation des calculs algébriques. Bien que décrivant essentiellement le même algorithme que celui de Michael Osborne, la présentation qui en est faite ici a l'ambition d'en exposer clairement les mécanismes, et utilise des variables di fférentes. Outre le fait d'aider à mieux comprendre cet algorithme visiblement sous-estimé, l'angle par lequel il est présenté éclaire le fait nouveau que la même méthode s'applique naturellement à la formulation régularisée du LASSO, et non uniquement à la formulation contrainte. La populaire méthode par homotopie (ou LAR-LASSO, ou LARS) est ensuite présentée comme une dérivation de la méthode d'ensemble actif, amenant une formulation alternative et quelque peu simpli fiée de cet algorithme qui fournit les solutions du LASSO pour chaque valeur de son paramètre. Il est montré que, contrairement aux résultats d'une étude récente de Jerome H. Friedman, des implémentations de ces algorithmes suivant ces reformulations sont plus effi caces en terme de temps de calcul qu'une méthode de descente par coordonnées. La troisième partie étudie dans quelles mesures ces trois algorithmes (ensemble actif, homotopie, et descente par coordonnées) peuvent gérer certains cas particuliers, et peuvent être appliqués à des extensions du LASSO ou d'autres problèmes similaires. Les cas particuliers incluent les dégénérescences, comme la présence de variables lineairement dépendantes, ou la sélection/désélection simultanée de variables. Cette dernière problématique, qui était délaissée dans les travaux précédents, est ici expliquée plus largement et une solution simple et efficace y est apportée. Une autre cas particulier est la sélection LASSO à partir d'un nombre très large, voire infi ni de variables, cas pour lequel la méthode d'ensemble actif présente un avantage majeur. Une des extensions du LASSO est sa transposition dans un cadre d'apprentissage en ligne, où il est désirable ou nécessaire de résoudre le problème sur un ensemble d'observations qui évolue dans le temps. A nouveau, la flexibilité limitée de la méthode par homotopie la disquali fie au pro fit des deux autres. Une autre extension est l'utilisation de la pénalisation l1 sur d'autres fonction coûts que la norme l2 du résidu, ou en association avec d'autres pénalisations, et il est rappelé ou établi dans quelles mesures et de quelle façon chaque algorithme peut être transposé à ces problèmes.